Stephen Boyd & Lieven Vandenberghe 凸优化额外练习资源

需积分: 10 47 浏览量更新于2024-07-19 2 收藏 1.07MB PDF 举报

"《凸优化课后额外练习》是一份补充材料，由Stephen Boyd和Lieven Vandenberghe编撰，旨在深化学习者对凸优化理论的理解。这些练习旨在配合他们的经典著作《凸优化》进行学习，适用于斯坦福大学的EE364a课程、UCLA的EE236b以及麻省理工学院的6.975课程。它们通常被用作学生的课后作业或考试题目，特别是那些涉及计算部分的，这些部分可能依赖于Matlab包CVX，其配套文件可在<www.stanford.edu/~boyd/cvxbook/>网站找到。本书中的许多习题最初是为原书设计的，但随着技术发展，作者团队正在将它们适配到其他两种优化工具：Python语言的CVXPY和Julia语言的Convex.jl。这意味着，即使一些习题要求具备基础分析知识，学习者依然可以利用这些资源，只要在使用时注明原作者。同时，也要感谢那些在教学过程中贡献了智慧的助教和学生，他们的努力使得这些资源得以不断完善。这份额外的练习集不仅包含了理论上的挑战，还提供了实践操作的机会，有助于巩固对凸优化问题求解策略、梯度下降法、拉格朗日乘子法等核心概念的掌握。对于希望深入理解并提升解决实际问题能力的读者来说，这是一个不可或缺的参考资料。通过解决这些练习，学生不仅可以检验自己的理论知识，还能锻炼编程技巧和实际问题建模的能力。"

3.7 The illumination problem. In lecture 1 we encountered the function

f(p) = max

i=1,...,n

|log a

p − log I

des

where a

∈ R

, and I

des

> 0 are given, and p ∈ R

(a) Show that exp f is convex on {p | a

p > 0, i = 1, . . . , n }.

(b) Show that the constraint ‘no more than half of the total power is in any 10 lamps’ is convex

(i.e., the set of vectors p that satisfy the constraint is convex).

3.8 Schur complements and LMI representation. Recognizing Schur complements (see §A5.5) often

helps to represent nonlinear convex constraints as linear matrix inequalities (LMIs). Consider the

function

f(x) = (Ax + b)

+ x

+ ··· + x

)

−1

(Ax + b)

where A ∈ R

m×n

, b ∈ R

, and P

= P

∈ R

m×m

, with domain

dom f = {x ∈ R

| P

+ x

+ ··· + x

 0}.

This is the composition of the matrix fractional function and an aﬃne mapping, and so is convex.

Give an LMI representation of epi f. That is, ﬁnd a symmetric matrix F (x, t), aﬃne in (x, t), for

which

x ∈ dom f, f(x) ≤ t ⇐⇒ F (x, t)  0.

Remark. LMI representations, such as the one you found in this exercise, can be directly used in

software systems such as CVX.

3.9 Complex least-norm problem. We consider the complex least `

-norm problem

minimize kxk

subject to Ax = b,

where A ∈ C

m×n

, b ∈ C

, and the variable is x ∈ C

. Here k · k

denotes the `

-norm on C

deﬁned as

kxk

i=1

1/p

for p ≥ 1, and kxk

∞

= max

i=1,...,n

|. We assume A is full rank, and m < n.

(a) Formulate the complex least `

-norm problem as a least `

-norm problem with real problem

data and variable. Hint. Use z = (<x, =x) ∈ R

as the variable.

