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

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

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[3]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[4]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[5]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[6]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[7]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226
[8]

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390
[9]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[10]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310
[11]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404
[12]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[13]

Tong Yang, Seiji Ukai, Huijiang Zhao. Stationary solutions to the exterior problems for the Boltzmann equation, I. Existence. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 495-520. doi: 10.3934/dcds.2009.23.495
[14]

Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521
[15]

Yulia O. Belyaeva, Björn Gebhard, Alexander L. Skubachevskii. A general way to confined stationary Vlasov-Poisson plasma configurations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021004
[16]

Michiel Bertsch, Flavia Smarrazzo, Andrea Terracina, Alberto Tesei. Signed Radon measure-valued solutions of flux saturated scalar conservation laws. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3143-3169. doi: 10.3934/dcds.2020041
[17]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[18]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[19]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[20]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences