Abstract

We consider the problem of minimizing a smooth convex function over the set of constrained minimizers of another smooth convex function. We show that this problem can be solved by a simple and explicit gradient descent type method. Standard constrained optimization is a particular case in this framework, corresponding to taking the lower level function as a penalty of the feasible set. We note that in the case of standard constrained optimization, the method does not require solving any penalization (or other optimization) subproblems, not even approximately, and does not perform projections (although explicit projections onto simple sets can be incorporated).

Author information

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

Mikhail Solodov

Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil

solodov@impa.br

Keywords

  • Convex minimization
  • bilevel optimization
  • penalty methods
  • descent methods

Mathematics Subject Classification

90C30, 65K05

References

  1. A. Ben-Tal, T. Margalit, A. Nemirovski: The ordered subsets mirror descent optimization method with applications to tomography, SIAM J. Optim. 12 (2001) 79–108.https://doi.org/10.1137/S1052623499354564Google Scholar
  2. D. P. Bertsekas: Nonlinear Programming, Athena Scientific, Belmont (1995).Google Scholar
  3. D. P. Bertsekas: Convex Analysis and Optimization, Athena Scientific, Belmont (2003).Google Scholar
  4. B. T. Boggs, J. W. Tolle: Sequential quadratic programming, Acta Numerica 4 (1996) 1–51.https://doi.org/10.1017/S0962492900002518Google Scholar
  5. J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal: Numerical Optimization: Theoretical and Practical Aspects, Springer, Berlin (2003).https://doi.org/10.1007/978-3-662-05078-1Google Scholar
  6. A. Cabot: Proximal point algorithm controlled by a slowly vanishing term: Applications to hierarchial minimization, SIAM J. Optim. 15 (2005) 555–572.https://doi.org/10.1137/S105262340343467XGoogle Scholar
  7. R. Cominetti, M. Courdurier: Coupling general penalty schemes for convex programming with the steepst descent and the proximal point algorithm, SIAM J. Optim. 13 (2002) 745–765.https://doi.org/10.1137/S1052623401397242Google Scholar
  8. M. Kočvara, J. V. Outrata: Optimization problems with equilibrium constraints and their numerical solution, Math. Program. 101 (2004) 119–149.https://doi.org/10.1007/s10107-004-0539-2Google Scholar
  9. A. V. Fiacco, G. P. McCormick: Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, New York (1968).Google Scholar
  10. M. Fukushima, Z.-Q. Luo, P. Tseng: A sequential quadratically constrained quadratic programming method for differentiable convex minimization, SIAM J. Optim. 13 (2003) 1098–1119.https://doi.org/10.1137/S1052623401398120Google Scholar
  11. Z.-Q. Luo, J.-S. Pang, D. Ralph: Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge (1996).https://doi.org/10.1017/CBO9780511983658Google Scholar
  12. B. T. Polyak: Introduction to Optimization, Optimization Software, New York (1987).Google Scholar
  13. A. V. Rodionov, A. A. Tret’yakov: A method for solving the convex programming problem, Voprosy Kibernet. 136 (1988) 111–117, in Russian.Google Scholar
  14. C. A. Sagastizábal, M. V. Solodov: On the relation between bundle methods for maximal monotone inclusions and hybrid proximal point algorithms, in: D. Butnariu, Y. Censor, S. Reich (eds.), Inherently Parallel Algorithms in Feasibility and Optimization and their Applications (Haifa, 2000), Stud. Comput. Math. 8, Elsevier, Amsterdam (2001) 441–455.https://doi.org/10.1016/S1570-579X(01)80026-4Google Scholar
  15. M. V. Solodov: On the sequential quadratically constrained quadratic programming methods, Math. Oper. Res. 29 (2004) 64–79.https://doi.org/10.1287/moor.1030.0069Google Scholar
  16. M. V. Solodov, B. F. Svaiter: A hybrid projection-proximal point algorithm, J. Convex Analysis 6 (1999) 59–70.https://doi.org/10.68381/jca06005Google Scholar
  17. M. V. Solodov, B. F. Svaiter: Error bounds for proximal point subproblems and associated inexact proximal point algorithms, Math. Program. 88 (2000) 371–389.https://doi.org/10.1007/s101070050022Google Scholar
  18. M. V. Solodov, B. F. Svaiter: A truly globally convergent Newton-type method for the monotone nonlinear complementarity problem, SIAM J. Optim. 10 (2000) 605–625.https://doi.org/10.1137/S1052623498337546Google Scholar

Suggested citation

M. Solodov. “An Explicit Descent Method for Bilevel Convex Optimization.” Journal of Convex Analysis 14 (2007), No. 2, 227–237. https://doi.org/10.68381/jca14016

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2007. Rights now held by Banach Press LLC.