没有合适的资源？快使用搜索试试~ 我知道了~

首页Convex Optimization solutions.pdf

资源详情

资源推荐

Convex Optimization

Solutions Manual

Stephen Boyd Lieven Vandenberghe

January 4, 2006

Chapter 2

Convex sets

Exercises

Exercises

Deﬁnition of convexity

2.1 Let C ⊆ R

n

be a convex set, with x

1

, . . . , x

k

∈ C, and let θ

1

, . . . , θ

k

∈ R satisfy θ

i

≥ 0,

θ

1

+ ··· + θ

k

= 1. Show that θ

1

x

1

+ ··· + θ

k

x

k

∈ C. (The deﬁnition of convexity is that

this holds for k = 2; you must show it for arbitrary k.) Hint. Use induction on k.

Solution. This is readily shown by induction from the deﬁnition of convex set. We illus-

trate the idea for k = 3, leaving the general case to the reader. Suppose that x

1

, x

2

, x

3

∈ C,

and θ

1

+ θ

2

+ θ

3

= 1 with θ

1

, θ

2

, θ

3

≥ 0. We will show that y = θ

1

x

1

+ θ

2

x

2

+ θ

3

x

3

∈ C.

At least one of the θ

i

is not equal to one; without loss of generality we can assume that

θ

1

6= 1. Then we can write

y = θ

1

x

1

+ (1 − θ

1

)(µ

2

x

2

+ µ

3

x

3

)

where µ

2

= θ

2

/(1 − θ

1

) and µ

2

= θ

3

/(1 − θ

1

). Note that µ

2

, µ

3

≥ 0 and

µ

1

+ µ

2

=

θ

2

+ θ

3

1 − θ

1

=

1 − θ

1

1 − θ

1

= 1.

Since C is convex and x

2

, x

3

∈ C, we conclude that µ

2

x

2

+ µ

3

x

3

∈ C. Since this point

and x

1

are in C, y ∈ C.

2.2 Show that a set is convex if and only if its intersection with any line is convex. Show that

a set is aﬃne if and only if its intersection with any line is aﬃne.

Solution. We prove the ﬁrst part. The intersection of two convex sets is convex. There-

fore if S is a convex set, the intersection of S with a line is convex.

Conversely, suppose the intersection of S with any line is convex. Take any two distinct

points x

1

and x

2

∈ S. The intersection of S with the line through x

1

and x

2

is convex.

Therefore convex combinations of x

1

and x

2

belong to the intersection, hence also to S.

2.3 Midpoint convexity. A set C is midpoint convex if whenever two points a, b are in C, the

average or midpoint (a + b)/2 is in C. Obviously a convex set is midpoint convex. It can

be proved that under mild conditions midpoint convexity implies convexity. As a simple

case, prove that if C is closed and midpoint convex, then C is convex.

Solution. We have to show that θx + (1 − θ)y ∈ C for all θ ∈ [0, 1] and x, y ∈ C. Let

θ

(k)

be the binary number of length k, i.e., a number of the form

θ

(k)

= c

1

2

−1

+ c

2

2

−2

+ ··· + c

k

2

−k

with c

i

∈ {0, 1}, closest to θ. By midpoint convexity (applied k times, recursively),

θ

(k)

x + (1 − θ

(k)

)y ∈ C. Because C is closed,

lim

k→∞

(θ

(k)

x + (1 − θ

(k)

)y) = θx + (1 − θ)y ∈ C.

2.4 Show that the convex hull of a set S is the intersection of all convex sets that contain S.

(The same method can be used to show that the conic, or aﬃne, or linear hull of a set S

is the intersection of all conic sets, or aﬃne sets, or subspaces that contain S.)

Solution. Let H be the convex hull of S and let D be the intersection of all convex sets

that contain S, i.e.,

D =

\

{D | D convex, D ⊇ S}.

We will show that H = D by showing that H ⊆ D and D ⊆ H.

First we show that H ⊆ D. Suppose x ∈ H, i.e., x is a convex combination of some

points x

1

, . . . , x

n

∈ S. Now let D be any convex set such that D ⊇ S. Evidently, we have

x

1

, . . . , x

n

∈ D. Since D is convex, and x is a convex combination of x

1

, . . . , x

