EE364A Homework 3

发表于 | 分类于 | 阅读次数：
本文字数： 9.1k | 阅读时长 ≈ 8 分钟

课程主页：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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
x =
    4.0000
   22.5000
   31.0000
    1.5000
r =
   12.0000
   32.5000
  139.0000
    9.0000
totr =
  192.5000
avgPrice =
    3.0000
    1.4444
    4.4839
    6.0000

2

(a)上述约束等价于

对应代码为

1
2
3
4
5
6
7
cvx_begin
    variable x(4);
    variable y(4);
    subject to
        x + 2 * y == 0
        x - y == 0
cvx_end

(b)上述约束等价于

对应代码为

1
2
3
4
5
6
cvx_begin
    variables x y t;
    subject to
        x + y == t
        t^4 <= x - y
cvx_end

(c)引入变量即可

对应代码为

1
2
3
4
5
6
7
cvx_begin
    variables u v;
    subject to
        u + v<= 1
        u >= 0
        v >= 0
cvx_end

(d)引入变量即可

对应代码为

1
2
3
4
5
6
7
8
9
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)引入变量即可

对应代码为

1
2
3
4
5
6
7
cvx_begin
    variables x u
    subject to
        x >= u
        x >= 0
        u > 0
cvx_end

(f)使用quad_over_lin函数即可

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

(g)引入变量即可

对应代码为

1
2
3
4
5
6
7
cvx_begin
    variables u v
    subject to
       u + v <= 1
       u >= 0
       v >= 0
cvx_end

(h)注意到

所以可以将原问题转化为

1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
8
9
10
11
12
%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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
p1 =
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
    0.3434
ans =
    0.4732
Least-squares with saturation
1
2
3
4
5
6
%Least-squares with saturation
p2 = A \ ones(n, 1);
p2(p2 < 0) = 0;
p2(p2 > 1) = 1;
p2
max(abs(log(A * p2)))
1
2
3
4
5
6
7
8
9
10
11
12
13
p2 =
     1
     0
     1
     0
     0
     1
     0
     1
     0
     1
ans =
    0.8628
Regularized least-squares

注意到

所以代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
%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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
p3 =
    0.5004
    0.4777
    0.0833
    0.0002
    0.4561
    0.4354
    0.4597
    0.4307
    0.4034
    0.4526
ans =
    0.4439
Chebyshev approximation
1
2
3
4
5
6
7
8
9
10
%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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
p4 =
    1.0000
    0.1165
    0.0000
    0.0000
    1.0000
    0.0000
    1.0000
    0.0249
    0.0000
    1.0000
ans =
    0.4198
Exact solution
1
2
3
4
5
6
7
8
9
10
%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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
p5 =
    1.0000
    0.2023
    0.0000
    0.0000
    1.0000
    0.0000
    1.0000
    0.1882
    0.0000
    1.0000
ans =
    0.3575

本文标题:EE364A Homework 3

文章作者:Doraemonzzz

发布时间:2019年10月09日 - 23:23:00

最后更新:2019年10月09日 - 23:28:04

原始链接:http://doraemonzzz.com/2019/10/09/EE364A Homework 3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。