A primal-infeasible interior point algorithm for linearly constrained convex programming

• Autorzy: Wang Y. , Fei P.
• Języki publikacji: EN

Abstrakty

EN

In this paper a primal-infeasible interior point algorithm is proposed for linearly constrained convex programming. A positive primal-infeasible dual-feasible point can be taken as the starting point of this algorithm in a large region. At each iterates it requires to solve approximately a nonlinear system. The polynomial complexity of the algorithm is obtained. It is shown that, after finite iterations a sufficiently good approximation to the optimal point is found, or there is no optimal point in a large region.

Słowa kluczowe

EN

linearly constrained convex programming; primal-infeasible interior point algorithm; polynomial complexity

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 3
• Strony: 687--704
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Wang Y.

autor

Fei P.

• Institute of Applied Physics and Computational Mathematics, P.O. Box 8009-15, Beijing, 100088, China,

Bibliografia

• GÜLER, 0. (1997) Hyperbolic polynomials and interior point methods for convex programming. Math. Oper. Res. 22, 350-377.
• HERTOG, D., (1994) Interior point approach to linear, quadratic and convex programming. Mathematics and Its Applications, 277. Kluwer Academic Publishers Group.
• KOJIMA, M., MEGIDDO, N. and MIZUO, S. (1993) A primal-dual infeasible-interior-point algorithms for linear programming. Math. Programming 61, 263-280.
• KOJIMA, M., NOMA, T., and YOSHISE, A. (1994) Global convergence of an infeasible-interior-point methods. Math. Programming 65, 43-72.
• KORTANEK, K.O., POTRA, F., and YE, Y. (1991) On some efficient interior point methods for nonlinear convex programming. Linear Algebra and Its Applications 152, 169-189.
• KORZAK, J. (2000) Convergence analysis of inexact infeasible-interior-point algorithms for solving linear programming problems. SIAM J. Optim. 11 (1), 133-148.
• MIZUNO, S. (1995) Polynomial complexity of infeasible-interior-point algoritms for linear programming. Math. Programming 67, 109-119.
• MIZUNO, S., and JARRE, F. (1999) Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation. Math. Program. 84 (1), 105-122.
• MONTEIRO, R.D.C., and ZHOU, F. (1997) On superlinear convergence of infeasible interior-point algorithms for linearly constrained convex programming. Comput. Optim. Appl. 8, 245-262.
• NESTEROV, Y., and NEMIROVSKI, A. (1994) Interior Point Polynomial Algorithms In Convex Programming. SIAM Publications, Philadelphia, PA.
• POTRA, F.A., and WRIGHT, S. (2000) Interior point methods, J. Comput. Appl Math. 124 (1-2), 281-302.
• POTRA, F.A., and YE, Y. (1996) Interior-point methods for nonlinear complementarity problems. J. Optim. Theory Appl. 88 (3), 617-642.
• RALPH, D., and WRIGHT, S. (1997) Superlinear convergence of an interior point method for monotone variational inequalities. In: Complementarity and Variational Problems: state of the Art. SIAM.
• RALPH, D., and WRIGHT, S. (2000) Superlinear convergence of an interior-point method despite dependent constrains. Math. Oper. Res. 25 (2), 179-194.
• SHI, Y. (2002) A combination of potential reduction steps and steepest decent steps for solving convex programming prblems. Numerical Linear Algebra with Applications 9, 195-203.
• TSENG, P. (1997) An infeasible path-following method for monotone complementarity problems. SIAM J. Optim. 7 (2), 386-402.
• WRIGHT, S. (1997) Primal-Dual Interior-Point Methods. SIAM, Philadelphia.
• WRIGHT, S., and RALPH, D. (1996) A Superlinear infeasible-interior-point algorithm for monotone complementarity problems. Math. Oper. Res. 21 (4), 815-838.
• YAMASHITA, N., KANZOW, C., MORIMOTO, T. and FUKUSHIMA, M. (2001) An infeasible interior proximal method for convex programming problems with linear constraints. J. Nonlinear Convex Anal. 2, 139-156.
• YE, Y. (1997) Interior Point Algorithms: Theory and Analysis. Wiley: New York.