Interior Point Methods for Nonconvex Nonlinear Programming

DMS-9805495非凸非线性规划的David F.Shanno内点方法摘要：研究非凸非线性规划的对数障碍方法。所研究的问题是具有非线性不等式约束的非线性目标函数的最小化问题。所研究的主题包括价值函数、信赖域和非凸问题的矩阵修改方法。一个广泛研究的主题将是求解由问题的一阶条件引起的非线性方程组的高阶方法，特别强调将Mehrotra的预估-校正方法推广到非凸问题。对于具有等式约束、界和值域以及不等式约束的一般非线性规划问题，所开发的算法将适用于可解。我们将仔细研究非凸非线性规划的不可行性和无界性的判定问题。对于没有二阶导数的问题，将开发特殊的算法。所有开发的算法都将经过编码和广泛测试。非线性规划问题出现在各种各样的应用中，这些问题来自广泛的工程和科学问题、统计学问题、经济问题和物流问题，仅举几个这样的问题常见的领域。例如，从数据库进行推理是一个统计问题，通常需要最小化受参数约束的非线性似然函数。当数据库非常大时，这个问题变得特别困难。所提出的研究将为这些非线性问题开发类似于内点法的方法，内点法已被证明对超大规模线性问题是如此有效。这些方法也非常适用于求解具有非线性边界条件的非线性偏微分方程组，这些方程被用于从飞机设计到桥梁等结构设计到估计地下地下水或石油储量的各种情况，作为无数应用的几个例子。该项目的一部分将是收集尽可能广泛的真实应用程序的问题集，以使算法适用于这些问题，并展示算法在最广泛的应用程序范围内的使用。在所有情况下，算法都将被设计为高效地解决非常大的问题，因为这些方法在高性能计算机上被证明对大问题非常有效。

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.