MatLab凸优化工具箱CVX-The Basics

时间:2022-05-19 03:54:29

cvx_begin and cvx_end

所有的CVX模型都必须以cvx_begin开始,以cvx_end结束。所有的变量声明、目标函数和约束都应该介于两者之间。cvx_begin命令可能包含一个以上的修饰符:

cvx_begin quiet
防止模型在解决过程中产生任何屏幕输出。
cvx_begin sdp
调用  semidefinite programming mode.
cvx_begin gp
调用  geometric programming mode.

可以在适当的时候组合这些修饰词。例如,cvx_begin sdp quiet 调用SDP模式,并使得solver静默输出。

Variables

在所有变量必须使用 variable 命令 (或 variables命令;见下文)声明,才能用于约束或目标函数。variable命令包括变量名,可选维度列表,以及 提供额外结构和内容的一个或多个关键词。

变量可以是实的或复的标量、向量、矩阵或n维数组。例如:

variable X
variable Y(20,10)
variable Z(5,5,5)

声明了326个(标量)变量:标量X,20*10的矩阵Y(包含200个标量变量),以及5*5*5数组Z(包含125个标量变量)。

变量声明还可以使用一个或多个关键词来表示不同结构的变量。例如,要声明一个复数变量,可以使用complex关键词:

variable w(50) complex
    非负变量和对称/埃尔米特半正定(PSD)矩阵可以分别用nonnegative和semidefinite 关键词来指定:
variable x(10) nonnegative
variable Z(5,5) semidefinite
variable Q(5,5) complex semidefinite

在这个例子中,x是非负变量,Z是实对称PSD矩阵,Q是复埃尔米特PSD矩阵。

对于MIDCPs,关键字integer和binary分别用于声明整数和二进制变量:

variable p(10) integer
variable q binary

不同的关键词可以帮助构建诸如对称的矩阵结构的变量。如下面代码:

variable Y(50,50) symmetric
variable Z(100,100) hermitian toeplitz

声明Y是一个实的50*50对称矩阵变量,Z是一个100*100埃尔米特托普利兹矩阵变量(注意hermitian关键词也指定矩阵是复的)。目前支持的结构关键词有:

banded(lb,ub)      diagonal           hankel             hermitian
skew_symmetric     symmetric          toeplitz           tridiagonal
lower_bidiagonal   lower_hessenberg   lower_triangular
upper_bidiagonal   upper_hankel       upper_hessenberg   upper_triangular

实际上下划线可以省略。例如,lower triangular也能被接受。这些关键词有两个例外:

banded(lb,ub)

upper_hankel



尽管variable语句很灵活,但是它只能用于声明一个变量,如果有很多变量要声明就很不方便了。CVX提供了variables语句来声明多个变量,即:

variables x1 x2 x3 y1(10) y2(10,10,10);

variables命令的缺点是不能声明复数、整数或结构变。如果这些必须一次声明,可以单独使用variable命令。

Objective functions 目标函数

声明目标函数需要根据情况使用minimize或maximize函数(也可以使用它们的同义词minimise和maximise)。 调用minimize的目标函数必须是凸的,调用maximize的目标函数必须是凹的。
minimize( norm( x, 1 ) )
maximize( geo_mean( x ) )

最多可以在CVX规范中声明一个目标函数,并且它必须具有标量值。

如果没有指定目标函数,则CVX将问题解释为可行问题,这与目标函数为0的最小化相同。在这种情况下,如果存在可行点或者+Inf,或者约束不可行,则cvx_optval也是0。

Constraints约束

CVX支持下述的约束类型:

  • 等式==约束,等式两边都是仿射表达式。
  • 小于等于<=-约束,左边表达式是凸的,右边表达式是凹的。
  • 大于等于>=约束,左边表达式是凹的,右边表达式是凸的。

    不等号~=不能用于约束;在任何情况下,这样的约束很少是凸的。CVX最新版本允许把不等式连接起来;例如l<=x<=u(之前的版本不允许。)

