Convex Optimization · Problem 6.8

Statistical estimation — Boyd & Vandenberghe

Mathematics — Optimization · robust-approximation-formulations

Problem

Formulate the following robust approximation problems as LPs, QPs, SOCPs, or SDPs. For each subproblem, consider the

\ell_1

\ell_2

-, and the

\ell_\infty

-norms. (a) Stochastic robust approximation with a finite set of parameter values, i.e., the sum-of-norms problem

\text{minimize} \quad \sum_{i=1}^k p_i \|A_i x - b\|

where

p \succeq 0

and

\mathbf{1}^T p = 1

. (See \S 6.4.1.) (b) Worst-case robust approximation with coefficient bounds:

\text{minimize} \quad \sup_{A \in \mathcal{A}} \|Ax - b\|

where

\mathcal{A} = \{A \in \mathbf{R}^{m \times n} \mid l_{ij} \leq a_{ij} \leq u_{ij},\ i = 1, \ldots, m,\ j = 1, \ldots, n\}.

Here the uncertainty set is described by giving upper and lower bounds for the components of

A

. We assume

l_{ij} < u_{ij}

. (c) Worst-case robust approximation with polyhedral uncertainty:

\text{minimize} \quad \sup_{A \in \mathcal{A}} \|Ax - b\|

where

\mathcal{A} = \{[a_1 \cdots a_m]^T \mid C_i a_i \preceq d_i,\ i = 1, \ldots, m\}.

The uncertainty is described by giving a polyhedron

\mathcal{P}_i = \{a_i \mid C_i a_i \preceq d_i\}

of possible values for each row. The parameters

C_i \in \mathbf{R}^{p_i \times n}

d_i \in \mathbf{R}^{p_i}

i = 1, \ldots, m

, are given. We assume that the polyhedra

\mathcal{P}_i

are nonempty and bounded.