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.