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 and 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.

[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.

[3]

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

[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.

[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.

show all references

References:
[1]

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

[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.

[3]

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

[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.

[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.

[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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]

Aleksandar Jović. Saddle-point type optimality criteria, duality and a new approach for solving nonsmooth fractional continuous-time programming problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022025
[14]

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

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

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[17]

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

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 and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[19]

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

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy