CVX工具箱：斯坦福教授开发的凸优化求解器

Matlab

需积分: 32 194 浏览量更新于2023-03-16 1 收藏 555KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"CVX工具箱是一个用于在MATLAB环境下解决凸优化问题的软件包，由斯坦福大学的Stephen P. Boyd教授开发。这个工具箱采用了一种名为纪律化凸编程（Disciplined Convex Programming, DCP）的方法，使得用户能够更容易地处理凸优化问题。CVX包括了多种求解器，并且支持多种平台安装。它提供了从简单的最小二乘问题到复杂的约束优化问题的解决方案，并具有基础操作、规则集、半定规划模式和几何规划模式等功能。" CVX工具箱的核心在于其提供的简单易用的接口和对凸优化问题的强大处理能力。通过这个工具箱，用户可以方便地定义变量、目标函数和约束条件，而无需直接处理底层的优化算法。 1. **纪律化凸编程(Disciplined Convex Programming)**：DCP是一种规则化的方法，用于确保构建的优化模型是凸的。它规定了如何组合和构造表达式，以保证它们始终保持凸性或凹性。这允许CVX自动验证和转换问题，使之适应内部的求解器。 2. **开始与结束标记(cvx_begin和cvx_end)**：在MATLAB脚本中，cvx_begin和cvx_end用来包围一个凸优化问题的定义，告诉CVX接下来的代码将表示一个优化模型。 3. **变量(Variables)**：在CVX中，变量是优化问题中的未知数，可以通过cvx_var函数声明。 4. **目标函数(Objective functions)**：优化问题的目标是最大化或最小化某个函数，CVX支持多种类型的函数作为目标，包括线性、二次和一些预定义的凸函数。 5. **约束(Constraints)**：CVX允许用户设置各种类型的约束，如线性不等式、等式，以及其他凸函数的上界和下界。 6. **函数(Functions)**：CVX包含一组预定义的函数库，这些函数被标记为凸的或凹的，以支持模型构建。用户也可以自定义函数，但必须遵循DCP规则。 7. **集成员资格(Set membership)**：用户可以指定变量必须属于特定的凸集合，如非负半轴、正定锥等。 8. **对偶变量(Dual variables)**：在优化问题的对偶形式中，对偶变量与原始问题的约束相关联，CVX允许用户直接处理对偶变量。 9. **赋值和表达式持有者(Assignment and expression holders)**：CVX提供了一些结构来存储和操作中间表达式，以便于构建复杂的模型。 10. **DCP规则集(The DCP ruleset)**：这是CVX的核心，规定了如何组合基本的凸和凹元素以构建合法的凸优化问题。包括顶级规则、约束规则、表达式规则和函数规则。 11. **半定规划模式(Semidefinite programming mode)**：对于涉及对称矩阵变量的优化问题，CVX支持半定规划模式，这些问题通常出现在处理二次约束或最小化二次函数时。 12. **几何编程模式(Geometric programming mode)**：几何编程是一种特殊的凸优化子领域，CVX也提供了对这种模式的支持，特别适用于处理比例和指数函数的问题。通过CVX工具箱，无论是学术研究还是工程应用，用户都可以更加高效地解决各种凸优化问题，无需深入理解底层的优化算法细节。这大大降低了凸优化的使用门槛，使得更多的人能够利用优化技术来解决实际问题。

资源详情

资源推荐

The CVX Users’ Guide, Release 2.1

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.1

??? 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 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.1

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.1

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

The CVX Users’ Guide, Release 2.1

3.4 Other constraints

We hope that, by now, it is not surprising that adding the simple bounds l  x  u to the problems above is

as simple as inserting the line l <= x <= u before the cvx_end statement in each CVX speciﬁcation.

In fact, CVX supports more complex constraints as well. For example, let us deﬁne new matrices C and d

in Matlab as follows,

p = 4;

C = randn(p,n);

d = randn(p,1);

Now let us add an equality constraint and a nonlinear inequality constraint to the original least-squares

problem:

cvx_begin

variable x(n);

minimize( norm(A

x-b) );

subject to

x == d;

norm(x,Inf) <= 1;

cvx_end

Both of the added constraints conform to the DCP rules, and so are accepted by CVX. After the cvx_end

command, CVX converts this problem to an SOCP, and solves it.

Expressions using comparison operators (==, >=, etc.) behave quite differently when they involve CVX

optimization variables, or expressions constructed from CVX optimization variables, than when they involve

simple numeric values. For example, because x is a declared variable, the expression C

x==d causes a

constraint to be included in the CVX speciﬁcation, and returns no value at all. On the other hand, outside of

a CVX speciﬁcation, if x has an appropriate numeric value—for example immediately after the cvx_end

command—that same expression would return a vector of 1s and 0s, corresponding to the truth or falsity of

each equality.

Likewise, within a CVX speciﬁcation, the statement norm(x,Inf)<=1 adds a nonlinear

constraint to the speciﬁcation; outside of it, it returns a 1 or a 0 depending on the numeric value of x

(speciﬁcally, whether its `

∞

-norm is less than or equal to, or more than, 1).

Because CVX is designed to support convex optimization, it must be able to verify that problems are convex.

To that end, CVX adopts certain rules that govern how constraint and objective expressions are constructed.

For example, CVX requires that the left- and right-hand sides of an equality constraint be afﬁne. So a

constraint such as

norm(x,Inf) == 1;

results in the following error:

??? Error using ==> cvx.eq

Disciplined convex programming error:

Both sides of an equality constraint must be affine.

In fact, immediately after the cvx_end command above, you would likely ﬁnd that most if not all of the values returned

would be 0. This is because, as is the case with many numerical algorithms, solutions are determined only to within some nonzero

numeric tolerance. So the equality constraints will be satisﬁed closely, but often not exactly.

14 Chapter 3. A quick start

剩余98页未读，继续阅读

m741584084

粉丝: 0
资源: 1

CVX工具箱：斯坦福教授开发的凸优化求解器

matlab基于log算子代码-cvxquad:在基于MATLAB的CVX中实现矩阵的各种凹凸函数（矩阵的几何平均值，量子相对熵等）

cvx——w64.zip

cvx.zip_CVX工具_CVX工具箱_matlab cvx_凸优化_凸函数优化

cvx.zip_CVX工具_cvx matlab_cvx工具箱下载_matlab 凸优化_凸优化 CVX

凸优化cvx工具箱

matlab——cvx工具箱

CVX工具箱-matlab

matlab cvx工具箱

cvx工具箱安装 下载

matlab安装cvx工具箱

matlab的cvx工具箱

matlab cvx工具箱使用mosek

CVX+PDF_CVX_cvx优化_CVX工具箱_dailylle_cvx凸优化_

CVX.rar_CVX_CVX工具箱_convex optimization_cvx说明_凸优化实例

cvx工具箱加指导文献.zip

CVX-Jigsaw:使用 Matlab 和 CVX 工具箱解决拼图游戏。-matlab开发

Matlab_SVM.zip_CVX_UCI 数据集_cvx_begin_matlab CVX工具箱_散点图 优化

CVX拼图：使用Matlab和CVX工具箱解决拼图问题（THU凸优化家庭作业）

最新资源

cvx工具箱安装下载

Matlab_SVM.zip_CVX_UCI 数据集_cvx_begin_matlab CVX工具箱_散点图优化