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

共8个文件

pdf：8个

；课后习题

3星 · 超过75%的资源需积分: 43 106 浏览量 2017-07-31 13:04:30 上传评论 10 收藏 919KB ZIP 举报

资源推荐

资源详情

资源评论

收起资源包目录

homeworks_and_solutions.zip （8个子文件）

作业与解答

hw3sol.pdf 137KB

hw2sol.pdf 85KB

hw1sol.pdf 76KB

hw5sol.pdf 165KB

hw7sol.pdf 158KB

hw6sol.pdf 156KB

hw8sol.pdf 97KB

hw4sol.pdf 169KB

EE364a, Winter 2007-08 Prof. S. Boyd

EE364a Homework 4 solutions

4.11 Problems involving ℓ

- and ℓ

∞

-norms. Formulate the following problems as LPs. Ex-

plain in detail the relation between the optimal solution of each problem and the

solution of its equivalent LP.

(a) Minimize kAx − bk

∞

(ℓ

∞

-norm approximation).

(b) Minimize kAx − bk

(ℓ

-norm approximation).

subject to kxk

∞

≤ 1.

(d) Minimize kxk

subject to kAx − bk

∞

≤ 1.

(e) Minimize kAx − bk

+ kxk

∞

In each problem, A ∈ R

m×n

and b ∈ R

are given. (See §6.1 for more problems

involving approximation and constrained approximation.)

Solution.

(a) Equivalent to the LP

minimize t

subject to Ax − b  t1

Ax − b  −t1.

in the variables x ∈ R

, t ∈ R. To see the equivalence, assume x is ﬁxed in this

problem, and we optimize only over t. The constraints say that

−t ≤ a

x − b

≤ t

for each k, i.e., t ≥ |a

x − b

|, i.e.,

t ≥ max

x − b

| = kAx − bk

∞

Clearly, if x is ﬁxed, the optimal value of the LP is p

⋆

(x) = kAx −bk

∞

. Therefore

optimizing over t and x simu ltaneously is equivalent to the original problem.

(b) Equivalent to the LP

minimize 1

subject to Ax − b  s

Ax − b  −s

with variables x ∈ R

ands ∈ R

. Assume x is ﬁxed in this problem, and we

optimize only over s. The constraints say that

−s

≤ a

x − b

≤ s

for each k, i.e., s

≥ |a

x −b

|. The objective function of the LP is separable, so

we achieve the optimum over s by choosing

= |a

x − b

and obtain the optimal value p

⋆

(x) = kAx −bk

. Therefore optimizing over x and

s simultaneously is equivalent to the original problem.

minimize 1

subject to −y  Ax − b  y

−1  x  1,

with variables x ∈ R

and y ∈ R

(d) Equivalent to the LP

minimize 1

subject to −y  x  y

−1  Ax − b  1

with variables x ∈ R

and y ∈ R

Another reformulation is to write x as the diﬀerence of two nonnegative vectors

x = x

− x

−

, and to express the problem as

minimize 1

+ 1

−

subject to −1  Ax

− Ax

−

− b  1

 0, x

−

 0,

with variables x

∈ R

and x

−

∈ R

(e) Equivalent to

minimize 1

y + t

subject to −y  Ax − b  y

−t1  x  t1,

with variables x ∈ R

, y ∈ R

, and t ∈ R.

4.16 Minimum fuel optimal control. We consider a linear dynamical system with state

x(t) ∈ R

, t = 0, . . . , N, and actuator or input signal u(t) ∈ R, for t = 0, . . . , N − 1.

The dynamics of the system is given by the linear recurrence

x(t + 1) = Ax(t) + bu(t), t = 0, . . . , N − 1,

where A ∈ R

n×n

and b ∈ R

are given. We assume that the initial state is zero, i.e.,

x(0) = 0.

The minimum fuel optimal control problem is to ch oose the inputs u(0), . . . , u(N − 1)

so as to minimize the total fuel consumed, which is given by

F =

N−1

t=0

f(u(t)),

subject to the constraint that x(N) = x

des

, where N is the (given) time horizon, and

des

∈ R

is the (given) desired ﬁnal or target state. The function f : R → R is the

fuel use map for the actuator, and gives the amount of fuel used as a function of the

actuator signal amplitude. In this problem we use

f(a) =

