Optimization: Theory, Algorithms and Applications

The linear programming problem: Is there a polynomial time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax ≥ b? (Problem 9 of 18 in Mathematical Problems for the Next Century by S. Smale)

Our implementation outperforms the industry-standard optimizer (CPLEX), shows very good parallel efficiency on massively parallel architecture and solves (optimization) problems of unprecedented sizes reaching 109 variables. (excerpt from Parallel Processing and Applied Mathematics 2005)

This O.R.(optimization)-based system was used by Procter & Gamble over a two-year period to manage purchases of $2.13 billion worth of goods yielding savings of $305 million, or 14%. (excerpt from Operations Research: The Science of Better website)

OVERVIEW

Optimization is an interdisciplinary area of mathematics and computer science that, simply speaking, amounts to choosing the best element from some set of available alternatives and studying its properties. Optimization has become ubiquitous to numerous theoretical and applied research directions of modern mathematics. Here, we understand optimization in its broad sense as a discipline that spans many areas including nonsmooth and convex analysis, numerical analysis, computational complexity theory, and the theory of algorithms; for example, especially in infinite-dimensional settings, just being able to guarantee the existence of a solution may require sophisticated tools of convex and variational analysis.

Modern optimization has its origins in linear programming, developed in the 1930s and 1940s by Leonid Kantorovich, John von Neumann and George Dantzig, which deals with the problem of minimizing a linear functional over a convex polyhedron in finite-dimensional vector spaces.

The current dramatic growth of the discipline of optimization is largely motivated by the successful solution of large-scale problems as well as the subsequent generation of even larger problems. The discovery and application of modern interior-point methods in the 1980s forever changed the landscape of convex and numerical optimization, pushing both our theoretical understanding and our computational capabilities well beyond the purely linear case.

Besides being truly interdisciplinary in nature, optimization has another distinct feature: it leads naturally to computational mathematics and computationally assisted discovery. For example, the dramatic progress in semidefinite programming — i.e., optimization over the cone of positive semidefinite matrices — within the past two decades in part contributed to the birth to a new research direction of convex real-algebraic geometry, which aims to develop the mathematical foundations and associated computational methods for the study of convex sets in real algebraic geometry.

In addition to our theoretical understanding of the subject, the ability to actually compute, or at least approximate, a solution to an optimization problem and judge its stability and sensitivity to the parameters is of equal importance. This naturally gives rise to the study of optimization algorithms. Many modern optimization algorithms with impressive practical performance are designed and understood through solid theoretical foundations such as convex and numerical analysis, duality theory, computational complexity theory. Further progress in optimization theory will inevitably lead to both theoretical and practical improvements in state-of-the-art optimization algorithms and the development of new ones.

However, even despite the recent theoretical breakthroughs and the dramatic increase in our computational capacities, there is an urgent need to push the boundaries of our knowledge even further. This urgency is driven not by just our own curiosity but also by many challenging real-world applications. Humankind draws great benefit from modern optimization and its applications to classical and biomedical engineering, optimal robust “green” energy dispatch, scheduling, economics and finance, to name but a few.

TIMELINESS AND IMPORTANCE

Historically, Canada has been a world leader in optimization especially since the genesis of the University of Waterloo in the east, with its famous Department of Combinatorics and Optimization. The Pacific Northwest has been a stronghold in optimization due to the outstanding group of mathematicians contributing to the field at the University of Washington (Klee, Grunbaum, Phelps and Rockafellar). The one-day West Coast Optimization Meetings (WCOM) have been offered continuously every year since 1985 at the University of Washington, with some infrequent additional meetings at SFU or UBC. The past decade has seen a substantial turnover in the local optimization community, with notable new faculty including Bauschke, Friedlander, W. Hare, Lu, Lucet, Stephen, Wang, and Zinchenko. In particular, the two new campuses in B.C. feature optimization prominently: SFU–Surrey has established a Centre for Operations Research and Decision Sciences (CORDS), while UBC–Okanagan has obtained CFI funding to build the Optimization, Convex Analysis and Nonsmooth Analysis (OCANA) CoLab (which became operational in Fall 2011). The arrival of this new cohort of researchers and establishment of these facilities provides an ideal opportunity to establish strong new collaborations and to extend the activities of researchers in this area substantially beyond the one-day WCOM meetings.

The goal of this CRG is to facilitate the creation of new mathematics that ultimately supports better decision making by creating a truly collaborative and permanent network of optimizers in the Pacific Northwest. The collaborative network will allow the optimization community to organize and integrate itself, to enhance existing largely informal collaborations, to better identify new promising research projects and teams, to provide graduate students and postdoctoral fellows with rich and productive work environment and research experiences.

PARTICIPANTS