(b) Formulate the complex least `

∞

-norm problem as an SOCP.

matrix A, you can use the Matlab command A = randn(m,n) + i*randn(m,n). Similarly,

use b = randn(m,1) + i*randn(m,1) to generate the vector b. Use the Matlab command

scatter to plot the optimal solutions of the two problems on the complex plane, and comment

(brieﬂy) on what you observe. You can solve the problems using the CVX functions norm(x,2)

and norm(x,inf), which are overloaded to handle complex arguments. To utilize this feature,

you will need to declare variables to be complex in the variable statement. (In particular,

you do not have to manually form or solve the SOCP from part (b).)

3.10 Linear programming with random cost vector. We consider the linear program

minimize c

subject to Ax  b.

Here, however, the cost vector c is random, normally distributed with mean E c = c

and covariance

E(c − c

)(c − c

)

= Σ. (A, b, and x are deterministic.) Thus, for a given x ∈ R

, the cost c

x is

a (scalar) Gaussian variable.

We can attach several diﬀerent meanings to the goal ‘minimize c

x’; we explore some of these

below.

(a) How would you minimize the expected cost E c

x subject to Ax  b?

(b) In general there is a tradeoﬀ between small expected cost and small cost variance. One way

to take variance into account is to minimize a linear combination

E c

x + γ var(c

x) (3)

of the expected value E c

x and the variance var(c

x) = E(c

− (E c

. This is called

the ‘risk-sensitive cost’, and the parameter γ ≥ 0 is called the risk-aversion parameter, since

it sets the relative values of cost variance and expected value. (For γ > 0, we are willing to

tradeoﬀ an increase in expected cost for a decrease in cost variance). How would you minimize

the risk-sensitive cost? Is this problem a convex optimization problem? Be as speciﬁc as you

can.

this problem a convex optimization problem?

(d) Another way to deal with the randomness in the cost c

x is to formulate the problem as

minimize β

subject to prob(c

x ≥ β) ≤ α

Ax  b.

Here, α is a ﬁxed parameter, which corresponds roughly to the reliability we require, and

might typically have a value of 0.01. Is this problem a convex optimization problem? Be as

speciﬁc as you can. Can you obtain risk-seeking by choice of α? Explain.

3.11 Formulate the following optimization problems as semideﬁnite programs. The variable is x ∈ R

;

F (x) is deﬁned as

F (x) = F

+ x

+ ··· + x

with F

∈ S

. The domain of f in each subproblem is dom f = {x ∈ R

| F (x)  0}.

(a) Minimize f(x) = c

F (x)

−1

c where c ∈ R

(b) Minimize f(x) = max

i=1,...,K

F (x)

−1

where c

∈ R

, i = 1, . . . , K.

kck

≤1

F (x)

−1

(d) Minimize f(x) = E(c

F (x)

−1

c) where c is a random vector with mean E c = ¯c and covariance

E(c − ¯c)(c − ¯c)

= S.

where f

: R

→ R are convex, and x ∈ R

is the variable. For simplicity, we will assume that

dom f

= R

for each i.

Now introduce a new scalar variable t ∈ R and form the convex problem

minimize c

subject to tf

(x/t) ≤ 0, i = 1, . . . , m,

Ax = b, t = 1.

Deﬁne

K = cl{(x, t) ∈ R

n+1

| tf

(x/t) ≤ 0, i = 1, . . . , m, t > 0}.

Then our original problem can be expressed as

minimize c

subject to (x, t) ∈ K,

Ax = b, t = 1.

This is a conic problem when K is proper.

You will relate some properties of the original problem to K.

(a) Show that K is a convex cone. (It is closed by deﬁnition, since we take the closure.)

(b) Suppose the original problem is strictly feasible, i.e., there exists a point ¯x with f

(x) < 0,

i = 1, . . . , m. (This is called Slater’s condition.) Show that K has nonempty interior.

(x) ≤ 0, i = 1, . . . , m} is

bounded. Show that K is pointed.

3.16 Exploring nearly optimal points. An optimization algorithm will ﬁnd an optimal point for a problem,

provided the problem is feasible. It is often useful to explore the set of nearly optimal points. When

a problem has a ‘strong minimum’, the set of nearly optimal points is small; all such points are close

to the original optimal point found. At the other extreme, a problem can have a ‘soft minimum’,

which means that there are many points, some quite far from the original optimal point found, that

are feasible and have nearly optimal objective value. In this problem you will use a typical method

to explore the set of nearly optimal points.

We start by ﬁnding the optimal value p

of the given problem

minimize f

(x)

subject to f

(x) ≤ 0, i = 1, . . . , m

(x) = 0, i = 1, . . . , p,

as well as an optimal point x

∈ R

. We then pick a small positive number , and a vector c ∈ R

and solve the problem

minimize c

subject to f

(x) ≤ 0, i = 1, . . . , m

(x) = 0, i = 1, . . . , p

(x) ≤ p

+ .

Note that any feasible point for this problem is -suboptimal for the original problem. Solving this

problem multiple times, with diﬀerent c’s, will generate (perhaps diﬀerent) -suboptimal points. If

the problem has a strong minimum, these points will all be close to each other; if the problem has

a weak minimum, they can be quite diﬀerent.

There are diﬀerent strategies for choosing c in these experiments. The simplest is to choose the

c’s randomly; another method is to choose c to have the form ±e

, for i = 1, . . . , n. (This method

gives the ‘range’ of each component of x, over the -suboptimal set.)

You will carry out this method for the following problem, to determine whether it has a strong

minimum or a weak minimum. You can generate the vectors c randomly, with enough samples for

you to come to your conclusion. You can pick  = 0.01p

, which means that we are considering the

set of 1% suboptimal points.

The problem is a minimum fuel optimal control problem for a vehicle moving in R

. The position

at time kh is given by p(k) ∈ R

, and the velocity by v(k) ∈ R

, for k = 1, . . . , K. Here h > 0 is

the sampling period. These are related by the equations

p(k + 1) = p(k) + hv(k), v(k + 1) = (1 − α)v(k) + (h/m)f(k), k = 1, . . . , K − 1,

where f(k) ∈ R

is the force applied to the vehicle at time kh, m > 0 is the vehicle mass, and

α ∈ (0, 1) models drag on the vehicle; in the absense of any other force, the vehicle velocity decreases

by the factor 1 − α in each discretized time interval. (These formulas are approximations of more

accurate formulas that involve matrix exponentials.)

The force comes from two thrusters, and from gravity:

f(k) =

cos θ

sin θ

(k) +

cos θ

sin θ

(k) +

−mg

, k = 1, . . . , K − 1.

Here u

(k) ∈ R and u

(k) ∈ R are the (nonnegative) thruster force magnitudes, θ

and θ

are the

directions of the thrust forces, and g = 10 is the constant acceleration due to gravity.

The total fuel use is

F =

K−1

k=1

(k) + u

(k)) .

(Recall that u

(k) ≥ 0, u

(k) ≥ 0.)

The problem is to minimize fuel use subject to the initial condition p(1) = 0, v(1) = 0, and the

way-point constraints

p(k

) = w

, i = 1, . . . , M.

(These state that at the time hk

, the vehicle must pass through the location w

∈ R

.) In addition,

we require that the vehicle should remain in a square operating region,

kp(k)k

∞

≤ P

max

, k = 1, . . . , K.

Both parts of this problem concern the speciﬁc problem instance with data given in thrusters_data.*.

(a) Find an optimal trajectory, and the associated minimum fuel use p

. Plot the trajectory p(k)

in R

(i.e., in the p

, p

plane). Verify that it passes through the way-points.

剩余191页未读，继续阅读

qq_41569312

粉丝: 1
资源: 1

Stephen Boyd & Lieven Vandenberghe 凸优化额外练习资源

凸优化英文教材讲义课后答案完整版

凸优化公开课（convex optimization，Boyd等著）课后作业及解答

凸分析和优化课后习题答案.zip

斯坦福教材凸优化课后习题答案

【凸优化】Stephen Boyd 凸优化+教材课后习题答案（英文版）

ssd6 课后练习 ssd6 课后练习

数据结构 课后复习练习

编译原理课后参考练习题

Java课后编程练习题答案

flash动画基于课后的练习

最新资源

数据结构课后复习练习