his project aims to study interior-point methods for conic programming problems. Improvements will be considered to allow these methods to easily detect when such problems are infeasible or unbounded, as often happens when new 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 function can be found: the project will study ways to construct such efficient barrier functions. These two themes can be studied in a unified 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 barrier functions for faces and recession cones of convex sets for which such barriers are known.
This project will continue investigations into interior-point methods for conic optimization problems. These methods have proved the most efficient for solving truly large-scale linear programming problems, as arise in resource allocation problems in industry, government, and the military. More recently, they have been extended to a range of nonlinear problems, in particular to second-order cone and semidefinite programming, which have applications in structural optimization, antenna array design, filter design, and portfolio optimization, and in obtaining tight bounds for hard combinatorial optimization problems. The project will extend the capabilities of these methods to detect when such problems have been poorly formulated so 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 in a previous NSF project with two former graduate students, and available to other users over the internet. Improvements in the code will be made available to practitioners and other code developers. Graduate students will be trained to become experts in the modelling and computational power of conic programming.
