Efficient Algorithms for Large Scale Convex Programming

本项目的目标是分析和开发大规模凸规划问题的算法。主要研究人员将通过在齐次锥上发展不变内点方法、原始内点方法和对偶内点方法来扩展内点方法的范围，这些方法形成了包括线性规划、半定规划和二阶锥规划在内的一大类问题。齐次锥具有丰富的对称性和分类理论，这使得它成为将结构化内点方法的理论扩展到半定规划之外的理想候选者。齐次锥规划的建模能力的研究将是该项目的一个重要部分，还将研究半定规划和双曲锥规划中的几个相关问题。该项目的第二个但相关的组成部分将是大规模凸规划的一阶方法的发展。这些方法具有较低的内存需求和全局收敛速度，它们(几乎)与基础优化问题的维度无关。因此，它们在解决大规模问题时很有吸引力，而内点方法由于其巨大的存储需求而可能是无效的。首席研究员和他的研究生将在凸规划中寻求这些问题和相关问题的答案。工业、工程和科学领域的大量问题(工程中的VLSI设计、天线阵列、桁架结构和控制系统、金融中的投资组合分析、量子化学中的分子结构、组合优化等)都依赖于有效的优化算法来解决。半定规划(SDP)已被证明是一个很好的框架，用来模拟大多数这类大规模问题，而SDP的内点方法在数值求解这些问题上也非常成功。医学成像和量子化学产生的超大规模问题为凸规划的一阶方法的发展提供了很好的激励。本研究所获得的理论见解将使我们对半定规划的内点方法有一个更深入的理解。这些洞察力将使首席研究员、他的学生和其他研究人员能够开发更快、更可靠的算法，使建模和解决更大问题成为可能。这些进展将为依赖现代优化技术解决问题的不同科学领域的研究人员提供一套最先进的算法，从而直接使他们受益。这个项目的研究将有助于推进凸规划科学研究的前沿，并将尽可能地纳入本科生和研究生教学。

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.