Hexo
0%

凸优化作业-1

Posted on Edited on In

凸优化作业-1

Problem 1：
$$
将优化问题

\text{最小化 } |Ax - b|_\infty

满足

|x|_1 \leq 1

转化为线性规划。
$$

解答：

  1. 重写 $|Ax - b|_\infty$：
    $$
    根据 \ell_\infty 范数的定义，我们可以引入一个辅助变量 t ，使得：

    \

    |Ax - b|\infty = \max{1 \leq i \leq m} |(Ax - b)_i| \leq t

    \

    这可以转化为以下约束：
    \
    -(Ax - b)_i \leq t \quad \text{和} \quad (Ax - b)_i \leq t \quad \text{对于所有 } i = 1, 2, \ldots, m
    \

    这意味着我们可以写出以下不等式：

    \
    Ax - b \leq t \mathbf{1} \quad \text{和} \quad -Ax + b \leq t \mathbf{1}
    \
    其中 \mathbf{1} 是一个全1的向量。
    $$

  2. 将问题转化为线性规划：
    于是我们需要最小化$t$，同时满足以下约束条件：
    $$
    Ax - b \leq t \mathbf{1}
    \

    -Ax + b \leq t \mathbf{1}
    \

    |x|_1 \leq 1
    $$
    最终的线性规划可以表述为：
    $$
    \text{最小化 } t
    \

    \text{满足 } Ax - b = t \mathbf{e}
    \

    -Ax + b = t \mathbf{e}
    \

    \sum_{j=1}^{n} |x_j| \leq 1
    $$

Problem 2：

(a)证明所有满足$X$是半正定的，且$I-X$也是半正定的$X$构成的集合$S$是凸集
$$
假设X_1 , X_2 \in S \

考虑Y = \lambda X_1 + ( 1 - \lambda ) X_2\

y^T X_1 y \geq 0 \quad \text{和} \quad y^T X_2 y \geq 0 \quad \text{对于所有 } y \in \mathbb{R}^n
\

考虑任意向量 y \in \mathbb{R}^n
\
计算 y^T Y y :
\
y^T Y y = y^T (\lambda X_1 + (1 - \lambda) X_2) y = \lambda y^T X_1 y + (1 - \lambda) y^T X_2 y
\
由于 X_1 和 X_2 都是半正定的，得到：

\
y^T Y y \geq \lambda \cdot 0 + (1 - \lambda) \cdot 0 = 0
\
因此，Y 是半正定的。
\
现在考虑 I - Y ：
\
I - Y = I - (\lambda X_1 + (1 - \lambda) X_2) = (1 - \lambda) I - \lambda X_1 + (1 - \lambda) I - (1 - \lambda) X_2
\
计算 y^T (I - Y) y ：
\
y^T (I - Y) y = y^T y - y^T Y y = y^T y - (\lambda y^T X_1 y + (1 - \lambda) y^T X_2 y)
\
从而得到：
\
y^T (I - Y) y = y^T y - \lambda y^T X_1 y - (1 - \lambda) y^T X_2 y
\
根据 I - X_1 和 I - X_2 都是半正定的，得到：
\
y^T (I - X_1) y \geq 0 \quad \text{和} \quad y^T (I - X_2) y \geq 0
\
所以：
\
y^T y \geq y^T X_1 y \quad \text{和} \quad y^T y \geq y^T X_2 y
\
结合线性组合性质：
\
y^T y \geq \lambda y^T X_1 y + (1 - \lambda) y^T X_2 y
\
因此，
\
y^T (I - Y) y \geq 0
\
这表明 I - Y 也是半正定的。
$$
(b) 证明集合 $S = { X \in S_n : \text{rank}(X) \leq 1 } $是否为凸集

证明：
$$
设X_1, X_2 \in S，这意味着\text{rank}(X_1) \leq 1和\text{rank}(X_2) \leq 1。
\

由于\text{rank}(X_1) \leq 1，我们可以表示 X_1为：
\
X_1 = u_1 v_1^T
\
其中 u_1 \in \mathbb{R}^m 和 v_1 \in \mathbb{R}^n。同理，X_2 可以表示为：
\
X_2 = u_2 v_2^T
\