n

, it follows

that x ∈ D. We have shown that for any convex set D that contains S, we have x ∈ D.

This means that x is in the intersection of all convex sets that contain S, i.e., x ∈ D.

Now let us show that D ⊆ H. Since H is convex (by deﬁnition) and contains S, we must

have H = D for some D in the construction of D, proving the claim.

2 Convex sets

Examples

2.5 What is the distance between two parallel hyperplanes {x ∈ R

n

| a

T

x = b

1

} and {x ∈

R

n

| a

T

x = b

2

}?

Solution. The distance between the two hyperplanes is |b

1

− b

2

|/kak

2

. To see this,

consider the construction in the ﬁgure below.

PSfrag replacements

a

x

1

= (b

1

/kak

2

)a

x

2

= (b

2

/kak

2

)a

a

T

x = b

2

a

T

x = b

1

The distance between the two hyperplanes is also the distance between the two points

x

1

and x

2

where the hyperplane intersects the line through the origin and parallel to the

normal vector a. These points are given by

x

1

= (b

1

/kak

2

2

)a, x

2

= (b

2

/kak

2

2

)a,

and the distance is

kx

1

− x

2

k

2

= |b

1

− b

2

|/kak

2

.

2.6 When does one halfspace contain another? Give conditions under which

{x | a

T

x ≤ b} ⊆ {x | ˜a

T

x ≤

˜

b}

(where a 6= 0, ˜a 6= 0). Also ﬁnd the conditions under which the two halfspaces are equal.

Solution. Let H = {x | a

T

x ≤ b} and

˜

H = {x | ˜a

T

x ≤

˜

b}. The conditions are:

• H ⊆

˜

H if and only if there exists a λ > 0 such that ˜a = λa and

˜

b ≥ λb.

• H =

˜

H if and only if there exists a λ > 0 such that ˜a = λa and

˜

b = λb.

Let us prove the ﬁrst condition. The condition is clearly suﬃcient: if ˜a = λa and

˜

b ≥ λb

for some λ > 0, then

a

T

x ≤ b =⇒ λa

T

x ≤ λb =⇒ ˜a

T

x ≤

˜

b,

i.e., H ⊆

˜

H.

To prove necessity, we distinguish three cases. First suppose a and ˜a are not parallel. This

means we can ﬁnd a v with ˜a

T

v = 0 and a

T

v 6= 0. Let ˆx be any point in the intersection

of H and

˜

H, i.e., a

T

ˆx ≤ b and ˜a

T

x ≤

˜

b. We have a

T

(ˆx + tv) = a

T

ˆx ≤ b for all t ∈ R.

However ˜a

T

(ˆx + tv) = ˜a

T

ˆx + t˜a

T

v, and since ˜a

T

v 6= 0, we will have ˜a

T

(ˆx + tv) >

˜

b for

suﬃciently large t > 0 or suﬃciently small t < 0. In other words, if a and ˜a are not

parallel, we can ﬁnd a point ˆx + tv ∈ H that is not in

˜

H, i.e., H 6⊆

˜

H.

Next suppose a and ˜a are parallel, but point in opposite directions, i.e., ˜a = λa for some

λ < 0. Let ˆx be any point in H. Then ˆx−ta ∈ H for all t ≥ 0. However for t large enough

we will have ˜a

T

(ˆx − ta) = ˜a

T

ˆx + tλkak

2

2

>

˜

b, so ˆx − ta 6∈

˜

H. Again, this shows H 6⊆

˜

H.

Exercises

Finally, we assume ˜a = λa for some λ > 0 but

˜

b < λb. Consider any point ˆx that satisﬁes

a

T

ˆx = b. Then ˜a

T

ˆx = λa

T

ˆx = λb >

˜

b, so ˆx 6∈

˜

H.

The proof for the second part of the problem is similar.

2.7 Voronoi description of halfspace. Let a and b be distinct points in R

n

. Show that the set

of all points that are closer (in Euclidean norm) to a than b, i.e., {x | kx−ak

2

≤ kx−bk

2

},

is a halfspace. Describe it explicitly as an inequality of the form c

T

x ≤ d. Draw a picture.

Solution. Since a norm is always nonnegative, we have kx − ak

2

≤ kx − bk

