Interior-Point Methods for Conic Optimization

他的项目旨在研究二次规划问题的内点方法。将考虑进行改进，以使这些方法能够容易地检测到此类问题何时是不可行的或无界的，就像开发新模型时经常发生的那样。在大多数情况下，最有效的内点方法是原始-对偶方法，但在某些情况下，只要能找到合适的障碍函数，对偶方法就有望更快：本项目将研究如何构造如此有效的障碍函数。这两个主题可以通过考虑一般的圆锥问题和与无界性相关的问题来统一地研究。我们将从这个角度来研究几个主题：两个公式的最优解、中心路径和牛顿步长之间的关系，以及已知这些障碍的凸集的面和后退锥面的所谓自协调障碍函数的发展。本项目将继续研究圆锥优化问题的内点方法。这些方法被证明是解决真正的大规模线性规划问题的最有效的方法，例如在工业、政府和军事的资源分配问题中。最近，它们被扩展到一系列非线性问题，特别是二阶锥和半定规划，它们在结构优化、天线阵设计、滤波器设计和投资组合优化中有应用，并在获得困难的组合优化问题的紧界方面得到应用。该项目将扩展这些方法的能力，以检测何时这些问题的表述不当，从而不存在最优解。将研究解决超大规模问题的改进方法。先进的方法将在之前的NSF项目中与两名前研究生一起开发的SDPT3软件包中进行测试，并可通过互联网向其他用户提供。代码中的改进将提供给从业人员和其他代码开发人员。研究生将接受培训，成为圆锥规划建模和计算能力方面的专家。

his project aims to study interior-point methods for conicprogramming problems. Improvements will be considered to allow these methods to easily detect when such problems are infeasible or unbounded, as often happens whennew models are developed. The most efficient interior-point methods in most cases are primal-dual methods, but in certain cases, dual methods are expected to be faster as long as a suitable barrier functioncan be found: the project will study ways to construct suchefficient barrier functions. These two themes can be studied in aunified way by considering a general conic problem and a related problem associated with unboundedness. Several topics will be investigated from this viewpoint:the relationship between optimal solutions, central paths,and Newton steps for the two formulations,and the development of so-called self-concordant barrierfunctions for faces and recession cones of convex sets forwhich such barriers are known.This project will continue investigations into interior-pointmethods for conic optimization problems. These methods have proved themost efficient for solving truly large-scale linear programming problems,as arise in resource allocation problems in industry, government, and themilitary. More recently, they have been extended to a range ofnonlinear problems, in particular to second-order cone andsemidefinite programming, which have applications in structuraloptimization, antenna array design, filter design, and portfolio optimization, and in obtaining tightbounds for hard combinatorial optimization problems.The project will extend the capabilities of these methods todetect when such problems have been poorly formulatedso that optimal solutions do not exist. Improved methods for very large-scale problems will be investigated.Advances will be tested in the software package SDPT3 developed ina previous NSF project with two former graduate students, andavailable to other users over the internet. Improvementsin the code will be made available to practitioners and other codedevelopers. Graduate students will be trained to become experts in the modelling and computational power of conic programming.