Interior Point Methods for Nonconvex Nonlinear Programming

DMS-9805495 大卫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.