Theory of cone programming and its applications

在锥规划问题中，变量的线性函数在变量的线性等式约束和变量在闭凸锥的基本约束下被最小化。锥规划，特别是半定规划(SDP)，在工程、科学、金融和统计等领域中有着广泛的应用。因此，开发高效可靠的算法来解决这些问题是至关重要的。本文旨在发展锥规划算法的理论和实现，并对锥规划的应用进行研究。该方案的目标包括：1)开发用于SDP和其他锥规划的高性能多项式和超线性收敛的原始-对偶内点(IP)方法；2)开发用于SDP和更一般的锥规划的基于迭代线性求解器的二阶IP算法；3)开发新的和/或改进用于SDP和更一般的锥规划问题的一阶光滑和非光滑方法的算法和实现；特别是开发用于这些问题的新的原始-对偶一阶方法；4)探索锥规划在稳健投资组合选择和统计决策中的广泛应用。拟议研究的预期影响是：1)为二阶原始-对偶IP算法和一阶光滑和非光滑方法的行为提供新的见解；2)开发和分发有效的实现，使从业者能够解决小规模到大规模的SDP和更一般的锥规划问题；3)提供锥规划在稳健投资组合选择和统计决策中的广泛应用，并分发高效和用户友好的软件来解决由这些领域产生的复杂决策问题。

In a cone programming problem, a linear function of variables is minimized subject to linear equality constraints on the variables and the essential constraint that the variables are in a closed convex cone. Cone programming, especially semidefinite program (SDP), problems arise in many applications in engineering, sciences, finance and statistics. Thus, it is of paramount importance to develop efficient and reliable algorithms to solve them.This proposal aims at the development of the theory and implementation of algorithms for cone programs and also investigates the applications of cone programs. The objectives of this proposal consist of: 1) developing high-performance polynomially and superlinearly convergent primal-dual interior-point (IP) methods for SDP and other cone programs; 2) developing second-order IP algorithms based on iterative linear solvers for SDP and more general cone programs; 3) developing new and/or improving existing algorithms and implementations for first-order smooth and non-smooth methods for SDP and more general cone programming problems; in particular, developing new primal-dual first-order methods for these problems; 4) exploring wide applications of cone programs in robust portfolio selection and statistical decision.The anticipated impact of the proposed research is: 1) to provide new insight into the behavior of second-order primal-dual IP algorithms and first-order smooth and non-smooth methods for SDP and more general cone programs; 2) to develop and distribute efficient implementations that will enable practitioners to solve small- to large-scale SDP and more general cone programming problems arising in diverse applications; 3) to provide wide applications of cone programs for robust portfolio selection and statistical decision, and to distribute efficient and user-friendly softwares for solving complex decision problems arising from these areas.