Interior-Point Methods for Conic Optimization

他的项目旨在研究圆锥规划问题的内点方法。将考虑改进这些方法，以便在这些问题不可行或无界时（在开发新模型时经常发生这种情况）轻松检测到这些问题。在大多数情况下，最有效的内点方法是原始对偶方法，但在某些情况下，只要能找到合适的势垒函数，对偶方法预计会更快：该项目将研究构建这种有效势垒函数的方法。这两个主题可以通过考虑一个一般的经济问题和一个与无界性相关的问题来统一地研究。从这一观点出发，我们将研究几个主题：两种公式的最优解、中心路径和牛顿步之间的关系，以及已知障碍的凸集的面和衰退锥的所谓自和谐障碍函数的发展。本项目将继续研究二次优化问题的内点法。这些方法已被证明是解决真正大规模线性规划问题的最有效方法，如工业、政府和军事中的资源分配问题。最近，它们已扩展到一系列非线性问题，特别是二阶锥和半定规划，它们在结构优化，天线阵列设计，滤波器设计和组合优化以及获得硬组合优化问题的紧界方面具有应用。该项目将扩展这些方法的能力，以检测这些问题是否表述不当，从而不存在最佳解决方案。我们将研究解决大规模问题的改进方法。在NSF之前的项目中，两名以前的研究生开发了软件包SDPT3，将在软件包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.