对偶习题

《凸优化》第五章部分习题

5.6

(a)

$$\begin{align} &\because\forall z\in\textbf{R}^m, \|z\|_\infty\geq\frac{1}{\sqrt{m}}\|z\|_2\\ &\therefore \|Ax_{ch}-b\|_2\leq\sqrt{m}\|Ax_{ch}-b\|_\infty\\ &\because \|Ax_{ch}-b\|_2\geq\|Ax_{ls}-b\|_2\text{(optimal)}\geq\|Ax_{ls}-b\|_{\infty}\text{(hint)}\\ &\therefore \|Ax_{ls}-b\|_\infty\leq \sqrt{m}\|Ax_{ch}-b\|_{\infty} \end{align}$$

(b)

容易得到 $|\hat\nu|_1\leq1$ ，$|\tilde{\nu}|_1\leq1$ 。

$$\begin{align} A^T\hat{\nu}&=(A^TAx_{ls}-A^Tb)/\|b-Ax_{ls}\|_1\\ &=(A^TA(A^TA)^{-1}A^Tb-A^Tb)/\|b-Ax_{ls}\|_1\\ &=0\\ A^T\tilde{\nu}&=-A^T\hat{\nu}=0 \end{align}$$

即两个 $\nu$ 都是问题的可行解。考虑 $b^T\nu$：

$$\begin{align} b^T\hat\nu&=\frac{-b^Tr_{ls}}{\|r_{ls}\|_1}=\frac{x_{ls}^TA^Tr_{ls}-b^Tr_{ls}}{\|r_{ls}\|_1}=-\frac{\|r_{ls}\|^2_2}{\|r_{ls}\|_1}\\ b^T\tilde\nu&=-b^T\hat\nu=\frac{\|r_{ls}\|^2_2}{\|r_{ls}\|_1}\\ \end{align}$$

即 $\tilde{\nu}$ 给出了更好（大）的下界。和(a)相比:

$$\begin{align} \frac{\|r_{ls}\|^2_2}{\|r_{ls}\|_1}=\frac{\|Ax_{ls}-b\|^2_2}{\|b-Ax_{ls}\|_1}\geq\frac{\|Ax_{ls}-b\|^2_2}{\sqrt{m}\|b-Ax_{ls}\|_2}\geq\frac{\|Ax_{ls}-b\|_\infty}{\sqrt{m}} \end{align}$$

比 (a) 给出了一个更好的下界。

总结：

解是一些矩阵代换。不过这一题还给出了一个通过最小二乘问题等其他问题的对偶问题来逼近原问题最优解的方法。通常这类问题没有解析解，通过其他问题的对偶问题的分析得到的下界通常比一般不等式要好。

5.7

(a)

$$L(x,y,\nu)=\max_{i=1,\cdots,m} y_i+\sum_i\nu_i(a^T_ix+b_i-y_i)\\ g(\nu)=\inf_{x,y}(\max_{i=1,\cdots,m} y_i+\sum_i\nu_i(a^T_ix+b_i-y_i))$$

对偶问题：

$$\begin{align} \text{maximize } &g(\nu)\\ \text{subject to }&\nu\succeq 0 \end{align}$$

由于原函数有线性部分，考虑 $g(\nu)$：

优化 $x$ 时，$\sum\nu^T a_i=0, i.e. A^T\nu=0$ 否则拉格朗日函数无下界。

优化 $y$ 时，$\max y_i-\nu^Ty=0$ 否则拉格朗日函数无下界，即 $v^T\textbf{1}=1$ 。

等价对偶问题：

$$\begin{align} \text{maximize } &\nu^Tb\\ \text{subject to }&\nu\succeq 0\\ &\nu^T\textbf{1}=1\\ &A^T\nu=0 \end{align}$$

(b)

原问题的上境图形式为LP：

$$\begin{align} \text{maximize } &t\\ \text{subject to }&\max(a_i^Tx+b_i)-t\leq 0 \end{align}$$

约束等价变换：

$$\begin{align} \text{maximize } &t\\ \text{subject to }&A_i^Tx+b_i-t\textbf{1}\preceq 0 \end{align}$$

