CVX用户指南：凸优化实战

需积分: 9 27 浏览量更新于2024-07-21 收藏 448KB PDF 举报

该资源是一本关于凸优化的用户指南，名为"The CVX Users' Guide Release 2.0 (beta)"，由Michael C. Grant和Stephen P. Boyd编写，出版于2012年9月28日。CVX是一个用于MATLAB的软件包，专门用于构建和求解凸优化问题。书中详细介绍了如何使用CVX，以及其背后的原理——纪律化凸优化（Disciplined Convex Programming, DCP）。正文：凸优化是优化理论中的一个重要分支，它主要研究那些在凸集上寻找全局最优解的问题。凸优化问题的特殊之处在于，它们通常具有更好的算法性能保证，比如能够确保找到全局最优解，而不需要遍历所有可能的解。在实际应用中，如工程、经济、信号处理和机器学习等领域，凸优化都有着广泛的应用。 CVX是一种工具，它允许用户用一种高层面的、基于MATLAB的语言来描述凸优化问题，而无需深入学习底层优化算法的细节。用户只需要按照DCP规则定义问题，CVX会自动将这些问题转化为可被高效求解器处理的形式。 DCP（Disciplined Convex Programming）是一套规则，用于确保用户编写的模型是凸的。DCP规则集分为几个部分：包括对变量、目标函数、约束、函数和表达式的一系列规定，确保了所构造的优化模型的合法性。例如，它规定了哪些函数组合仍然是凸的，以及如何定义和使用变量和约束。书中的“快速启动”章节通过一些基本的例子，如最小二乘问题、带约束的最小二乘问题、不同范数和函数的优化，以及其他类型的约束，引导读者快速上手CVX的使用。此外，还介绍了如何安装CVX，包括支持的平台、安装步骤以及与Gurobi或MOSEK等外部求解器的配合使用。在“基础知识”部分，详细讲解了cvx_begin和cvx_end语句的使用，定义变量、设置目标函数、构建约束以及利用函数和集合成员资格来描述优化问题的方法。还涵盖了双变量的概念，以及赋值和表达式持有者的作用。 “DCP规则集”章节进一步深入，讨论了曲率的分类、顶级规则、约束和表达式的规则，以及如何组合这些规则来构造更复杂的凸优化模型。特别地，它阐述了非线性组合的单调性，这是理解和解决凸优化问题的关键。这本书为使用CVX进行凸优化提供了全面的指导，适合希望利用凸优化解决实际问题的科研人员和工程师。通过阅读和实践，读者可以掌握如何用MATLAB和CVX构建和求解各种凸优化问题，从而提高问题解决的效率和准确性。

The CVX Users’ Guide, Release 2.0 (beta)

and full rank (i.e., m ≥ n and Rank(A) = n). Let us create the data for a small test problem in Matlab:

m = 16; n = 8;

A = randn(m,n);

b = randn(m,1);

Then the least-squares solution x = (A

−1

b is easily computed using the backslash operator:

x_ls = A \ b;

Using CVX, the same problem can be solved as follows:

cvx_begin

variable x(n)

minimize( norm(A

x-b) )

cvx_end

(The indentation is used for purely stylistic reasons and is optional.) Let us examine this speciﬁcation line

by line:

• cvx_begin creates a placeholder for the new CVX speciﬁcation, and prepares Matlab to accept

variable declarations, constraints, an objective function, and so forth.

• variable x(n) declares x to be an optimization variable of dimension n. CVX requires that all

problem variables be declared before they are used in the objective function or constraints.

• minimize( norm(A

x-b) ) speciﬁes the objective function to be minimized.

• cvx_end signals the end of the CVX speciﬁcation, and causes the problem to be solved.

Clearly there is no reason to use CVX to solve a simple least-squares problem. But this example serves

as sort of a “Hello world!” program in CVX; i.e., the simplest code segment that actually does something

useful.

When Matlab reaches the cvx_end command, the least-squares problem is solved, and the Matlab variable

x is overwritten with the solution of the least-squares problem, i.e., (A

−1

b. Now x is an ordinary

length-n numerical vector, identical to what would be obtained in the traditional approach, at least to within

the accuracy of the solver. In addition, several additional Matlab variables are created; for instance,

• cvx_optval contains the value of the objective function;

• cvx_status contains a string describing the status of the calculation (see Interpreting the results).

All of these quantities—x, cvx_optval, and cvx_status, etc.—may now be freely used in other

Matlab statements, just like any other numeric or string values.

There is not much room for error in specifying a simple least-squares problem, but if you make one, you

will get an error or warning message. For example, if you replace the objective function with

maximize( norm(A

x-b) );

which asks for the norm to be maximized, you will get an error message stating that a convex function

cannot be maximized (at least in disciplined convex programming):

If you type who or whos at the command prompt, you may see other, unfamiliar variables as well. Any variable that begins

with the preﬁx cvx_ is reserved for internal use by CVX itself, and should not be changed.

10 Chapter 3. A quick start

The CVX Users’ Guide, Release 2.0 (beta)

??? Error using ==> maximize

Disciplined convex programming error:

Objective function in a maximization must be concave.

3.2 Bound-constrained least squares

Suppose we wish to add some simple upper and lower bounds to the least-squares problem above: i.e.,

minimize kAx − bk

subject to l  x  u

where l and u are given data vectors with the same dimension as x. The vector inequality u  v means

componentwise, i.e., u

≤ v

for all i. We can no longer use the simple backslash notation to solve this

problem, but it can be transformed into a quadratic program (QP) which can be solved without difﬁculty

with a standard QP solver.

Let us provide some numeric values for l and u:

bnds = randn(n,2);

l = min( bnds, [], 2 );

u = max( bnds, [], 2 );

If you have the Matlab Optimization Toolbox, you can use quadprog to solve the problem as follows:

x_qp = quadprog( 2

A’

A, -2

A’

b, [], [], [], [], l, u );

This actually minimizes the square of the norm, which is the same as minimizing the norm itself. In contrast,

the CVX speciﬁcation is given by

cvx_begin

variable x(n)

minimize( norm(A

x-b) )

subject to

l <= x <= u

cvx_end

Two new lines of CVX code have been added to the CVX speciﬁcation:

• The subject to statement does nothing—CVX provides this statement simply to make speciﬁca-

tions more readable. As with indentation, it is entirely optional.

• The line l <= x <= u represents the 2n inequality constraints.

As before, when the cvx_end command is reached, the problem is solved, and the numerical solution is

assigned to the variable x. Incidentally, CVX will not transform this problem into a QP by squaring the

objective; instead, it will transform it into an SOCP. The result is the same, and the transformation is done

automatically.

In this example, as in our ﬁrst, the CVX speciﬁcation is longer than the Matlab alternative. On the other

hand, it is easier to read the CVX version and relate it to the original problem. In contrast, the quadprog

There are also a number of solvers speciﬁcally designed to solve bound-constrained least-squares problems, such as BCLS by

Michael Friedlander.

3.2. Bound-constrained least squares 11

The CVX Users’ Guide, Release 2.0 (beta)

version requires us to know in advance the transformation to QP form, including the calculations such as

A’

A and -2

A’

b. For all but the simplest cases, a CVX speciﬁcation is simpler, more readable, and

more compact than equivalent Matlab code to solve the same problem.

3.3 Other norms and functions

Now let us consider some alternatives to the least-squares problem. Norm minimization problems involving

the `

∞

or `

norms can be reformulated as LPs, and solved using a linear programming solver such as

linprog in the Matlab Optimization Toolbox; see, e.g., Section 6.1 of Convex Optimization. However,

because these norms are part of CVX’s base library of functions, CVX can handle these problems directly.

For example, to ﬁnd the value of x that minimizes the Chebyshev norm kAx − bk

∞

, we can employ the

linprog command from the Matlab Optimization Toolbox:

f = [ zeros(n,1); 1 ];

Ane = [ +A, -ones(m,1) ; ...

-A, -ones(m,1) ];

bne = [ +b; -b ];

xt = linprog(f,Ane,bne);

x_cheb = xt(1:n,:);

With CVX, the same problem is speciﬁed as follows:

cvx_begin

variable x(n)

minimize( norm(A

x-b,Inf) )

cvx_end

The code based on linprog, and the CVX speciﬁcation above will both solve the Chebyshev norm mini-

mization problem, i.e., each will produce an x that minimizes kAx − bk

∞

. Chebyshev norm minimization

problems can have multiple optimal points, however, so the particular x‘s produced by the two methods can

be different. The two points, however, must have the same value of kAx − bk

∞

Similarly, to minimize the `

norm k · k

, we can use linprog as follows:

f = [ zeros(n,1); ones(m,1); ones(m,1) ];

Aeq = [ A, -eye(m), +eye(m) ];

lb = [ -Inf(n,1); zeros(m,1); zeros(m,1) ];

xzz = linprog(f,[],[],Aeq,b,lb,[]);

x_l1 = xzz(1:n,:) - xzz(n+1:end,:);

The CVX version is, not surprisingly,

cvx_begin

variable x(n)

minimize( norm(A

x-b,1) )

cvx_end

CVX automatically transforms both of these problems into LPs, not unlike those generated manually for

linprog.

12 Chapter 3. A quick start

The CVX Users’ Guide, Release 2.0 (beta)

The advantage that automatic transformation provides is magniﬁed if we consider functions (and their re-

sulting transformations) that are less well-known than the `

∞

and `

norms. For example, consider the

norm

kAx − bk

lgst,k

= |Ax − b|

[1]

+ ··· + |Ax − b|

[k]

where |Ax − b|

[i]

denotes the ith largest element of the absolute values of the entries of Ax − b. This is

indeed a norm, albeit a fairly esoteric one. (When k = 1, it reduces to the `

∞

norm; when k = m, the

dimension of Ax − b, it reduces to the `

norm.) The problem of minimizing kAx − bk

lgst,k

over x can

be cast as an LP, but the transformation is by no means obvious so we will omit it here. But this norm is

provided in the base CVX library, and has the name norm_largest, so to specify and solve the problem

using CVX is easy:

k = 5;

cvx_begin

variable x(n);

minimize( norm_largest(A

x-b,k) );

cvx_end

Unlike the `

, `

, or `

∞

norms, this norm is not part of the standard Matlab distribution. Once you have

installed CVX, though, the norm is available as an ordinary Matlab function outside a CVX speciﬁcation.

For example, once the code above is processed, x is a numerical vector, so we can type

cvx_optval

norm_largest(A

x-b,k)

The ﬁrst line displays the optimal value as determined by CVX; the second recomputes the same value from

the optimal vector x as determined by CVX.

The list of supported nonlinear functions in CVX goes well beyond norm and norm_largest. For

example, consider the Huber penalty minimization problem

minimize

i=1

φ((Ax − b)

)

with variable x ∈ R

, where φ is the Huber penalty function

φ(z) =

(

|z|

|z| ≤ 1

2|z| − 1 |z| ≥ 1

The Huber penalty function is convex, and has been provided in the CVX function library. So solving the

Huber penalty minimization problem in CVX is simple:

cvx_begin

variable x(n);

minimize( sum(huber(A

x-b)) );

cvx_end

CVX automatically transforms this problem into an SOCP, which the core solver then solves. (The CVX

user, however, does not need to know how the transformation is carried out.)

3.3. Other norms and functions 13

剩余93页未读，继续阅读

小林君

粉丝: 0
资源: 3

CVX用户指南：凸优化实战

凸优化中文版

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

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

利用cvx 解决凸优化问题实例代码.rar_matlab 凸优化_凸优化_凸优化程序_凸优化问题_利用cvx 解决凸优化问题实例

凸优化 习题解答凸优化凸优化 习题解答

MATLAB 凸优化处理

一些凸优化相关的matlab代码.rar_Matlab代码_matlab凸优化_凸优化代码_凸优化相关matlab代码_凸优化问

凸优化理论笔记.zip_凸优化_凸优化笔记

cvpr2013_IRL1_denoising.zip_凸优化_凸优化 图像_凸优化加权_迭代凸优化_非凸

sca_SCA凸优化_凸优化SCA_SCA_凸优化_

最新资源

凸优化习题解答凸优化凸优化习题解答

cvpr2013_IRL1_denoising.zip_凸优化_凸优化图像_凸优化加权_迭代凸优化_非凸