# Penalty/barrier path-following in linearly constrained optimization

Discussiones Mathematicae, Differential Inclusions, Control and Optimization (2000)

- Volume: 20, Issue: 1, page 7-26
- ISSN: 1509-9407

## Access Full Article

top## Abstract

top## How to cite

topChristian Grossmann. "Penalty/barrier path-following in linearly constrained optimization." Discussiones Mathematicae, Differential Inclusions, Control and Optimization 20.1 (2000): 7-26. <http://eudml.org/doc/271436>.

@article{ChristianGrossmann2000,

abstract = {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 [1,11], 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.},

author = {Christian Grossmann},

journal = {Discussiones Mathematicae, Differential Inclusions, Control and Optimization},

keywords = {penalty/barrier; interior point methods; convex optimization},

language = {eng},

number = {1},

pages = {7-26},

title = {Penalty/barrier path-following in linearly constrained optimization},

url = {http://eudml.org/doc/271436},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Christian Grossmann

TI - Penalty/barrier path-following in linearly constrained optimization

JO - Discussiones Mathematicae, Differential Inclusions, Control and Optimization

PY - 2000

VL - 20

IS - 1

SP - 7

EP - 26

AB - 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 [1,11], 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.

LA - eng

KW - penalty/barrier; interior point methods; convex optimization

UR - http://eudml.org/doc/271436

ER -

## References

top- [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. Zbl0872.90067
- [3] A. Ben-Tal and M. Zibulevsky, Penalty/barrier multiplier methods for convex programming problems, SIAM J. Optimization 7 (1997), 347-366. Zbl0872.90068
- [4] B. Chen and P.T. Harker, A noninterior continuation method for quadratic and linear programming, SIAM J. Optimization 3 (1993), 503-515. Zbl0795.90040
- [5] B. Chen and P.T. Harker, A continuation method for monotone variational inequalities, Math. Programming 69 (1995), 237-253. Zbl0844.90093
- [6] R. Cominetti and J.M. Peres-Cerda, Quadratic rate of convergence for a primal-dual exponential penalty algorithm, Optimization 39 (1997), 13-32. Zbl0867.90104
- [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. Zbl0760.65056
- [8] J.-P. Dussault, Numerical stability and efficiency of penalty algorithms, SIAM J. Numer. Anal. 32 (1995), 296-317. Zbl0816.65039
- [9] A.V. Fiacco and G.P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, Wiley, New York 1968. Zbl0193.18805
- [10] R.M. Freund and S. Mizuno, Interior point methods: current status and future directions, OPTIMA, Math. Programming Soc. Newsletter 51 (1996). Zbl0955.90149
- [11] C. Grossmann, Asymptotic analysis of a path-following barrier method for linearly constrained convex problems, Optimization 45 (1999), 69-88. Zbl0949.90074
- [12] C. Grossmann and A.A. Kaplan, Straf-Barriere-Verfahren und modifizierte Lagrangefunktionen in der nichtlinearen Optimierung, Teubner, Leipzig 1979. Zbl0425.65035
- [13] M. Halická and M. Hamala, Duality transformation functions in the interior point methods, Acta Math. Univ. Comenianae LXV (1996), 229-245. Zbl0926.90076
- [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. Zbl0846.90112
- [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. Zbl0957.65056
- [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₂ barrier penalty function for nonlinear optimization, Working paper, March 1999, University of Tokyo. Zbl1072.90050

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.