A subgradient-based convex approximations method for DC programming and its applications

Previous Article
Multi-criteria media mix decision model for advertising a single product with segment specific and mass media
JIMO Home
This Issue
Next Article
An inventory model for items with imperfect quality and quantity discounts under adjusted screening rate and earned interest

October 2016, 12(4): 1349-1366. doi: 10.3934/jimo.2016.12.1349

A subgradient-based convex approximations method for DC programming and its applications

Jian Gu ^1, , Xiantao Xiao ^2, and Liwei Zhang ^2,

1.	School of Sciences, Dalian Ocean University, Dalian 116023, China
2.	School of Mathematical Sciences, Dalian University of Technology, Dalian 116023

Received September 2014 Revised May 2015 Published January 2016

Abstract
Related Papers

We consider an optimization problem that minimizes a function of the form $f=f_0+f_1-f_2$ with the constraint $g-h\leq 0$, where $f_0$ is continuous differentiable, $f_1,f_2$ are convex and $g,h$ are lower semicontinuous convex. We propose to solve the problem by an inexact subgradient-based convex approximations method. Under mild assumptions, we show that the method is guaranteed to converge to a stationary point. Finally, some preliminary numerical results are given.

Keywords: stationary point, set-valued analysis, DC programming, convergence., convex program.

Mathematics Subject Classification: Primary: 90C26, 49M05; Secondary: 49J5.

Citation: Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

References:

[1]	L. T. H. An, An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints, Math. Program., 87 (2000), 401-426. doi: 10.1007/s101070050003.
[2]	L. T. H. An, L. H. Minh and P. D. Tao, Optimization based DC programming and DCA for hierarchical clustering, European J. Oper. Res., 183 (2007), 1067-1085. doi: 10.1016/j.ejor.2005.07.028.
[3]	L. T. H. An and P. D. Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.
[4]	C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.
[5]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, {Springer, New York}, 2000. doi: 10.1007/978-1-4612-1394-9.
[6]	D. H. Fang, C. Li and X. Q. Yang, Asymptotic closure condition and Fenchel duality for DC optimization problems in locally convex spaces, Nonliner Anal., 75 (2012), 3672-3681. doi: 10.1016/j.na.2012.01.023.
[7]	M. Fazel, Matrix Rank Minimization with Applications, PhD thesis, Stanford University, 2002.
[8]	Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach, PhD thesis, National University of Singapore, 2010.
[9]	S. He, Z. Luo, J. Nie and S. Zhang, Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization, SIAM J. Optim., 19 (2008), 503-523. doi: 10.1137/070679041.
[10]	L. J. Hong, Y. Yang and L. Zhang, Sequential convex approximations to joint chance constrained programs: a Monte Carlo approach, Oper. Res., 59 (2011), 617-630. doi: 10.1287/opre.1100.0910.
[11]	R. Horst and N. V. Thoni, DC programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.
[12]	Z. Luo, W. Ma, A. So, Y. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Process Mag., 27 (2010), 20-34. doi: 10.1109/MSP.2010.936019.
[13]	Z. Luo, N. Sidiropoulos, P. Tseng and S. Zhang, Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optim., 18 (2007), 1-28. doi: 10.1137/050642691.
[14]	B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, Springer, Berlin, 2006.
[15]	A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996. doi: 10.1137/050622328.
[16]	B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), 471-501. doi: 10.1137/070697835.
[17]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[18]	W. Schirotzek, Nonsmooth Analysis, Springer, Berlin, 2007. doi: 10.1007/978-3-540-71333-3.
[19]	F. Shan, L. Zhang and X. Xiao, A smoothing function approach to joint chance-constrained programs, J. Optim. Theory Appl., 59 (2014), 181-199. doi: 10.1007/s10957-013-0513-3.
[20]	A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718751.
[21]	N. Sidiropoulos, T. Davidson and Z. Luo, Transmit beamforming for physical-layer multicasting, IEEE Trans. Signal Process., 54 (2006), 2239-2251. doi: 10.1109/TSP.2006.872578.
[22]	N. V. Thoai, Reverse convex programming approach in the space of extreme criteria for optimization over efficient sets, J. Optim. Theory Appl., 147 (2010), 263-277. doi: 10.1007/s10957-010-9721-2.
[23]	X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints, J. Ind. Manag. Optim., 8 (2012), 733-747. doi: 10.3934/jimo.2012.8.733.

