Interior-point methods have proven to be efficient for the solution of large, sparse linear and quadratic programming problems. The objective of this research is to extend these methods so that they can be applied to the more general class of nonlinear optimization problems. In particular, the proposer's linear/quadratic solver, {\sc loqo}, will be enhanced so as to become an easy-to-use and efficient system for the solution of smooth nonlinear programming problems. If a problem is convex, the system will find a globally optimal solution. If it is nonconvex, then the system will find a locally optimal solution in a neighborhood of a given initial solution.
To carry out this plan, several algorithmic issues must be addressed including (a) which merit function to use, (b) when and by how much to perturb indefinite Hessians, (c) how to adapt the predictor-corrector variant, (d) how and when to sparsify Hessians, (e) how much to push initial values away from bounds, (f) how to detect and handle problems in which the constraints don't satisfy a constraint qualification condition, and (g) how to ensure that the infeasible interior-point method doesn't evaluate any function outside its domain. The resolution of these issues forms a significant part of the proposed research. This part of the research will be collaborative with Dave Shanno at Rutgers University.
Another major issue when studying nonlinear optimization is how to express a problem to a solver. The simple answer is to use a general purpose optimizationmodeling language, such as AMPL or GAMS, but until recently these modeling languages were unable to provide Hessian information, which is needed to implement interior-point methods. However, AMPL recently acquired this capability. Working in collaboration with David Gay at Lucent Technologies, who is one of the authors of AMPL, an easy to use environment is being developed in which one can solve nonlinear optimization problems using state-of-the-art interior-point methods. As part of this collaboration, an internet-accessible database of real-world AMPL models that can be used by anyone for both algorithmic studies and to aid in solving related real-world problems is being assembled.
Semidefinite programming (SDP) problems form an important subclass of the class of convex programming problems. These problems are important because of their many applications in engineering design problems, in particular eigenvalue optimization, and because they provide tight relaxations for certain combinatorial optimization problems. To date, algorithms for SDP have been created specifically for these problems. The interior-point-based system for nonlinear programming described above can, in principle, be applied directly to SDP problems. This generic approach will be compared against existing specialized codes.