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

Jian  Gu; Xiantao Xiao; Liwei Zhang

doi:10.3934/jimo.2016.12.1349

Article Contents

2016, Volume 12, Issue 4: 1349-1366. Doi: 10.3934/jimo.2016.12.1349

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

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

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

Received: August 31, 2014

Revised: April 30, 2015

Published: September 2016

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.