Case Study: Projection on Polyhedron with Various Norms

Data and solution in Run-File Environment

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	100	100,000	0.10589	4.89
Dataset2	Problem statement	Data	Solution	100	500,000	0.10833	25.23
Dataset3	Problem statement	Data	Solution	100	1,000,000	0.11259	41.27
Dataset4	Problem statement	Data	Solution	100	2,000,000	0.11259	160.24
Dataset5	Problem statement	Data	Solution	100	5,000,000	0.11370	442.18
Dataset6	Problem statement	Data	Solution	100	9,000,000	0.11370	847.96

——————————————————
Alpha =0.968377, Solver Precision = 7
——————————————————
Download Problem Data

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	1000	20,000	0.00866	92.55
Dataset2	Problem statement	Data	Solution	1000	50,000	0.00867	273.03
Dataset3	Problem statement	Data	Solution	1000	100,000	0.00877	408.29
Dataset4	Problem statement	Data	Solution	1000	200,000	0.00877	1363.49
Dataset5	Problem statement	Data	Solution	1000	500,000	0.00877	2617.07
Dataset6	Problem statement	Data	Solution	1000	900,000	0.00877	4654.56

NOTE: Problem statements can be simplified using MultiConstraint.

PROBLEM2: problem_mix_L1_L_Infinity
minimizing [(1-lambda)*polynom_abs+ lambda*max_comp_abs]
subject to
Ax ≤b (multiple linear constraints representing convex polyhedron set)
Box constraints (lower bounds on variables)
——————————————————————–——————
polynom_abs = polynomial absolute function
max_comp_abs=maximum component absolute function
Box constraints = constraints on individual decision variables
——————————————————————–——————
——————————————————
Lambda =0.90909, Solver Precision = 7
——————————————————

Download Problem Data

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	100	100,000	1.01459	6.62
Dataset2	Problem statement	Data	Solution	100	500,000	1.05439	27.53
Dataset3	Problem statement	Data	Solution	100	1,000,000	1.06657	47.81
Dataset4	Problem statement	Data	Solution	100	2,000,000	1.07531	168.45
Dataset5	Problem statement	Data	Solution	100	5,000,000	1.09822	468.64
Dataset6	Problem statement	Data	Solution	100	9,000,000	1.10039	851.35

NOTE: Problem statements can be simplified using MultiConstraint.

——————————————————
Lambda =0.95744, Solver Precision = 7
——————————————————
Download Problem Data

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	500	20,000	0.38609	35.07
Dataset2	Problem statement	Data	Solution	500	50,000	0.38966	70.52
Dataset3	Problem statement	Data	Solution	500	100,000	0.39170	128.08
Dataset4	Problem statement	Data	Solution	500	500,000	0.39654	744.98
Dataset5	Problem statement	Data	Solution	500	1,000,000	0.39868	1571.72
Dataset6	Problem statement	Data	Solution	500	1,500,000	0.39956	2574.43
Dataset7	Problem statement	Data	Solution	500	1,800,000	0.40005	2909.3

NOTE: Problem statements can be simplified using MultiConstraint.

——————————————————
Lambda =0.96923, Solver Precision = 7
——————————————————

Download Problem Data

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	1000	20,000	0.26782	161.54
Dataset2	Problem statement	Data	Solution	1000	50,000	0.26938	318.55
Dataset3	Problem statement	Data	Solution	1000	100,000	0.27064	475.09
Dataset4	Problem statement	Data	Solution	1000	200,000	0.27165	1209.68
Dataset5	Problem statement	Data	Solution	1000	500,000	0.27194	3165.31
Dataset6	Problem statement	Data	Solution	1000	900,000	0.27194	5612.34

NOTE: Problem statements can be simplified using MultiConstraint.

PROBLEM3: problem_quadratic
minimizing quadratic (square of L_2 norm)
subject to
Ax ≤b (multiple linear constraints representing convex polyhedron set)
Box constraints (lower bounds on variables)
——————————————————————–——————
quadratic = quadratic function
Box constraints = constraints on individual decision variables
——————————————————————–——————

——————————
Solver Precision = 7
——————————

Download Problem Data