对偶问题：

$$\begin{align} \text{maximize } &\lambda^Tb\\ \text{subject to }&A^T\lambda=0\\ &\lambda^T\textbf{1}=1\\ &\lambda\succeq0 \end{align}$$

和(a)中对偶问题完全等价。

(c)

考虑无约束几何规划对偶问题的最优解 $d^\star$ 以及其最优点 $z^\star$ ：

$$p^\star_{gp}\leq d^\star=b^Tz_i-\sum_iz^\star_i\log z^\star_i$$

将其变换成LP ，对某个 $\nu$ 有以下式子成立：

$$b^T\nu= p^\star_{gp} -\sum_iz^\star_i\log z^\star_i$$

又因为 $z^\star$ 在GP对偶问题上的可行域也是原分片线性极小化对偶问题的可行域，即 $z^\star$ 为此LP的可行解：

$$\begin{align} p^\star_{pw1}&\geq b^T\nu=p^\star_{gp}-\sum_iz^\star_i\log z^\star_i\\ p^\star_{gp}-p^\star_{pw1}&\leq \sum_iz^\star_i\log z^\star_i\leq \log m \end{align}$$

(d)

写出对偶问题，先变换问题为

$$\begin{align} \text{maximize } &(1/\gamma)\log(\sum_i\exp(\gamma y_i))\\ \text{subject to }&Ax+b=y \end{align}$$

拉格朗日函数：

$$L(x,\lambda)=(1/\gamma)\log\sum\exp(\gamma y_i)+\lambda^T(Ax+b-y)$$

$x$ 的最优化条件为 $A^T\lambda=0$ ，对 y 第一项为 Log-Sum-Exp 函数，其导数为 Softmax。即 $y$ 的最优化条件为：

$$\frac{e^{\gamma y_i}}{\sum e^{\gamma y_i}}=\lambda_i$$

对偶问题为：

$$\begin{align} \text{maximize } &\lambda^Tb-(1/\gamma)\sum_{i=1}^m\lambda_i\log\lambda_i\\ \text{subject to }&A^T\lambda=0\\ &\textbf{1}^T\lambda=1 \end{align}$$

按照处理(c)中GP对偶问题的步骤，第二项可以放缩为 $1/\gamma \log m$令其最优解为 $p^\star_{gp}(\gamma)-1/\gamma\log m$ 有：

$$p^\star_{gp}(\gamma)-1/\gamma\log m\leq p^\star_{pw1}\leq p^\star_{gp}(\gamma)$$

可看出 $\gamma$ 变大会让此优化问题逼近 $p^\star_{pw1}$ 。

总结：

问题的拉格朗日对偶问题常常会因为保证满足优化时极小值可达所需要的条件，从而消去一些项使目标函数或约束变得简单 （拉格朗日对偶问题优化拉格朗日变量，对原问题优化变量直接取inf下界，化成等价问题时常常消去inf，即把原优化变量全部去掉），等价问题还可能直接优化成LP形式。(c)的解法比较技巧化，即通过辅助的LP问题分析，能用到之前分片线性极小化问题的性质。

5.16

(a)

因为 $f0$凸，$f_i$凸，所以$\max{0, f_i}$凸，所以$\max{i=1,\cdots,m}\max{0,f_i}$凸，所以$\phi$ 凸。

(b)

$$\begin{align} L(x,\lambda)&=f_0(x)+\sum_i\lambda_if_i(x)\\ g(\lambda)&=\inf_x(f_0(x)+\sum_i\lambda_if_ix(x))\\ L'(x,y,\lambda,\nu)&=f_0(x)+\alpha y+\sum_i\lambda_i(f_i(x)-y)-\nu y\\ g'(\lambda,\nu)&=\inf_{x,y}(f_0(x)+\alpha y+\sum_i\lambda_i(f_i(x)-y)-\nu y)\\ &=\inf_x(f_0(x)+\sum\lambda_if_i(x))+\inf_y((\alpha-\nu-\sum_i\lambda_i)y) \end{align}$$

优化 $g’(\lambda,\nu)$ 的等价问题：

