Interior Point Methods for Nonconvex Nonlinear Programming

这项工作将继续发展LOQO内点编码的算法，用于一般连续数学规划问题，并扩大它可以应用于问题的范围。研究领域包括更好地检测不可行性和无界性，更好地检测约束的线性相关性，以及更好地估计最优点的初始估计。高阶方法的工作将继续进行，这可以大大提高算法的效率，特别是对应用滤波方法感兴趣。为了扩大算法可以解决的问题类型的范围，研究将关注使用内点法解决离散问题。所考虑的问题类型将是混合整数二次规划。这类问题通常出现在金融领域。混合整数线性规划问题也将被研究，最初的重点是快速找到可行的解。进一步的工作将涉及一般的互补性问题，特别是在经济学和工程学中出现的问题。在所有情况下，将使用AMPL对实际应用程序中出现的问题进行适当的建模。这些将通过互联网提供，LOQO程序的扩展程序也将提供。用于解决各种类型的数学规划问题的LOQO代码在过去四年里一直在开发中，这是首席研究员和普林斯顿大学的罗伯特·范德贝教授共同研究的成果。该代码可以通过互联网免费获得，到目前为止已经被下载了数千次。它用于解决工程设计、投资组合优化、航空公司调度问题等各种问题，目前正被用于医学研究中的各种项目。所提出的研究集中在提高代码的效率和增加代码可用于的问题集合上。希望代码能够有效修改的新类型的问题是变量必须是整数的问题，通常是0或1。这些问题非常常见，具有很大的实用价值。例如，在将飞机分配给航线时，必须将整个飞机分配到特定的航线，而不是飞机的某一部分。在上下文中包括整数变量的这种类型的算法是非常新的，将通过重要的特定应用程序进行初步探讨。

The work will continue to develop the algorithm of the LOQO interior point code for general continuous mathematical programming problems, and expand the range of problems to which it can be applied. Areas of research include betterdetection of infeasibility and unboundedness, better detection of linear dependence of the constraints, and better estimates of initial estimates to the optimum point. Work on higher order methods, which can greatly improve algorithmic efficiency, will be continued, with particular interest in applying filter methods. In an attempt to expand the scope of the types of problems that the algorithm can solve, the research will be concerned with solving discrete problems using interior point methods. On type of problem considered will be mixed integer quadratic programming. Problems of this type commonly arise in finance. Mixed integer linear programming problems will also be studied, with an initial focus on quickly finding feasible solutions. Further work will be concerned with general complementarity problems, especially those that arise in economics and engineering. In all cases, appropriate collections of problems arising from real applications will be modeled in AMPL. These will be made available via the internet, as will extensions to the LOQO program.The LOQO code for solving a variety of types of mathematical programming problems has been under development for the past four years as a joint research effort of the principal investigator and Professor Robert Vanderbei of Princeton University. The code is made freely available via the internet, and to date has been downloaded several thousand times. It is used to solve problems as diverse as engineering design, portfolio optimization, airline scheduling problems, and is currently being adapted for various projects in medical research. The proposed research is concentrated both on improving the efficiency of the code and increasing the set of problems for which the code can be used. The new types of problems for which it is hoped the code can be adapted efficiently are problems with variables that must be an integer, generally 0 or 1. These problems are extremely common, and of great practical value. For example, when assigning aircraft to routes, a whole plane must be assigned to a specific route, not some fraction of a plane. Including integer variables within the context an algorithm of this type is very new, and will be approached initially through important specific applications.