# Institute for Mathematical Sciences Programs & Activities

**Optimization: Computation, Theory and Modeling**

(1 November - 23 December 2012)

**Optimization: Computation, Theory and Modeling**

(1 November - 23 December 2012)

Organizing Committee · Visitors and Participants · Overview · Activities · Venue · Funding for Participants

*Co-Chairs*

- Defeng Sun (National University of Singapore)
- Kim-Chuan Toh (National University of Singapore)

**Members**

- Michael C. Ferris (University of Wisconsin-Madison)
- Jong-Shi Pang (University of Illinois at Urbana-Champaign)
- Alexander Shapiro (Georgia Institute of Technology)
- Melvyn Sim (National University of Singapore)
- Michael Todd (Cornell University)
- Daniel Ralph (University of Cambridge)
- Franz Rendl (University of Klagenfurt)
- Yinyu Ye (Stanford University)

The field of optimization has found numerous applications in science, engineering, economics, finance, and risk management. The optimization research has achieved much progress recently in theory, algorithms and applications. Yet, exciting new developments continue to emerge at a speed that has never been seen in the history of optimization.

Given two real vectors c and b and a real matrix A, the linear programming (LP) takes the form of minimizing <c,x> subject to Ax =b and x â‰¥ 0, where <.,.> denotes the usual dot inner product. The simplex method introduced by George B. Dantzig in 1947 announced the birth of LP. Since then, many optimization models have been formulated and investigated. Among them, semi-definite programming (SDP) of optimizing a linear objective over the intersection of a convex polyhedral set and the cone of symmetric and positive semi-definite matrices, is arguably the most extensively studied class due to its mathematical elegance, rich applications, and wide links to other subjects. The early success of SDP, and in general symmetric cone programming (SCP), can be partially credited to the discovery of modern polynomial time interior point methods. To date, most generic solvers for medium scale SDPs are based on interior-point methods, and they are routinely used to solve practical problems arising from areas such as signal processing and control theory.

Recent research on SDP and SCP has focused on algorithmic development for solving large scale problems. There is a great demand for solvers for large scales SDP and SCD as such problems arise frequently in diverse areas ranging from combinatorial optimization, finance and risk management, data mining, applied statistics, and sensor network. Recent algorithmic progress (based on the fundamental ideas of the classical proximal point methods including the augmented Lagrangian method and other first order methods) has provided convincing evidences that it is time to tackle large scale problems. This program will provide a platform for exchanging ideas in solving large scale conic optimization problems including SDP and SCP.

Given a closed convex K (not polyhedral in general) in a finite dimensional Euclidean space, the conic programming (CP) takes the following form: min{<c,x> | Ax =b with x in K}. For example, one may take K to be the epigraph of the operator norm of a matrix X, i.e., the largest singular value of X. Different from the SDP cone, the above defined cone is no longer symmetric. Of course, one may use other norm functions such as the L-1, L-âˆž, the nuclear norm (the sum of all singular values) or even Ky Fanâ€™s k-norm to define corresponding non-symmetric cones, which all have all found important applications in practice.

In many situations, one also has to deal with nonlinear conic optimization. For example, in many statistical models such as in the maximum likelihood sparse estimation of Gaussian graphical model, one often faces the task of maximizing an objective function with the log-determinant of a positive semi-definite matrix with some of its coefficients being set to zeros. This is a nonlinear SDP problem as the objective function is nonlinear and possibly non-smooth if a kind of sparse structure is also sought. Another example that arises from the finance and insurance industry is to look for a correlation matrix to minimize ||X-G|| for a given possibly ill-defined correlation matrix due to insufficient observations, stress testing and many other reasons. This is a least squares conic optimization problem. It will be no surprising at all to see the need for solving nonlinear conic problems from different fields.

The algorithmic design will not be and cannot be successful without our deep understanding on the theoretical aspect of the conic optimization problems. For example, the design, implementation, and convergence analysis of the aforementioned augmented Lagrangian method for solving SDP strongly relied on the progress achieved during the last several decades in variational analysis, often under the framework of complementarity problems. The research on complementarity and its extensions not only provides much needed theoretical foundation for tackling large scale conic optimization problems, but also sheds lights on solving a broad class of problems in game-theoretic models, dynamic traffic equilibrium, non-smooth dynamical systems. This program will witness reports on the latest exciting developments in complementarity and beyond.

Another closely related theme in this program is optimization under uncertainty. Almost all real world optimization problems are subject to uncertain data or parameters. This is particularly the case for problems involving future decision. In many situations one has to make a decision while facing uncertainty of future realizations of involved parameters. There are several ways how uncertainty can be modeled. The classical approach is to specify a probability distribution of uncertain parameters and to optimize a relevant objective function on average. This is basically the approach of stochastic programming. Another approach, which recently gained a lot of popularity, is to specify a set of uncertainty of involved parameters and to optimize the worst case. Both approaches have long history and can be applied in different situations. Inevitably, one has to overcome many theoretical difficulties so as to deal with large scale problems involved in these models. In recent years a considerable progress was made in these areas of research due to better understanding modeling issues and development of more powerful algorithms especially those based on randomization techniques. Additionally, exciting applications of optimization models involving uncertainty from engineering, data mining, financial economics, supply chain management, and etc. are highly anticipated.

**Workshop 1 - Large Scale Conic Optimization:**19 - 23 Nov 2012

**Organizers:**Franz Rendl (University of Klagenfurt), Defeng Sun (National University of Singapore), Michael Todd (Cornell University), Kim Chuan Toh (National University of Singapore) and Yinyu Ye (Stanford University)

Tutorials on Conic Optimization 19 Nov 2012

The tutorials will be conducted by Jean Lasserre and the invited speakers are as follows:

