Penalty/barrier path-following in linearly constrained optimization

Christian Grossmann

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

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

Abstract

top
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.

How to cite

top

Christian 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. [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. [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. [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. [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. [5] B. Chen and P.T. Harker, A continuation method for monotone variational inequalities, Math. Programming 69 (1995), 237-253. Zbl0844.90093
  6. [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. [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. [8] J.-P. Dussault, Numerical stability and efficiency of penalty algorithms, SIAM J. Numer. Anal. 32 (1995), 296-317. Zbl0816.65039
  9. [9] A.V. Fiacco and G.P. McCormick, Nonlinear programming: Sequential unconstrained minimization techniques, Wiley, New York 1968. Zbl0193.18805
  10. [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. [11] C. Grossmann, Asymptotic analysis of a path-following barrier method for linearly constrained convex problems, Optimization 45 (1999), 69-88. Zbl0949.90074
  12. [12] C. Grossmann and A.A. Kaplan, Straf-Barriere-Verfahren und modifizierte Lagrangefunktionen in der nichtlinearen Optimierung, Teubner, Leipzig 1979. Zbl0425.65035
  13. [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. [14] F.A. Lootsma, Boundary properties of penalty functions for constrained minimization, Philips Res. Rept. Suppl. 3 1970. 
  15. [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. [16] Yu. Nesterov and A. Nemirovskii, Interior-point polynomial algorithms in convex programming, SIAM Studies in Appl. Math., Philadelphia 1994. 
  17. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.