A constraint shifting homotopy method for general non-linear programming

Abstract

In this article, a constraint shifting homotopy method (CSHM) is proposed for solving non-linear programming with both equality and inequality constraints. A new homotopy is constructed, and existence and global convergence of a homotopy path determined by it are proven. All problems that can be solved by the combined homotopy interior point method (CHIPM) can also be solved by the proposed method. In contrast to the combined homotopy infeasible interior point method (CHIIPM), it needs a weaker regularity condition. And the starting point in the proposed method is not necessarily a feasible point or an interior point, so it is more convenient to be implemented than CHIPM and CHIIPM. Numerical results show that the proposed algorithm is feasible and effective.

Keywords:

• non-linear programming
• homotopy method
• global convergence

AMS Subject Classifications::

• 49M05
• 90C30

Acknowledgements

The authors thank the anonymous reviewers, whose precise and substantial remarks led to an improved version of this article. The research was supported by the National Natural Science Foundation of China (11171051, 11101067, 70971070), the Fundamental Research Funds for the Central Universities, and the Natural Science Foundation of Shandong Province (ZR2009HM004).