Rescaled proximal methods for linearly constrained convex problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 367-380.

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.

DOI : https://doi.org/10.1051/ro:2007032
Classification : 90C25,  90C33
Mots clés : interior proximal methods, linearly constrained convex problems
@article{RO_2007__41_4_367_0,
     author = {Silva, Paulo J. S. and Humes Jr., Carlos},
     title = {Rescaled proximal methods for linearly constrained convex problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {367--380},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {4},
     year = {2007},
     doi = {10.1051/ro:2007032},
     mrnumber = {2361291},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2007032/}
}
Silva, Paulo J. S.; Humes Jr., Carlos. Rescaled proximal methods for linearly constrained convex problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 367-380. doi : 10.1051/ro:2007032. http://www.numdam.org/articles/10.1051/ro:2007032/

[1] A. Auslender and M. Haddou, An inteirior proximal method for convex linearly constrained problems. Math. Program. 71 (1995) 77-100. | Zbl 0855.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. | Zbl 1039.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. | Zbl 1039.90529

[4] Y. Censor and J. Zenios, The proximal minimization algorithms with D-functions. J. Optim. Theor. App. 73 (1992) 451-464. | Zbl 0794.90058

[5] J. Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18 (1993) 202-226. | Zbl 0807.47036

[6] C.C. Gonzaga, Path-following methods for linear programming. SIAM Rev. 34 (1992) 167-224. | Zbl 0763.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. | Zbl 0845.90099

[8] A.N. Iusem, M. Teboulle and B. Svaiter, Entropy-like proximal methods in covex programming. Math. Oper. Res. 19 (1994) 790-814. | Zbl 0821.90092

[9] B. Martinet, Regularisation d'inequations variationelles par approximations successives. Rev. Fr. Inf. Rech. Oper. (1970) 154-159. | Numdam | Zbl 0215.21103

[10] B. Martinet, Determination approch d'un point fixe d'une application pseudo-contractante. C.R. Acad. Sci. Paris 274A (1972) 163-165. | Zbl 0226.47032

[11] R.T. Rockafellar, Convex Analysis. Princeton University Press (1970). | MR 274683 | Zbl 0193.18401

[12] R.T. Rockafellar, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976) 887-898. | Zbl 0358.90053

[13] P.J.S. Silva and J. Eckstein, Double regularizations proximal methods, with complementarity applications. Comput. Optim. Appl. 33 (2006) 115-116. | Zbl 1111.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. | Zbl 1039.90053

[15] M. Teboulle, Entropic proximal methods with aplications to nonlinear programming. Math. Oper. Res. 17 (1992) 670-690. | Zbl 0766.90071

[16] M. Teboulle, Convergence of proximal-like algorithms. SIAM J. Optim. 7 (1997) 1069-1083. | Zbl 0890.90151

[17] P. Tseng and D. Bertesekas, On the convergence of the exponential multiplier method for convex programming. Math. Program. 60 (1993) 1-19. | Zbl 0783.90101

[18] Stephen J. Wright, Primal-Dual Interior-Point Methods. SIAM (1997). | MR 1422257 | Zbl 0863.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 Analysis 2 (2001) 139-156. | Zbl 1009.90087