robustlp.gms : Robust linear programming as an SOCP

Description

Consider a linear optimization problem of the form
min_x c^Tx s.t. a_i^Tx <= b_i, i=1,..,m.

In practice, the coefficient vectors a_i may not be known perfectly,
as they are subject to noise. Assume that we only know that a_i in E_i,
where E_i are given ellipsoids. In robust optimization, we seek to minimize
the original objective, but we insist that each constraint be satisfied,
irrespective of the choice of the corresponding vector a_i in E_i.
We obtain the second-order cone optimization problem
min_x c^Tx s.t. a'_i^Tx + ||R_i^Tx|| <= b_i, i=1,..,m,
where E_i = { a'_i + R_iu | ||u|| <= 1}. In the above, we observe that
the feasible set is smaller than the original one, due to the terms involving
the l_2-norms.

The figure above illustrates the kind of feasible set one obtains in a particular
instance of the above problem, with spherical uncertainties (that is, all the
ellipsoids are spheres, R_i = rho I for some rho >0). We observe that the robust
feasible set is indeed contained in the original polyhedron.

In this particular example we allow coefficients A(i,*) to vary in an ellipsoid.
The robust LP is reformulated as a SOCP.

Contributed by Michael Ferris, University of Wisconsin, Madison


Reference

  • Lobo, M S, Vandenberghe, L, Boyd, S, and Lebret, H, Applications of Second Order Cone Programming. Linear Algebra and its Applications 284, 1-3 (1998), 193-228.

Small Model of Type : QCP


Category : GAMS Model library


Main file : robustlp.gms

$Title Robust linear programming as an SOCP (ROBUSTLP,SEQ=416)

$ontext
Consider a linear optimization problem of the form
min_x c^Tx s.t. a_i^Tx <= b_i, i=1,..,m.

In practice, the coefficient vectors a_i may not be known perfectly, 
as they are subject to noise. Assume that we only know that a_i in E_i, 
where E_i are given ellipsoids. In robust optimization, we seek to minimize 
the original objective, but we insist that each constraint be satisfied, 
irrespective of the choice of the corresponding vector a_i in E_i. 
We obtain the second-order cone optimization problem
min_x c^Tx s.t. a'_i^Tx + ||R_i^Tx|| <= b_i, i=1,..,m,
where E_i = { a'_i + R_iu | ||u|| <= 1}. In the above, we observe that 
the feasible set is smaller than the original one, due to the terms involving 
the l_2-norms.

The figure above illustrates the kind of feasible set one obtains in a particular 
instance of the above problem, with spherical uncertainties (that is, all the 
ellipsoids are spheres, R_i = rho I for some rho >0). We observe that the robust 
feasible set is indeed contained in the original polyhedron.

In this particular example we allow coefficients A(i,*) to vary in an ellipsoid.
The robust LP is reformulated as a SOCP.

Contributed by Michael Ferris, University of Wisconsin, Madison


Lobo, M S, Vandenberghe, L, Boyd, S, and Lebret, H, Applications of
Second Order Cone Programming. Linear Algebra and its Applications,
Special Issue on Linear Algebra in Control, Signals and Image
Processing. 284 (November, 1998).

$offtext

$if not set mu $set mu 1.0e-2

set i /1*7/;
set j /1*4/;

parameter b(i), c(j), A(i,j);

b(i) = 1;
c(j) = -1;

option seed = 0;
A(i,j) = uniform(0,1);

variables obj, x(j);
equations defobj, cons(i);

defobj..
  obj =e= sum(j, c(j)*x(j));

cons(i)..
  sum(j, A(i,j)*x(j)) =l= b(i);

model lpmod /defobj, cons/;

solve lpmod using lp min obj;
parameter results(*,*);
results('lp',j) = x.l(j);
results('lp','obj') = obj.l;

scalar mu / %mu% /;
positive variables lambda(j), gamma(j);
equations lpcons(i), defdual(j);

* A(i,*) \in A(i,*) + [-mu(i) 1, mu(i) 1] (infty norm ball)
* constraint is mu(i) * norm(x)_1  + Ax <= b  (just use one mu here)
* just implement one norm (dual of inf norm) using lambda and gamma
lpcons(i)..
  mu*sum(j, lambda(j) + gamma(j)) + sum(j, A(i,j)*x(j)) =l= b(i);

defdual(j)..
  lambda(j) - gamma(j) =e= x(j);

model lproblp /defobj,lpcons,defdual/;
solve lproblp using lp min obj;
results('roblp',j) = x.l(j);
results('roblp','obj') = obj.l;

alias(j,k);
parameter P(i,j,k);
P(i,j,j) = %mu%;

variables y(i), v(i,k);
equations defrhs(i), defv(i,k), socpcons(i);

defrhs(i)..
  y(i) =e= b(i) - sum(j, A(i,j)*x(j));

defv(i,k)..
  v(i,k) =e= sum(j, P(i,j,k)*x(j));

equations socpqcpcons(i);
socpqcpcons(i)..
  sqr(y(i)) =g= sum(k, sqr(v(i,k)));

model roblpqcp /defobj, socpqcpcons, defrhs, defv/;
y.lo(i) = 0;
option qcp = cplexd;
solve roblpqcp using qcp min obj;
results('qcp',j) = x.l(j);
results('qcp','obj') = obj.l;

display results;