Cutting Planes and Surfaces, and Conic Programming

切割平面和曲面以及圆锥规划

• 批准号: 0715446
• 负责人: John Mitchell
• 金额: $ 26万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0715446&HistoricalAwards=false
• 关键词: Cutting; Planes; Surfaces; Conic; Programming

Convex optimization problems arise in many practical areas. They are vitally important in engineering, financial, medical, and scientific applications. Development of more effective methods for large-scale convex optimization problems will enable the solution of more accurate and detailed models in these fields. The power of convex optimization is beginning to be realized, with state-of-the-art techniques being exploited in real-world settings, and sophisticated models being developed to take advantage of the availability of these techniques. Some specific areas of application are network utility maximization, development of novel medications, and optimization of financialportfolios.The research in this proposal is aimed at developing good algorithms for certain classes of large-scale convex optimization problems. Further, techniques will be developed for solving integer programming and certain nonconvex problems that have relaxations that are convex. The methods of interest require constructing a convex relaxation of the original problem, finding a good solution to the relaxation, and then improving the relaxation if the solution to the relaxation is not a good enough solution to the original problem. The scientific interest is in the method for selection of the candidate point and in the discovery of methods for improving the relaxation. Taking place alongside the development of algorithms will be the development of models that can exploit the algorithms. Relaxations that are conic optimization problems are of particular interest. Candidate good points in such relaxations can be found efficiently using interior-point methods, and the relaxations can be updated through the addition of nonlinear conic constraints that accurately approximate the original model in the region of the candidate point.

凸优化问题出现在许多实际领域。 它们在工程、金融、医疗和科学应用中至关重要。 发展更有效的方法来解决大规模的凸优化问题，将使这些领域中更精确和详细的模型的解决方案。 凸优化的力量开始被认识到，最先进的技术被利用在现实世界的设置，和复杂的模型正在开发，以利用这些技术的可用性。 一些具体的应用领域是网络效用最大化，开发新的药物，优化financialportfolio.The研究在这个提案的目的是发展良好的算法，某些类的大规模凸优化问题。 此外，技术将被开发用于解决整数规划和某些非凸问题，具有松弛是凸的。 感兴趣的方法需要构造原始问题的凸松弛，找到松弛的好解，然后如果松弛的解不是原始问题的足够好的解，则改进松弛。 科学的兴趣在于选择候选点的方法和发现改善松弛的方法。 与算法的发展一起发生的将是可以利用算法的模型的发展。 松弛是圆锥优化问题是特别感兴趣的。 在这样的松弛的候选好点可以有效地使用邻域点方法，并可以通过添加非线性圆锥约束，准确地近似的候选点的区域中的原始模型更新的松弛。