# American Institute of Mathematical Sciences

September  2020, 16(5): 2351-2367. doi: 10.3934/jimo.2019057

## A new concave reformulation and its application in solving DC programming globally under uncertain environment

 School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China

* Corresponding author: Yanjun Wang

Received  July 2018 Revised  January 2019 Published  September 2020 Early access  May 2019

Fund Project: We gratefully acknowledge the valuable cooperation of Prof. R. Tyrrell Rockafellar(University of Washington). This research was supported by NSFC (11271243)

In this paper, a new concave reformulation is proposed on a convex hull of some given points. Based on its properties, we attempt to solve DC Programming problems globally under uncertain environment by using Robust optimization method and CVaR method. A global optimization algorithm is developed for the Robust counterpart and CVaR model with two kinds of special convex hulls: simplex set and box set. The global solution is obtained by solving a sequence of convex relaxation programming on the original constraint sets or divided subsets with branch and bound method. Finally, numerical experiments are given for DC programs under uncertain environment with two kinds of constraints: simplex and box sets. Simulation results show the feasibility and efficiency of the proposed global optimization algorithm.

Citation: Yanjun Wang, Kaiji Shen. A new concave reformulation and its application in solving DC programming globally under uncertain environment. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2351-2367. doi: 10.3934/jimo.2019057
##### References:

show all references

##### References:
h(x,ω0) and l(x,ω0) in box case
h(x,ω0) and l(x,ω0) in simplex case
Optimal value comparison of Robust Model and CVaR model
 α CPU(s) Step Nodes Opt Solution Opt Value Opt* 0.70 356.11 87 69 (0.0000, 1.1250, 1.8750)T -2.2690 -2.2689 0.75 956.11 163 101 (0.0000, 1.0547, 1.5703)T -2.1214 -2.1214 0.80 847.73 163 106 (0.0000, 0.7969, 1.1191)T -1.9628 -1.9628 0.85 516.92 132 106 (0.0000, 0.6211, 0.8789)T -1.7508 -1.7508 0.90 518.31 122 107 (0.0000, 0.4569, 0.6797)T -1.5661 -1.5663 0.95 321.43 78 68 (0.0000, 0.3580, 0.5326)T -1.4453 -1.4452 0.97 143.17 31 27 (0.0000, 0.3387, 0.5038)T -1.4228 -1.4228 0.98 160.39 30 24 (0.0104, 0.3437, 0.5156)T -1.4222 -1.4222 0.99 167.81 31 26 (0.0023, 0.3281, 0.5000)T -1.4221 -1.4221 Robust 218.18 52 51 (0.0080, 0.3515, 0.5002)T -1.4221 -1.4221
 α CPU(s) Step Nodes Opt Solution Opt Value Opt* 0.70 356.11 87 69 (0.0000, 1.1250, 1.8750)T -2.2690 -2.2689 0.75 956.11 163 101 (0.0000, 1.0547, 1.5703)T -2.1214 -2.1214 0.80 847.73 163 106 (0.0000, 0.7969, 1.1191)T -1.9628 -1.9628 0.85 516.92 132 106 (0.0000, 0.6211, 0.8789)T -1.7508 -1.7508 0.90 518.31 122 107 (0.0000, 0.4569, 0.6797)T -1.5661 -1.5663 0.95 321.43 78 68 (0.0000, 0.3580, 0.5326)T -1.4453 -1.4452 0.97 143.17 31 27 (0.0000, 0.3387, 0.5038)T -1.4228 -1.4228 0.98 160.39 30 24 (0.0104, 0.3437, 0.5156)T -1.4222 -1.4222 0.99 167.81 31 26 (0.0023, 0.3281, 0.5000)T -1.4221 -1.4221 Robust 218.18 52 51 (0.0080, 0.3515, 0.5002)T -1.4221 -1.4221
 α CPU(s) Step Nodes Opt Solution Opt Value Opt* 0.70 264.90 24 22 (0.0000, 0.6719, 0.9844)T -2.2410 -2.2410 0.75 105.19 25 29 (0.0000, 0.6641, 0.9844)T -2.1214 -2.1215 0.80 217.65 24 19 (0.0000, 0.7187, 0.9844)T -1.9520 -1.9520 0.85 516.92 55 40 (0.0000, 0.6250, 0.8750)T -1.7506 -1.7505 0.90 350.26 39 34 (0.0000, 0.4531, 0.6741)T -1.5661 -1.5661 0.95 208.85 38 32 (0.0000, 0.3580, 0.5326)T -1.4452 -1.4452 0.97 143.17 31 27 (0.0000, 0.3437, 0.5156)T -1.4228 -1.4228 0.98 167.81 30 26 (0.0104, 0.3437, 0.5156)T -1.4222 -1.4222 0.99 160.39 31 24 (0.0023, 0.3281, 0.5000)T -1.4221 -1.4221 Robust 216.98 35 27 (0.0080, 0.3515, 0.5002)T -1.4221 -1.4221
 α CPU(s) Step Nodes Opt Solution Opt Value Opt* 0.70 264.90 24 22 (0.0000, 0.6719, 0.9844)T -2.2410 -2.2410 0.75 105.19 25 29 (0.0000, 0.6641, 0.9844)T -2.1214 -2.1215 0.80 217.65 24 19 (0.0000, 0.7187, 0.9844)T -1.9520 -1.9520 0.85 516.92 55 40 (0.0000, 0.6250, 0.8750)T -1.7506 -1.7505 0.90 350.26 39 34 (0.0000, 0.4531, 0.6741)T -1.5661 -1.5661 0.95 208.85 38 32 (0.0000, 0.3580, 0.5326)T -1.4452 -1.4452 0.97 143.17 31 27 (0.0000, 0.3437, 0.5156)T -1.4228 -1.4228 0.98 167.81 30 26 (0.0104, 0.3437, 0.5156)T -1.4222 -1.4222 0.99 160.39 31 24 (0.0023, 0.3281, 0.5000)T -1.4221 -1.4221 Robust 216.98 35 27 (0.0080, 0.3515, 0.5002)T -1.4221 -1.4221
