学习

凸优化作业-1

凸优化作业-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) $$