Title of article :
On the complexity of a combined homotopy interior method for convex programming
Author/Authors :
Yu، نويسنده , , Bo and Xu، نويسنده , , Qing Yi Feng، نويسنده , , Guochen، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2007
Pages :
15
From page :
32
To page :
46
Abstract :
In [G.C. Feng, Z.H. Lin, B. Yu, Existence of an interior pathway to a Karush–Kuhn–Tucker point of a nonconvex programming problem, Nonlinear Anal. 32 (1998) 761–768; G.C. Feng, B. Yu, Combined homotopy interior point method for nonlinear programming problems, in: H. Fujita, M. Yamaguti (Eds.), Advances in Numerical Mathematics, Proceedings of the Second Japan–China Seminar on Numerical Mathematics, Lecture Notes in Numerical and Applied Analysis, vol. 14, Kinokuniya, Tokyo, 1995, pp. 9–16; Z.H. Lin, B. Yu, G.C. Feng, A combined homotopy interior point method for convex programming problem, Appl. Math. Comput. 84 (1997) 193–211.], a combined homotopy was constructed for solving non-convex programming and convex programming with weaker conditions, without assuming the logarithmic barrier function to be strictly convex and the solution set to be bounded. It was proven that a smooth interior path from an interior point of the feasible set to a K–K–T point of the problem exists. This shows that combined homotopy interior point methods can solve the problem that commonly used interior point methods cannot solve. However, so far, there is no result on its complexity, even for linear programming. The main difficulty is that the objective function is not monotonically decreasing on the combined homotopy path. In this paper, by taking a piecewise technique, under commonly used conditions, polynomiality of a combined homotopy interior point method is given for convex nonlinear programming.
Keywords :
Polynomiality , Convex programming , homotopy method , Interior-point method , Path-following
Journal title :
Journal of Computational and Applied Mathematics
Serial Year :
2007
Journal title :
Journal of Computational and Applied Mathematics
Record number :
1553642
Link To Document :
بازگشت