Interior Point Methods for Nonconvex Nonlinear Programming

工作将继续发展一般连续数学规划问题的LOQO内点码算法，并扩大其可应用的问题范围。研究领域包括更好地检测不可行性和无界性，更好地检测约束的线性依赖性，以及更好地估计对最优点的初始估计。对高阶方法的研究，可以大大提高算法的效率，将继续进行，特别是对应用过滤方法的兴趣。为了扩大算法可以解决的问题类型的范围，研究将涉及使用内点法解决离散问题。考虑的一类问题将是混合整数二次规划。这类问题通常出现在金融领域。混合整数线性规划问题也将研究，最初的重点是快速找到可行的解决方案。进一步的工作将涉及一般的互补性问题，特别是在经济学和工程学中出现的问题。在所有情况下，由实际应用程序产生的问题的适当集合将在AMPL中建模。这些将通过互联网提供，LOQO计划的扩展也将提供。用于解决各种数学规划问题的LOQO代码在过去四年中一直在开发中，是首席研究员和普林斯顿大学的Robert Vanderbei教授的共同研究成果。该代码通过互联网免费提供，迄今已被下载数千次。它被用来解决各种各样的问题，如工程设计、投资组合优化、航班调度问题，目前正被用于医学研究的各种项目。所提出的研究集中在提高代码的效率和增加代码可用于的问题集。希望代码能够有效适应的新类型问题是变量必须为整数（通常为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.