Efficient Algorithms for Large Scale Convex Programming

这个项目的目标是分析和开发大规模凸规划问题的算法。主要研究者将通过发展齐次锥上的不变内点法、原始内点法和对偶内点法来扩展内点法的范围，这些内点法形成了包括线性规划、半定规划和二阶锥规划在内的大类问题。齐次锥具有丰富的对称性质和分类理论，是将结构内点法理论扩展到半定规划以外的理想对象。研究齐次锥规划的建模能力将是本课题的重要组成部分，同时还将研究半定规划和双曲锥规划中的几个相关课题。第二个，但这个项目的相关组成部分将是大规模凸规划的可证明有效的一阶方法的发展。这些方法具有较低的内存需求和全局收敛率，并且（几乎）与底层优化问题的维数无关。因此，它们对于解决非常大规模的问题是有吸引力的，对于这些问题，内点方法可能由于其广泛的内存需求而无效。首席研究员和他的研究生将在凸规划中寻找这些问题和相关问题的答案。所得到的算法将进行数值测试，以确认其有效性。工业、工程和科学中的许多问题（VLSI、天线阵列、桁架结构和工程控制系统的设计、金融中的投资组合分析、量子化学中的分子结构、组合优化以及许多其他问题）都依赖于有效的优化算法来解决。半定规划（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.