Interior-point Methods for Large-scale Nonlinear Programming

这个研究项目的目的是扩展内点方法，使其可以应用于光滑的非线性优化问题。特别是，现有的线性/二次求解器将得到改进，使其成为解决这些问题的一个易于使用和有效的系统。如果一个问题是凸的，系统将找到一个全局最优解。如果它是非凸的，那么系统将在给定初始解的邻域内找到局部最优解。需要解决的算法问题包括：(a)使用哪个优点函数，(b)何时以及以多大程度扰动不定的Hessians， (c)如何适应预测校正变量，(d)如何以及何时稀疏Hessians， (e)将初始值推离边界的程度，(f)如何检测和处理约束不满足约束限定条件的问题，以及(g)如何确保不可行内点法不评估其域外的任何函数。作为本研究的一部分，将建立一个真实世界非线性优化模型的数据库。该数据库将通过互联网免费提供。最后，将寻求技术，使人们能够使用基于内点的非线性规划系统来解决半定规划问题。非线性优化在应用科学和工程的各个分支中都起着重要的作用。无论是最大限度地提高颤振破坏机翼的速度，最大限度地减少水热发电中不可再生资源的使用，设计一种可以用最少的材料承受特定载荷的结构，还是在保持主瓣特性的同时最小化天线阵列输出中的副瓣信号强度，都有一个共同的主题：优化。内点方法为解决这些问题提供了一种新的方法，它有望使人们比以前更可靠、更有效地解决这些问题。本研究项目将集中于解决产生一种高效且鲁棒的非线性优化内点算法所涉及的问题。

9870317Robert VanderbeiThe objective of this research project is to extend interior-point methods so that they can be applied to smooth nonlinear optimization problems. In particular, an existing linear/quadratic solver will be enhanced so as to become an easy-to-use and efficient system for the solution of these problems. If a problem is convex, the system will find a globally optimal solution. If it is nonconvex, then the system will find a locally optimal solution in a neighborhood of a given initial solution. The algorithmic issues to be addressed include: (a) which merit function to use, (b) when and by how much to perturb indefinite Hessians, (c) how to adapt the predictor-corrector variant, (d) how and when to sparsify Hessians, (e) how much to push initial values away from bounds, (f) how to detect and handle problems in which the constraints don't satisfy a constraint qualification condition, and (g) how to ensure that the infeasible interior-point method doesn't evaluate any function outside its domain. As part of this research, a database of real-world nonlinear optimization models will be assembled. This database will be freely available via the internet. Finally, techniques will be sought that will enable one to use the interior-point-based nonlinear-programming system to solve semidefinite programming problems.Nonlinear optimization plays a fundamental role in all branches of applied science and engineering. Whether it is maximizing the speed at which flutter destroys a wing, minimizing the use of nonrenewable resources in hydrothermal power generation, designing a structure that can bear a specified load with minimal amount of material, or minimizing side-lobe signal strength in the output of an antenna array while preserving main-lobe characteristics, there is one commonly shared theme: optimization. Interior-point methods provide a new approach to the solution of these problems, which promises to enable one to solve them more reliably and much more efficiently than before. This research project will focus on resolving the issues involved in producing an efficient and robust interior-point algorithm for nonlinear optimization.