TimeHouse

Boring

0%

凸优化作业-1

发表于 更新于 分类于

凸优化作业-1

Problem 1：
将优化问题最小化 ∥Ax−b∥∞满足∥x∥1≤1转化为线性规划。 将优化问题 \text{最小化 } \|Ax - b\|_\infty 满足 \|x\|_1 \leq 1 转化为线性规划。

解答：

  1. 重写 ∥Ax−b∥∞\|Ax - b\|_\infty：

    根据ℓ∞范数的定义，我们可以引入一个辅助变量t，使得：∥Ax−b∥∞=max⁡1≤i≤m∣(Ax−b)i∣≤t这可以转化为以下约束：−(Ax−b)i≤t和(Ax−b)i≤t对于所有 i=1,2,…,m这意味着我们可以写出以下不等式：Ax−b≤t1和−Ax+b≤t1其中1是一个全1的向量。 根据 \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. 将问题转化为线性规划：
    于是我们需要最小化tt，同时满足以下约束条件：

    Ax−b≤t1−Ax+b≤t1∣x∣1≤1 Ax - b \leq t \mathbf{1} \\ -Ax + b \leq t \mathbf{1} \\ |x|_1 \leq 1

    最终的线性规划可以表述为：

    最小化 t满足 Ax−b=te−Ax+b=te∑j=1n∣xj∣≤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)证明所有满足XX是半正定的，且I−XI-X也是半正定的XX构成的集合SS是凸集
假设X1,X2∈S考虑Y=λX1+(1−λ)X2yTX1y≥0和yTX2y≥0对于所有 y∈Rn考虑任意向量y∈Rn计算yTYy:yTYy=yT(λX1+(1−λ)X2)y=λyTX1y+(1−λ)yTX2y由于X1和X2都是半正定的，得到：yTYy≥λ⋅0+(1−λ)⋅0=0因此，Y是半正定的。现在考虑I−Y：I−Y=I−(λX1+(1−λ)X2)=(1−λ)I−λX1+(1−λ)I−(1−λ)X2计算yT(I−Y)y：yT(I−Y)y=yTy−yTYy=yTy−(λyTX1y+(1−λ)yTX2y)从而得到：yT(I−Y)y=yTy−λyTX1y−(1−λ)yTX2y根据I−X1和I−X2都是半正定的，得到：yT(I−X1)y≥0和yT(I−X2)y≥0所以：yTy≥yTX1y和yTy≥yTX2y结合线性组合性质：yTy≥λyTX1y+(1−λ)yTX2y因此，yT(I−Y)y≥0这表明I−Y也是半正定的。 假设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∈Sn:rank(X)≤1}S = \{ X \in S_n : \text{rank}(X) \leq 1 \} 是否为凸集

证明：
设X1,X2∈S，这意味着rank(X1)≤1和rank(X2)≤1。由于rank(X1)≤1，我们可以表示X1为：X1=u1v1T其中u1∈Rm和v1∈Rn。同理，X2可以表示为：X2=u2v2T对于θ∈[0,1]，考虑矩阵：Xθ=θX1+(1−θ)X2=θ(u1v1T)+(1−θ)(u2v2T)然而两个矩阵的和的秩有可能是2，故而不是凸集 设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)⊂Rn B(0, 1) \subset \mathbb{R}^n 是单位欧几里得球，考虑集合N(x)={u∈Rn:uT(y−x)≤0 对于所有 y∈B(0,1)}N(x) = \{ u \in \mathbb{R}^n : u^T (y - x) \leq 0 \text{ 对于所有 } y \in B(0, 1) \}

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

选择任意u1,u2∈N(x):根据定义，对于任意y∈B(0,1)，都有：u1T(y−x)≤0和u2T(y−x)≤0考虑非负组合：对于任意非负标量α,β≥0，考虑u=αu1+βu2。验证条件：我们需要验证uT(y−x)≤0对于所有y∈B(0,1)：uT(y−x)=(αu1+βu2)T(y−x)=αu1T(y−x)+βu2T(y−x)由于u1T(y−x)≤0和u2T(y−x)≤0，因此：uT(y−x)≤α⋅0+β⋅0=0所以，u∈N(x)。因此，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∈B(0,1)，我们有：∣y∣2≤1因此，y−x的范数可以表示为：∥y−x∥2≤∥y∥2+∥x∥2≤1+∥x∥2要使得uT(y−x)≤0对所有y成立，u必须在某个方向上与y−x形成一个夹角不小于90度。这意味着u必须指向x的反方向。因此，N(x)可以描述为所有指向x的反方向的向量的集合：N(x)={u∈Rn:uTx≤0} 我们可以考虑 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) 找到 ΠH−(s,c)(x) \Pi_{H^-}(s, c)(x) 的公式并证明其正确性

投影公式：

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

证明：
希望找到一个点y∈H−(s,c)，使得∣∣y−x∣∣最小。根据投影的定义，最优解y应满足：sTy=c设y=x+αs，其中α是一个待定的标量。我们需要找到α使得y满足sTy=c：sT(x+αs)=sTx+α∥s∥2=c解这个方程得到：α=c−sTx∥s∥2代入y：y=x+c−sTx∥s∥2s验证y在半空间内：sTy=sTx+(c−sTx)=c因此y在超平面上，且由于y是通过向量s的方向调整得到的，所以y在半空间H−(s,c)内。因此ΠH−(s,c)(x)=x−sTx−c∥s∥2s 希望找到一个点 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∈Rn v \in \mathbb{R}^n 和 δ∈R \delta \in \mathbb{R} ，都有ΠΔ(v)=ΠΔ(v+δe)\Pi_{\Delta}(v) = \Pi_{\Delta}(v + \delta e)

证明：
对于v的投影：ΠΔ(v)=argminx∈Δ∥x−v∥对于v+δe的投影：ΠΔ(v+δe)=argminx∈Δ∥x−(v+δe)∥由于eTx=1的约束是线性的，且δ只是对所有坐标的均匀偏移，因此投影的结果不会受到δ的影响。故ΠΔ(v)=ΠΔ(v+δ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)