This grant provides funding to support the development of novel algorithms for large-scale nonlinear optimization that are based on fast estimation of active inequality constraints. Many important methods for nonlinear optimization seek to determine which inequality constraints hold as equalities at the solution, so that the problem can be simplified to an equality constrained problem. As the number of inequality constraints grows, the standard approaches, which use quadratic programming, become too slow. Thus one needs to predict the correct active constraints in a more efficient way. The active-set identification techniques developed in this project will be based on the solution of linear programming subproblems and will allow the estimate of the active constraint set to change by many constraints at a time. New general purpose nonlinear optimization algorithms will be developed using these active-set identification techniques. This project will develop software implementations of these algorithms, as well as a general theory of active-set identification that covers these algorithms.
If successful, the proposed research will allow for the solution of significantly larger nonlinear optimization models (particularly problems with many inequality constraints) than can currently be solved using active-set methods. These more powerful algorithms may be applied to previously intractable models arising in areas such as medical imaging, classification, signal processing, chemical process control, power systems management, integrated circuit design and finance. In addition, active set approaches like this will be more effective at making use of a warm start compared with interior point methods. This will be beneficial for quickly solving subproblems that arise in branch and bound methods for mixed integer nonlinear programming. The theoretical framework for active-set identification developed as part of this project will provide a basis for exploring the development of future active-set based algorithms.
