Rescaled proximal methods for linearly constrained convex problems

Paulo J.S. Silva; Carlos Humes

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 4, page 367-380
  • ISSN: 0399-0559

Abstract

top
We present an inexact interior point proximal method to solve linearly constrained convex problems. In fact, we derive a primal-dual algorithm to solve the KKT conditions of the optimization problem using a modified version of the rescaled proximal method. We also present a pure primal method. The proposed proximal method has as distinctive feature the possibility of allowing inexact inner steps even for Linear Programming. This is achieved by using an error criterion that bounds the subgradient of the regularized function, instead of using ϵ-subgradients of the original objective function. Quadratic convergence for LP is also proved using a more stringent error criterion.

How to cite

top

Silva, Paulo J.S., and Humes, Carlos. "Rescaled proximal methods for linearly constrained convex problems." RAIRO - Operations Research 41.4 (2007): 367-380. <http://eudml.org/doc/250138>.

@article{Silva2007,
abstract = { We present an inexact interior point proximal method to solve linearly constrained convex problems. In fact, we derive a primal-dual algorithm to solve the KKT conditions of the optimization problem using a modified version of the rescaled proximal method. We also present a pure primal method. The proposed proximal method has as distinctive feature the possibility of allowing inexact inner steps even for Linear Programming. This is achieved by using an error criterion that bounds the subgradient of the regularized function, instead of using ϵ-subgradients of the original objective function. Quadratic convergence for LP is also proved using a more stringent error criterion. },
author = {Silva, Paulo J.S., Humes, Carlos},
journal = {RAIRO - Operations Research},
keywords = {Interior proximal methods; Linearly constrained convex problems; interior proximal methods; linearly constrained convex problems},
language = {eng},
month = {10},
number = {4},
pages = {367-380},
publisher = {EDP Sciences},
title = {Rescaled proximal methods for linearly constrained convex problems},
url = {http://eudml.org/doc/250138},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Silva, Paulo J.S.
AU - Humes, Carlos
TI - Rescaled proximal methods for linearly constrained convex problems
JO - RAIRO - Operations Research
DA - 2007/10//
PB - EDP Sciences
VL - 41
IS - 4
SP - 367
EP - 380
AB - We present an inexact interior point proximal method to solve linearly constrained convex problems. In fact, we derive a primal-dual algorithm to solve the KKT conditions of the optimization problem using a modified version of the rescaled proximal method. We also present a pure primal method. The proposed proximal method has as distinctive feature the possibility of allowing inexact inner steps even for Linear Programming. This is achieved by using an error criterion that bounds the subgradient of the regularized function, instead of using ϵ-subgradients of the original objective function. Quadratic convergence for LP is also proved using a more stringent error criterion.
LA - eng
KW - Interior proximal methods; Linearly constrained convex problems; interior proximal methods; linearly constrained convex problems
UR - http://eudml.org/doc/250138
ER -

References

top
  1. A. Auslender and M. Haddou, An inteirior proximal method for convex linearly constrained problems. Math. Program.71 (1995) 77–100.  Zbl0855.90095
  2. A. Auslender, M. Teboulle and S. Ben-Tiba, Interior proximal and multiplier methods based on second order homogeneous kernels. Math. Oper. Res.24 (1999) 645–668.  Zbl1039.90518
  3. A. Auslender, M. Teboulle and S. Ben-Tiba, A logarithmic-quadratic proximal method for variational inequalities. Comput. Optim. Appl.12 (1999) 31–40.  Zbl1039.90529
  4. Y. Censor and J. Zenios, The proximal minimization algorithms with D-functions. J. Optim. Theor. App.73 (1992) 451–464.  Zbl0794.90058
  5. J. Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res.18 (1993) 202–226.  Zbl0807.47036
  6. C.C. Gonzaga, Path-following methods for linear programming. SIAM Rev.34 (1992) 167–224.  Zbl0763.90063
  7. A.N. Iusem and M. Teboulle, Convergence rate analysis of nonquadratic proximal methods for convex and linear programming. Math. Oper. Res.20 (1995) 657–677.  Zbl0845.90099
  8. A.N. Iusem, M. Teboulle and B. Svaiter, Entropy-like proximal methods in covex programming. Math. Oper. Res.19 (1994) 790–814.  Zbl0821.90092
  9. B. Martinet, Regularisation d'inequations variationelles par approximations successives. Rev. Fr. Inf. Rech. Oper. (1970) 154–159.  Zbl0215.21103
  10. B. Martinet, Determination approch d'un point fixe d'une application pseudo-contractante. C.R. Acad. Sci. Paris274A (1972) 163–165.  Zbl0226.47032
  11. R.T. Rockafellar, Convex Analysis. Princeton University Press (1970).  Zbl0193.18401
  12. R.T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim.14 (1976) 887–898.  Zbl0358.90053
  13. P.J.S. Silva and J. Eckstein, Double regularizations proximal methods, with complementarity applications. Comput. Optim. Appl.33 (2006) 115–116.  Zbl1111.90111
  14. P.J.S. Silva, J. Eckstein and C. Humes Jr, Rescaling and stepsize selection in proximal methods using generalized distances. SIAM J. Optim.12 (2001) 238–261.  Zbl1039.90053
  15. M. Teboulle, Entropic proximal methods with aplications to nonlinear programming. Math. Oper. Res.17 (1992) 670–690.  Zbl0766.90071
  16. M. Teboulle, Convergence of proximal-like algorithms. SIAM J. Optim.7 (1997) 1069–1083.  Zbl0890.90151
  17. P. Tseng and D. Bertesekas, On the convergence of the exponential multiplier method for convex programming. Math. Program.60 (1993) 1–19.  
  18. Stephen J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997).  Zbl0863.65031
  19. N. Yamashita, C. Kanzow, T. Morimoto and M. Fukushima, An infeasible interior proximal method for convex programming problems with linear constraints. Journal Nonlinear Convex Analysis2 (2001) 139–156.  Zbl1009.90087

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.