EE364A Homework 3

课程主页: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 国际 转载请保留原文链接及作者。