Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T19:12:21.886Z Has data issue: false hasContentIssue false
  • English
  • Français

Rescaled proximal methods for linearly constrained convex problems

Published online by Cambridge University Press:  11 October 2007

Paulo J.S. Silva  and
Carlos Humes Jr.
Paulo J.S. Silva
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil; [email protected], [email protected]
Carlos Humes Jr.
Affiliation:
Instituto de Matemática e Estatística, Universidade de São Paulo, Brazil; [email protected], [email protected]
Get access

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.

Keywords

Interior proximal methodsLinearly constrained convex problems
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 4 , October 2007 , pp. 367 - 380
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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