分布鲁棒优化2-锥优化概述_盛煌娱乐-注册登录站

分布鲁棒优化2-锥优化概述

盛煌资讯 | 2024-05-13 09:13

提锥规划的原因是因为这个技巧可以用求解一些鲁棒优化导致的问题, 比如我们在之前使用范数2来选择不确定集合 $\\mathcal U$ 的时候, 其最终形式就涉及锥规划问题了.

首先回忆标准形式的LP:

$\\min \\quad$ $c^T x$

s.t. $Ax=b$

$x \\geq 0$

我们可以拓展该LP模型来包含非线性. 前两行可以讨论的不多, 但是最后一行的非负条件我们可以进行改动. 这里我们在比较两个向量 $x$ 和 $0$ 的大小, 我们可以写成 $x \\geq 0 \\Leftrightarrow x_i \\geq 0, \\; \\forall i$ . 这并不是唯一的定义方法, 这是我们引入非线性的突破点.

从代数角度

" $\\geq$ " 定义了一个"good"排序, 因为其满足如下性质:

Partial order (偏序关系):

1) 自反性 (Reflexivity): $u \\geq u$

2) 反对称性 (Anti-symmetry): $u \\geq v$ and $v \\geq u$ $\\Rightarrow$ $u=v$

3) 迁移性 (Transitivity): $u \\geq v$ and $v \\geq w$ $\\Rightarrow$ $u\\geq w$

同时, 还有:

4) 齐性 (homogeneity): $u \\geq v$ and $\\alpha \\geq 0 \\Rightarrow \\alpha u \\geq \\alpha v$

5) 可加性 (additivity): $u \\geq v$ and $w \\geq z \\Rightarrow u + w \\geq v + z$

这允许我们证明:

Farkas lemma: certifying (in)feasibility of linear system
Strong duality: certifying optimality of a pair of primal-dual LPs

从几何角度

考虑集合 $K=\\{ x \\in \\mathbb R^n: x_i \\geq 0, \\forall i \\}=\\mathbb R_+^n$

该集合是闭集, 且 $0\\in K$ , 且 $K$ 的内部(也就是不要边界) $\ ext{int}(k)=\\mathbb R_{++}^n \ eq \\emptyset$ (严格正).

此外, 其还是个 尖锥 (pointed cone), 其需要满足:

1) $K \ eq \\emptyset$ : $u, v\\in K \\Rightarrow u + v \\in K$

2) $u \\in K, \\alpha > 0 \\Rightarrow \\alpha u \\in K$

3) $u, -u \\in K \\Rightarrow u=0$

这给了我们对 $K$ 的直观理解:

现在我们就有了如下问题: 代数角度中, 是否 " $\\geq$ " 是唯一满足(1)-(5)的关系? 几何角度中, 是否 $\\mathbb R_+^n$ 是唯一包含原点和非空内部的closed pointed cone? 答案是否定的, 这里我们可以举两个标准的例子:

二阶锥 Second-order/Lorentz cone

$K=Q^{n + 1}=\\{ (t, x) \\in \\mathbb R \ imes \\mathbb R^n: t \\geq ||x||_2\\}$ 其中 $t$ 为标量, $x$ 为向量.

练习: 证明 $Q^{n+1}$ with $0\\in Q^{n+1}$ 且 $\ ext{int}(Q^{n+1}) \ eq \\emptyset$ 是closed pointed cone. 确定 $\ ext{int}(Q^{n+1})$ .

练习: 证明 $Q^{n+1}$ 不是一个多面体 Polyhedron - finite intersection of halfspaces.

我们也可以从代数角度去考虑: 我们重新定义order " $\\geq_{Q^{n+1}}$ " 为:

$(s, x) \\geq_{Q^{n+1}}(t,y) \\Leftrightarrow (s-t, x-y) \\in Q^{n+1}$

练习: 证明order" $\\geq_{Q^{n+1}}$ "是good order.

2. $K=S_+^n=\\{ y \\in S^n: u^Ty\\:u \\geq 0,\\; \\forall u \\}$ , 其中 $S^n$ 为 $n\ imes n$ 的对称阵, 且满足半正定的性质. 这个集合被称为 半正定锥 (semidefinite cone). 比如当 $n=2$ 时, $S$ 可以选择的元素有3个, 可以写为 $\\begin{bmatrix}x & y\\\\ y & z \\end{bmatrix}$ , 则其必须满足以下条件:

$x, z \\geq 0$

$xz - y^2 \\geq 0$

若 $n=3$ , 我们可以选择的元素就有6个, 则更加复杂.

练习: 证明 $S_+^n$ 是一个closed pointed cone, 其中 $0\\in S_+^n$ 且 $\ ext{int}(S_+^n) \ eq \\emptyset$ . 确定 $\ ext{int}(S_+^n)$ .

PS: 这里不难发现 $Q^{n+1}$ 与 $S_+^n$ 不一样, 因为 $S_+^2$ 是三维的, $S_+^3$ 是6维的, 并不是每个维数都有, 而 $Q^{n+1}$ 每个维数都有.

我们考虑order" $\\geq_{S_+^n}$ "的定义为 $x \\geq_{S_+^n}y \\Leftrightarrow x - y \\in S_+^n$ .

练习: 证明order" $\\geq_{S_+^n}$ "是good order.

有了上述两个方式, 我们就可以去重新定义LP了:

现在我们假设有一个closed pointed cone $K$ , 其包含 0 与非空内部, 我们可以构建conic LP:

(P) $\\begin{align}\\inf \\quad &<c, x> \\\\ s.t. \\quad &<a_i, x>=b_i \\\\ & x \\in K \\end{align}$

