课程主页:https://see.stanford.edu/Course/EE364A
这次回顾凸优化Homework 3。
3.42
考虑下水平集
即
现在$\forall x, y\in S_0, 0\le \alpha \le 1$,考虑
那么
所以$S_0$是凸集。
3.54
(a)
当$x \ge 0$时
(b)
(c)利用单调性可得
所以当$x<0$时,两边关于$t$积分可得
所以
(d)
由(c)可得
3.57
矩阵凸等价于$\forall z \in \mathrm R^n ,X\in \mathbf{S}_{++}^{n}$,我们有
而这是显然的。
4.1
(a)画图可得最优集$(\frac 2 5, \frac 1 5)$,最优值$\frac 3 5$
(b)无最优集和最优值。
(c)画图可得最优集$(0, x_2),x_2\ge 1$,最优值$0$
(d)画图可得最优集$(\frac 13 ,\frac 1 3)$,最优值$\frac 1 3$
(e)画图可得最优集$(\frac 12 ,\frac 1 6)$,最优值$\frac 12 $
4.4
(a)$\forall Q_j \in \mathcal G, j=1,\ldots, k$,我们有
对于$ s\neq t$,我们有
那么我们同样有
这是因为如果上式不成立,那么
这说明
从而
(b)
(c)如果存在最优点$x$,那么由(b)可得,对于$\bar x $
另一方面,由(a)可得
所以结论成立。
(d)显然置换矩阵$P$构成群,那么最优点为
对于置换矩阵,我们有
并且由置换矩阵的定义,我们有
4.8(a-e)
(a)如果$b \notin \mathcal R(A)$,那么无解。
否则设
其中
那么
如果$c^Tx_1=0$,那么最小值为$c^Tx_0$,否则不存在最小值。
(b)设
其中
那么
如果$t>0$,那么由于$a^T x \le b$,所以无下界;如果$t\le 0$,那么第一项$ta^Tx \ge tb$,考虑第二项$\hat a^T x$。
如果$\hat a \neq 0$,考虑
那么
这说明此时$\hat a^Tx$也没有下界。
如果$\hat a =0$,
(c)
由条件可得
所以
(d)假设
那么
当
时取等号。
如果$1^Tx\le 1$,当$c_1 <0$时,最小值依然为$c_1$,否则最小值为$0$,当
时取等号。
(e)假设
如果$\alpha $为整数,那么
即最优解为
如果$\alpha $不是整数,那么
那么最优解为
如果$1^Tx \le \alpha$,那么最优解为
4.17
原问题为
画图可得
所以原问题可以化为如下优化问题
接下来使用LP即可。
补充题
1
1 | A = [ 1 2 0 1; |
1 | x = |
2
(a)上述约束等价于
对应代码为
1 | cvx_begin |
(b)上述约束等价于
对应代码为
1 | cvx_begin |
(c)引入变量即可
对应代码为
1 | cvx_begin |
(d)引入变量即可
对应代码为
1 | cvx_begin |
(e)引入变量即可
对应代码为
1 | cvx_begin |
(f)使用quad_over_lin函数即可
1 | cvx_begin |
(g)引入变量即可
对应代码为
1 | cvx_begin |
(h)注意到
所以可以将原问题转化为
1 | cvx_begin |
3
Equal lamp powers
1 | %Equal lamp powers |
1 | p1 = |
Least-squares with saturation
1 | %Least-squares with saturation |
1 | p2 = |
Regularized least-squares
注意到
所以代码为
1 | %Regularized least-squares |
1 | p3 = |
Chebyshev approximation
1 | %Chebyshev approximation |
1 | p4 = |
Exact solution
1 | %Exact solution |
1 | p5 = |