DRO-2 Conic Linear Programming

发表于 2023-11-25 更新于 2026-08-18 阅读次数： Artalk：

在继续学习DRO之前，继续拓展对于Linear Programming 的知识。传统上“Linear Programming”是线性的，那么我们想让一个问题“less linear”， how should we make it ?

这一章节与“robust” 无关

Why Conic Linear Programming

Recall standard form of LP:
$$
\begin{aligned}
& \min & & c^T x \\
& \text{s.t.} & & Ax = b \\
& & & x \geq 0
\end{aligned}
$$
如何在这个模型中引入”非线性“？

conic linear programming，选择在相对简单易处理的 ”$x\geq0$“ 这一约束上做文章。

Q: Is this the only definition we can use to compare 2 vectors? Let us investigate the propoerties of the realation “$\geq$” ?

Algebraic View

“$\geq$” defines a good order if :

Reflexivity: $u\geq u$ , $\forall u$
Anti-symmetry:

$\left.\begin{array}{l}
u \geqslant v \\
v \geqslant u
\end{array}\right\} \Rightarrow u=v$
Transitivity:

$\left.\begin{array}{l}
u \geqslant v \\
v \geqslant w
\end{array}\right\} \Rightarrow u \geqslant w$
Homogeneity:

$\begin{aligned}
& \left.\begin{array}{l}
u \geqslant v \\
\alpha \geqslant 0
\end{array}\right\} \Rightarrow \alpha u \geqslant \alpha v \\
&
\end{aligned}$
Additivity:

$\begin{aligned} & \left.\begin{array}{l}u \geqslant v \\ w \geqslant z\end{array}\right\} \Rightarrow \alpha u+w \geqslant \alpha v+z & \end{aligned}$

These 5 properties can help us prove Farkas Lemma and then prove “Strong Duality”

Geometric View

Consider
$$
\begin{aligned}
K & =\left\{x \in \mathbb{R}^n: x_i \geqslant 0 \forall i\right\} \\
& =\mathbb{R}_{+}^n
\end{aligned}
$$
$x \geqslant 0 \Leftrightarrow x \in \mathbb{R}_{+}^n$ in $LP$

This is a closed set. Moreover, this is also a “pointed cone”.

Ponited Cone:

Closed under addition: $K \neq \phi$ and $u, v \in K \Rightarrow u+v \in K$
Conic: $u \in K, \alpha>0 \Rightarrow \alpha u \in K$
Pointedness: $u,-u \in k \Rightarrow u=0$

很显然$\mathbb{R}_{+}^n$ is a pointed cone.

We have 2 questions:

Is “$\geq$” the only ordering , satisifies those 5 properties?
Is $\mathbb{R}_{+}^n$ the only closed pointed cone with nonempty interior?

The answer is NO !

Examples:

Lorentz Cone / Second-order cone:

$Q^{n+1}=\left\{(t, x) \in \mathbb{R} \times \mathbb{R}^n: t \geqslant\|x\|_2\right\}$

Claim: $Q^{n+1}$ is a closed pointed cone with $int(Q^{n+1})\neq \emptyset$

Define: Consider the order $\succeq_{Q^{n+1}}$ defined by
$$
(t, x) \succeq_{Q^{n+1}}(s, y) \Leftrightarrow (t-s, x-y) \in Q^{n+1}
$$

Exercise: E $\succeq_{Q^{n+1}} $ is a good order.

Semidefinite Cone: $K=S_{+}^n=\left\{Y \in S^n: u^{\top} \bar{Y} u \geqslant 0 \forall u \in R^n \right\}$
- $S_{+}^n$ is a closed pointed cone with $0 \in S_{+}^n$ and $\operatorname{int}\left(S_{+}^n\right) \neq \phi$.
- Consider the order " $\succeq_{S_{+}^n}$ " defined by
$$
x\succeq_{S_{+}^n} y \Leftrightarrow x-y \in S_{+}^n
$$

Conic Linear Programming

With a closed pointed cone $K$ containing $O$ and having non-empty interior, we can formulate the following problem, known as conic LP:

$$
\begin{align}
& \inf_{x}
& & \langle c, x \rangle \tag{P} \\
& \text{s.t.}
& & \langle a_i, x \rangle = b_i, \\
& & & x \in K
\end{align}
$$

Here, $\langle \cdot , \cdot \rangle$ is an inner product on some Euclidean space.

Similar to the traditional LP , the conic linear programming has a dual problem:
$$
\begin{align}
\tag{D}
& \text{Sup} & \sum_{i=1}^{m} b_i y_i & \text{ where } b, y \in \mathbb{R}^m, \\
& & & b = (b_1, \ldots, b_m) \\
& & & y = (y_1, \ldots, y_m) \\
& \text{s.t.} & C - \sum_{i=1}^{m} y_i a_i & \in K^*
\end{align}
$$
Where $k^*=\left\{y:\langle x, y\rangle \geqslant 0 \quad \forall x \in K \right\}$ is the dual cone of $K$