对于 \theta \in [0, 1] ，考虑矩阵：
\
X_\theta = \theta X_1 + (1 - \theta) X_2 = \theta (u_1 v_1^T) + (1 - \theta) (u_2 v_2^T)
\
然而两个矩阵的和的秩有可能是2，故而不是凸集
$$
Problem 3：

设$ B(0, 1) \subset \mathbb{R}^n $是单位欧几里得球，考虑集合$N(x) = { u \in \mathbb{R}^n : u^T (y - x) \leq 0 \text{ 对于所有 } y \in B(0, 1) }$

(a) 证明 ( N(x) ) 是一个凸锥

$$
选择任意u_1, u_2 \in N(x): 根据定义，对于任意 y \in B(0, 1) ，都有：
\
u_1^T (y - x) \leq 0 \quad \text{和} \quad u_2^T (y - x) \leq 0
\

考虑非负组合：对于任意非负标量 \alpha, \beta \geq 0 ，考虑 u = \alpha u_1 + \beta u_2 。
\
验证条件：我们需要验证 u^T (y - x) \leq 0 对于所有 y \in B(0, 1) ：
\
u^T (y - x) = (\alpha u_1 + \beta u_2)^T (y - x) = \alpha u_1^T (y - x) + \beta u_2^T (y - x)
\
由于 u_1^T (y - x) \leq 0 和 u_2^T (y - x) \leq 0 ，因此：
\
u^T (y - x) \leq \alpha \cdot 0 + \beta \cdot 0 = 0
\
所以，u \in N(x) 。

因此， N(x) 是一个凸锥。
$$

(b) 给出 ( N(x) ) 的显式描述
$$
我们可以考虑 N(x) 中的向量 u 的条件。对于任意 y \in B(0, 1)，我们有：
\
|y|_2 \leq 1
\
因此，y - x 的范数可以表示为：
\
|y - x|_2 \leq |y|_2 + |x|_2 \leq 1 + |x|_2
\

要使得 u^T (y - x) \leq 0 对所有 y 成立，u 必须在某个方向上与 y - x 形成一个夹角不小于 90 度。这意味着 u 必须指向 x 的反方向。
\
因此， N(x) 可以描述为所有指向 x 的反方向的向量的集合：
\
N(x) = { u \in \mathbb{R}^n : u^T x \leq 0 }
\
$$
Problem 4：

(a) 找到 $ \Pi_{H^-}(s, c)(x) $ 的公式并证明其正确性

投影公式：

对于任意点 $x \in \mathbb{R}^n $，其在半空间 $ H^-(s, c) $ 上的投影可以通过以下公式给出：
$\Pi_{H^-}(s, c)(x) = x - \frac{s^T x - c}{|s|^2} s$

证明：
$$
希望找到一个点 y \in H^-(s, c) ，使得 ||y - x|| 最小。根据投影的定义，最优解 y 应满足：
\
s^T y = c
\

设 y = x + \alpha s ，其中 \alpha 是一个待定的标量。我们需要找到 \alpha 使得 y 满足 s^T y = c ：
\
s^T (x + \alpha s) = s^T x + \alpha |s|^2 = c
\
解这个方程得到：
\
\alpha = \frac{c - s^T x}{|s|^2}
\

代入 y ：
\
y = x + \frac{c - s^T x}{|s|^2} s
\

验证 y 在半空间内：
\
s^T y = s^T x + (c - s^T x) = c
\
因此 y 在超平面上，且由于 y 是通过向量s 的方向调整得到的，所以 y 在半空间 H^-(s, c) 内。
\
因此
\
\Pi_{H^-}(s, c)(x) = x - \frac{s^T x - c}{|s|^2} s
\
$$
(b) 证明对于任意 $ v \in \mathbb{R}^n $ 和 $ \delta \in \mathbb{R} $，都有$\Pi_{\Delta}(v) = \Pi_{\Delta}(v + \delta e)$

证明：
$$
对于 v 的投影：
\
\Pi_{\Delta}(v) = \text{argmin}_{x \in \Delta} |x - v|
\

对于 v + \delta e 的投影：
\
\Pi_{\Delta}(v + \delta e) = \text{argmin}{x \in \Delta} |x - (v + \delta e)|
\
由于 e^T x = 1 的约束是线性的，且 \delta 只是对所有坐标的均匀偏移，因此投影的结果不会受到 \delta 的影响。
\
故\Pi{\Delta}(v) = \Pi_{\Delta}(v + \delta e)
$$