Abstract

We consider the problem min⁡x∈Rn{f(x)∣Ax=b, x∈C‾, gj(x)≤0, j=1,…,s}\min_{x\in\R^n}\{f(x)\mid Ax=b, \ x\in \overline{C},\ g_j(x)\le0,\ j=1,\ldots,s\}, where b∈Rmb\in\R^m, A∈Rm×nA\in\R^{m\times n} is a full rank matrix, C‾\overline{C} is the closure of a nonempty, open and convex subset CC of Rn\R^n, and gj(⋅)g_j(\cdot), j=1,…,sj=1,\ldots,s, are nonlinear convex functions. Our strategy consists firstly in to introduce a barrier-type penalty for the constraints gj(x)≤0g_j(x)\le0, then endowing {x∈Rn∣Ax=b,x∈C}\{x\in \R^n\mid Ax=b, x\in C\} with the Riemannian structure induced by the Hessian of an essentially smooth convex function hh such that C=int(dom h)C=\hbox{int}(\dom h), and finally considering the flow generated by the Riemannian penalty gradient vector field. Under minimal hypotheses, we investigate the well-posedness of the resulting ODE and we prove that the value of the objective function along the trajectories, which are strictly feasible, converges to the optimal value. Moreover, the value convergence is extended to the sequences generated by an implicit discretization scheme which corresponds to the coupling of an inexact generalized proximal point method with parametric barrier schemes. Specializations and simple illustrations of the general results are given for the positive orthant, the unitary simplex and the second-order cone

Author information

Contact details are reproduced from the original publication and may be historical.

Felipe Alvarez

Dep. de Ingeniería Matemática, Centro de Modelamiento Matemático, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile
and: CNRS UMI 2807

falvarez@dim.uchile.cl

Julio López

Dep. de Ingeniería Matemática, Centro de Modelamiento Matemático, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile
and: CNRS UMI 2807

jclopez@dim.uchile.cl