这里 $<,>$ 是在欧几里得空间的内积, 如果 $c$ 和 $x$ 都是向量, 那么我们可以等价写成 $c^Tx$ ; 同样地, 这里我们可以写成 $a_i^T x=b_i$ . 唯一的不同是这里 $x$ 不再 $\\in \\mathbb R_+^n$ , 从而体现了非线性的约束条件.

它有一个对偶问题:

(D) $\\begin{align}\\sup &\\quad b^T y \\\\ s.t. &\\quad c - \\sum_i y_i a_i \\in K^* \\end{align}$

PS: 这里 $\\inf$ 和 $\\sup$ 指的是 infimum and supremum, 也就是一个集合最大的下界/最小的上界

其中 $K^*=\\{ y: \\; <x, y> \\geq 0 \\;\\forall x \\in K \\}$ 是 $K$ 的对偶锥.

怎么理解呢? 如果我们要求内积为非负, 那从几何角度来说, 就要求夹角<90°, 我们可以从下图来理解:

就是找到距离 $K$ 两条边界的90°的另外两条边, 其构成的锥就是 $K^*$ .

那么我们可以怎么描述这两个问题呢?

(P) 中有线性目标函数, 等式的约束条件, 决策变量必须要在锥中;

(D) 还是在优化一个线性目标函数, 但对于约束条件, 我们先看左边的项 $c - \\sum_i y_i a_i \\in K^*$ , 它是对决策变量 $y$ 的一个仿射 (affine) 函数, 因此我们可以将(D)描述成, 我们在优化一个线性函数, s.t. conic constraint on affine map of $y$ .

Proposition: 若 $K$ 是一个closed pointed cone, 其内部非空, 且 $K^*$ 也满足, 则 (P) 和 (D) 性质相同.

练习: show that $\\mathbb R_+^n, Q^{n + 1}, S_{+}^n$ are self-dual, i.e., $(\\mathbb R_+^n)^*=\\mathbb R_+^n, (Q^{n+1})^*=Q^{n+1}, ...$

我们可以从几何的角度入手, 比如对于 $R_+^2$ :

接下来我们介绍一些例子:

(1) SOCP 二阶锥规划

(P) $\\inf \\quad c^T x$

s.t. $Ax=b$

$x \\in Q^{n + 1}$

(D) $\\sup \\quad b^T y$

s.t. $c - \\sum_i y_i a_i \\in Q^{n+1}$ 因为 $(Q^{n+1})^*=Q^{n+1}$

在文献中, 通常写成如下形式:

令 $a_i=(u_i, a_{i,1}, ..., a_{i, n}) \\in \\mathbb R^{n + 1}$ 是一个列向量

$c=(v, d_1, ..., d_n) \\in \\mathbb R^{n+1}$

那么, $c - \\sum_i y_i a_i \\in Q^{n+1}$ 可以写为:

$(c - u^T y, d - \\bar{A}^T y) \\in Q^{n+1}\\Leftrightarrow c - u^T y \\geq ||d - \\bar{A}^T y||_2$ (回忆 $Q^{n+1}$ 中, $t \\geq ||x||_2$ )

其中 $c - u^T y$ 是一维的, $d - \\bar{A}^T y$ 是n维的, $\\bar A=\\begin{bmatrix}\\quad \\\\ a_{i,1}, ..., a_{i, n}\\\\ \\quad \\end{bmatrix}$

也有其他的方法去写 $c - \\sum_i y_i a_i \\in Q^{n+1}$ :

$(c - u^T y, d - \\bar{A}^T y) \\in Q^{n+1}\\Leftrightarrow c - u^T y \\geq ||d - \\bar{A}^T y||_2 \\Leftrightarrow \\begin{bmatrix}v\\\\d\\end{bmatrix}- \\begin{bmatrix}u^T\\\\ \\bar{A}^T\\end{bmatrix}y \\in Q^{n+1}$

(2) SDP 半正定规划

(P) $\\inf \\quad C \\cdot X$ 要求 $C, A_i \\in S^n$ , 对两矩阵内积 $A\\cdot B=Tr(AB)=\\sum_{i, j}A_{ij}B_{ij}$

s.t. $A_i \\cdot X=b_i$

$X \\in S_+^n$ 可知 $X$ 是一个矩阵

(D) $\\sup \\quad b^T y$

s.t. $C - \\sum_i y_i A_i \\in S_+^n$ $C, A_i \\in S^n$ , 这两个矩阵都是对称的, 最后的差仍为对称阵

接下来我们举个例子, 回忆:

(RLC) $a^T x \\leq b$ $\\forall (a, b)=(a^0, b_0) + \\sum_{j=1}^l \\xi_j (a^j, b_j), \\quad \\xi \\in \\mathcal{U}\\in \\mathbb R^l$

当 $\\mathcal{U}=\\{ y \\in \\mathbb R^l: \\; ||y||_2 \\leq l \\}$ , 我们有:

(RLC) $\\Leftrightarrow \\bigg[ \\sum_{j=1}^l \\big( (a^j)^T x - b_j \\big)^2 \\bigg]^{1/2}\\leq b_0 - (a^0)^T x \\Leftrightarrow ||\\:[(a^j)^T x - b_j ]\\:||_2 \\leq b_0 - (a^0)^T x$

因为左右项都是对 $x$ 的仿射函数, 可以看出这是个二阶锥 (SOC) 约束. 也就是, 虽然我们的RLC是线性的, 但如果我们使用2范数来选择不确定集, 那么我们就会得到一个SOC约束条件.

那为什么我们要大费周章讨论LP, SOCP和SDP呢? 就是因为它们是非常标准的凸问题, 有许多成熟的工具和solver, 而且这三类问题可以在多项式时间内求解.