On asymptotic Lagrangian duality for nonsmooth optimization

Abstract

Zero duality gap for nonconvex optimization problems requires the use of a generalized Lagrangian function in the definition of the dual problem. We analyze the situation in which the original problem is associated with a sequence of Lagrangian functions, which in turn defines a sequence of dual problems. Under a set of basic assumptions, we prove that the generated sequence of optimal dual values converges to the optimal primal value, and call the latter situation strong duality for the sequence of Lagrangian functions. As an application of our theory, we construct two sequences of augmented Lagrangians for general equality constrained optimization problems in finite dimensions which exhibit strong duality in this new sense. References

• R. S. Burachik, W. P. Freire and C. Y. Kaya. Interior epigraph directions method for nonsmooth and nonconvex optimization via generalized augmented Lagrangian duality. Journal of Global Optimization, 60(3):501–529, 2014. doi:10.1007/s10898-013-0108-4
• R. S. Burachik, R. N. Gasimov, N. A. Ismayilova and C. Y. Kaya. On a modified subgradient algorithm for dual problems via sharp augmented Lagrangian. Journal of Global Optimization, 34(1):55–78, 2006. doi:10.1007/s10898-005-3270-5
• R. S. Burachik, A. N. Iusem and J. G. Melo. The exact penalty map for nonsmooth and nonconvex optimization. Optimization, 64(4):717–738, 2015. doi:10.1080/02331934.2013.830117
• R. S. Burachik, A. N. Iusem and J. G. Melo. An inexact modified subgradient algorithm for primal-dual problems via augmented Lagrangians. Journal of Optimization Theory and Applications, 157(1):108–131, 2013. doi:10.1007/s10957-012-0158-7
• R. S. Burachik, A. N. Iusem and J. G. Melo. A primal dual modified subgradient algorithm with sharp Lagrangian. Journal of Global Optimization, 46(3): 347–361, 2010. doi:10.1007/s10898-009-9429-8
• R. S. Burachik, A. N. Iusem and J. G. Melo. Duality and exact penalization for general augmented Lagrangians, Journal of Optimization Theory and Applications, 147(1):125–140, 2010. doi:10.1007/s10957-010-9711-4
• R. S. Burachik and C. Y. Kaya. An augmented penalty function method with penalty parameter updates for nonconvex optimization, Nonlinear Analysis: Theory, Methods and Applications, 75(3):1158–1167, 2012. doi:10.1016/j.na.2011.03.013
• R. S. Burachik and C. Y. Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial Management and Optimization, 3(2): 381–398, 2007. doi:10.3934/jimo.2007.3.381
• R. S. Burachik, C. Y. Kaya and M. Mammadov. An inexact modified subgradient algorithm for nonconvex optimization. Computational Optimization and Applications, 45(1):1–24, 2010. doi:10.1007/s10589-008-9168-7
• R. S. Burachik and X. Q. Yang, Asymptotic strong duality, Numerical Algebra, Control and Optimization (NACO), 1(3):539–548, 2011. doi:10.3934/naco.2011.1.539
• R. S. Burachik and A. M. Rubinov. Abstract convexity and augmented Lagrangians. SIAM Journal on Optimization, 18(2):413–436, 2007. doi:10.1137/050647621
• R. S. Burachik and A. M. Rubinov, On the absence of duality gap for Lagrange-type functions, Journal of Industrial and Management Optimization, 1(1):33–38, 2005. doi:10.3934/jimo.2005.1.33
• R. N. Gasimov. Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming. Journal of Global Optimization, 24(2):187–203, 2002. doi:10.1023/A:1020261001771
• R. N. Gasimov and A. M. Rubinov. On augmented Lagrangians for optimization problems with a single constraint. Journal of Global Optimization, 28(2):153–173, 2004. doi:10.1023/B:JOGO.0000015309.88480.2b
• O. Guler. Foundations of Optimization, Graduate texts in Mathematics 258, Springer, Berlin, 2010. doi:10.1007/978-0-387-68407-9
• G. Li. Global error bounds for piecewise convex polynomials. Mathematical Programming, 137(1):37–64, 2013. doi:10.1007/s10107-011-0481-z
• X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Acta Mathematica Sinica, English Series, 22:1283–1296, 2006. doi:10.1007/s10114-005-0702-6
• R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin, 1998. doi:10.1007/978-3-642-02431-3
• A. M. Rubinov, X. X. Huang and X. Q. Yang, The zero duality gap property and lower semicontinuity of the perturbation function, Mathematics of Operations Research, 27:775–791, 2002. doi:10.1287/moor.27.4.775.295
• C. Y. Wang, X. Q. Yang and X. M. Yang, A unified nonlinear Lagrangian approach to duality and optimal paths, Journal of Optimization Theory and Applications 135:85–100, 2007. doi:10.1007/s10957-007-9225-x