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

Yanjun Wang; Kaiji Shen

doi:10.3934/jimo.2019057

Article Contents

2020, Volume 16, Issue 5: 2351-2367. Doi: 10.3934/jimo.2019057

This issue Previous Article Projection methods for solving split equilibrium problems Next Article Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case

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
^* Corresponding author: Yanjun Wang

Received: July 2018

Revised: January 2019

Early access: May 2019

Published: August 2020

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

Abstract Full Text(HTML) Figure(3) / Table(4) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 65K05; Secondary: 90C90.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.