$$\begin{align} \text{maximize } &g(\lambda)\\ \text{subject to }&\textbf{1}^T\lambda-\alpha\leq0\\ &\lambda\succeq0\\ \end{align}$$

(c)

$\lambda^\star$ 为原对偶问题最优解：

$$\begin{align} \text{maximize } &g(\lambda)\\ \text{subject to } &\lambda\succeq0\\ \end{align}$$

辅助问题最优解 $x_s^\star\geq \lambda^\star_s$ ，且容易知道辅助问题对偶最优解 $\lambda^\star_s$ 在原对偶问题上可行。又有 $\alpha>\textbf{1}^T\lambda^\star$ ， 即 $\lambda^\star$ 也是辅助问题对偶最优解，两者可行域以及优化函数等价，辅助问题的最优解是其对偶问题最优解，由于原问题强对偶成立，所以对偶问题最优解也是原问题最优解，即：辅助问题的最优解也是原问题的最优解。

总结：

比较常规的对偶分析。罚函数项和一些损失函数正则项有相似之处。

5.23

(a)

设不存在这样的 $z$ ，即 $-c\notin{\sum z_ia_i\mid z_i\geq0}$ ，右侧为闭凸集，根据严格分离超平面定理，存在超平面 $u^Tx$ 严格分离点和集合。即：

$$-u^Tc>\sum u^Tz_ia_i=u^TA^Tz$$

约束为 $z\succeq 0$ ，可以看出 $u^Tc<0, u^TA^T<0$ 。令 $x=x^\star+tu$ ：

$$a^T_ix=a^T_ix^\star+a^T_itu\leq b_i+ta^T_iu<b_i$$

即 $x$ 可行；考虑目标函数：

$$c^Tx=c^Tx^\star+tc^Tu<c^Tx^\star$$

我们找到了比 $x^\star$ 更优的解，矛盾。所以存在满足题意的 $z$ 。

(b)

对偶问题可行即 $-b\notin {Ax+s\mid s\succeq0}$ ，右侧为闭凸集，根据严格分离超平面定理，存在超平面 $v^Tx$ 严格分离点和集合。即：

$$-v^Tb>v^TAx+v^Ts$$

在 $x$ 任意取值下成立需要 $v^TA=0$ ， 等价式子为：

$$v^TA=0, v^Tb<0,v\succeq 0$$

那么对偶问题可行性条件 $A^Tz+c=0=A^T(z+v)$ ，即对偶问题在 $v$ 方向上是无界的， $d^\star =\infty$。

(c)

原问题容易看出不可行 ($0\leq -1$)，$p^\star=\infty$ 。

$$L(x,\lambda_1,\lambda_2)=x+\lambda_1(x-1)+\lambda_2$$

可行性条件 $\lambda_1+1=0$ ，对偶线性规划：

$$\begin{align} \text{maximize } &\lambda_2-\lambda_1\\ \text{subject to }&\lambda_1+1=0\\ &\lambda_1,\lambda_2\geq0\\ \end{align}$$

容易看出此问题约束 $\lambda_1=-1\geq0$ 不能满足，对偶问题不可行。$d^\star=-\infty$ 。

5.27

拉格朗日函数：

$$\begin{align} L(x,\nu)&=\|Ax-b\|^2_2+\nu^T(Gx-h)\\ &=x^TA^TAx-2b^TAx+b^Tb+\nu G^T x-\nu^Th\\ &=x^TA^TAx+(G^T\nu-2A^Tb)^Tx-\nu^Th+b^Tb \end{align}$$

KKT条件:

$$2A^TAx^\star-2A^Tb+G^T\nu^\star=0\\ Gx^\star-h=0$$

最优解 $x^\star$ 可以用 $\nu^\star$ 显式表达：

$$x^\star=(\frac{1}{2}(A^TA)^{-1})(-G^T\nu^\star+2A^Tb)$$

代入 $Gx^\star-h=0, x^\star=G^{-1}h$ 后 $\nu^\star$ 可独立写出：

$$\nu^\star=(G^T)^{-1}(2A^Tb-2A^TAG^{-1}h)$$