Interior-Point Methods for Conic Optimization

圆锥优化的内点方法

• 批准号: 0513337
• 负责人: Michael Todd
• 金额: $ 31.88万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-08-01 至 2009-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0513337&HistoricalAwards=false
• 关键词: Interior; Point; Methods; Conic; Optimization

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.

他的项目旨在研究圆锥规划问题的边界点方法。将考虑改进，使这些方法能够很容易地检测到这些问题是不可行的或无界的，因为经常发生在开发新模型时。 在大多数情况下，最有效的邻域点方法是原始-对偶方法，但在某些情况下，只要能找到合适的障碍函数，对偶方法预计会更快：该项目将研究如何构造这种有效的障碍函数。这两个主题可以通过考虑一个一般的圆锥曲线问题和一个与无界性相关的问题来统一研究。从这个观点出发，将研究几个课题：两个公式的最优解、中心路径和牛顿步骤之间的关系，以及已知这种障碍的凸集的面和凹锥的所谓自协调障碍函数的发展。本项目将继续研究圆锥优化问题的边界点方法。这些方法被证明是解决真正的大规模线性规划问题，如在工业，政府和商业中的资源分配问题中出现的最有效的方法。最近，他们已经扩展到一系列的非线性问题，特别是二阶锥和半定规划，这在结构优化，天线阵列设计，滤波器设计和投资组合优化的应用，该项目将扩展这些方法的能力，以检测何时此类问题的公式化程度很差，从而使最优解不存在. 改进的方法非常大规模的问题将进行调查。进步将在软件包SDPT 3测试在以前的NSF项目与两名前研究生，并提供给其他用户在互联网上。代码中的成果将提供给从业者和其他代码开发人员。研究生将接受培训，成为圆锥规划建模和计算能力的专家。