(

|a| |a| ≤ 1

2|a| − 1 |a| > 1.

This means that fuel use is proportional to the absolute value of the actuator signal,

for actuator signals between −1 and 1; for larger actuator signals the marginal fuel

eﬃciency is half.

Formulate the minimu m fuel optimal control problem as an LP.

Solution. The minimum fuel optimal control problem is equivalent to the LP

minimize 1

subject to Hu = x

des

−y  u  y

t  y

t  2y −1,

with variables u ∈ R

, y ∈ R

, and t ∈ R, where

H =

N−1

b A

N−2

b ··· Ab b

There are several other possible LP formulations. For example, we can keep the state

trajectory x(0), . . . , x(N) as optimization variables, and replace the equality constraint

above, Hu = x

des

, with the equality constraints

x(t + 1) = Ax(t) + bu(t), t = 0, . . . , N − 1, x(0) = 0, x(N) = x

des

In this formulation, the variables are u ∈ R

, x(0), . . . , x(N) ∈ R

, as well as y ∈ R

and t ∈ R

Yet another variation is to not use the intermediate variable y introduced above, and

express the problem just in terms of the variable t ( and u):

−t  u  t, 2u − 1  t, −2u − 1  t,

with variables u ∈ R

and t ∈ R

4.29 Maximizing probability of satisfying a linear inequality. Let c be a random variable in

, normally distributed with mean ¯c and covariance matrix R. Consider the problem

maximize prob(c

x ≥ α)

subject to F x  g, Ax = b.

Find the conditions under which this is equivalent to a convex or quasiconvex optimiza-

tion problem. When these conditions hold, formulate the problem as a QP, QCQP, or

SOCP (if the problem is convex), or explain how you can solve it by solving a sequence

of QP, QCQP, or SOCP feasibility problems (if the problem is quasiconvex).

Solution. Deﬁne u = c

x, a scalar random variable, normally distributed with mean

E u = ¯c

x and variance E(u − E u)

= x

Rx. The random variable

u − ¯c

√

has a normal distribution with mean zero and unit variance, so

prob(u ≥ α) = prob

u − ¯c

√

≥

α − ¯c

√

= 1 − Φ

α − ¯c

√

where Φ(z) =

√

2π

−∞

−t

dt is the standard normal CDF.

To maximize prob(u ≥ α), we can minimize (α −¯c

x)/

√

Rx (since Φ is increasing),

i.e., solve the problem

maximize (¯c

x − α)/

√

subject to F x  g

Ax = b.

(1)

This is not a convex optimization problem, since the objective is not concave.

The problem can, however, be solved by quasiconvex optimization provided a condtion

holds. (We’ll derive the condition below.) The objective exceeds a value t if and only

¯c

x − α ≥ t

√

holds. This last inequality is convex, in fact a second-order cone constraint, provided

t ≥ 0. So now we can state the condition: There exists a feasible x for which ¯c

x ≥ α.

(This condition is easily checked as an LP feasibility problem.) This condition, by the

way, can also be stated as: There exists a feasible x for which prob(u ≥ α) ≥ 1/2.

Assume that this condition holds. This means that the optimal value of our original

problem is at least 0.5, and the optimal value of the problem (1) is at least 0. This

means that we can state our problem as

maximize t

subject to F x  g, Ax = b

¯c

x − α ≥ t

√

Rx,

where we can assume that t ≥ 0. This can be solved by bisection on t, by solving an

SOCP feasibility problem at each step. In other words: the function (¯c

x−α)/

√

is quasiconcave, provided it is nonnegative.

In fact, provided the condition above holds (i.e., there exists a feasible x with ¯c

x ≥ α)

we can solve the problem (1) via convex optimization. We make the change of variables

y =

¯c

x − α

, s =

¯c

x − α

so x = y/s. This yields the problem

minimize

subject to F y  gs

Ay = bs

¯c

y − αs = 1

s ≥ 0.

4.30 A heated ﬂuid at temperature T (degrees above ambient temperature) ﬂows in a pipe

with ﬁxed length and circular cross section with radius r. A layer of insulation, with

thickness w ≪ r, surrounds the pipe to reduce heat loss th rough the pipe walls. The

design variables in this problem are T , r, and w.

The heat loss is (approximately) proportional to T r/w, so over a ﬁxed lifetime, th e

energy cost due to heat loss is given by α

T r/w. The cost of the pipe, which has

a ﬁxed wall thickness, is approximately prop ortional to the total material, i.e., it is

given by α

r. The cost of the insulation is also approximately proportional to the total

insulation material, i.e., α

rw (using w ≪ r). The total cost is the sum of these three

costs.

The heat ﬂow down the pipe is entirely due to the ﬂow of the ﬂuid, which has a ﬁxed

velocity, i.e., it is given by α

T r

. The constants α

are all positive, as are the variables

T , r, and w.

Now the problem: maximize the total heat ﬂow down the pipe, subject to an upper

limit C

max

on total cost, and the constraints

min

≤ T ≤ T

max

, r

min

≤ r ≤ r

max

, w

min

≤ w ≤ w

max

, w ≤ 0.1r.

Express this problem as a geometric program.

Solution. The problem is

maximize α

T r

subject to α

T w

−1

+ α

r + α

rw ≤ C

max

min

≤ T ≤ T

max

min

≤ r ≤ r

max

min

≤ w ≤ w

max

w ≤ 0.1r.

评论收藏

内容反馈

weixin_41353029

2018-01-28

根本就是2006年留的作业的答案，答案没有覆盖到书上所有习题，没有代码，不如下载最高下载数那个。
婕儿9607

2017-10-29

很好，很全面。

cq_panfeng

粉丝: 1
资源: 2

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

最新资源

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

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

Convex Optimization（课后答案）

convex optimiation教材及课后答案

凸优化Convex Optimization

Convex Optimization By Stephen Boyd & Lieven Vandenberghe 2006 Solution 课后习题答案

凸优化中文版

凸优化习题答案【Boyd】

Convex Optimization_Boyd_英文版_凸优化_王会宁译_中文版

Convex Optimization书、课后习题及考试答案全解

Boyd凸优化资料（含中英文课本教材、习题、PPT、Matlab习题）

convex optimization凸优化_Stephen Boyd, Lieven Vandenberghe英文版.pdf

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

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

凸优化 习题解答

Convex Optimization---Stephen Boy 课本课件以及课后习题答案

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

斯坦福凸优化课程书籍课件和练习.rar

斯坦福大学凸优化课件

convex optimization

Convex_Optimization.pdf

Convex Optimization_答案.zip

Convex Optimization

最优化理论convex optimization全本加答案解析加课件，超精品

斯坦福EE364a凸优化课程第2章作业题解

凸优化_王书宁译&amp;英文版Convex Optimization习题答案

Convex optimization 英文原版，可复制文字版

Convex Optimization 习题答案

最新资源

凸优化习题解答

凸优化_王书宁译&英文版Convex Optimization习题答案