$S_{+}^n,Q^n ,\mathbb{R}_{+}^n$ are self dual

Examples:

1) SOCP

$$
\begin{align}
\tag{P}
& \inf & & \mathbf{c}^\top \mathbf{x} \\
& \text{s.t.} & & \mathbf{A}\mathbf{x} = \mathbf{b}, \\
& & & \mathbf{x} \in \mathbb{Q}^{n+1}
\end{align}
$$

$$
\begin{align}
\tag{D}
& \sup & & \mathbf{b}^\top \mathbf{y} \\
& \text{s.t.} & & \mathbf{C} - \sum_{i=1}^{m} y_i \mathbf{a}_i \in \mathbb{Q}^{n+1}
\end{align}
$$

2) SDP

$$
\begin{align}
\tag{P}
& \inf & & \mathbf{C} \cdot \mathbf{X} \\
& \text{s.t.} & & \mathbf{A}_i \cdot \mathbf{X} = b_i, \\
& & & \mathbf{X} \in \mathbb{S}^n_+
\end{align}
$$

$$
\begin{align}
\tag{D}
& \sup & & \mathbf{b}^\top \mathbf{y} \\
& \text{s.t.} & & \mathbf{C} - \sum_{i=1}^{m} y_i \mathbf{A}_i \in \mathbb{S}^n_+
\end{align}
$$

Strong Duality in Conic Linear Programming

The lagrangian of Primal Problem:
$$
§ \Leftrightarrow \inf_{x \in E} \sup_{y \in \mathbb{R}^m, w \in K^*}
\underbrace{\left\langle c, x \right\rangle + \sum_{i=1}^m y_i \left( b_i - \left\langle a_i, x \right\rangle \right) - \left\langle w, x \right\rangle}_{\mathcal{L}_{K}(x, y, w)}
$$
By changing order we can get:
$$
\sup_{y \in \mathbb{R}^m, w \in K^*} \inf_{x \in E}
\left\langle c-\sum_{i=1}^m y_i a_i-w_2 x\right\rangle+\sum_{i=1}^m y_i b_i \Leftrightarrow (D)
$$

Q: Is $P^* = D^*$ ? Can we just switch the order?

Conic Linear Programming

Primal Problem (P)

$v\_p^\* = \inf \\{ \langle c, x \rangle \\}$

such that $ \langle a\_i, x \rangle = b\_i$

$x \in K$

Dual Problem (D)

$v\_d^\* = \sup \\{ b^T y \\}$

such that $c - \sum\_{i=1}^{m} y\_i a\_i \in K^\*$

Theorem (Strong Duality for Conic LPs)

$$
\begin{align*}
\text{Suppose that} & \substack{ \color{blue}\text{§ is bounded below}\\ \color{red} \text{ (D) is bounded above}} \text{ and is strictly feasible i.e., } \exists \text{ feasible } \substack{\color{blue}x\\\color{red}\tilde{y}} \text{ to } \substack{§\\(D)} \quad \text{s.t. } \substack{\color{blue}x \in \text{int}(K)\\\color{red}c - \sum_i \tilde y_i a_i \in \text{int}(K^*)} ,
&.
\end{align*}
$$

Then:

$V_p^* = V_D^*$

$$
\begin{align*}\exists \text{ optimal } \substack{\color{blue}\text{Dual Solution } y^*\\\color{red}\text{Primal Solution } x^*} \text{ such that } \substack{\color{blue} b^{T}y^*\\\color{red} c^Tx^*} = V_P^* =V_D^*\end{align*}
$$

Interestingly, P is strictly feasible didnt imply that there exist primal solution but it implies there exists dual optimal solution.

Example: $\inf _{x>0} \frac{1}{x}$

doesn’t exist $x^*$ but exist $y^*$

Compare with LP Duality Theory

LP strong duality:

$$
\begin{align*}
\text{Suppose that} & \substack{\color{blue}\text{ § is bounded below}\\ \color{red}\text{ (D) is bounded above}} \text{ and is feasible }:
\end{align*}
$$

Then:

$V_p^* = V_D^*$.
Both § and (D) have optimal solutions.

使用conic linear programming的强对耦定理需要check ！！！严格可行！！！。

Counter Example (Failure of Strong Duality):

thus 他的dual 问题为：

(D)$\Leftrightarrow$sup $-y_1$ s.t. $y_1+y_2 \geqslant \sqrt{1+\left(y_1-y_2\right)^2} \Leftrightarrow \substack{4y_1y_2\geq 1\\y_1+y_2\geq 0}$

可以看出，对于（D）问题，optimal下,令$y_1$ 无限接近于0，最优值为0，但不存在最优解。

但$({D})$问题是否是严格feasible？of course.

while § 问题没有strictly feasible solution.