1 Introduction
1.1 Contributions
-
We consider the new class of distributionally robust optimization problems in the form (1.1), which are given by polynomial functions and moment ambiguity sets. The Moment-SOS relaxation method is proposed to solve them globally. It has more attractive properties than prior existing methods. Numerical examples are given to show the efficiency.
-
When the objective f(x) and the constraining set X are given by SOS-convex polynomials, we prove the DROM is equivalent to a linear conic optimization problem.
-
Under some general assumptions, we prove the asymptotic and finite convergence of the proposed method. There is little prior work on finite convergence for solving DROM. In particular, when the random variable \(\xi \) is univariate, we show that the lowest order Moment-SOS relaxation is sufficient for solving (1.8) exactly.
-
We also show how to obtain the measure \(\mu ^*\) that achieves the worst case expectation constraint.
2 Preliminaries
2.1 Notation
2.2 SOS and Nonnegative Polynomials
2.3 Truncated Moment Problems
3 Moment Optimization Reformulation
4 The Moment-SOS Relaxation Method
4.1 An Algorithm for Solving the DROM
GloptiPoly3
[20], YALMIP
[30] and SeDuMi
[48]. In Step 0, we assume \(\overline{ { cone}({Y}) }\) can be expressed by linear, second order or semidefinite cones. See Sect. 5 for more details. In Step 1, if (4.1) is unbounded from below, then (3.11) must also be unbounded from below. If (4.2) is unbounded from above, then (3.14) may be unbounded from above (and hence (3.11) is infeasible) , or it may be because the relaxation order k is not large enough. We refer to [38] for how to verify unboundedness of (3.14). Generally, one can assume (4.1) and (4.2) have optimizers. In Step 3, the finitely atomic measure \(\mu \) can be obtained by computing Schur decompositions and eigenvalues. We refer to [19] for the method. It is also implemented in the software GloptiPoly3
. Note that the measure \(\mu \) associated with \(y^*\) may not belong to \({\mathcal {M}}\). This is because (4.2) has the conic constraint \(y\in \overline{cone(Y)}\) instead of \(y\in Y\). Once the atomic measure \(\mu \) is extracted, we can choose a scalar \(\beta >0\) such that \(\beta \mu \in {\mathcal {M}}\).4.2 Convergence of Algorithm 4.4
5 Numerical Experiments
GloptiPoly3
[20], YALMIP
[30] and SeDuMi
[48] are used for the implementation. For neatness of presentation, we only display four decimal digits.-
If \(Y=\{y : T y + u \ge 0\}\) is a nonempty polyhedron, given by some matrix T and vector u, thenIt is also a polyhedron and is closed.$$\begin{aligned} \overline{ cone(Y)} \, = \, \{y: Ty+s u \ge 0,\, s \in {\mathbb {R}}_+ \}. \end{aligned}$$(5.1)
-
Consider that \(Y =\{y : {\mathcal {A}}(y) + B \succeq 0 \}\) is given by a linear matrix inequality, for a homogeneous linear symmetric matrix valued function \({\mathcal {A}}\) and a symmetric matrix B. If Y is nonempty and bounded, thenWhen Y is unbounded, the \({ cone}({Y})\) may not be closed and its closure \(\overline{ { cone}({Y}) }\) may be tricky. We refer to the work [33] for such cases. When Y is given by second order conic conditions, we can do similar things for obtaining \(\overline{ { cone}({Y}) }\).$$\begin{aligned} \overline{ cone(Y) } \, = \, \left\{ y : {\mathcal {A}}(y) + s B \succeq 0,\, s \in {\mathbb {R}}_+ \right\} . \end{aligned}$$(5.2)
MATLAB
commands makedist
and truncate
to generate samples of \(\xi \) with the sample size \(N\in \{50,100,200\}\), and then construct Y as in (5.11) with \(s = 5\) and \(d = n = 3\). Case |
\(F^*\)
|
\(x^*\)
|
\(\theta \)
|
\(u_1,\, u_2,\,u_3\)
|
---|---|---|---|---|
(i) |
\(-0.9711\)
|
\(\left[ \begin{array}{ccc} 0.0159\\ 0.2824\\ 0.7017\end{array}\right] \)
|
\(\left[ \begin{array}{ccc}0.0746\\ 0.7297\\ 0.1957\end{array}\right] \)
|
\(\left[ \begin{array}{ccc} 0.0000\\ 0.4555\\ 0.1266\end{array}\right] ,\left[ \begin{array}{ccc} 0.5675\\ 0.0000\\ 0.1074\end{array}\right] , \left[ \begin{array}{ccc} 0.8492\\ 1.0000\\ 0.3832\end{array}\right] \)
|
(ii) |
\(-0.9743\)
|
\(\left[ \begin{array}{ccc} 0.0163\\ 0.2711\\ 0.7125\end{array}\right] \)
|
\(\left[ \begin{array}{ccc} 0.0749\\ 0.7320\\ 0.1931\end{array}\right] \)
|
\(\left[ \begin{array}{ccc} 0.0000\\ 0.5170\\ 0.1563\end{array}\right] , \left[ \begin{array}{ccc}0.5898\\ 0.0000\\ 0.1103\end{array}\right] , \left[ \begin{array}{ccc} 0.8103\\ 1.0000\\ 0.4343\end{array}\right] \)
|
(iii) |
\(-0.9749\)
|
\(\left[ \begin{array}{ccc} 0.0171\\ 0.2829\\ 0.6999\end{array}\right] \)
|
\(\left[ \begin{array}{ccc} 0.0937\\ 0.7096\\ 0.1967\end{array}\right] \)
|
\(\left[ \begin{array}{ccc} 0.0000\\ 0.4666\\ 0.1370\end{array}\right] , \left[ \begin{array}{ccc} 0.5616\\ 0.0000\\ 0.1122\end{array}\right] , \left[ \begin{array}{ccc} 0.8450\\ 1.0000\\ 0.4474\end{array}\right] \)
|