Efficient Algorithms for Large Scale Convex Programming

点击翻译按钮获取中文摘要

The goal of this project is to analyze and develop algorithms for large scale convex programming problems. The principal investigator will extend the scope of interior point methods by developing invariant, primal and dual interior point methods over homogeneous cones, which form a large class of problems including linear programming, semidefinite programming, and second order cone programming. Homogeneous cones have rich symmetry properties and a classification theory, which make them an ideal candidate for extending the theory of structured interior point methods beyond semidefinite programming. The investigation of the modeling power of homogeneous cone programming will be an important part of the project, and several related topics in semidefinite programming and hyperbolic cone programming will also be investigated. A second, but related component of this project will be the development of provably efficient first order methods for large scale convex programming. These methods have low memory requirements and global convergence rates which are (nearly) independent of the dimension of the underlying optimization problem. Hence, they are attractive for solving very large scale problems for which interior point methods may be ineffective because of their extensive memory requirements. The principal investigator and his graduate students will seek answers to these and related problems in convex programming. The resulting algorithms will be numerically tested in order to confirm their effectiveness.Numerous problems from industry, engineering, and science (designs of VLSI, antenna arrays, truss structures, and control systems in engineering, portfolio analysis in finance, structure of molecules in quantum chemistry, combinatorial optimization, and many others) depend on efficient optimization algorithms for their resolution. Semidefinite programming (SDP) has proved to be an excellent framework in which to model most of these large scale problems, and interior point methods for SDP have been very successful in solving them numerically. Very large scale problems arising from medical imaging and quantum chemistry provide good incentives for developing first order methods for convex programming. The theoretical insights gained from this research will lead to a deeper understanding of interior point methods for semidefinite programming and beyond. These insights will enable the principal investigator, his students, and other researchers to develop faster, more reliable algorithms which will make it possible to model and solve larger problems. These advances will directly benefit researchers in diverse scientific fields, who rely on modern optimization techniques to solve their problems, by providing them with a set of state of the art algorithms. The research of this project will help advance the frontiers of scientific research in convex programming, and will be incorporated into undergraduate and graduate teaching whenever possible.