American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

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

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

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

[5]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, {Springer, New York}, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

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

[7]

M. Fazel, Matrix Rank Minimization with Applications, PhD thesis, Stanford University, 2002. Google Scholar

[8]

Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach, PhD thesis, National University of Singapore, 2010. Google Scholar

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

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

[11]

R. Horst and N. V. Thoni, DC programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.  Google Scholar

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

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

[14]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, Springer, Berlin, 2006.  Google Scholar

[15]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996. doi: 10.1137/050622328.  Google Scholar

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

[17]

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

[18]

W. Schirotzek, Nonsmooth Analysis, Springer, Berlin, 2007. doi: 10.1007/978-3-540-71333-3.  Google Scholar

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

[20]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

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

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

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

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.  Google Scholar

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

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

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

[5]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, {Springer, New York}, 2000. doi: 10.1007/978-1-4612-1394-9.  Google Scholar

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

[7]

M. Fazel, Matrix Rank Minimization with Applications, PhD thesis, Stanford University, 2002. Google Scholar

[8]

Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach, PhD thesis, National University of Singapore, 2010. Google Scholar

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

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

[11]

R. Horst and N. V. Thoni, DC programming: Overview, J. Optim. Theory Appl., 103 (1999), 1-43. doi: 10.1023/A:1021765131316.  Google Scholar

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

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

[14]

B. S. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, Springer, Berlin, 2006.  Google Scholar

[15]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996. doi: 10.1137/050622328.  Google Scholar

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

[17]

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

[18]

W. Schirotzek, Nonsmooth Analysis, Springer, Berlin, 2007. doi: 10.1007/978-3-540-71333-3.  Google Scholar

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

[20]

A. Shapiro, D. Dentcheva and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718751.  Google Scholar

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

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

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

[1]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2015, 20 (10) : 3461-3474. doi: 10.3934/dcdsb.2015.20.3461
[9]

Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327
[10]

Qingbang Zhang, Caozong Cheng, Xuanxuan Li. Generalized minimax theorems for two set-valued mappings. Journal of Industrial & Management Optimization, 2013, 9 (1) : 1-12. doi: 10.3934/jimo.2013.9.1
[11]

Sina Greenwood, Rolf Suabedissen. 2-manifolds and inverse limits of set-valued functions on intervals. Discrete & Continuous Dynamical Systems, 2017, 37 (11) : 5693-5706. doi: 10.3934/dcds.2017246
[12]

Mariusz Michta. Stochastic inclusions with non-continuous set-valued operators. Conference Publications, 2009, 2009 (Special) : 548-557. doi: 10.3934/proc.2009.2009.548
[13]

Guolin Yu. Topological properties of Henig globally efficient solutions of set-valued problems. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 309-316. doi: 10.3934/naco.2014.4.309
[14]

Zengjing Chen, Yuting Lan, Gaofeng Zong. Strong law of large numbers for upper set-valued and fuzzy-set valued probability. Mathematical Control & Related Fields, 2015, 5 (3) : 435-452. doi: 10.3934/mcrf.2015.5.435
[15]

Michele Campiti. Korovkin-type approximation of set-valued and vector-valued functions. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021032
[16]

C. R. Chen, S. J. Li. Semicontinuity of the solution set map to a set-valued weak vector variational inequality. Journal of Industrial & Management Optimization, 2007, 3 (3) : 519-528. doi: 10.3934/jimo.2007.3.519
[17]

Guolin Yu. Global proper efficiency and vector optimization with cone-arcwise connected set-valued maps. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 35-44. doi: 10.3934/naco.2016.6.35
[18]

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 & Optimization, 2013, 3 (3) : 567-581. doi: 10.3934/naco.2013.3.567
[19]

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 & Heterogeneous Media, 2013, 8 (3) : 745-772. doi: 10.3934/nhm.2013.8.745
[20]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (3115)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy