凸问题习题

《凸优化》第四章部分习题。

4.2

(a)

先证充分性： $Av\preceq 0$ ，则对于任意一点$x_0\in \textbf{dom}f$， 有

$$\forall k\in R^+, A(x_0+kv)=Ax_0+k\cdot Av\preceq Ax_0 \prec b$$

即 $x_0+kv$ 也在定义域中。所以 $\textbf{dom} f$ 无界。

再证必要性：若 $\textbf{dom} f$ 无界，则存在序列 $x^k\in\textbf{dom} f$ 在 $k\rightarrow \infty$ 时 $|x^k|_2\rightarrow \infty$ 。若不存在 $v\neq 0$ 满足 $Av\preceq 0$ ，则对于 $v\neq 0$ ，$Av$ 必定存在某一分量大于0。 令 $A(kv)=k\cdot Av$ 为对 $Ax^k$ 的一个逼近，即可使 $v=x^k/|x^k|_2$ ，那么 $k\rightarrow \infty$ 时， $kv$ 逼近 $x^k$ ，应有 $A(kv)\prec b$ ，但由于 $Av$ 必定存在某一分量大于0，所以 $k\cdot Av\prec b$ 不成立，此处 $b$ 亦可为任意实数。 结论自相矛盾，假设不成立。所以存在 $v\neq 0$ 满足 $Av\preceq 0$ 。

(b)

由择一定理可以得到，存在 $v$ 满足 $Av\preceq 0, Av\neq 0$ 的充要条件是，不存在 $z\succ 0$ 使得 $A^Tz=0$ 。

对于原命题，先证充分性：存在 $Av\preceq 0$ ， $Av\neq 0$ ，即对 $Av$ 的每个分量都有 $a^T_iv_i\leq 0$ ，且 $Av\neq 0$ 。由于(1)可知此时定义域无界，对于 $x_0\in \textbf{dom} f$ ，有 $\forall k\in R^+, x_0+kv\in\textbf{dom} f$ :

$$f_0(x_0+kv)=-\sum^m_{i=1}\log(b_i-a^T_ix_0-k\cdot a^T_iv)$$

因为对每个分量都有 $a^T_iv\leq 0$ 且 $Av\neq 0$ ，在 $k\rightarrow \infty$ 时很容易看出 $f_0(x_0+kv)\rightarrow -\infty$ ，即 $f_0$ 无下界。

再证必要性：若 $f_0$ 无下界，设序列 $x_1,x_2,\cdots,x_k$ 为无界序列，即 $k\rightarrow \infty\Rightarrow b-Ax\rightarrow -\infty\Rightarrow f_0(x_k)\rightarrow -\infty$ 。且存在 $z\succ 0$ ，使得 $A^Tz=0$ ，展开 $f_0(x_k)$ 在 $x_0$ 处的一阶条件：

$$f_0(x_k)\geq f_0(x_0)+\sum^m_{i=1}\frac{1}{b_i-a^T_ix}a_i^T(x_k-x_0)$$

(c)

设其定义域 $\textbf{dom} f_0$ 有界，则 $f_0$ 下水平集为闭，极小值可达。
若其定义域无界，则由 (a) 有其等同于存在 $v\neq 0, Av\preceq 0$ ； $f_0$ 有下界，则不存在 $v$ 使 $Av\preceq 0, Av\neq 0$ 。因为 $v\neq 0$ ，所以只有 $A=0$才能满足条件，此时函数值恒为定值，极小值可达。

(d)

由最优性条件：

$$\triangledown f_0(x)=\sum^m_{i=1}\frac{1}{b_i-a^T_ix}a_i=0$$

若 $Av=0$ ，则有 $a^T_iv=0$ ，即 $b_i-a^T_ix^\star=b_i-a^T_ix^\star+a^T_iv=b_i-a^T_i(x^\star+v)$ ，即对于任意最优解 $x^\star$ ，$x^\star+v$ 也是最优解( $Av=0$ ) 。

总结：

这题我认为主要的点是在：

• 怎么判断无界(用序列 $x+kv$ 逼近无穷)
• 怎么表达可达($X_{opt}$非空，大部分情况下问题应有界)
• 拆矩阵分析

4.8

(a)

若问题不可行，则 $p^\star=+\infty$ 。

若问题可行，将 $c$ 分解为 $c=A^T\lambda+\hat{c}$ ，$A\hat{c}=0$ ：
若 $c$ 与 $A$ 的零空间正交，因为正交性，有 $\hat{c}=0$， $c^Tx=\lambda^TAx=\lambda b$ 即最优值为 $\lambda b$ ；
若 $c$ 与 $A$ 的零空间不正交，则问题无下界，因为 $c^Tx=\lambda b+\hat{c}^Tx$ ，$x$ 在可行集内可以无限小，只需要无限减小 $\hat{c}$ 分量的值。

所以此问题的最优值为

$$p^\star=\begin{cases} & +\infty, \text{ if } \forall x, Ax\neq b\\ & \lambda b,\text{ if for some } \lambda<0, c=A^T\lambda=0 \\ & -\infty, \text{ if } otherwise \end{cases}$$

(b)

问题可行集为半空间，此问题一定可行。

将 $c$ 分解为 $c=\lambda a +\hat{a}$ ，$a^T\hat{a}=0$ ，即分解成与 $a$ 平行和正交的两个分量。目标函数可以表示为： $c^Tx=\hat{a}^Tx+\lambda a^Tx$ ，可以容易知道 $c$ 与 $a$ 平行时，问题才有界。否则解可以无限在 $\hat{a}$ 的方向上滑动。且 $c,a$ 必须反向，即 $\lambda <0$ ，此时最优解为 $\lambda a^Tx=\lambda b$ 。

所以此问题的最优值为

$$p^\star=\begin{cases} & \lambda b,\text{ if for some } \lambda<0, \hat{a}=0 \\ & -\infty, \text{ if } \lambda\geq0 \end{cases}$$

(c)

问题可行集为矩形，问题一定可行。由于 $l\preceq x\preceq u$ ，容易知道最优值为

$$p^\star=\begin{cases} & c^Tl,\text{ if } c<0, \\ & c^Tu, \text{ if } c>0, \\ & \forall x \text{ in rectangle, if } c=0 \end{cases}$$

(d)

将 $c$ 中元素排序，设最小元素为 $c_1$ ，显然最优值为 $p^\star=c_1$ ，即投资组合优化问题中全部投资收益率最高的项目。

等式约束被替换为不等式约束时，由于 $1^Tx$ 可以为0，则在 $c_1>0$ 时，最优值为 $p^\star=0$ (即投资组合优化问题中，收益率为负时，可以选择不投资)。总最优值为 $p^\star=\min{0,c_1}$ 。

(e)

仍然将 $c$ 中元素排序，设为 $c_1\leq c_2\leq \cdots \leq c_n$ ，显然最优值为

$$p^\star=\sum_{i=1}^\alpha c_i$$

即全预算投资收益率前 $\alpha$ 的项目。

若 $\alpha$ 不为整数，最优值仍然可以按照原思想得出:

$$p^\star=\sum_{i=1}^{\lfloor\alpha\rfloor}c_i+(\alpha-\lfloor\alpha\rfloor)c_{\lfloor\alpha\rfloor}$$

若等式变为 $1^Tx\leq\alpha$ ，则对于收益率为负的部分，可以选择不投资。令 $c_m$ 为其中最大的负值，则最优值为：

$$p^\star=\sum_{i=m}^{\min\{\alpha+m,n\}}c_i$$

(f)

可以定义收益性价比为 $vi=c_i/d_i$ ，容易知道到全资投资收益性价比高的总会拥有比别的方案更高的收益。按性价比对 $c$ 中元素排序，设为 $v_1\leq v_2\leq \cdots\leq v_n$，且 $\sum{i=1}^m dix_i\leq \alpha\leq \sum{i=1}^{m+1}d_ix_i$ 显然最优值为

$$p^\star=\sum_{i=1}^{m}c_i+c_{m+1}\frac{\alpha-\sum_{i=1}^md_ix_i}{d_i}$$

总结:

如何显示求LP的解？一个比较常用的方法是把系数 $c$ 拆成两个互相正交方向，通常一个是下降方向，即另一个和约束平面平行。这种方法在其他题目上也有体现，比如将矩阵拆成正定矩阵和非正定矩阵的和。

4.24

(a)

L1范数:

$$\begin{align} \text{minimize } &\sum_{i=1}^m|a_i^Tx-b|\\ \end{align}$$

直接引入新优化实变量 $t_i=|a^T_ix-b|$ ，则引入了新约束 $|a^T_ix-b|\leq t_i$ ， 可以将约束用范数展开：

$$\begin{align} &\sum|a^T_ix-b|\\ &=\sum\sqrt{[Re(a^T_ix-b)]^2+[Im(a^T_ix-b)]^2}\\ &=\sum\sqrt{[Re(a^T_i)Re(x)-Im(a^T_i)Im(x)-Re(b)]^2}\\ &\overline{+[Re(a^T_i)Im(x)+Im(a^T_i)Re(x)-Im(b)]^2}\\ &=\|\begin{bmatrix} Re(a_i^T)&-Im(a^T_i) \\ Im(a^T_i)&Re(a_I^T) \end{bmatrix}\begin{bmatrix} Re(x)\\ Im(x) \end{bmatrix}-\begin{bmatrix} Re(b)\\ Im(b) \end{bmatrix}\|_2 \end{align}$$

SOCP形式：

$$\begin{align} \text{minimize } &\sum_{i=1}^m t_i\\ \text{subject to } & \|\begin{bmatrix} Re(a_i^T)&-Im(a^T_i) \\ Im(a^T_i)&Re(a_I^T) \end{bmatrix}\begin{bmatrix} Re(x)\\ Im(x) \end{bmatrix}-\begin{bmatrix} Re(b)\\ Im(b) \end{bmatrix}\|_2\leq t_i \end{align}$$

(b)

L2范数：

同L1范数，可以容易写出

$$\begin{align} \|Ax-b\|_2&={\|Re(Ax-b)\|_2+\|Im(Ax-b)\|_2}^{1/2}\\ &=\|\begin{bmatrix} Re(A)&-Im(A) \\ Im(A)&Re(A) \end{bmatrix}\begin{bmatrix} Re(x)\\ Im(x) \end{bmatrix}-\begin{bmatrix} Re(b)\\ Im(b) \end{bmatrix}\|_2^{1/2} \end{align}$$

SOCP形式:

$$\begin{align} \text{minimize } &\sum_{i=1}^m t_i\\ \text{subject to } & \|\begin{bmatrix} Re(A)&-Im(A) \\ Im(A)&Re(A) \end{bmatrix}\begin{bmatrix} Re(x)\\ Im(x) \end{bmatrix}-\begin{bmatrix} Re(b)\\ Im(b) \end{bmatrix}\|_2^{1/2}\leq t_i \end{align}$$

(c)

L∞范数：

$$\begin{align} \text{minimize } \max_{i=1,\cdots,m} |a_i^Tx-b| \end{align}$$

同样引入新约束变量：

$$\begin{align} \text{minimize } &t\\ \text{subject to } &|a^T_ix-b|\leq t \end{align}$$

SOCP形式:

$$\begin{align} \text{minimize } &t\\ \text{subject to } & \|\begin{bmatrix} Re(a_i^T)&-Im(a^T_i) \\ Im(a^T_i)&Re(a_I^T) \end{bmatrix}\begin{bmatrix} Re(x)\\ Im(x) \end{bmatrix}-\begin{bmatrix} Re(b)\\ Im(b) \end{bmatrix}\|_2\leq t \end{align}$$

总结：凑SOCP形式，经常会凑出来目标函数为单一个 $t$ (正常情况是 $c^Tx$ 或 $f^Tx$)。将其他条件凑成二范数的约束(二次锥约束)。

4.40

(a) LP：

$$\begin{align} \text{minimize } &c^Tx+d\\ \text{subject to } &Gx\preceq h\\ &Ax=b \end{align}$$

直接把不等式约束写成对应矩阵形式即可，对应SDP：

$$\begin{align} \text{minimize } &c^Tx+d\\ \text{subject to } &\textbf{diag}(Gx-h)\preceq 0\\ &Ax=b \end{align}$$

(b) QP:

$$\begin{align} \text{minimize } &(1/2)x^TPx+q^Tx+r,\ P\in S^n_+\\ \text{subject to } &Gx\preceq h\\ &Ax=b \end{align}$$

设 $A\in S^r_{++}, C\in S^s, B\in R^{r\times s}$ ，有

$$\begin{bmatrix} A&B \\ B^T&C \end{bmatrix}\succeq 0\Leftrightarrow C-B^TA^{-1}B\succeq 0$$

令 $P=QQ^T, Q\in R^{n\times r}$ ，则目标函数变为 $(1/2)(Q^Tx)^T(Q^Tx)+q^Tx+r$ ，引入新优化变量 $t\geq x^TPx=(Q^Tx)^T(Q^Tx)$ ，目标函数变为 $(1/2)t+q^Tx+r$ ，且有新的约束 $t\geq (Q^Tx)^T(Q^Tx),\ i.e.\ tI-(Q^Tx)^TI^{-1}(Q^Tx)\succeq 0$ 。按照上式变换新约束，则原问题对应SDP为：

