补充 Convex Optimization 练习题合集

需积分: 9 198 浏览量更新于2024-07-17 收藏 1.16MB PDF 举报

"这是一份关于凸优化的额外练习集，由Stephen Boyd和Lieven Vandenberghe编撰，日期为2019年2月16日。这些练习旨在补充《凸优化》一书中的内容，适合用于课程作业或考试题目。部分练习原本是为书籍准备的，但后来被移除。很多练习包含了使用CVX（Matlab）、CVXPY（Python）或Convex.jl（Julia）等凸优化软件包的计算部分。这些练习的所需文件可以在斯坦福大学Stephen Boyd的书籍网站上找到。用户可以自由使用这些练习，只需注明来源。这些练习的开发和完善得到了许多助教和学生们的帮助。" 在凸优化这一领域，以下是一些关键的知识点： 1. **凸函数与凸集**：凸优化的核心在于处理凸函数和凸集。凸函数是在其定义域内，任意两点连线段上的所有点的函数值都小于或等于这两点的函数值。凸集则是集合内的任何两点的线性组合依然在集合内。 2. **凸优化问题的形式**：标准形式的凸优化问题是求解形如 `minimize f(x)` 的问题，其中 `f` 是凸函数，`x` 属于一个凸集。 3. **优化算法**：包括梯度下降法、拟牛顿法、共轭梯度法等，这些方法在凸优化中特别有效，因为它们能保证在每一步迭代后函数值下降，直到找到全局最小值。 4. **软件包的应用**： - **CVX (Matlab)**：这是一个将数学模型转换为标准凸优化形式的工具，然后调用求解器解决。 - **CVXPY (Python)**：类似地，CVXPY允许用户用Python表达凸优化问题，自动处理转换和求解。 - **Convex.jl (Julia)**：这是Julia语言中的一个库，同样用于定义和解决凸优化问题。 5. **计算组件**：这些练习可能涉及到如何使用上述软件包来建立和求解实际的凸优化模型，包括变量定义、约束设定以及目标函数的构建。 6. **课程应用**：这些额外的练习适用于斯坦福大学的EE364a、UCLA的EE236b和麻省理工学院的6.975课程，表明它们涵盖了从基础到进阶的多种难度水平。 7. **教学资源**：这些练习可自由使用，只要注明出处，这对于教授或自学者来说是一个宝贵的资源，可以帮助他们深入理解和应用凸优化理论。通过解决这些额外练习，学习者能够增强对凸优化理论的理解，掌握如何运用到实际问题中，同时也能够熟悉不同的编程环境和优化工具。

3 Convex optimization problems

3.1 Minimizing a function over the probability simplex. Find simple necessary and suﬃcient conditions

for x ∈ R

to minimize a diﬀerentiable convex function f over the probability simplex, {x | 1

x =

1, x  0}.

3.2 ‘Hello World’ in CVX*. Use CVX, CVXPY, or Convex.jl to verify the optimal values you obtained

(analytically) for exercise 4.1 in Convex Optimization.

3.3 Reformulating constraints in CVX*. Each of the following CVX code fragments describes a convex

constraint on the scalar variables x, y, and z, but violates the CVX rule set, and so is invalid.

Brieﬂy explain why each fragment is invalid. Then, rewrite each one in an equivalent form that

conforms to the CVX rule set. In your reformulations, you can use linear equality and inequality

constraints, and inequalities constructed using CVX functions. You can also introduce additional

variables, or use LMIs. Be sure to explain (brieﬂy) why your reformulation is equivalent to the

original constraint, if it is not obvious.

Check your reformulations by creating a small problem that includes these constraints, and solving

it using CVX. Your test problem doesn’t have to be feasible; it’s enough to verify that CVX

processes your constraints without error.

Remark. This looks like a problem about ‘how to use CVX software’, or ‘tricks for using CVX’.

But it really checks whether you understand the various composition rules, convex analysis, and

constraint reformulation rules.

(a) norm([x + 2*y, x - y]) == 0

(b) square(square(x + y)) <= x - y

