快速探测模型不可行性的非线性规划算法的理论与应用研究

Nonlinear programming has extensive applications in science and engineering area, social and economic area, management, and so on. Many problems in these areas can be modeled as nonlinear programs. However, since the data is not complete or anything else, these programs may not be feasible initially and correct and effective models may be derived after several improvements. Currently, absolutely most of existing research works focus on algorithms with global and rapid local convergence to the solution under some assumptions, without considering the possible infeasibility of these programs. Although there are some algorithms, including some papers completed by the applicant and members, which have been proved to be able to deal with infeasible problems, they do not have the rapid convergence in general. This project attempts to develop a class of new algorithms capable of rapidly detecting the infeasibility of nonlinear programs, and apply these algorithms to solve some practical problems. These methods should be of strong global convergence, and locally not only have the probability to rapidly detect the infeasibility of nonlinear programs, but also have the rapid convergence to the Karush-Kuhn-Tucker point under suitable assumptions. It is expected that, by implementing this project, we have new gains in the theory and applications on algorithms for nonlinear programming.

非线性规划在工程、科学、社会、经济与管理等各个领域具有广泛的应用，这些领域中的许多问题都可以用非线性规划模型来描述。然而由于信息不完全等原因，模型可能不可行且需要多次反复修正才能正确描述所求解的问题。目前文献中的绝大多数算法和理论仅考虑在适当假设条件下能够快速找到问题的解，但没有给出关于模型不可行时的理论和数值结果，包括申请人在内的部分研究能够处理不可行性问题但不具有快速收敛性。本项目旨在申请人等已有工作的基础上，研究开发一类新的能够快速探测约束最优化模型不可行性的非线性规划方法及其收敛性理论，并考虑它在解决实际问题中的应用。所提出方法应具有强全局收敛性质，局部不仅应具有快速探测模型不可行性的能力，而且在求解可行非线性规划问题时也能够快速收敛到问题的解。我们期待通过本项目的研究，能够进一步改善非线性规划算法求解实际问题的能力，并能够在非线性规划算法理论和应用研究方面取得新的进展。

非线性规划在工程、科学、社会、经济与管理等各个领域具有广泛的应用，这些领域中的许多问题都可以用非线性规划模型来描述。然而由于信息不完全等原因，模型可能不可行且需要多次反复修正才能正确描述所求解的问题。目前文献中的绝大多数算法和理论仅考虑在适当假设条件下能够快速找到问题的解，但没有给出关于模型不可行时的算法理论和数值结果。受能够快速探测模型不可行性的逐步二次规划方法的研究启发，本项目主要研究开发了一类能够快速探测约束最优化模型不可行性的原始对偶内点方法及其收敛性理论。所提出的方法除了具有强全局收敛性质、在求解可行非线性规划问题时局部能够快速收敛到问题的解外，还在模型不可行时具有快速探测模型不可行性的能力。在此基础上，我们进一步在国际上首创地提出了能够探测模型不可行性的原始对偶内点松弛方法。所提出的原始对偶内点松弛方法不要求原始对偶迭代点是严格内点，能够改善经典原始对偶内点方法在求解大规模线性规划时不能很好利用问题的稀疏性、以及在靠近最优解时正规矩阵常常出现坏条件数的问题。通过本项目的研究，有望改善内点算法在求解大规模实际问题时的精度和速度，并进一步促进和提高优化方法解决实际应用问题的能力。