$$\begin{align} \text{minimize } &(1/2)t+q^Tx+r\\ \text{subject to } &\textbf{diag}(Gx-h)\preceq 0\\ &\begin{bmatrix} I& Q^Tx\\ x^TQ &tI \end{bmatrix}\succeq0\\ &Ax=b \end{align}$$

优化变量为 $x,t$ 。

QCOP:

$$\begin{align} \text{minimize } &(1/2)x^TP_0x+q_0^Tx+r_0)\\ \text{subject to } &(1/2)x^TP_ix+q_i^Tx+r_i\leq 0,\ i=1,\cdots,i\\ &Ax=b \end{align}$$

仿照上述过程，处理约束 $(1/2)x^TP_ix+q_i^Tx+r_i =(1/2)(Q_i^Tx)^T(Q_i^Tx)+q^T_ix+r_i\leq 0$ ，引入新的优化变量 $t_i$ ，则约束变为 $(1/2)t_i+q_i^Tx+r_i\leq 0$ ，同时引入新约束 $t_iI-(Q_i^Tx)^TI^{-1}(Q_i^Tx)\succeq 0$ 。原问题对应SDP为：

$$\begin{align} \text{minimize } &(1/2)t_0+q_0^Tx+r_0\\ \text{subject to } &(1/2)t_i+q^T_ix+r_i\leq 0\\ &\begin{bmatrix} I& Q_i^Tx\\ x^TQ &t_iI \end{bmatrix}\succeq0,\ i=0,1,\cdots,m\\ &Ax=b \end{align}$$

SOCP:

$$\begin{align} \text{minimize } &c^Tx\\ \text{subject to } &\|A_ix+b_i\|_2\leq c^T_ix+d_i,i=1,\cdots,m\\ &Fx=g \end{align}$$

仿照上述过程，约束可以化为

$$\begin{align} (A_ix+b_i)^T(A_ix+b_i)&\leq (c_i^Tx+d_i)^2\\ (c^T_ix+d_i)(c_i^Tx+d_i)-(A_ix+b_i)^T(A_ix+b_i)&\geq0\\ (c^T_ix+d_i)-(c^T_ix+d_i)^{-1}(A_ix+b_i)^T(A_ix+b_i)&\geq0\\ (c^T_ix+d_i)I-(A_ix+b_i)^T(c^T_ix+d_i)^{-1}I^{-1}(A_ix+b_i)&\succeq 0\\ \begin{bmatrix} (c^T_ix+d_i)I& A_ix+b_i\\ (A_ix+b_i)^T & (c^T_ix+d_i)I \end{bmatrix}&\succeq 0 \end{align}$$

原问题SDP为：

$$\begin{align} \text{minimize } &c^Tx\\ \text{subject to } &\begin{bmatrix} (c^T_ix+d_i)I& A_ix+b_i\\ (A_ix+b_i)^T & (c^T_ix+d_i)I \end{bmatrix}\succeq 0\\ &Fx=g \end{align}$$

(c)

引入新优化变量 $t=(Ax+b)^TF(x)^{-1}(Ax+b)$ ，则引入了新约束 $(Ax+b)^TF(x)^{-1}(Ax+b)-t\leq 0$ ，仿照上述形式，约束变为：

$$\begin{align} \begin{bmatrix} F(x)& Ax+b\\ (Ax+b)^T & tI \end{bmatrix}&\succeq 0 \end{align}$$

问题可以化成等价的上境图形式，同时也是SDP形式：

$$\begin{align} \text{minimize } &t\\ \text{subject to } &\begin{bmatrix} F(x)& Ax+b\\ (Ax+b)^T & tI \end{bmatrix}\succeq 0\\ \end{align}$$

总结：

SDP更广所以LP、QP、QCQP、SOCP都可以转换成SDP形式。这里的Hint非常有用，提供了通过变量代换将约束/目标函数转换成对角阵形式约束的方法。

4.43

(a)

$$\begin{align} \text{minimize } &\lambda_1(x)\\ \end{align}$$

引入新优化变量 $t=\lambda_1(x)$ ，则容易知道引入了新约束 $A(x)\preceq tI$ 即 $A(x)-tI$ 负定。SDP形式为:

$$\begin{align} \text{minimize } &t\\ \text{subject to } &A(x)\preceq tI \end{align}$$

