没有合适的资源?快使用搜索试试~ 我知道了~
首页Additional Exercises for Convex Optimization
Additional Exercises for Convex Optimization
5星 · 超过95%的资源 需积分: 5 104 下载量 58 浏览量
更新于2023-03-16
评论 3
收藏 4.82MB PDF 举报
国内找了很久都没找到,跑去外网下了一个,分享给大家,Stanford教授Stephen Boyd的cvx optimization课程附加练习的答案
资源详情
资源评论
资源推荐
Additional Exercises for Convex Optimization
Stephen Boyd Lieven Vandenberghe
March 18, 2016
This is a collection of additional exercises, meant to supplement those found in the book Convex
Optimization, by Stephen Boyd and Lieven Vandenberghe. These exercises were used in several
courses on convex optimization, EE364a (Stanford), EE236b (UCLA), or 6.975 (MIT), usually for
homework, but sometimes as exam questions. Some of the exercises were originally written for the
book, but were removed at some point. Many of them include a computational component using
CVX, a Matlab package for convex optimization; files required for these exercises can be found at
the book web site www.stanford.edu/~boyd/cvxbook/. We are in the process of adapting many
of these problems to be compatible with two other packages for convex optimization: CVXPY
(Python) and Convex.jl (Julia). Some of the exercises require a knowledge of elementary analysis.
You are free to use these exercises any way you like (for example in a course you teach), provided
you acknowledge the source. In turn, we gratefully acknowledge the teaching assistants (and in
some cases, students) who have helped us develop and debug these exercises. Pablo Parrilo helped
develop some of the exercises that were originally used in 6.975.
Course instructors can obtain solutions by email to us. Please specify the course you are teaching
and give its URL.
We’ll update this document as new exercises become available, so the exercise numbers and
sections will occasionally change. We have categorized the exercises into sections that follow the
book chapters, as well as various additional application areas. Some exercises fit into more than
one section, or don’t fit well into any section, so we have just arbitrarily assigned these.
Stephen Boyd and Lieven Vandenberghe
1
Contents
1 Convex sets 3
2 Convex functions 8
3 Convex optimization problems 29
4 Duality 95
5 Approximation and fitting 136
6 Statistical estimation 204
7 Geometry 235
8 Unconstrained and equality constrained minimization 279
9 Interior point methods 298
10 Mathematical background 321
11 Circuit design 324
12 Signal processing and communications 350
13 Finance 375
14 Mechanical and aerospace engineering 455
15 Graphs and networks 513
16 Energy and power 533
17 Miscellaneous applications 576
2
1 Convex sets
1.1 Is the set {a ∈ R
k
| p(0) = 1, |p(t)| ≤ 1 for α ≤ t ≤ β}, where
p(t) = a
1
+ a
2
t + ···+ a
k
t
k−1
,
convex?
Solution. Yes, it is convex; it is the intersection of an infinite number of slabs,
{a | − 1 ≤ a
1
+ a
2
t + ···+ a
k
t
k−1
≤ 1},
parametrized by t ∈ [α, β], and the hyperplane
{a | a
0
= 1}.
1.2 Set distributive characterization of convexity. [?, p21], [?, Theorem 3.2] Show that C ⊆ R
n
is
convex if and only if (α + β)C = αC + βC for all nonnegative α, β.
Solution. The equality is trivially true for α = β = 0, so we will assume that α + β 6= 0, and
dividing by α + β, we can rephrase the theorem as follows: C is convex if and only if
C = θC + (1 − θ)C
for 0 ≤ θ ≤ 1.
C ⊆ θC + (1 − θ)C for all θ ∈ [0, 1] is true for any set C, because x = θx + (1 − θ)x.
C ⊇ θC + (1 − θ)C for all θ ∈ [0, 1] is just a rephrasing of Jensen’s inequality.
1.3 Composition of linear-fractional functions. Suppose φ : R
n
→ R
m
and ψ : R
m
→ R
p
are the
linear-fractional functions
φ(x) =
Ax + b
c
T
x + d
, ψ(y) =
Ey + f
g
T
y + h
,
with domains dom φ = {x | c
T
x + d > 0}, dom ψ = {y | g
T
x + h > 0}. We associate with φ and
ψ the matrices
"
A b
c
T
d
#
,
"
E f
g
T
h
#
,
respectively.
Now consider the composition Γ of ψ and φ, i.e., Γ(x) = ψ(φ(x)), with domain
dom Γ = {x ∈ dom φ | φ(x) ∈ dom ψ}.
Show that Γ is linear-fractional, and that the matrix associated with it is the product
"
E f
g
T
h
#"
A b
c
T
d
#
.
3
Solution. We have, for x ∈ dom Γ,
Γ(x) =
E((Ax + b)/(c
T
x + d)) + f
g
T
(Ax + b)/(c
T
x + d) + h
.
Multiplying numerator and denominator by c
T
x + d yields
Γ(x) =
EAx + Eb + f c
T
x + fd
g
T
Ax + g
T
b + hc
T
x + hd
=
(EA + fc
T
)x + (Eb + f d)
(g
T
A + hc
T
)x + (g
T
b + hd)
,
which is the linear fractional function associated with the product matrix.
1.4 Dual of exponential cone. The exponential cone K
exp
⊆ R
3
is defined as
K
exp
= {(x, y, z) | y > 0, ye
x/y
≤ z}.
Find the dual cone K
∗
exp
.
We are not worried here about the fine details of what happens on the boundaries of these cones,
so you really needn’t worry about it. But we make some comments here for those who do care
about such things.
The cone K
exp
as defined above is not closed. To obtain its closure, we need to add the points
{(x, y, z) | x ≤ 0, y = 0, z ≥ 0}.
(This makes no difference, since the dual of a cone is equal to the dual of its closure.)
Solution. The dual cone can be expressed as
K
∗
exp
= cl{(u, v, w) | u < 0, −ue
v/u
≤ ew}
= {(u, v, w) | u < 0, −ue
v/u
≤ ew} ∪ {(0, v, w) | v ≥ 0, w ≥ 0},
where cl means closure. We didn’t expect people to add the points on the boundary, i.e., to work
out the second set in the second line.
The dual cone can be expressed several other ways as well. The conditions u < 0, −ue
v/u
≤ ew
can be expressed as
(u/w) log(−u/w) + v/w − u/w ≥ 0,
or
u log(−u/w) + v − u ≥ 0,
or
log(−u/w) ≤ 1 − (v/u).
Now let’s derive the result. For (u, v, w) to be in K
∗
exp
, we need to have ux + vy + wz ≥ 0 whenever
y > 0 and ye
x/y
≤ z. Thus, we must have w ≥ 0; otherwise we can make ux + vy + wz negative
4
by choosing a large enough z. Now let’s see what happens when w = 0. In this case we need
ux + vy ≥ 0 for all y > 0. This happens only if u = 0 and v ≥ 0. So points with
u = 0, v ≥ 0, w = 0
are in K
∗
exp
.
Let’s now consider the case w > 0. We’ll minimize ux + vy + wz over all x, y and z that satisfy
y > 0 and ye
x/y
≤ z. Since w > 0, we minimize over z by taking z = ye
x/y
, which yields
ux + vy + wye
x/y
.
Now we will minimize over x. If u > 0, this is unbounded below as x → −∞. If u = 0, the minimum
is not achieved, but occurs as x → −∞; the minimum value is then vy. This has a nonnegative
minimum value over all y > 0 only when v ≥ 0. Thus we find that points satisfying
u = 0, v ≥ 0, w > 0
are in K
∗
exp
.
If u < 0, the minimum of ux + vy + wye
x/y
occurs when its derivative with respect to x vanishes.
This leads to u+we
x/y
= 0, i.e., x = y log(−u/w). For this value of x the expression above becomes
y(u log(−u/w) + v − u).
Now we minimize over y > 0. We get −∞ if u log(−u/w)+v−u < 0; we get 0 if u log(−u/w)+v−u ≥
0.
So finally, we have our condition:
u log(−u/w) + v − u ≥ 0, u < 0, w > 0.
Dividing by u and taking the exponential, we can write this as
−ue
v/u
≤ ew, u < 0.
(The condition w > 0 is implied by these two conditions.)
Finally, then, we have
K
∗
exp
= {(u, v, w) | u < 0, −ue
v/u
≤ ew} ∪ {(0, v, w) | v ≥ 0, w ≥ 0}.
1.5 Dual of intersection of cones. Let C and D be closed convex cones in R
n
. In this problem we will
show that
(C ∩ D)
∗
= C
∗
+ D
∗
.
Here, + denotes set addition: C
∗
+ D
∗
is the set {u + v | u ∈ C
∗
, v ∈ D
∗
}. In other words, the
dual of the intersection of two closed convex cones is the sum of the dual cones.
(a) Show that C ∩D and C
∗
+ D
∗
are convex cones. (In fact, C ∩D and C
∗
+ D
∗
are closed, but
we won’t ask you to show this.)
5
剩余631页未读,继续阅读
Dreama_CS
- 粉丝: 3
- 资源: 11
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1