Parameterizing the uncertainty set in robust optimization

In this quick post, we look at the problem of having parameterized uncertainty sets, and how these can be dealt with by reparameterizing the uncertainty.

The type of models YALMIP works with in robust optimization is assumed to of the form

However, in some cases it might be that the uncertainty set is parameterized, and the parameters defining the geometry are seen as decision variables. A typical case would be that the size of the set is parameter, and we wish to compute a robust solution which is some compromise between the level of robustness and conservativity. YALMIP does not support this, as YALMIP cannot distinguish between normal decision variables, and parameters in uncertainty sets. If a constraint is defined using both uncertain variables and variables which are not declared as uncertain, it will be considered to be an uncertain constraint, and not a definition of an uncertainty set.

Reparameterizing the uncertainty

As an example, let us consider the problem of computing the Chebychev L1-ball of a polytope, i.e., the largest possible romb that can be placed inside a given polytope. This can be formulated as the robust optimization problem

Here, \(z\) is the uncertain variable, and the center of the ball \(z_c\) and the size of the ball \(r\) are parameters in the uncertainty description.

The incorrect YALMIP model would be

A = randn(10,2);b = rand(10,1)*10;

z = sdpvar(2,1);
zc = sdpvar(2,1);
r = sdpvar(1);

UncertainConstraint = [A*z <= b];
UncertaintyModel = [norm(z-zc,1) <= r];
optimize([UncertainConstraint,UncertaintyModel,uncertain(z)],-r)

This model will fail, since YALMIP cannot find the intended uncertainty desciption here, as there is no constraint which only involves uncertain variables. Adding \(r\) and \(z_c\) to the list of uncertain variables does not make sense either, as they are not uncertain, but simply not decided yet.

The way to model this setup is to think of a normalized uncertainty, and then write the uncertainty in terms of this normalized uncertainty. In our case, we can see the uncertainty as a scaled and translated uncertainty.

w = sdpvar(2,1);
zc = sdpvar(2,1);
r = sdpvar(1);

z = r*w + zc;
UncertainConstraint = [A*z <= b];
UncertaintyModel = [norm(w,1) <= 1];
optimize([UncertainConstraint,UncertaintyModel,uncertain(w)],-r)

This is a very simple model, and YALMIP derives the robust counterpart and computes the largest inscribed L1-ball.

plot(A*w <= b,w,'red');hold on;
plot(norm(w - value(zc),1)<= value(r),w,'yellow')