Abstract

We consider nonconvex conic optimization that covers Standard Nonlinear Programming, Semidefinite Programming, Second Order Cone Programming. To the dual Lagrangian problem, we associate a relaxed primal convex problem, and give bounds for the duality gap. Then we propose a proximal extension of the column generation method of Dantzig-Wolfe algorithm (PECGM) which provides these bounds if we suppose in addition Slater's condition. Finally new applications are given in order to make implementable the step of PECGM for which a nonconvex program is supposed to be solved numerically.

Author information

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

Alfred Auslender

Institut Camille Jordan, Université Claude Bernard, 43 Boulevard du 11 Novembre 1918, 69622 Villeurbanne - Lyon, France
and: Département d'Economie, Ecole Polytechnique, Palaiseau, France

Keywords

  • Standard nonlinear programming
  • semidefinite programming
  • second order cone programming
  • duality gap
  • generation column algorithm
  • proximal method

References

  1. B. Alkire, L. Vandenberghe: Convex optimization problems involving autocorrelation sequences, Math. Program., Ser. A 93 (2002) 331–359.https://doi.org/10.1007/s10107-002-0334-xGoogle Scholar
  2. J. P. Aubin, I. Ekeland: Estimates of the duality gap in nonconvex optimization, Math. Oper. Res. 1(3) (1976) 225–245.https://doi.org/10.1287/moor.1.3.225Google Scholar
  3. A. Ben-Tal, A. Nemirovski: Lectures on Modern Convex Optimization. Analysis, Algorithms, and Engineering Applications, MPS/SIAM Series on Optimization 2, SIAM, Philadelphia (2001).https://doi.org/10.1137/1.9780898718829Google Scholar
  4. A. Ben-Tal, M. Teboulle: Hidden convexity in some quadratically constrained quadratic programming, Math Program., Ser. A 72(1) (1996) 51–63.https://doi.org/10.1007/BF02592331Google Scholar
  5. J. Bolte, A. Daniilidis, O. Ley, L. Mazet: Characterizations of Lojasiewicz inequalities and applications (2008), to appear.Google Scholar
  6. G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton (1963).https://doi.org/10.1515/9781400884179Google Scholar
  7. J. E. Falk, K. R. Hoffman: A successive underestimation method for concave minimization, Math. Oper. Res. 1(3) (1976) 251–259.https://doi.org/10.1287/moor.1.3.251Google Scholar
  8. R. Hettich, K. O. Kortanek: Semi-infinite programming: theory, methods, and applications, SIAM Rev. 35(3) (1993) 380–429.https://doi.org/10.1137/1035089Google Scholar
  9. W. Hare, C. Sagastizabal: Computing points of nonconvex functions, Math. Program., Ser. B 116 (2009) 221–258.https://doi.org/10.1007/s10107-007-0124-6Google Scholar
  10. J. B. Lasserre: Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11 (2001) 796–817.https://doi.org/10.1137/S1052623400366802Google Scholar
  11. G. Lan, Z. Lu, R. D. C. Monteiro: Primal-dual first order methods with 0( 1ε) iterations for conic progamming, Technical Report, School of Industrial and Systems Enginnering, Georgia Institute of Technology, Atlanta (2006).Google Scholar
  12. T. L. Magnanti, J. F. Shapiro, M. H. Wagner: Generalized linear programming solves the dual, Manage. Sci. 22(11) (1976) 1195–1203.https://doi.org/10.1287/mnsc.22.11.1195Google Scholar
  13. Yu. Nesterov: Squared functional systems and optimization problems, in: High Performance Optimization, H. Frenk et al. (ed.), Appl. Optim 33, Kluwer, Dordrecht (2000) 405–440.https://doi.org/10.1007/978-1-4757-3216-0_17Google Scholar
  14. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin (1998)https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  15. W. W. Rogosinsky: Moments of non-negative mass, Proc. R. Soc. Lond., Ser. A 245 (1958) 1–27.https://doi.org/10.1098/rspa.1958.0062Google Scholar
  16. D. C. Sorensen: Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim. 7(1) (1997) 141–161.https://doi.org/10.1137/S1052623494274374Google Scholar
  17. H. Tuy: Concave programming under linear constraints, Sov. Math., Dokl. 5 (1964) 1437–1440.Google Scholar

Suggested citation

A. Auslender. “A Proximal Extension of the Column Generation Method to Nonconvex Conic Optimization Providing Bounds for the Duality Gap.” Journal of Convex Analysis 17 (2010), No. 3&4, 721–736. https://doi.org/10.68381/jca17048

Download BibTeXPublished by Heldermann Verlag.

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