Figure 1.
h(x,ω0) and l(x,ω0) in box case
-
Previous Article
Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case
- JIMO Home
- This Issue
-
Next Article
Projection methods for solving split equilibrium problems
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 |
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.
Keywords:
Concave reformulation,
DC programming,
global optimization,
convex relaxation,
branch and bound.
Mathematics Subject Classification:
Primary: 65K05; Secondary: 90C90.
Citation:
Yanjun Wang, Kaiji Shen. A new concave reformulation and its application in solving DC programming globally under uncertain environment. Journal of Industrial and Management Optimization,
2020, 16
(5)
: 2351-2367.
doi: 10.3934/jimo.2019057
![]()
References:
| [1] |
A. Ben-Tal and A. Nemirovski,
Robust convex optimization, Mathematics of Operations Research, 23 (1998), 769-805.
doi: 10.1287/moor.23.4.769. |
| [2] |
A. Ben-Tal and A. Nemirovski,
Robust solutions of uncertain linear programs, Operations research letters, 25 (1999), 1-13.
doi: 10.1016/S0167-6377(99)00016-4. |
| [3] |
A. Ben-Tal and A. Nemirovski,
Robust solutions of linear programming problems contaminated with uncertain data, Mathematical Programming, 88 (2000), 411-424.
doi: 10.1007/PL00011380. |
| [4] |
T. P. Dinh,
The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 113 (2005), 23-46.
doi: 10.1007/s10479-004-5022-1. |
| [5] |
T. P. Dinh and A. Le Thi Hoai,
A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8 (1998), 476-505.
doi: 10.1137/S1052623494274313. |
| [6] |
A. Edward, H. F. Xu and D. L. Zhang, Confidence levels for cvar risk measures and minimax limits, Business Analytics, 2014. |
| [7] |
R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, Second edition. Springer-Verlag, Berlin, 1993.
doi: 10.1007/978-3-662-02947-3. |
| [8] |
C. D. Maranas and C. A. Floudas,
Global optimization in generalized geometric programming, Computers & Chemical Engineering, 21 (1997), 351-369.
|
| [9] |
G. C. Pflug,
Some remarks on the value-at-risk and the conditional value-at-risk, Probabilistic constrained optimization, 8 (2000), 272-281.
doi: 10.1007/978-1-4757-3150-7_15. |
| [10] |
H. Reiner and T. Nguyen V,
Robust solutions of linear programming problems contaminated with uncertain data, Journal of Optimization Theory and Applications, 103 (1999), 1-43.
|
| [11] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
|
| [12] |
R. T. Rockafellar and S. Uryasev,
Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-41.
doi: 10.21314/JOR.2000.038. |
| [13] |
R. T. Rockafellar and S. Uryasev,
Conditional value-at-risk for general loss distributions, Journal of Banking & Finance, 26 (2002), 1443-1471.
|
| [14] |
R. T. Rockafellar,
Coherent approaches to risk in optimization under uncertainty, OR Tools and Applications: Glimpses of Future Technologies, 8 (2007), 38-61.
doi: 10.1287/educ.1073.0032. |
| [15] |
P. P. Shen and C. F. Wang,
Global optimization for sum of linear ratios problem with coefficients, Applied Mathematics and Computation, 176 (2006), 219-229.
doi: 10.1016/j.amc.2005.09.047. |
| [16] |
Y. J. Wang and Y. Lan,
Global optimization for special reverse convex programming, Computers & Mathematics with Applications, 55 (2008), 1154-1163.
doi: 10.1016/j.camwa.2007.04.046. |
show all references
References:
| [1] |
A. Ben-Tal and A. Nemirovski,
Robust convex optimization, Mathematics of Operations Research, 23 (1998), 769-805.
doi: 10.1287/moor.23.4.769. |
| [2] |
A. Ben-Tal and A. Nemirovski,
Robust solutions of uncertain linear programs, Operations research letters, 25 (1999), 1-13.
doi: 10.1016/S0167-6377(99)00016-4. |
| [3] |
A. Ben-Tal and A. Nemirovski,
Robust solutions of linear programming problems contaminated with uncertain data, Mathematical Programming, 88 (2000), 411-424.
doi: 10.1007/PL00011380. |
| [4] |
T. P. Dinh,
The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 113 (2005), 23-46.
doi: 10.1007/s10479-004-5022-1. |
| [5] |
T. P. Dinh and A. Le Thi Hoai,
A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8 (1998), 476-505.
doi: 10.1137/S1052623494274313. |
| [6] |
A. Edward, H. F. Xu and D. L. Zhang, Confidence levels for cvar risk measures and minimax limits, Business Analytics, 2014. |
| [7] |
R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, Second edition. Springer-Verlag, Berlin, 1993.
doi: 10.1007/978-3-662-02947-3. |
| [8] |
C. D. Maranas and C. A. Floudas,
Global optimization in generalized geometric programming, Computers & Chemical Engineering, 21 (1997), 351-369.
|
| [9] |
G. C. Pflug,
Some remarks on the value-at-risk and the conditional value-at-risk, Probabilistic constrained optimization, 8 (2000), 272-281.
doi: 10.1007/978-1-4757-3150-7_15. |
| [10] |
H. Reiner and T. Nguyen V,
Robust solutions of linear programming problems contaminated with uncertain data, Journal of Optimization Theory and Applications, 103 (1999), 1-43.
|
| [11] |
R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.
|
| [12] |
R. T. Rockafellar and S. Uryasev,
Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-41.
doi: 10.21314/JOR.2000.038. |
| [13] |
R. T. Rockafellar and S. Uryasev,
Conditional value-at-risk for general loss distributions, Journal of Banking & Finance, 26 (2002), 1443-1471.
|
| [14] |
R. T. Rockafellar,
Coherent approaches to risk in optimization under uncertainty, OR Tools and Applications: Glimpses of Future Technologies, 8 (2007), 38-61.
doi: 10.1287/educ.1073.0032. |
| [15] |
P. P. Shen and C. F. Wang,
Global optimization for sum of linear ratios problem with coefficients, Applied Mathematics and Computation, 176 (2006), 219-229.
doi: 10.1016/j.amc.2005.09.047. |
| [16] |
Y. J. Wang and Y. Lan,
Global optimization for special reverse convex programming, Computers & Mathematics with Applications, 55 (2008), 1154-1163.
doi: 10.1016/j.camwa.2007.04.046. |
Figure 2.
h(x,ω0) and l(x,ω0) in simplex case
Figure 3.
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 |
Table 3.
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 |
Table 4.
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 and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647 |
| [2] |
Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2087-2102. doi: 10.3934/jimo.2019044 |
| [3] |
Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104 |
| [4] |
Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349 |
| [5] |
Gang Li, Xiaoqi Yang, Yuying Zhou. Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces. Journal of Industrial and 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 and 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 and 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 and 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 and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775 |
| [10] |
Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions for composite DC infinite programming problems. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022064 |
| [11] |
Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial and Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004 |
| [12] |
Shaolin Ji, Xiaomin Shi. Recursive utility optimization with concave coefficients. Mathematical Control and Related Fields, 2018, 8 (3&4) : 753-775. doi: 10.3934/mcrf.2018033 |
| [13] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
| [14] |
Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 |
| [15] |
Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial and Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817 |
| [16] |
Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial and Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733 |
| [17] |
Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9 |
| [18] |
Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091 |
| [19] |
Tomáš Roubíček. On certain convex compactifications for relaxation in evolution problems. Discrete and Continuous Dynamical Systems - S, 2011, 4 (2) : 467-482. doi: 10.3934/dcdss.2011.4.467 |
| [20] |
Jean-François Babadjian, Clément Mifsud, Nicolas Seguin. Relaxation approximation of Friedrichs' systems under convex constraints. Networks and Heterogeneous Media, 2016, 11 (2) : 223-237. doi: 10.3934/nhm.2016.11.223 |
2021 Impact Factor: 1.411
Tools
Article outline
Figures and Tables
[Back to Top]