Interior-Point Methods for Conic Optimization

圆锥优化的内点方法

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

Todd0209457 In this project, the investigator and his students studyimproved interior-point algorithms for convex, especiallysecond-order and semidefinite, programming problems. Inparticular, they investigate finding more accurate solutions tolarge-scale problems of this kind, interpreting the output ofinfeasible-interior-point methods as searching for infeasibilitycertificates when applied to infeasible problems, using ideas ofRiemannian geomentry to develop new interior-point methods forpossibly infeasible problems, and studying new barrier functionsto be used in highly asymmetric problems, where usual primal-onlyor primal-dual methods would be inefficient. All these ideas aretested out by implementing them in the software package SDPT3,developed by the investigator and two of his collaborators, whichis a competitive primal-dual code available over the internet (e.g., athttp://www.math.cmu.edu/~reha/sdpt3.html) and within the NEOS system (http://www-neos.mcs.anl.gov/neos/server-solvers.html)for distributed computing. Interior-point algorithms are a new and excitingcomputational method for solving large-scale resource allocationand other optimization problems. For example, they have beenused to develop better designs for truss structures, such asbridges, that are better able to resist a wide range of externalloads. Another application is the design of antenna arrays tohighlight the receptivity in certain directions while muting thatin all other directions. In finance, they are used to develop"optimal portfolios" to balance an acceptable rate of return withlow volatility (unfortunately, these methods are only as good asthe data they employ, and past history often does not give a goodindication of future performance). In this and other contexts,the idea of robust optimization, to find solutions to problemsthat satisfy all constraints even when the data are perturbed alittle, and that give good performance measures even when thedata are slightly changed, is very attractive, and this class ofmethods is successful in treating some problems of this kindalso. A last application mentioned here is currently beingstudied by the investigator and a statistics colleague: trying tofind a good way to classify new data into one of two classes(e.g., with or without a cancerous tumour) on the basis of sometraining data (with known classification). This problem is ofinterest in data mining and biomedical fields. In all theseproblems, there is a desire to solve larger and larger instances(involving tens of thousands of variables and constraints) moreand more accurately. The investigator and his collaboratorsstudy theoretically and practically ways to improve existingalgorithms to extend their capabilities in these directions.

中国人0209457 在这个项目中，调查员和他的学生研究改进的边界点算法的凸，特别是二阶和半定，规划问题。 特别是，他们调查寻找更准确的解决方案，以大规模的问题，这类，解释输出ofinfeasible-internal-point方法作为搜索infeasibilitycertificates时，适用于不可行的问题，使用的想法黎曼geomentry开发新的边界点方法可能不可行的问题，并研究新的障碍functions被用于高度不对称的问题，其中通常的原始-唯一或原始-对偶方法将是低效的。 所有这些想法都是通过在软件包SDPT 3中实现来测试的，SDPT 3是由研究者和他的两个合作者开发的，这是一个可以在互联网上获得的竞争性原始对偶代码（例如，http：//www.math.cmu.edu/neos/server-solvers.html）和近地天体系统（http：//www-neos.mcs.anl.gov/neos/server-solvers.html）内进行分布式计算。 内点算法是求解大规模资源分配等优化问题的一种新的、令人兴奋的计算方法。 例如，它们已经被用于开发更好的桁架结构设计，如桥梁，能够更好地抵抗各种外部载荷。 另一个应用是天线阵列的设计，以突出在某些方向的接收能力，而在所有其他方向静音。 在金融领域，它们被用来开发“最优投资组合”，以平衡可接受的回报率和低波动性（不幸的是，这些方法的好坏取决于它们所使用的数据，而过去的历史往往不能很好地预测未来的表现）。 在这种和其他情况下，鲁棒优化的思想，找到解决问题的办法，满足所有的约束条件，即使当数据受到干扰一点点，并给予良好的性能措施，即使当数据略有变化，是非常有吸引力的，这类方法是成功的治疗这类问题也。 这里提到的最后一个应用程序目前正在由调查人员和一位统计学同事研究：试图找到一种好的方法将新数据分为两类（例如，有或没有癌性肿瘤）。 该问题是数据挖掘和生物医学领域的研究热点。 在所有这些问题中，人们希望越来越精确地解决越来越大的实例（涉及成千上万的变量和约束）。 研究人员和他的合作者从理论上和实践上研究改进现有算法的方法，以在这些方向上扩展它们的能力。