Nonlinear Optimization: Algorithms, Software, Applications

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Nonlinear programming (the minimization of a smooth nonlinear function subject to smooth (possibly) nonlinear constraints) is a touchstone problem in optimization. The problem continues to excite strong interest among optimization researchers for many reasons, among them new developments in algorithms and software (especially of the interior-point variety), the study of mathematical programs with equilibrium constraints (MPEC), and the discovery of new application areas. The broad scope of the nonlinear programming paradigm admits a great many pathologies in the geometric nature of the problem and in its algebraic speci.cation. It is impossible to design algorithms that converge reliably in all circumstances. Local convergence theory for most algorithms depends on regularity and strict complementarity assumptions, and problems for which these assumptions are not satis.ed (degenerate problems) are the cause of undesirable and awkward behavior in most algorithms and codes. This project will investigate some approaches to nonlinear programming, related to approaches currently in use, that have the potential for improved performance on degenerate and large-scale problems. These techniques will be theoretically rigorous and practical, in that the marginal computational cost of handling degeneracy will not be too great and in that they will behave well even when implemented in .oating-point arithmetic. Particular attention will be given to MPECs, which exhibit degeneracy of a speci.c type. Extensions to degenerate complementary problems and variational inequalities will also be investigated. Special attention will be paid to the numerical aspects of implementing these algorithms, an important issue because of the ill conditioning that may be present in the subproblems at each iteration. All this research will be carried out in a coordinated manner, coupling theoretical advances with computational experiments using both prototype software and modi.cations to production software. Work on applications of nonlinear programming, performed in collaboration with domain scientists and engineers, will be the second key contribution of the proposal. Interdisciplinary research of this type plays a key role in any research program in algorithmic optimization. The PI has ongoing collaborations in such areas as engineering control, statistics, and cancer treatment planning. The intellectual merit of the proposed work lies in improvements to our understanding of nonlinear programs and of the algorithms that solve these problems, in the construction of better algorithms and software that are robust in the face of degeneracy, and in the impact of these advances on many application areas including those described in the proposal. The work will have a wider impact on users of optimization technology, ultimately bene.ting many of those who use optimization software packages to solve problems in an extremely wide range of applications. Domain scientists and engineers in the areas highlighted in the proposal will bene.t especially.