Problem Datasets				# of Variables	# of Rows	Objective Value	Solving Time, PC 2.83GHz (sec)
Dataset1	Problem statement	Data	Solution	100	100,000	1.03483	2.47
Dataset2	Problem statement	Data	Solution	100	500,000	1.11188	15.83
Dataset3	Problem statement	Data	Solution	100	1,000,000	1.14674	30.70
Dataset4	Problem statement	Data	Solution	100	2,000,000	1.15551	134.57
Dataset5	Problem statement	Data	Solution	100	5,000,000	1.20912	324.14
Dataset6	Problem statement	Data	Solution	100	9,000,000	1.21178	914.29
Dataset7	Problem statement	Data	Solution	500	20,000	0.15307	4.30
Dataset8	Problem statement	Data	Solution	500	50,000	0.15612	21.83
Dataset9	Problem statement	Data	Solution	500	100,000	0.15752	25.26
Dataset10	Problem statement	Data	Solution	500	500,000	0.16135	115.8
Dataset11	Problem statement	Data	Solution	500	1,000,000	0.16346	291.92
Dataset12	Problem statement	Data	Solution	500	1,500,000	0.16393	335.87
Dataset13	Problem statement	Data	Solution	500	1,800,000	0.16425	388.55
Dataset14	Problem statement	Data	Solution	1000	20,000	0.05064	0.63
Dataset15	Problem statement	Data	Solution	1000	50,000	0.05064	0.94
Dataset16	Problem statement	Data	Solution	1000	100,000	0.05064	1.50
Dataset17	Problem statement	Data	Solution	1000	200,000	0.05064	2.57
Dataset18	Problem statement	Data	Solution	1000	500,000	0.05064	5.87
Dataset19	Problem statement	Data	Solution	1000	900,000	0.05064	162.24

CASE STUDY SUMMARY

This case study considers the projection problems with various norms on a polyhedron set given by a system of linear inequalities. In particular, we consider the Scaled CVaR Absolute Norm introduced in Pavlikov and Uryasev (2013). The Scaled CVaR Absolute Norm in is a family of norms based on CVaR concept. This family has a control parameter <imgsrc=”http: 129.49.108.249=”” wp-content=”” uploads=”” 2013=”” 05=”” cs_projection_cvar_norm_cvar_comp_abs_clip_image009.gif”=”” alt=”” width=”15″ height=”14″>, so-called confidence level, controlling conservativeness of the norm. CVaR term and the optimization approach for CVaR was introduced in Rockafellar and Uryasev (2000). For the most conservative case, , the Scaled CVaR Absolute Norm equals the maximum absolute value of components of the vector. The least conservative norm, with , averages absolute values of all components. In the intermediate case, for , when is a multiple of , the norm of a vector is defined as the average of largest absolute values of components. If is not a multiple of , then Scaled CVaR Absolute Norm is defined as a convex combination of two values of the norm with nearest to upper and lower multiples of confidence levels. Computational experiments for and spaces are presented. Several polyhedron sets with different number of hyperplanes were generated, such that . The projection of 0 on is solved with CVaR Absolute Norm, norm, and the weighted average of and norms. Problem 1 solves the projection problem with CVaR Absolute Norm with confidence level for different dimensions and different polyhedrons.
Then, Problem 1 solves the projection problems with CVaR Absolute Norm for dimensions = 100, 500, 1000,and confidence levels, , , , accordingly. The confidence levels, in this case, were selected with the formula , which corresponds to the best approximation of norm by the CVaR Absolute Norm, see Gotoh and Uryasev (2013).
Problem 2 solves projection problems with weighted average of and norms for dimensions = 100, 500, 1000. Weighting is done with the parameter as follows: The weighting parameter is a function of dimension to make the best approximation of the norm by the weighted average of the and norms, i.e., , , , see Gotoh and Uryasev (2013).
Problem 3 solves projection problems with square of norm for dimensions = 100, 500, 1000.</imgsrc=”http:>

References
• Pavlikov K, and S. Uryasev (2013): CVaR Absolute Norm and Applications in Optimization.
Research Report # 2013-1.
• Rockafellar, R.T. and S. Uryasev (2013): The Fundamental Risk Quadrangle in Risk
Management, Optimization, and Statistical Estimation. Surveys in Operations Research and
Management Science, 18 (to appear).
• Rockafellar, R. T. and Uryasev, S. (2000), “Optimization of conditional value-at-risk”,
Journal of Risk , Vol. 2, pp. 21–41.
• Gotoh, J. and S. Uryasev (2013): Approximation of Euclidean norm by LP-representable
norms and applications. Draft paper.