Abstract

We provide three new proofs of the strong concavity of the dual function of some convex optimization problems. For problems with nonlinear constraints, we show that the assumption of strong convexity of the objective cannot be weakened to convexity and that the assumption that the gradients of all constraints at the optimal solution are linearly independent cannot be further weakened. Finally, we illustrate our results with several examples.

Author information

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

Vincent Guigues

School of Applied Mathematics, Fundacao Getulio Vargas, Rio de Janeiro, Brazil

vincent.guigues@fgv.br

Keywords

  • Convex analysis
  • duality
  • strong convexity
  • optimization

Mathematics Subject Classification

26B25, 49N15

References

  1. J.-B. Baillon, G. Haddad: Quelques propriétés des opérateurs angle-bornés et n-cycliquement monotones, Israel J. Math. 26 (1977) 137–150.https://doi.org/10.1007/BF03007664Google Scholar
  2. H. H. Bauschke, J. Bolte, M. Teboulle: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications, Math. Oper. Res. 42/2 (2016) 330–348.https://doi.org/10.1287/moor.2016.0817Google Scholar
  3. V. Guigues: Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs, SIAM J. Optimization 26/4 (2016) 2468–2494.https://doi.org/10.1137/140983136Google Scholar
  4. V. Guigues: Inexact stochastic mirror descent for two-stage nonlinear stochastic programs, Math. Programming 187 (2021) 533–577.https://doi.org/10.1007/s10107-020-01490-5Google Scholar
  5. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms I, Grundlehren der Mathematischen Wissenschaften 305, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  6. G. Lan, A. Nemirovski, A. Shapiro: Validation analysis of mirror descent stochastic approximation method, Math. Programming 134/2 (2012) 425–458.https://doi.org/10.1007/s10107-011-0442-6Google Scholar
  7. R. T. Rockafellar, R. J-B Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin (1997).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  8. H. Yu, J. Neely: On the convergence time of the drift-plus-penalty algorithm for strongly convex programs, 54th IEEE Conference on Decision and Control (CDC) (2015) 2673–2679.https://doi.org/10.1109/CDC.2015.7402619Google Scholar

Suggested citation

V. Guigues. “On the Strong Concavity of the Dual Function of an Optimization Problem.” Journal of Convex Analysis 29 (2022), No. 1, 243–256. https://doi.org/10.68381/jca29015

Download BibTeXPublished by Heldermann Verlag.

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