Simplex feasible
 CPU Time(s) Nodes SEED RDC 91 11 1 Floudas 227 42 1 RDC 100 15 2 Floudas 204 40 2 RDC 120 25 3 Floudas 280 75 3
 CPU Time(s) Nodes SEED RDC 91 11 1 Floudas 227 42 1 RDC 100 15 2 Floudas 204 40 2 RDC 120 25 3 Floudas 280 75 3
Box feasible
 CPU Time(s) Nodes SEED RDC 88 8 1 Floudas 220 40 1 RDC 105 12 2 Floudas 207 36 2 RDC 117 20 3 Floudas 281 68 3
 CPU Time(s) Nodes SEED RDC 88 8 1 Floudas 220 40 1 RDC 105 12 2 Floudas 207 36 2 RDC 117 20 3 Floudas 281 68 3
 [1] Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 [2] 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 [3] Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 [4] Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 [5] Gang Li, Xiaoqi Yang, Yuying Zhou. Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces. Journal of Industrial & Management Optimization, 2013, 9 (3) : 671-687. doi: 10.3934/jimo.2013.9.671 [6] Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499 [7] Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767 [8] Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070 [9] Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 [10] Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004 [11] Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 [12] Shaolin Ji, Xiaomin Shi. Recursive utility optimization with concave coefficients. Mathematical Control & Related Fields, 2018, 8 (3&4) : 753-775. doi: 10.3934/mcrf.2018033 [13] Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817 [14] Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 [15] 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 [16] Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9 [17] Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167 [18] Tomáš Roubíček. On certain convex compactifications for relaxation in evolution problems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (2) : 467-482. doi: 10.3934/dcdss.2011.4.467 [19] Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks & Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223 [20] Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091

2020 Impact Factor: 1.801