- Erling Andersen (MOSEK ApS)
- Christine Bachoc (UniversitÃ© Bordeaux 1)
- Venkat Chandrasekaran (California Institute of Technology)
- Chek-Beng Chua (Nanyang Technological University)
- Christoph Helmberg (Chemnitz University of Technology)
- Florian Jarre (Heinrich Heine UniversitÃ¤t DÃ¼sseldorf)
- Etienne de Klerk (Nanyang Technological University)
- Jean Lasserre (LAAS-CNRS)
- Monique Laurent (Centrum Wiskunde & Informatica)
- Lek-Heng Lim (University of Chicago)
- Shinji Mizuno (Tokyo Institute of Technology)
- Jiawang Nie (University of California at San Diego)
- Dima Pasechnik (Nanyang Technological University)
- Houduo Qi (University of Southampton, UK)
- Franz Rendl (University of Klagenfurt)
- Anthony Man-Cho So (The Chinese University of Hong Kong)
- Kim-Chuan Toh (National University of Singapore)
- Steve Vavasis (University of Waterloo)
- Hayato Waki (Kyushu University)
- Yinyu Ye (Stanford University)
- Akiko Yoshise (University of Tsukuba, Japan)
- Xiaoming Yuan (Hong Kong Baptist University)
- Shuzhong Zhang (University of Minnesota)

**Workshop 2 - Optimization Under Uncertainty:**10 - 14 Dec 2012

**Organizers:**Alexander Shapiro (Georgia Institute of Technology) and Melvyn Sim (National University of Singapore)

This workshop will include**tutorials**(10-11 Dec 2012) and a**symposium**(12-14 Dec 2012) of the following themes:

- Stochastic Optimization
- Robust Optimization
- Machine learning

The tutorials will be conducted by Arkadii Nemirovski and Werner RÃ¶misch and the invited symposium keynote speakers are as follows:

- Dimitris Bertsimas (Massachusetts Institute of Technology)
- Andrew B. Philpott (The University of Auckland)
- R. Tyrrell Rockafellar (University of Washington)
- Werner RÃ¶misch (Humboldt-UniversitÃ¤t zu Berlin)
- Andrzej Ruszczynski (Rutgers, The State University of New Jersey)
- Stephen Wright (University of Wisconsin-Madison)

- Shabbir Ahmad (Georgia Institute of Technology)
- Darinka Dentcheva (Stevens Institute of Technology)
- Dan Iancu (Stanford University)
- Daniel Kuhn (Imperial College London)
- Karthik Natarajan (Singapore University of Technology and Design)
- Georgia Perakis (Massachusetts Institute of Technology)
- Melvyn Sim (National University of Singapore)
- Anthony Man-Cho So (The Chinese University of Hong Kong)
- Chung Piaw Teo (National University of Singapore)
- Wiesemann Wolfram (Imperial College London)
- Huan Xu (National University of Singapore)
- Huifu Xu (University of Southampton)
- Shushang Zhu (Sun Yat-sen University)

**Workshop 3 - Complementarity And Its Extensions :**17 - 21 Dec 2012

**Organizers:**Michael Ferris (University of Wisconsin-Madison), Jong-Shi Pang (University of Illinois at Urbana-Champaign), Daniel Ralph (University of Cambridge), Defeng Sun (National University of Singapore) and Kim-Chuan Toh (National University of Singapore)

This workshop will include**tutorials**(17 Dec 2012) and**invited talks**(18 - 21 Dec 2012). This workshop is a continuation of the four previous International Conferences on Complementarity Problems held at the Johns Hopkins University (1995), University of Wisconsin at Madison (1999), Cambridge University (2002), and Stanford University (2005). So this workshop can also be referred as**ICCP2012**: International Conferences on Complementarity Problems (2012). Topics of the workshop will range from core and emergent areas of complementarity and variational problems to diverse application areas such as those in electricity and energy markets, signal processing for communication, contact problems in mechanics, and game theory and learning, to name a few. The workshop will organize an afternoon excursion on Thursday 20 Dec 2012 followed by a dinner banquet in the evening (both events are self-paid), and conclude with a last day of lectures on Friday. Each speaker will deliver a 30-minutes invited lecture in one of the following themes:

- Electricity/markets
- Signal processing for communication
- Contact mechanics/friction
- Differential variational inequality
- Optimal control
- Quasi-variational inequality
- Econ/mechanism design/game
- Cone complementarity
- Computation/software
- Imaging/functional space
- Stochastic equilibria
- MPEC/hierarchical
- Distributed algorithms/applications
- New directions and applications

Students and researchers who are interested in attending these activities are requested to complete the online registration form.

The following do not need to register:

- Those invited to participate.
- Those applying for financial support.

**Sponsor to ICCP2012 (Workshop III): SIAM **

SIAM provides partial financial support to participants from US institutions to this workshop. Since this is NSF money so SIAM will need receipts and they must use coach fairs and adhere to the Fly America Act http://www.siam.org/meetings/guidelines/flyamerica.php

- Funding for 2 speakers from US institutions. This is reimbursement of expenses up to US$2500 each.
- Funding for 2 students from US institutions. This is reimbursement of up to US$600 each, and can include reimbursement of some registration fees.
- Funding for 2 early-career/post-doc attendees from US institutions. This is an attendee within 5 years of his/her PhD at the time of the meeting. This is reimbursement of up to US$700 each, and can include reimbursement of some registration fees.

Application for financial support is closed.

Â

For general enquiries, please email us at ims(AT)nus.edu.sg.

For enquiries on scientific aspects of the program, please email Defeng Sun at matsundf(AT)nus.edu.sg.

Â

Organizing Committee · Visitors and Participants · Overview · Activities · Venue · Funding for Participants