Principal Investigators
Yuriy Zinchenko (Mathematics, University of Calgary)
Michael Friedlander (Computer Science, UBC)
Heinz Bauschke (Mathematics, UBC–Okanagan)

PIMS Faculty
Martial Agueh (U Victoria)
Jim Burke (Mathematics, U Washington)
Jane Ye (Mathematics, U Victoria)
Tamon Stephen (Mathematics, SFU)
Laleh Behjat (ECE, U Calgary)
Cedric Chauve (SFU)
Yong Gao (UBC–Okanagan)
Donovan Hare (UBC–Okanagan)
Warren Hare (UBC–Okanagan)
Philip Loewen (UBC)
Jason Loeppky (UBC–Okanagan) Zhaosong Lu (SFU),
Yves Lucet (UBC–Okanagan)
Ross Mitchell (Radiology, U Calgary)
Adam Oberman (Mathematics, SFU)
Rene Poliquin (U Alberta)
Terry Rockafellar (U Washington)
William Rosehart (ECE, U Calgary)
Rekha Thomas (U Washington)
Xianfu Wang (UBC–Okanagan)
Julie Zhou (U Victoria)

Other Faculty
David Bremner (U New Brunswick)
Tim Craig (Princess Margaret Hospital)
Antoine Deza (McMaster University)
Robert Mifflin (Washington State University)
Michael Sharpe (Princess Margaret Hospital)

Scientific Committee
Rob Freund (MIT)
Adrian Lewis (Cornell)
Tamas Terlaky (Lehigh)
Henry Wolkowicz (Waterloo)
Yinyu Ye (Stanford)
Jesus De Loera (UC Davis).

PLANNED SCIENTIFIC ACTIVITIES

2012:

• Spring 2012: The West Coast Optimization Meeting at the University of Washington (Organizer: J. Burke).
• Spring 2012: Workshop on Robust Optimization, at BIRS (Organizers: Z. Lu, Y. Zinchenko).
• Summer 2012: Optimization Workshop, UBC-O (Organizers: H.  Bauschke, W. Hare, Y. Lucet, and S. Wang).
• Fall 2012: The West Coast Optimization Meeting, at UBC (Organizer: M. Friedlander).

2013:

• Spring 2013: The West Coast Optimization Meeting at the University of Washington (Organizer: J. Burke).
• June 2013: Follow-up 2-day workshop on the 2011 BIRS workshop on High-Performance Numerical Methods Supporting Radiation Therapy Treatment Planning, at Lehigh University (Organizers: Y. Zinchenko, T. Terlaky).
• June 2012: Women Optimize in the West (WOW), UC (Organizer: Laleh Behjat).
• June 2012: Optimization Summer School at UCalgary
• Summer 2013: A 5-day conference on Geometric Aspects of Optimization, at the University of Calgary (Organizers: D. Bermner, A. Deza, J. De Loera, R. Thomas and Y. Zinchenko).
• August 2013: Workshop on Numerical Linear Algebra and Optimization (Organizers: I. Dumitriu , C. Greif  and E. Mengi). The main summer event for this CRG, this workshop will recognize Michael Overton and his seminal work in optimization and numerical linear algebra on the occasion of his 60th birthday. The selected topics are representative of his research interests.
• Focus Period 2013: A 2-3-week-long Summer School on Optimization, at the University of Calgary (Organizers: Y. Zinchenko, H. Bauschke, and X. Wang).
• Focus Period 2013 Women Optimize in the West (WOW) mentor-mentee international workshop (coordinated by J. Ye and S. Moffat).
• Fall 2013: The West Coast Optimization Meeting(Organizers: Jane Ye, Martial Argueh, Julie Zhou).

2014:

• Spring 2014: The West Coast Optimization Meeting, at the University of Washington (Organizer: J. Burke).
• Fall 2014: The West Coast Optimization Meeting, at SFU–Surrey (Organizers: Z. Lu and T. Stephen).

2015

• Summer 2015: Curvature of the Central Path in Linear Programming, at the University of Calgary (Organizer: A. Deza & Y Zinchenko)

Ongoing events:

• A shared Optimization Seminar Series, with remote access and participation capabilities (Organizer: H. Bauschke).
• At least one team-taught graduate course per academic year. The initial format we envision is 5 − 6 instructors who teach independent modules (Organizers: H. Bauschke, T. Stephen and Y. Zinchenko).

Distinguished Visitors:

We intend to bring in 4 distinguished visitors in Year 1 and Year 2 of the CRG, for short-term visits, to give 2 − 3 lectures at a PIMS site. Details will be available soon.

Postdoctoral Fellows
We intend to supervise 3 postdoctoral fellows, each for 2 years. Due to interdisciplinary and collaborative aspects of our research proposal, it is expected that each postdoctoral fellow will spend his/her time at at least 2 different PIMS sites.