EE364A Homework 3

课程主页：https://see.stanford.edu/Course/EE364A

这次回顾凸优化Homework 3。

3.42

考虑下水平集

$S_0=\{ x |W(x) \le T_0 \}$

即

$\forall x \in S_0, \left|x_{1} f_{1}(t)+\cdots+x_{n} f_{n}(t)-f_{0}(t)\right| \le \epsilon$

现在$\forall x, y\in S_0, 0\le \alpha \le 1$，考虑

$z =\alpha x +(1-\alpha) y$

那么

$\begin{aligned} \left|z_{1} f_{1}(t)+\cdots+z_{n} f_{n}(t)-f_{0}(t)\right| &= \left|\left(\alpha x +(1-\alpha) y\right)_{1} f_{1}(t)+\cdots+ \left(\alpha x +(1-\alpha) y\right)_{n} f_{n}(t)-f_{0}(t)\right|\\ &\le \alpha \left|x_{1} f_{1}(t)+\cdots+x_{n} f_{n}(t)-f_{0}(t)\right| +(1-\alpha) \left|y_{1} f_{1}(t)+\cdots+y_{n} f_{n}(t)-f_{0}(t)\right|\\ &\le \epsilon \end{aligned}$

所以$S_0$是凸集。

3.54

(a)

$\begin{aligned} f'(x)&=\frac 1 {\sqrt{2\pi} } e^{-x^2/2}\\ f''(x)&=- \frac x {\sqrt{2\pi} }e^{-x^2/2} \end{aligned}$

当$x \ge 0$时

$f''(x) f(x) \le 0 \le f'(x)^2$

(b)

$\begin{aligned} t^2 /2 -xt +x^2/2 &=\frac 12 (x-t)^2\\ &\ge 0 \end{aligned}$

(c)利用单调性可得

$e^{-t^{2} / 2} \leqslant e^{x^{2} / 2-x t}$

所以当$x<0$时，两边关于$t$积分可得

$\int_{-\infty}^{x} e^{-t^{2} / 2} d t \le e^{x^{2} / 2} \int_{-\infty}^{x} e^{-x t} d t =-e^{x^{2} / 2} \frac 1 x e^{-x^2} =-\frac 1 x e^{-x^2/2}$

所以

$-x \int_{-\infty}^{x} e^{-t^{2} / 2} d t \le e^{-x^2/2}$

(d)

$\begin{aligned} f^{\prime \prime}(x) f(x) &=- \frac x {\sqrt{2\pi} }e^{-x^2/2}\frac{1}{\sqrt{2 \pi} } \int_{-\infty}^{x} e^{-t^{2} / 2} d t\\ &=-\frac x {2\pi} e^{-x^2/2}\int_{-\infty}^{x} e^{-t^{2} / 2} d t\\ f'(x)^2&=\frac 1 {2\pi} e^{-x^2}\\ &=\frac 1 {2\pi} e^{-x^2/ 2} e^{-x^2/ 2} \end{aligned}$

由(c)可得

$f''(x) f(x) \le f'(x)^2$

3.57

矩阵凸等价于$\forall z \in \mathrm R^n ,X\in \mathbf{S}_{++}^{n}$，我们有

$z^T f(X)z =z^T X^{-1}z \ge 0$

而这是显然的。

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$，我们有

$\begin{aligned} Q_j \bar x &=\frac 1 k Q_j \sum_{i=1}^k Q_i x\\ &=\frac 1 k \sum_{i=1}^k (Q_j Q_i)x \end{aligned}$

对于$ s\neq t$，我们有

$Q_s \neq Q_t$

那么我们同样有

$Q_jQ_s \neq Q_j Q_t$

这是因为如果上式不成立，那么

$\begin{aligned} Q_jQ_s &= Q_j Q_t \\ Q_j^{-1}Q_jQ_s &= Q_j^{-1}Q_j Q_t\\ Q_s &= Q_t \end{aligned}$

这说明

$\{Q_j Q_1,\ldots, Q_j Q_k\}=\{Q_1,\ldots, Q_k\}$

从而

$\begin{aligned} Q_j \bar x &=\frac 1 k \sum_{i=1}^k (Q_j Q_i)x\\ &=\frac 1 k \sum_{i=1}^{k} Q_{i} x\\ &=\bar x \end{aligned}$

(b)

$\begin{aligned} f(\bar x ) &= f\left(\frac 1 k \sum_{i=1}^{k} Q_{i} x\right)\\ &\le \frac 1 k \sum_{i=1}^k f(Q_i x)\\ &=\frac 1 k \sum_{i=1}^k f(x)\\ &=f(x) \end{aligned}$

(c)如果存在最优点$x$，那么由(b)可得，对于$\bar x $

$f_0(\bar x) \le f _0(x)$

