Cutting Planes and Surfaces, and 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.