show all references

References:

[1]	L. T. H. An, An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints, Math. Program., 87 (2000), 401-426. doi: 10.1007/s101070050003.
[2]	L. T. H. An, L. H. Minh and P. D. Tao, Optimization based DC programming and DCA for hierarchical clustering, European J. Oper. Res., 183 (2007), 1067-1085. doi: 10.1016/j.ejor.2005.07.028.
[3]	L. T. H. An and P. D. Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133 (2005), 23-46. doi: 10.1007/s10479-004-5022-1.
[4]	C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.
[5]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, {Springer, New York}, 2000. doi: 10.1007/978-1-4612-1394-9.
[6]	D. H. Fang, C. Li and X. Q. Yang, Asymptotic closure condition and Fenchel duality for DC optimization problems in locally convex spaces, Nonliner Anal., 75 (2012), 3672-3681. doi: 10.1016/j.na.2012.01.023.
[7]	M. Fazel, Matrix Rank Minimization with Applications, PhD thesis, Stanford University, 2002.
[8]	Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach, PhD thesis, National University of Singapore, 2010.
[9]	S. He, Z. Luo, J. Nie and S. Zhang, Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization, SIAM J. Optim., 19 (2008), 503-523. doi: 10.1137/070679041.
[10]	L. J. Hong, Y. Yang and L. Zhang, Sequential convex approximations to joint chance constrained programs: a Monte Carlo approach, Oper. Res., 59 (2011), 617-630. doi: 10.1287/opre.1100.0910.
[11]	R. Horst and N. V. Thoni, DC programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.
[12]	Z. Luo, W. Ma, A. So, Y. Ye and S. Zhang, Semidefinite relaxation of quadratic optimization problems, IEEE Signal Process Mag., 27 (2010), 20-34. doi: 10.1109/MSP.2010.936019.
[13]	Z. Luo, N. Sidiropoulos, P. Tseng and S. Zhang, Approximation bounds for quadratic optimization with homogeneous quadratic constraints, SIAM J. Optim., 18 (2007), 1-28. doi: 10.1137/050642691.
[14]	B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, Springer, Berlin, 2006.
[15]	A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996. doi: 10.1137/050622328.
[16]	B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), 471-501. doi: 10.1137/070697835.
[17]	R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, New York, 1998. doi: 10.1007/978-3-642-02431-3.
[18]	W. Schirotzek, Nonsmooth Analysis, Springer, Berlin, 2007. doi: 10.1007/978-3-540-71333-3.
[19]	F. Shan, L. Zhang and X. Xiao, A smoothing function approach to joint chance-constrained programs, J. Optim. Theory Appl., 59 (2014), 181-199. doi: 10.1007/s10957-013-0513-3.
[20]	A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718751.
[21]	N. Sidiropoulos, T. Davidson and Z. Luo, Transmit beamforming for physical-layer multicasting, IEEE Trans. Signal Process., 54 (2006), 2239-2251. doi: 10.1109/TSP.2006.872578.
[22]	N. V. Thoai, Reverse convex programming approach in the space of extreme criteria for optimization over efficient sets, J. Optim. Theory Appl., 147 (2010), 263-277. doi: 10.1007/s10957-010-9721-2.
[23]	X. Xiao, J. Gu, L. Zhang and S. Zhang, A sequential convex program method to DC program with joint chance constraints, J. Ind. Manag. Optim., 8 (2012), 733-747. doi: 10.3934/jimo.2012.8.733.