另一方面，由(a)可得

$\bar x \in \mathcal F$

所以结论成立。

(d)显然置换矩阵$P$构成群，那么最优点为

$\bar x =\frac 1 k \sum_{i=1}^k P_i x$

对于置换矩阵，我们有

$k=n!$

并且由置换矩阵的定义，我们有

$\bar x =\frac 1 k \sum_{i=1}^k P_i x =\frac 1 n\left(\sum_{i=1}^n x_i\right)1_n$

4.8(a-e)

(a)如果$b \notin \mathcal R(A)$，那么无解。

否则设

$x= x_0 +tx_1$

其中

$\begin{aligned} Ax_0&=b\\ Ax_1 &=0 \end{aligned}$

那么

$c^Tx = c^Tx_0 +tc^Tx_1$

如果$c^Tx_1=0$，那么最小值为$c^Tx_0$，否则不存在最小值。

(b)设

$c = ta+\hat a$

其中

$\hat a^Ta =0$

那么

$c^Tx = ta^Tx +\hat a^Tx$

如果$t>0$，那么由于$a^T x \le b$，所以无下界；如果$t\le 0$，那么第一项$ta^Tx \ge tb$，考虑第二项$\hat a^T x$。

如果$\hat a \neq 0$，考虑

$x= \frac{ba}{\| a\|^2} -u\hat a, u\ge 0$

那么

$\begin{aligned} a^Tx& = b\\ \hat a^Tx &=-u\|\hat a \|^2 \end{aligned}$

这说明此时$\hat a^Tx$也没有下界。

如果$\hat a =0$，

$c^Tx = ta^Tx +\hat a^Tx =ta^Tx \ge tb$

(c)

$\begin{aligned} c^Tx &= \sum_{i=1}^n c_i x_i\\ &=\sum_{i=1}^n (c_i^+- c_i^-) x_i\\ &=\sum_{i=1}^nc_i^+ x_i -\sum_{i=1}^nc_i^-x_i \end{aligned}$

由条件可得

$\begin{aligned} \sum_{i=1}^nc_i^+ l_i&\le \sum_{i=1}^nc_i^+ x_i \le \sum_{i=1}^nc_i^+ u_i \\ \sum_{i=1}^nc_i^- l_i&\le \sum_{i=1}^nc_i^- x_i \le \sum_{i=1}^nc_i^- u_i \end{aligned}$

所以

$\sum_{i=1}^nc_i^+ l_i -\sum_{i=1}^nc_i^- u_i \le c^T x \le \sum_{i=1}^nc_i^+ u_i- \sum_{i=1}^nc_i^- l_i$

(d)假设

$c_1\le \ldots \le c_n$

那么

$c^Tx \ge c_1$

当

$x_1= 1,x_i =0, i\neq 1$

时取等号。

如果$1^Tx\le 1$，当$c_1 <0$时，最小值依然为$c_1$，否则最小值为$0$，当

$x_i =0$

时取等号。

(e)假设

$c_1\le \ldots \le c_n$

如果$\alpha $为整数，那么

$c^Tx \ge \sum_{i=1}^\alpha c_i$

即最优解为

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

如果$\alpha $不是整数，那么

$c^Tx \ge \sum_{i=1}^{[\alpha]} c_i + c_{[\alpha] + 1}\{\alpha\}$

那么最优解为

$\sum_{i=1}^{[\alpha]} c_i + c_{[\alpha] + 1}\{\alpha\}$

如果$1^Tx \le \alpha$，那么最优解为

$\min\{0,\sum_{i=1}^{[\alpha]} c_i + c_{[\alpha] + 1}\{\alpha\}\}$

4.17

原问题为

$\begin{array}{cl}{ {\operatorname{maximize} }} & {\sum_{j=1}^{n} r_{j}\left(x_{j}\right)} \\ {\text { subject to } } & {x \succeq 0} \\ {} & {A x \preceq c^{\max } }\end{array}$

画图可得

$r_{j}\left(x_{j}\right)=\min \left\{p_{j} x_{j}, p_{j} q_{j}+p_{j}^{\operatorname{disc} }\left(x_{j}-q_{j}\right)\right\}$

所以原问题可以化为如下优化问题

$\begin{array}{ll}{\text { maximize } } & {1^{T} u} \\ {\text { subject to } } & {x \succeq 0} \\ {} & {A x \preceq c^{\text {max } }} \\ {} & {p_{j} x_{j} \geq u_{j}, \quad p_{j} q_{j}+p_{j}^{\text {disc } }\left(x_{j}-q_{j}\right) \geq u_{j}, \quad j=1, \ldots, n}\end{array}$

接下来使用LP即可。

补充题

1

A = [ 1 2 0 1;
0 0 3 1;
0 3 1 1;
2 1 2 5;
1 0 3 2];
cmax = [100;100;100;100;100];
p = [3;2;7;6];
pdisc = [2;1;4;2];
q = [4; 10 ;5; 10];

cvx_begin
    variable x(4)
    maximize(sum(min(p.*x, p .* q + pdisc .* (x - q))))
    subject to
        x >= 0;
        A * x <= cmax;
cvx_end

x
r = min(p.*x, p .* q + pdisc .* (x - q))
totr = sum(r)
avgPrice = r ./ x

2

(a)上述约束等价于

$\begin{aligned} x + 2y & = 0\\ x - y&=0 \end{aligned}$

对应代码为

cvx_begin
    variable x(4);
    variable y(4);
    subject to
        x + 2 * y == 0
        x - y == 0
cvx_end

(b)上述约束等价于

$\begin{aligned} x + y & =z\\ z^4 &\le x-y \end{aligned}$

对应代码为

cvx_begin
    variables x y t;
    subject to
        x + y == t
        t^4 <= x - y
cvx_end

(c)引入变量即可

$\begin{aligned} x&=\frac 1 u\\ y &=\frac1 v\\ u + v&\le 1\\ u &\ge 0\\ v &\ge 0 \end{aligned}$

对应代码为

cvx_begin
    variables u v;
    subject to
        u + v<= 1
        u >= 0
        v >= 0
cvx_end

(d)引入变量即可

$\begin{aligned} \max(x, 1) & = u\\ \max(y, 2) & =v \end{aligned}$

对应代码为

cvx_begin
    variables x y u v;
    subject to
        norm([u v]) <= 3 * x + y
        u >= x
        u >= 1
        v >= y
        v >= 2
cvx_end

(e)引入变量即可

$\begin{aligned} \frac 1 y &= u \end{aligned}$

对应代码为

cvx_begin
    variables x u
    subject to
        x >= u
        x >= 0
        u > 0
cvx_end

(f)使用quad_over_lin函数即可

cvx_begin
    variables x y
    subject to
        quad_over_lin(x + y, sqrt(y)) <= x - y + 5
cvx_end

(g)引入变量即可

$\begin{aligned} x^3 &= u\\ y^3 &=v \end{aligned}$

对应代码为

cvx_begin
    variables u v
    subject to
       u + v <= 1
       u >= 0
       v >= 0
cvx_end

(h)注意到

$\sqrt{x y-z^{2} }=\sqrt{y\left(x-z^{2} / y\right)}$

所以可以将原问题转化为

cvx_begin
    variables x y z
    subject to
        x + z <= 1 + geo_mean([y, x - quad_over_lin(z, y)])
        x >= 0
        y >= 0
cvx_end

3

Equal lamp powers

%Equal lamp powers
N = 100
gamma = linspace(0, 1, N);
f0 = zeros(1, N);
for i = 1: N
    f0(i) = max(abs(log(A * gamma(i) * ones(m, 1))));
end
figure(2)
plot(gamma, f0)
gamma_opt = gamma(f0 == min(f0))
p1 = gamma_opt * ones(m, 1)
max(abs(log(A * p1)))

Least-squares with saturation

%Least-squares with saturation
p2 = A \ ones(n, 1);
p2(p2 < 0) = 0;
p2(p2 > 1) = 1;
p2
max(abs(log(A * p2)))

Regularized least-squares

注意到

$\begin{aligned} \|A p-1\|_{2}^{2}+\rho\|p-(1 / 2) \mathbf{1}\|_{2}^{2} &= \left\| \left[ \begin{matrix} A\\ \sqrt \rho I \end{matrix} \right] p - \left[ \begin{matrix} \mathbf{1}\\ \sqrt {\rho}(1/2) \mathbf{1} \end{matrix} \right]\right\|_2^2 \end{aligned}$

所以代码为

%Regularized least-squares
N1 = 10000;
Rho = linspace(0, 5, N1);
for i = 1: N1
    rho = Rho(i);
    p3 = [A; sqrt(rho) * eye(m)] \ [ones(n, 1); sqrt(rho) * 0.5 * ones(m, 1)];
    cnt = 0;
    cnt = sum(p3 < 0);
    cnt = cnt + sum(p3 > 1);
    if cnt == 0
        break
    end
end
p3
max(abs(log(A * p3)))

Chebyshev approximation

%Chebyshev approximation
cvx_begin
    variable p4(m)
    minimize(norm(A * p4 - ones(n, 1), inf))
    subject to
        p4 >= 0
        p4 <= 1
cvx_end
p4
max(abs(log(A * p4)))

Exact solution

%Exact solution
cvx_begin
    variable p5(m)
    minimize(max([A * p5; inv_pos(A * p5)]))
    subject to
        p5 <= 1
        p5 >= 0
cvx_end
p5
max(abs(log(A * p5)))