References

  1. F. Alizadeh, D. Goldfarb: Second-order cone programming, Math. Program., Ser. B 95(1) (2003) 3–51.https://doi.org/10.1007/s10107-002-0339-5Google Scholar
  2. F. Alvarez, J. Bolte, O. Brahic: Hessian Riemannian gradient flows in convex programming, SIAM J. Control Optim. 43(2) (2004) 477–501.https://doi.org/10.1137/S0363012902419977Google Scholar
  3. F. Alvarez, R. Cominetti: Primal and dual convergence of a proximal point exponential penalty method for linear programming, Math. Program., Ser. A 93(1) (2002) 87–96.https://doi.org/10.1007/s10107-002-0295-0Google Scholar
  4. H. Attouch, R. Cominetti: A dynamical approach to convex minimization coupling approximation with the steepest descent method, J. Differ. Equations 128 (1996) 519–540.https://doi.org/10.1006/jdeq.1996.0104Google Scholar
  5. H. Attouch, M. Teboulle: Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization, J. Optimization Theory Appl. 121(3) (2004) 541–570.https://doi.org/10.1023/B:JOTA.0000037603.51578.45Google Scholar
  6. H. Attouch, J. Bolte, P. Redont, M. Teboulle: Singular Riemannian barrier methods and gradient-projection dynamical systems for constrained optimization, Optimization 53 (2004) 435–454.https://doi.org/10.1080/02331930412331327184Google Scholar
  7. A. Auslender: Penalty and barrier methods: a unified framework, SIAM J. Optim. 10(1) (1999) 211–230.https://doi.org/10.1137/S1052623497324825Google Scholar
  8. J.-B. Baillon, R. Cominetti: A convergence result for non-autonomous subgradient evolution equations and its application to the steepest descent exponential penalty trajectory in linear programming, J. Funct. Anal. 187 (2001) 263–273.https://doi.org/10.1006/jfan.2001.3828Google Scholar
  9. H. Bauschke, J. M. Borwein, P. Combettes: Bregman monotone optimization algorithms, SIAM J. Control Optim. 42(2) (2003) 596–636.https://doi.org/10.1137/S0363012902407120Google Scholar
  10. J. Bolte, M. Teboulle: Barrier operators and associated gradient-like dynamical systems for constrained minimization problems, SIAM J. Control Optim. 42(4) (2003) 1266–1292.https://doi.org/10.1137/S0363012902410861Google Scholar
  11. Y. Censor, S. A. Zenios: The proximal minimization algorithm with D-function, J. Optimization Theory Appl. 73(3) (1992) 451–464.https://doi.org/10.1007/BF00940051Google Scholar
  12. G. Chen, M. Teboulle: Convergence analysis of proximal-like minimization algorithm using Bregman functions, SIAM J. Optim. 3(3) (1993) 538–543.https://doi.org/10.1137/0803026Google Scholar
  13. R. Cominetti: Coupling the proximal point algorithm with approximation methods, J. Optimization Theory Appl. 95 (1995) 581–600.https://doi.org/10.1023/A:1022621905645Google Scholar
  14. R. Cominetti, M. Courdurier: Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm, SIAM J. Optim. 13(3) (2002) 745–765.https://doi.org/10.1137/S1052623401397242Google Scholar
  15. J. X. da Cruz Neto, O. P. Ferreira, P. R. Oliveira, R. C. M. Silva: Central paths in semidefinite programming, generalized proximal-point method and Cauchy trajectories in Riemannian manifolds, J. Optimization Theory Appl. 139(2) (2008) 227–242.https://doi.org/10.1007/s10957-008-9422-2Google Scholar
  16. J. Eckstein: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Math. Oper. Res. 18 (1993) 202–226.https://doi.org/10.1287/moor.18.1.202Google Scholar
  17. L. E. Faybusovich: Dynamical systems which solve optimization problems with linear constraints, IMA J. Math. Control Inf. 8 (1991) 135–149.https://doi.org/10.1093/imamci/8.2.135Google Scholar
  18. O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim. 29(2) (1991) 403–419.https://doi.org/10.1137/0329022Google Scholar
  19. U. Helmke, J. B. Moore: Optimization and Dynamical Systems, Communications and Control Engineering Series, Springer, London (1994).https://doi.org/10.1007/978-1-4471-3467-1Google Scholar
  20. S. Herzel, M. C. Recchioni, F. Zirilli: A quadratically convergent method for linear programming, Linear Algebra Appl. 151 (1991) 255–290.https://doi.org/10.1016/0024-3795(91)90278-5Google Scholar
  21. A. N. Iusem, B. F. Svaiter, J. X. da Cruz Neto: Central paths, generalized proximal point methods and Cauchy trajectories in Riemannian manifolds, SIAM J. Control Optim. 37(2) (1999) 566–588.https://doi.org/10.1137/S0363012995290744Google Scholar
  22. N. Karmarkar: Riemannian geometry underlying interior point methods for linear programming, in: Mathematical Developments arising from Linear Programming (Brunswick, 1988), J. C. Lagarias, M. J. Todd (eds.), Contemp. Math. 114, AMS, Providence (1990) 51–75.https://doi.org/10.1090/conm/114/1097865Google Scholar
  23. K. C. Kiwiel: Proximal minimization methods with generalized Bregman functions, SIAM J. Control Optim. 35 (1997) 1142–1168.https://doi.org/10.1137/S0363012995281742Google Scholar
  24. K. Knopp: Theory and Application of Infinite Series, Blackie & Sons, Glasgow (1951).Google Scholar
  25. G. Pacelli, M. C. Recchioni: Monotone variable-metric algorithm for linearly constrained nonlinear programming, J. Optimization Theory Appl. 104(2) (2000) 255–279.https://doi.org/10.1023/A:1004645328197Google Scholar
  26. B. Polyak: Introduction to Optimization, Optimization Software, New York (1987).Google Scholar
  27. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  28. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar

Suggested citation

F. Alvarez, J. López. “Convergence to the Optimal Value for Barrier Methods Combined with Hessian Riemannian Gradient Flows and Generalized Proximal Algorithms.” Journal of Convex Analysis 17 (2010), No. 3&4, 701–720. https://doi.org/10.68381/jca17047

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2010. Rights now held by Banach Press.