2

if and only

if kx − ak

2

2

≤ kx − bk

2

2

, so

kx − ak

2

2

≤ kx − bk

2

2

⇐⇒ (x − a)

T

(x − a) ≤ (x − b)

T

(x − b)

⇐⇒ x

T

x − 2a

T

x + a

T

a ≤ x

T

x − 2b

T

x + b

T

b

⇐⇒ 2(b − a)

T

x ≤ b

T

b − a

T

a.

Therefore, the set is indeed a halfspace. We can take c = 2(b − a) and d = b

T

b − a

T

a.

This makes good geometric sense: the points that are equidistant to a and b are given by

a hyperplane whose normal is in the direction b − a.

2.8 Which of the following sets S are polyhedra? If possible, express S in the form S =

{x | Ax b, F x = g}.

(a) S = {y

1

a

1

+ y

2

a

2

| − 1 ≤ y

1

≤ 1, − 1 ≤ y

2

≤ 1}, where a

1

, a

2

∈ R

n

.

(b) S = {x ∈ R

n

| x 0, 1

T

x = 1,

P

n

i=1

x

i

a

i

= b

1

,

P

n

i=1

x

i

a

2

i

= b

2

}, where

a

1

, . . . , a

n

∈ R and b

1

, b

2

∈ R.

(c) S = {x ∈ R

n

| x 0, x

T

y ≤ 1 for all y with kyk

2

= 1}.

(d) S = {x ∈ R

n

| x 0, x

T

y ≤ 1 for all y with

P

n

i=1

|y

i

| = 1}.

Solution.

(a) S is a polyhedron. It is the parallelogram with corners a

1

+ a

2

, a

1

− a

2

, −a

1

+ a

2

,

−a

1

− a

2

, as shown below for an example in R

2

.

PSfrag replacements

a

1

a

2

c

2

c

1

For simplicity we assume that a

1

and a

2

are independent. We can express S as the

intersection of three sets:

• S

1

: the plane deﬁned by a

1

and a

2

• S

2

= {z + y

1

a

1

+ y

2

a

2

| a

T

1

z = a

T

2

z = 0, −1 ≤ y

1

≤ 1}. This is a slab parallel to

a

2

and orthogonal to S

1

• S

3

= {z + y

1

a

1

+ y

2

a

2

| a

T

1

z = a

T

2

z = 0, −1 ≤ y

2

≤ 1}. This is a slab parallel to

a

1

and orthogonal to S

1

Each of these sets can be described with linear inequalities.

• S

1

can be described as

v

T

k

x = 0, k = 1, . . . , n − 2

where v

k

are n −2 independent vectors that are orthogonal to a

1

and a

2

(which

form a basis for the nullspace of the matrix [a

1

a

2

]

T

).

剩余301页未读，继续阅读

沧海一声喵

- 粉丝: 1
- 资源: 1

上传资源 快速赚钱

- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助

#### 会员权益专享

### 最新资源

- 基于嵌入式ARMLinux的播放器的设计与实现 word格式.doc
- 经典：大学答辩通过_基于ARM微处理器的嵌入式指纹识别系统设计.pdf
- 嵌入式系统课程设计.doc
- 基于飞思卡尔控制器的智能寻迹车设计ARM基础课程课程设计.doc
- 下载基于ARM7的压电陶瓷换能器导纳圆测量仪的研制PDF格式可编辑.pdf
- 课程设计基于ARM的嵌入式家居监控系统的研究与设计.doc
- 论文基于嵌入式ARM的图像采集处理系统设计.doc
- 嵌入式基于ARM9的中断驱动程序设计—课程设计.doc
- 在Linux系统下基于ARM嵌入式的俄罗斯方块.doc
- STK-MirrorStore Product Release Notes（96130）-44
- STK-MirrorStore Storage Connectivity Guide for StorageTek Disk A
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科毕业设计.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-.doc
- 龙虾养殖远程监控系统的设计与实现数据采集上位-机软件模块-本科生毕业论文.doc
- 麻阳风貌展示网站的设计与实现毕业论文.pdf
- 高速走丝气中电火花线切割精加工编程设计.doc

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈

安全验证

文档复制为VIP权益，开通VIP直接复制

信息提交成功