(d) norm([max(x,1), max(y,2)]) <= 3*x + y

(e) x*y >= 1; x >= 0; y >= 0

(f) (x + y)^2/sqrt(y) <= x - y + 5

(g) x^3 + y^3 <= 1; x >= 0; y >= 0

(h) x + z <= 1 + sqrt(x*y - z^2); x >= 0; y >= 0

3.4 Optimal activity levels. Solve the optimal activity level problem described in exercise 4.17 in Convex

Optimization, for the instance with problem data

A =







1 2 0 1

0 0 3 1

0 3 1 1

2 1 2 5

1 0 3 2







, c

max







100







, p =













, p

disc













, q =













You can do this by forming the LP you found in your solution of exercise 4.17, or more directly,

using CVX*. Give the optimal activity levels, the revenue generated by each one, and the total

revenue generated by the optimal solution. Also, give the average price per unit for each activity

level, i.e., the ratio of the revenue associated with an activity, to the activity level. (These numbers

should be between the basic and discounted prices for each activity.) Give a very brief story

explaining, or at least commenting on, the solution you ﬁnd.

3.5 Minimizing the ratio of convex and concave piecewise-linear functions. We consider the problem

minimize

max

i=1,...,m

x + b

)

min

i=1,...,p

x + d

)

subject to F x  g,

with variable x ∈ R

. We assume that c

x+d

> 0 and max

i=1,...,m

x+b

) ≥ 0 for all x satisfying

F x  g, and that the feasible set is nonempty and bounded. This problem is quasiconvex, and can

be solved using bisection, with each iteration involving a feasibility LP. Show how the problem can

be solved by solving one LP, using a trick similar to one described in §4.3.2.

3.6 Two problems involving two norms. We consider the problem

minimize

kAx − bk

1 − kxk

∞

, (1)

and the very closely related problem

minimize

kAx − bk

1 − kxk

∞

. (2)

In both problems, the variable is x ∈ R

, and the data are A ∈ R

m×n

and b ∈ R

. Note that

the only diﬀerence between problem (1) and (2) is the square in the numerator. In both problems,

the constraint kxk

∞

< 1 is implicit. You can assume that b /∈ R(A), in which case the constraint

kxk

∞

< 1 can be replaced with kxk

∞

≤ 1.

Answer the following two questions, for each of the two problems. (So you will answer four questions

all together.)

(a) Is the problem, exactly as stated (and for all problem data), convex? If not, is it quasiconvex?

Justify your answer.

(b) Explain how to solve the problem. Your method can involve an SDP solver, an SOCP solver,

an LP solver, or any combination. You can include a one-parameter bisection, if necessary.

(For example, you can solve the problem by bisection on a parameter, where each iteration

consists of solving an SOCP feasibility problem.)

Give the best method you can. In judging best, we use the following rules:

• Bisection methods are worse than ‘one-shot’ methods. Any method that solves the problem

above by solving one LP, SOCP, or SDP problem is better than any method that uses a

one-parameter bisection. In other words, use a bisection method only if you cannot ﬁnd

a ‘one-shot’ method.

• Use the simplest solver needed to solve the problem. We consider an LP solver to be

simpler than an SOCP solver, which is considered simpler than an SDP solver. Thus, a

method that uses an LP solver is better than a method that uses an SOCP solver, which

in turn is better than a method that uses an SDP solver.

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.

剩余214页未读，继续阅读

优绎

粉丝: 3
资源: 2

补充 Convex Optimization 练习题合集

凸优化算法：Convex Optimization 介绍

自己制作的Convex Optimization书签版

Stephen Boyd & Lieven Vandenberghe的(Convex Optimization)英文原版

Additional Exercises for Convex Optimization

convex optimization extra excercise

Convex Optimization

convex optimization中文版

斯坦福大学凸优化教材：Convex Optimization精髓解读

深度学习中的非凸优化：Non-convex Optimization for Machine Learning

Java源码ssm框架的房屋租赁系统-合同-毕业设计论文-期末大作业.rar

最新资源