American Institute of Mathematical Sciences

Advanced
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

Yanjun Wang , and  Kaiji Shen

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

* Corresponding author: Yanjun Wang

Received  July 2018 Revised  January 2019 Published  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.

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

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

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

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

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

[6]

A. Edward, H. F. Xu and D. L. Zhang, Confidence levels for cvar risk measures and minimax limits, Business Analytics, 2014. Google Scholar

[7]

R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, Second edition. Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02947-3.  Google Scholar

[8]

C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming, Computers & Chemical Engineering, 21 (1997), 351-369.   Google Scholar

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

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

[11] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.   Google Scholar
[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.  Google Scholar

[13]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, Journal of Banking & Finance, 26 (2002), 1443-1471.   Google Scholar

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

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

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

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

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

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

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

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

[6]

A. Edward, H. F. Xu and D. L. Zhang, Confidence levels for cvar risk measures and minimax limits, Business Analytics, 2014. Google Scholar

[7]

R. Horst and H. Tuy, Global Optimization: Deterministic Approaches, Second edition. Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02947-3.  Google Scholar

[8]

C. D. Maranas and C. A. Floudas, Global optimization in generalized geometric programming, Computers & Chemical Engineering, 21 (1997), 351-369.   Google Scholar

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

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

[11] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970.   Google Scholar
[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.  Google Scholar

[13]

R. T. Rockafellar and S. Uryasev, Conditional value-at-risk for general loss distributions, Journal of Banking & Finance, 26 (2002), 1443-1471.   Google Scholar

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

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

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

Figure 1.  h(x,ω0) and l(x,ω0) in box case
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  h(x,ω0) and l(x,ω0) in simplex case
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Optimal value comparison of Robust Model and CVaR model
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.   
α 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
Table Options

Download as excel

α 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
Table 2.   
α 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 Options

Download as excel

α 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
Table Options

Download as excel

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
Table Options

Download as excel

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]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]

Bingru Zhang, Chuanye Gu, Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs†. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061
[4]

Mengyao Chen, Qi Li, Shuangjie Peng. Bound states for fractional Schrödinger-Poisson system with critical exponent. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021038
[5]

Claudianor O. Alves, Giovany M. Figueiredo, Riccardo Molle. Multiple positive bound state solutions for a critical Choquard equation. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021061
[6]

Alexander Tolstonogov. BV solutions of a convex sweeping process with a composed perturbation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021012
[7]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[8]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067
[9]

Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068
[10]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[11]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063
[12]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[13]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032
[14]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055
[15]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[16]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[17]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391
[18]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053
[19]

Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1809-1823. doi: 10.3934/jimo.2020047
[20]

Kai Cai, Guangyue Han. An optimization approach to the Langberg-Médard multiple unicast conjecture. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021001

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (115)
  • HTML views (555)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences