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

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

[5]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, {Springer, (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. doi: 10.1016/j.na.2012.01.023. Google Scholar

[7]

M. Fazel, Matrix Rank Minimization with Applications,, PhD thesis, (2002). Google Scholar

[8]

Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach,, PhD thesis, (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. 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. 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. 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. 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. doi: 10.1137/050642691. Google Scholar

[14]

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

[15]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs,, SIAM J. Optim., 17 (2006), 969. 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. doi: 10.1137/070697835. Google Scholar

[17]

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

[18]

W. Schirotzek, Nonsmooth Analysis,, Springer, (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. 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, (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. 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. 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. 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. 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. 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. 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. Google Scholar

[5]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, {Springer, (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. doi: 10.1016/j.na.2012.01.023. Google Scholar

[7]

M. Fazel, Matrix Rank Minimization with Applications,, PhD thesis, (2002). Google Scholar

[8]

Y. Gao, Structured Low Rank Matrix Optimization Problems: A Penalty Approach,, PhD thesis, (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. 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. 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. 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. 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. doi: 10.1137/050642691. Google Scholar

[14]

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

[15]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs,, SIAM J. Optim., 17 (2006), 969. 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. doi: 10.1137/070697835. Google Scholar

[17]

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

[18]

W. Schirotzek, Nonsmooth Analysis,, Springer, (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. 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, (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. 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. 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. 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]

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

[8]

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

[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 - A, 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]

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

[16]

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

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

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

[19]

Shay Kels, Nira Dyn. Bernstein-type approximation of set-valued functions in the symmetric difference metric. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 1041-1060. doi: 10.3934/dcds.2014.34.1041

[20]

Ying Gao, Xinmin Yang, Jin Yang, Hong Yan. Scalarizations and Lagrange multipliers for approximate solutions in the vector optimization problems with set-valued maps. Journal of Industrial & Management Optimization, 2015, 11 (2) : 673-683. doi: 10.3934/jimo.2015.11.673

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]