Navigator

Robust optimizationSupported ScenariosSimple linear programming examplesconic uncertainty modelsadvanced problemsUncertain semidefinite and second order conefeaturesReferences

Robust optimization

robust optimization guide可以见这系列博客。一般情况下，robust optimization处理两组变量，包括决策变量($\mathbf{x}$)和不确定变量($\mathbf{w}$)，deterministic worst case cost的目标函数追求最小化并且约束条件为鲁棒可行(robustly feasible)，不确定参数可以从一个定义的不确定集合中任意取值 $$\begin{gathered} \underset{x}{\min }\underset{w}{\max }f(x,w) \\ s.t.g(x,w)\le 0\forall w:h(w)\le 0 \end{gathered}$$ YALMIP也无法求解任意的不确定问题，而且这类问题一般是intractable problem，但是可以求解特定类型的robust optimization problem.

Supported Scenarios

在robust optimization中，不同的情况称为场景(scenarios)，对应的robust counterpart称为filters. 主要有三种场景

元素级别的约束$b^{T}x+(A^{T}x+c{)}^{T}w\le 0$，可以使用对偶理论或者迭代法（需要安装MPT）消除不确定性.当不确定约束在一个正则球(norm-ball, p=1,2,∞)，可以在worst case的情况下对目标函数的robust counterpart取极值消除不确定性.conic constraints使用迭代法消除

Simple linear programming examples

对于box uncertainty的建模方式可以使用worst case直接建模

for simple box uncertainty as in this case, YALMIP explictly performs the maximization, leading to a more efficient worst-case model.

sdpvar x w F = [x+w<=1]; W = [-0.5<=w<=0.5, uncertain(w)]; obj = -x; % max x sol = optimize([F W], obj);

另一种对不确定性建模的方式可以使用convex hull，引入辅助变量$t_1$和$t_2$表示不确定变量

%% convex hull sdpvar x w t1 t2 F = [x+w<=1]; W = [w==t1*(-0.5)+t2*0.5, t1+t2==1, 0<=[t1 t2]<=1]; W = [W, uncertain([t1 t2 w])]; obj=-x; sol = optimize([F, W], obj);

设置使用duality filter

%% duality filter sdpvar x w t1 t2 F = [x+w <= 1]; W = [w == t1*(-0.5) + t2*0.5, t1+t2 == 1, 0 <= [t1 t2] <= 1]; W = [W,uncertain([t1 t2 w])]; objective = -x; sol = optimize(F + W,objective,sdpsettings('robust.lplp','duality'));

conic uncertainty models

The uncertainty description has to be conic representable (which in YALMIP means that it only uses linear conic constraints, or nonlinear operators that can be represented using linear conic constraint).

考虑如下conic optimization问题，容易计算出$x_{\max }=0$

%% sdpvar x w(2, 1) F = [x+sum(w)<=1]; W = [norm(w)<=1/sqrt(2), uncertain(w)]; obj = -x; sol = optimize([F W], obj)

等效建立模型如下

%% sdpvar x w(2, 1) F = [x+sum(w)<=1]; W = [w'*w<=1/2, uncertain(w)]; obj = -x; sol = optimize([F W], obj)

advanced problems

使用强对偶定理或者迭代法求解robust optimization，这表示问题中的决策变量可存在整数或者逻辑约束

The robustification is done using strong duality arguments in the uncertainty space, or by simple enumeration. This means that there is no problem with integer and logic constraint in the decision variables.

%% sdpvar x w F = [x+w<=1, ismember(x, [0.2 0.4])]; % 加入逻辑约束 W = [-0.5<=w<=0.5, uncertain(w)]; obj=-x; sol = optimize([F W], obj);

求解关于sum-of-squares的不确定问题（使用非线性算子），希望找到一个整数值$a$，其取值范围在$[3,5]$，使得多项式$a{x}^4+y^4+uxy+1\ge t$在任意$-1\le u\le 1$成立.

%% sdpvar x y t u a p = a*x^4+y^4+u*x*y+1; F = [uncertain(u), -1<=u<=1]; F = [F, ismember(a, [3 4 5])]; F = [F, sos(p-t)]; solvesos(F, -t) % lower bound by maximizing t

其中关于sos的定义如下

sos: Declare sum-of-squares structure F = sos(p) input: p: SDPVAR object output: F: Constraint Example: Typical usage is F = sos(p) An experimental feature is to search for low rank decompositions. To search for a decomposition using at most 3 terms, use a second argument F = sos(p,3) Note that his feature requires the solver LMIRANK.

Uncertain semidefinite and second order cone

本例中通过在robust counterpart部分的顶点上迭代，每次求解一个新的SOCP或者SDP问题

YALMIP can robustify SOCP and SDP constraints with affine dependence on the uncertainty, under the restriction that the uncertainty is constrained to a polytopic set.

%% t = sdpvar(1,1); P = sdpvar(2,2); A = [-1 t;0.2 -1] F = [A'*P + P*A <= -eye(2), 1 <= t <= 2, uncertain(t)]; sol = optimize(F,trace(P))

features

有时只需要推导出robust counterpart但不需要求解，可以通过robustify指令完成

[Frobust,robust_objective] = robustify(F + W,objective);

求解通过如下指令完成

sol = optimize(Frobust,robust_objective);

References

Robust optimization Automatic_robust_convex_programming