注意=和==的重要区别:=是赋值语句,==表示相等。

    严格不等式<和>也能被接受,但是它们和对应的非严格不等式是相同的。我们强烈不鼓励这样用,CVX的下一个版本可能会删去这样的用法。

    不等式和等式约束以元素化的方式应用。例如:如果A和B都是m*n的矩阵,那么A<=B就等价于mn个不等式约束A(i,j)<=B(i,j)。当一边是标量时,值被复制。例如,A>0等价于A(i,j)>=0。

Functions函数

基本CVX函数库包括很多凸函数、凹函数和仿射函数,它们接收CVX变量或者表达式作为参数。 诸如sum, trace, diag,sqrt,max, min的常用Matlab函数根据需要重新实现以支持CVX;其他函数则是在Matlab中未找到的新函数。(不懂什么意思)Many are common Matlab functions such as sum, trace, diag, sqrt, max, and min, re-implemented as needed to support CVX; others are new functions not found in Matlab.
基本库中可以Reference guide找到完整的函数列表。自己也可以增加新函数, 参见 Adding new functions to the atom library

Set membership集合关系

As an example, consider the second-order or Lorentz cone(洛伦兹锥),

MatLab凸优化工具箱CVX-The Basics

where epi denotes the epigraph(上境图) of a function.  An element of  MatLab凸优化工具箱CVX-The Basics is an ordered list, with two elements: the first is an m-vector, and the second is a scalar. we can use this cone(锥体) to express this simple least-squares problem from the section   Least squares (in a fairly complicated way) as follows:

MatLab凸优化工具箱CVX-The Basics

CVX uses Matlab's cell array facility to mimic(模拟) this notation:

cvx_begin
    variables x(n) y;
    minimize( y );
    subject to
        { A*x-b, y } <In> lorentz(m);
cvx_end

The function call lorentz(m) returns an unnamed variable(i.e., a pair consisting of a vector and a scalar variable), constrainted to lie in the Lorentz cone of length m. So the constraint in this specification requires that the pair {A*x-b,y} lies in the appropriately-sized Lorentz cone.

Dual variables

When a disciplined convex program is solved, the associated dual problem is also solved. (In this context, the original problem is called the primal problem.) The optimal dual variables, each of which is associated with a constraint in the original problem, give valuable information about the original problem, such as the sensitivities with respect to perturbing the constraints (c.f. Convex Optimization, chapter 5). To get access to the optimal dual variables in CVX, you simply declare them, and associate them with the constraints. Consider, for example, the LP

MatLab凸优化工具箱CVX-The Basics
with variable  MatLab凸优化工具箱CVX-The Basics, and m inequality constraints. To associate the dual variable y with the inequality constraint  MatLab凸优化工具箱CVX-The Basics in this LP, we use the following syntax:
n = size(A,2);
cvx_begin
    variable x(n);
    dual variable y;
    minimize( c' * x );
    subject to
        y : A * x <= b;
cvx_end

The line

dual variable y

tells CVX that y will represent the dual variable, and the line

y : A * x <= b;
associates it with the inequality constraint.  Notice how the colon  :  operator is being used in a different manner than in standard Matlab, where it is used to construct numeric sequences like  1:10 . This new behavior is in effect only when a dual variable is present, so there should be no confusion or conflict. No dimensions are given for y; they are automatically determined from the constraint with which it is associated. For example, if m=20,  typing y  at the Matlab command prompt immediately before cvx_end yields
y =
    cvx dual variable (20x1 vector)

It is not necessary to place the dual variable on the left side of the constraint; for example, the line above can also be written in this way:

A * x <= b : y;
In addition, dual variables for inequality constraints will always be nonnegative, which means that the sense of the inequality can be reversed without changing the dual variable’s value; i.e.,
b >= A * x : y;
yields an identical result.  For  equality  constraints, on the other hand, swapping the left- and right- hand sides of an equality constraint will  negate  the optimal value of the dual variable.