(b)

$$\begin{align} \text{minimize } \lambda_1(x)-\lambda_m(x) \end{align}$$

引入新优化变量 $t_1=\lambda_1(x), t_2=\lambda_m(x)$ ，仿照上题可直接写出SDP形式

$$\begin{align} \text{minimize } &t_1-t_2\\ \text{subject to } &t_2I\preceq A(x)\preceq t_1I \end{align}$$

(c)

$$\begin{align} &\text{minimize } \lambda_1(x)/\lambda_m(x)\\ &\text{subject to } A(x)\succ 0 \end{align}$$

引入新变量 $\lambda=\lambda_1(x), \gamma=\lambda_m(x)$ ，同时引入了新约束 $\gamma I\preceq A(x)\preceq \lambda I$ 。作变量替换 $y=x/\gamma, t=\lambda/\gamma, s=1/\gamma$ ，则目标函数就变成了 $t$ ，约束可以两边同除 $\gamma$ 消元：$I\preceq A(x)/\gamma \preceq tI$ ，将 $A(x)$ 展开可以得到更清晰的形式：$I\preceq 1/\gamma A_0+y_1A_1+\cdots+y_nA_n\preceq tI$ 。因为至少有一个 $x$ 满足 $A(x)\succ 0$ ，所以需要 $\gamma > 0$ ，即 $1/\gamma >0$ 。

$$\begin{align} \text{minimize } &t\\ \text{subject to } &s> 0\\ &I\preceq sA_0+y_1A_1+\cdots+y_nA_n\preceq tI \end{align}$$

(d)

$$\begin{align} \text{minimize } |\lambda_1(x)|+\cdots+|\lambda_m(x)| \end{align}$$

$A(x)$ 变形为正负部 $A(x)=A+-A-$，这样 $A+,A-$ 都绝对半正定。设 $t+=\textbf{tr}A+, t-=\textbf{tr}A-$ ，可以看出正负部各自拥有原矩阵的正特征值和负特征值，即两者和即为目标函数。原问题SDP：

$$\begin{align} \text{minimize } &\textbf{tr}A_++\textbf{tr}A_-\\ \text{subject to } &A(x)=A_+-A_-\\ &A_+\succeq 0， A_-\succeq 0 \end{align}$$

总结:

优化特征值的等价问题。常用的等价问题代换除了特征值<=>单位阵，还有小于<=>极大值小于；。。

4.53

设两个点 $t_1, t_2\in \textbf{R}^q$ 在集合里，即满足 $f_0(x_1)\preceq_K t_1, f_0(x_2)\preceq_K t_2$ ，有原向量优化为凸问题，即 $f_0$ 是 K-凸的，即

$$f_0[\theta x_1+(1-\theta)x_2]\preceq_K \theta f_0(x_1)+(1-\theta)f_0(x_2)$$

所以对 $0\leq\theta\leq1$ ，有：

$$\begin{align} &\theta t_1+(1-\theta)t_2-\theta f_0(x_1)-(1-\theta)f_0(x_2)\\ =&\theta (t_1-f_0(x_1))+(1-\theta)(t_2-f_0(x_2))\in K\\ i.e.\ &f_0[\theta x_1+(1-\theta)x_2]\preceq_K\theta f_0(x_1)+(1-\theta)f_0(x_2)\preceq_K t_1+(1-\theta)t_2 \end{align}$$

因为原向量优化为凸问题， $\theta x_1+(1-\theta)x_2$ 在可行集中，即 $\theta t_1+(1-\theta)t_2\in A$ ，$A$ 为凸集。

若 $a$ 为 $A$ 的极小元，$o$ 为 $O$ 的极小元，将 $a$ 分解成 $O$ 上的元素的形式，即 $a=a’+b, a’\in O, b\succeq_K 0$ 。由于 $A$ 是凸集，则 $a=a’+kb$ 也属于 $A$ ，可以得到 $b=0$ 否则 $k<1$ 时 $a$ 将不是极小元。此时由于 $a$ 的极小元性质，对于任意 $v\in A, v\preceq_K a \Rightarrow v=a$ 。那么对于任意 $v’\in O, v\preceq_K a’ \Rightarrow v’\in A, v\preceq_K a’=a \Rightarrow v=a=a’$ ，即 $v’$ 满足 $O$ 中的极小元性质，且 $v=a$ ，即两者极小元相同。

总结:

重点是可行、极小元的概念，还有元素的分解。