[1]	Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial and Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[2]	Zhenhua Peng, Zhongping Wan, Weizhi Xiong. Sensitivity analysis in set-valued optimization under strictly minimal efficiency. Evolution Equations and Control Theory, 2017, 6 (3) : 427-436. doi: 10.3934/eect.2017022
[3]	Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051
[4]	Yihong Xu, Zhenhua Peng. Higher-order sensitivity analysis in set-valued optimization under Henig efficiency. Journal of Industrial and Management Optimization, 2017, 13 (1) : 313-327. doi: 10.3934/jimo.2016019
[5]	Xing Wang, Nan-Jing Huang. Stability analysis for set-valued vector mixed variational inequalities in real reflexive Banach spaces. Journal of Industrial and Management Optimization, 2013, 9 (1) : 57-74. doi: 10.3934/jimo.2013.9.57
[6]	Roger Metzger, Carlos Arnoldo Morales Rojas, Phillipe Thieullen. Topological stability in set-valued dynamics. Discrete and Continuous Dynamical Systems - B, 2017, 22 (5) : 1965-1975. doi: 10.3934/dcdsb.2017115
[7]	Geng-Hua Li, Sheng-Jie Li. Unified optimality conditions for set-valued optimizations. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1101-1116. doi: 10.3934/jimo.2018087
[8]	Dante Carrasco-Olivera, Roger Metzger Alvan, Carlos Arnoldo Morales Rojas. Topological entropy for set-valued maps. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3461-3474. doi: 10.3934/dcdsb.2015.20.3461
[9]	Kendry J. Vivas, Víctor F. Sirvent. Metric entropy for set-valued maps. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022010
[10]	Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control and Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327
[11]	Qingbang Zhang, Caozong Cheng, Xuanxuan Li. Generalized minimax theorems for two set-valued mappings. Journal of Industrial and Management Optimization, 2013, 9 (1) : 1-12. doi: 10.3934/jimo.2013.9.1
[12]	Sina Greenwood, Rolf Suabedissen. 2-manifolds and inverse limits of set-valued functions on intervals. Discrete and Continuous Dynamical Systems, 2017, 37 (11) : 5693-5706. doi: 10.3934/dcds.2017246
[13]	Mariusz Michta. Stochastic inclusions with non-continuous set-valued operators. Conference Publications, 2009, 2009 (Special) : 548-557. doi: 10.3934/proc.2009.2009.548
[14]	Guolin Yu. Topological properties of Henig globally efficient solutions of set-valued problems. Numerical Algebra, Control and Optimization, 2014, 4 (4) : 309-316. doi: 10.3934/naco.2014.4.309
[15]	Zengjing Chen, Yuting Lan, Gaofeng Zong. Strong law of large numbers for upper set-valued and fuzzy-set valued probability. Mathematical Control and Related Fields, 2015, 5 (3) : 435-452. doi: 10.3934/mcrf.2015.5.435
[16]	Michele Campiti. Korovkin-type approximation of set-valued and vector-valued functions. Mathematical Foundations of Computing, 2022, 5 (3) : 231-239. doi: 10.3934/mfc.2021032
[17]	C. R. Chen, S. J. Li. Semicontinuity of the solution set map to a set-valued weak vector variational inequality. Journal of Industrial and Management Optimization, 2007, 3 (3) : 519-528. doi: 10.3934/jimo.2007.3.519
[18]	Guolin Yu. Global proper efficiency and vector optimization with cone-arcwise connected set-valued maps. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 35-44. doi: 10.3934/naco.2016.6.35
[19]	Jiawei Chen, Zhongping Wan, Liuyang Yuan. Existence of solutions and $\alpha$-well-posedness for a system of constrained set-valued variational inequalities. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 567-581. doi: 10.3934/naco.2013.3.567
[20]	Benjamin Seibold, Morris R. Flynn, Aslan R. Kasimov, Rodolfo R. Rosales. Constructing set-valued fundamental diagrams from Jamiton solutions in second order traffic models. Networks and Heterogeneous Media, 2013, 8 (3) : 745-772. doi: 10.3934/nhm.2013.8.745

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Jian Gu Xiantao Xiao Liwei Zhang
on Google Scholar
Jian Gu Xiantao Xiao Liwei Zhang

[Back to Top]