American Institute of Mathematical Sciences

Advanced
2011, 1(3): 539-548. doi: 10.3934/naco.2011.1.539

Asymptotic strong duality

Regina S. Burachik 1, and  Xiaoqi Yang 2,

1. 

School of Mathematics and Statistics, University of South Australia, SA 5095, Australia
2. 

Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong

Received  June 2011 Revised  August 2011 Published  September 2011

Given a nonconvex and nonsmooth optimization problem, we define a family of ``perturbed'' Lagrangians, which induce well-behaved approximations of the dual problem. Our family of approximated problems is said to verify {\em strong asymptotic duality} when the optimal dual values of the perturbed problems approach the primal optimal value. Our perturbed Lagrangians can have the same order of smoothness as the functions of the original problem, a property not shared by the classical (unperturbed) augmented Lagrangian. Therefore our proposed scheme allows the use of efficient numerical methods for solving the perturbed dual problems. We establish general conditions under which strong asymptotic duality holds, and we relate the latter with both strong duality and lower semicontinuity of the perturbation function. We illustrate our perturbed duality scheme with two important examples: Constrained Nonsmooth Optimization and Nonlinear Semidefinite programming.
Keywords: duality schemes, nonsmooth optimization, augmented Lagrangians, Nonconvex programming, nonlinear semidefinite programming..
Mathematics Subject Classification: Primary: 90C26, 49M29, 49M37, 90C9.
Citation: Regina S. Burachik, Xiaoqi Yang. Asymptotic strong duality. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 539-548. doi: 10.3934/naco.2011.1.539
References:
[1]

K. M. Abadir and J. R. Magnus, "Matrix Algebra," Cambridge University Press, 2005.  Google Scholar

[2]

X. X. Huang, K. L. Teo and X. Q. Yang, Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs, Acta Mathematica Sinica, English Series., 22 (2006), 1283-1296. doi: 10.1007/s10114-005-0702-6.  Google Scholar

[3]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[4]

A. M. Rubinov, X. X. Huang and X. Q. Yang, The zero duality gap property and lower semicontinuity of the perturbation function, Math. Oper. Res., 27 (2002), 775-791. doi: 10.1287/moor.27.4.775.295.  Google Scholar

[5]

C. Y. Wang, X. Q. Yang and X. M. Yang, Unified nonlinear Lagrangian approach to duality and optimal paths, J. Optimiz. Theory Appl., 135 (2007), 85-100. doi: 10.1007/s10957-007-9225-x.  Google Scholar

show all references

References:
[1]

K. M. Abadir and J. R. Magnus, "Matrix Algebra," Cambridge University Press, 2005.  Google Scholar

[2]

X. X. Huang, K. L. Teo and X. Q. Yang, Approximate Augmented Lagrangian Functions and Nonlinear Semidefinite Programs, Acta Mathematica Sinica, English Series., 22 (2006), 1283-1296. doi: 10.1007/s10114-005-0702-6.  Google Scholar

[3]

R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[4]

A. M. Rubinov, X. X. Huang and X. Q. Yang, The zero duality gap property and lower semicontinuity of the perturbation function, Math. Oper. Res., 27 (2002), 775-791. doi: 10.1287/moor.27.4.775.295.  Google Scholar

[5]

C. Y. Wang, X. Q. Yang and X. M. Yang, Unified nonlinear Lagrangian approach to duality and optimal paths, J. Optimiz. Theory Appl., 135 (2007), 85-100. doi: 10.1007/s10957-007-9225-x.  Google Scholar

[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[2]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[3]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[4]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[5]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[6]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[7]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[8]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[9]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[10]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[11]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[12]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[13]

Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
[14]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[15]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[16]

Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[17]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[18]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[19]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[20]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

 Impact Factor: 

Tools

Metrics

  • PDF downloads (55)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences