Differential
Inclusions, Control and Optimization 20 (2000) 7-26

doi: 10.7151/dmdico.1001

Christian Grossmann

*Institute of Numerical Mathematics
Dresden University of Technology, D-01062 Dresden, Germany
*

In the present paper rather general penalty/barrier path-following methods (e.g. with p-th power penalties, logarithmic barriers, SUMT, exponential penalties) applied to linearly constrained convex optimization problems are studied. In particular, unlike in previous studies [,], here simultaneously different types of penalty/barrier embeddings are included. Together with the assumed 2nd order sufficient optimality conditions this required a significant change in proving the local existence of some continuously differentiable primal and dual path related to these methods. In contrast to standard penalty/barrier investigations in the considered path-following algorithms only one Newton step is applied to the generated auxiliary problems. As a foundation of convergence analysis the radius of convergence of Newton's method depending on the penalty/barrier parameter is estimated. There are established parameter selection rules which guarantee the overall convergence of the considered path-following penalty/barrier techniques.

**Keywords:** penalty/barrier, interior point methods, convex optimization.

**1991 Mathematics Subject Classification:** 49M15, 65K10, 65H10, 90C25.

[1] | D. Al-Mutairi, C. Grossmann and K.T. Vu, Path-following barrier and penalty methods
for linearly constrained problems, Preprint MATH-NM-10-1998, TU Dresden 1998 (to
appear in Optimization). |

[2] | A. Auslender, R. Cominetti and M. Haddou, Asymptotic analysis for penalty and
barrier methods in convex and linear programming, Math. Operations Res. 22
(1997), 43-62. |

[3] | A. Ben-Tal and M. Zibulevsky, Penalty/barrier multiplier methods for convex
programming problems, SIAM J. Optimization 7 (1997), 347-366. |

[4] | B. Chen and P.T. Harker, A noninterior continuation method for quadratic and linear
programming, SIAM J. Optimization 3 (1993), 503-515. |

[5] | B. Chen and P.T. Harker, A continuation method for monotone variational
inequalities, Math. Programming 69 (1995), 237-253. |

[6] | R. Cominetti and J.M. Peres-Cerda, Quadratic rate of convergence for a primal-dual
exponential penalty algorithm, Optimization 39 (1997), 13-32. |

[7] | P. Deuflhard and F. Potra, Asymptotic mesh independence of Newton-Galerkin methods
via a refined Mysovskii theorem, SIAM J. Numer. Anal. 29 (1992), 1395-1412. |

[8] | J.-P. Dussault, Numerical stability and efficiency of penalty algorithms, SIAM
J. Numer. Anal. 32 (1995), 296-317. |

[9] | A.V. Fiacco and G.P. McCormick, Nonlinear programming: Sequential unconstrained
minimization techniques, Wiley, New York 1968. |

[10] | R.M. Freund and S. Mizuno, Interior point methods: current status and future
directions, OPTIMA, Math. Programming Soc. Newsletter 51 (1996). |

[11] | C. Grossmann, Asymptotic analysis of a path-following barrier method for linearly
constrained convex problems, Optimization 45 (1999), 69-88. |

[12] | C. Grossmann and A.A. Kaplan, Straf-Barriere-Verfahren und modifizierte
Lagrangefunktionen in der nichtlinearen Optimierung, Teubner, Leipzig 1979. |

[13] | M. Halická and M. Hamala, Duality transformation functions in the interior point
methods, Acta Math. Univ. Comenianae LXV (1996), 229-245. |

[14] | F.A. Lootsma, Boundary properties of penalty functions for constrained minimization,
Philips Res. Rept. Suppl. 3 1970. |

[15] | S. Mizuno, F. Jarre and J. Stoer, A unified approach to infeasible-interior-point
algorithms via geometric linear complementarity problems, Appl. Math. Optimization 33
(1996), 315-341. |

[16] | Yu. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex
programming, SIAM Studies in Appl. Math., Philadelphia 1994. |

[17] | M.H. Wright, Ill-conditioning and computational error in interior methods for
nonlinear programming, SIAM J. Opt. 9 (1998), 84-111. |

[18] | S.J. Wright, On the convergence of the Newton/Log-barrier method, Preprint
ANL/MCS-P681-0897, MCS Division, Argonne National Lab., August 1997 (revised version
1999). |

[19] | H. Yamashita and H. Yabe, An interior point method with a primal-dual l, Working paper, March 1999,
University of Tokyo. _{2}
barrier penalty function for nonlinear optimization |

Received 13 November 1999

Revised 26 January 2000