Interior Point Methods for Nonconvex Nonlinear Programming

点击翻译按钮获取中文摘要

DMS-9805495 David F. Shanno Interior Point Methods for Nonconvex Nonlinear Programming Abstract: The research is concerned with studying logarithmic barrier methods for nonconvex nonlinear programming. The problem studied is the problem of minimizing a nonlinear objective function subject to nonlinear inequality constraints. Topics to be studied include merit functions, trust regions, and matrix modification methods for nonconvex problems. A topic of extensive study will be higher order methods for solving the nonlinear system of equations arising from the first order conditions for the problem, with particular emphasis on extending Mehrotra's predictor-corrector method to nonconvex problems. The general nonlinear programming problem, which has equality contraints, bounds and ranges as well as inequality constraints will be adapted so as to be solvable with the algorithms developed. Careful study will be made of the problem of determining infeasiblility and unboundedness for nonconvex nonlinear programs. Special algorithms will be developed for problems where second derivatives are not available. All developed algorithms will be coded and extensively tested. Nonlinear programming problems arise in a wide variety of applications drawn from a broad spectrum of engineering and science problems, statistics problems, economics problems, and logistics problems to name a few of the many areas where such problems are common. For example, drawing inference from data bases is a statistics problem that often requires the minimization of a nonlinear likelihood function subject to parametric constraints. This problem becomes particularly difficult when the dtabase is very large. The proposed research will develop methods for these nonlinear problems that are akin to the interior point methods that have proved so efficient for very large scale linear problems. These methods are also highly applicable to solving nonlinear partial differential equations with n onlinear boundary conditions, which are used in everything from aircraft design to design of structures such as bridges to estimating the reserves in an underground groundwater or oil reserve, as a few examples of the myriad applications. Part of the project will be to collect as broad a problem set of real applications as possible to adapt the algorithms to be efficient for these problems, and to demonstrate the use of the algoritms across the widest possible spectrum of applications. In all cases, the the algorithms will be designed to solve very large problems efficiently, as these methods are proving extremely efficient for large problems on high performance computers.