CVX学习笔记

时间：2024-12-13 07:32:18

CVX介绍

 适用于解决凸函数问题。其支持多标准问题模型，包括线性和二次程序。二阶圆锥程序和半正定型程序，同时也可以解决不可微函数的问题。

入门例子

最小二乘法

找x ∈ Rn，使得|| Ax - b ||2 最小，A ∈ Rm*n ( m ≥ n and Rank( A) = n ),可知此式子的解为x =(ATA)-1ATb

m = 16; n = 8;
A = randn(m,n);					  		//生成了一个16*8的矩阵
b = randn(m,1); 		      		    //b为8*1的矩阵
cvx_begin	
   variable x(n)					    //变量声明,n表示其维度
   minimize ( norm(A*x-b))              //需要取最小化的目标函数
cvx_end

运行后的将得到以下几个Matlab的变量值：

  1. cvx_optval显示目标函数的最优值
  2. cvx_status计算状态的描述，如果成功解决，则显示为solved
有界约束的最小二乘法

问题模型

									minimize   ||Ax-b||2
									subject to  l ⪯ x ⪯ u

l和u是给定的向量，l,u∈Rn*1,此程序为二次程序（QP）。

cvx_begin
   variable x(n)
   minimize( norm(A*x-b) )
   subject to									
       l <= x <= u								//声明了两个不等式
cvx_end
其他规范功能
  1. 无穷范数
cvx_begin
   variable x(n)
   minimize( norm(A*x-b,Inf) )
cvx_end

2.一范数

cvx_begin
   variable x(n)
   minimize( norm(A*x-b,1) )
cvx_end

3.其他范数

k = 5;
cvx_begin
   variable x(n);
   minimize( norm_largest(A*x-b,k) );
cvx_end

4,Huber函数

cvx_begin
    variable x(n);
    minimize( sum(huber(A*x-b)) );
cvx_end
其他约束

CVX也支持更多复杂的约束，例如在此添加等式约束。

p = 4;
C = randn(p,n);
d = randn(p,1);
cvx_begin
    variable x(n);
    minimize( norm(A*x-b) );
    subject to
        C*x == d;			//添加等式约束，等式符号==
        norm(x,Inf) <= 1;
cvx_end

CVX基础

CVX模型以cvx_begin开始，以cvx_end结束。变量、目标函数、约束都介于两者之间。cvx_begin命令包含多种修饰符：
cvx_begin quiet
防止模型在解算时产生任何屏幕输出。
cvx_begin sdp
调用半确定编程模式。
cvx_begin gp
调用几何编程模式。

变量

CVX的变量可以是实数或复数标量，向量，矩阵或者n维数组。

variable X								//标量
variable Y(20,10)	                    //矩阵Y
variable Z(5, 5, 5)					   //n维数据

变量声明还可以包含一个或多个关键字来表示变量上的各种结构或条件

variable w(50) complex		                                       	//关键字complex，定义了一个复数矩阵

非负变量和对称/埃尔米特半正定（PSD）矩阵可分别用非负半定义关键字指定

variable x(10) nonnegative											//关键字nonnegative,x是一个非负向量
variable Z(5,5) semidefinite											//关键字semidefinite，z是一个半正定矩阵
variable Q(5,5) complex semidefinite
//厄密共轭矩阵

整数和二进制关键字分别用于声明整数和二进制变量

variable p(10) integer
//关键字integer,p为整数向量
variable q binary
//关键字binary,q声明了一个2进制变量

可以使用多种关键字来帮助构造具有矩阵结构（例如对称性或条带性）的变量

variable Y(50,50) symmetric
//关键字symmetric,定义了一个半正定的矩阵  
variable Z(100,100) hermitian toeplitz
//关键字hermitian toeplitz，定义了一个Hermitian Toeplitz矩阵

当前支持的结构关键字：

//下划线可不写
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
(lb,ub)
该矩阵以较低的带宽lb和较高的带宽ub进行带限。 如果lb和ub均为零，则产生对角矩阵。 ub可以省略，在这种情况下，它被设置为等于lb.例如，带状（1,1）（或带状（1））是三对角矩阵

变量语句，允许声明多个变量，但不能声明复杂的，整型的或结构化的变量。 这些必须使用单数变量命令一次一个地声明

variables x1 x2 x3 y1(10) y2(10,10,10);
目标函数

声明一个目标函数需要使用最小化函数或最大化函数。调用中最小化的目标函数必须是凸的，最大化的目标函数必须是凹的

//至多有一个目标函数可以在CVX规范中声明，并且它必须有一个标量值
minimize(norm(x,1))
maximize(geo_mean(x))
约束

约束类型：

  1. 等号约束==，等式约束是放射的
  2. 小于约束<=, 不等式约束，左侧表达式为凸，右侧表达式为凹
  3. 大于约束>=, 不等式约束，左侧表达式为凹，右侧表达式为凸
  4. 允许不等式约束链接，1 <= x <= u
  5. ~=不等
函数

CVX函数库包含各种凸，凹和仿射函数。Reference guide中提供了基础库中功能的完整列表。 也可以添加自己的新功能; 请参阅document中的 Adding new functions to the atom library。
基础库示例：
二次超线性函数quad_over_lin
这里我们使（Ax-b，cTx + d）的二次超线性函数最小化，使用

minimize( quad_over_lin( A * x - b, c' * x + d ) )
设置集合

CVX支持凸集的定义和使用，Matlab语言没有一个集合运算符，因此为了表示一个集合，我们使用一个返回一个未命名的变量的函数，该变量需要在集合中。我们用**==或In**来设定集合

//X被约束成等于一个未命名的变量，它必须是一个n×n对称正半定矩阵
X == semidefinite(n)
X <In> semidefinite(n);

集合可以在仿射表达式中组合，并且我们可以将仿射表达式约束在凸集合中

A*X*A'-X <In> B*semidefinite(n)*B';
//其中X是n×n对称变量矩阵，A和B是nn×n个常数矩阵。 这个约束要求这里写图片描述，对于某些

CVX还支持其元素是有序数量列表的集合。 作为一个例子，考虑二阶或洛伦兹锥
Qm = { (x,y) ∈ Rm × R | ∥x∥2 ≤ y } = epi∥⋅∥2 ,
二阶或洛伦兹锥

//用matlab模拟此方法
cvx_begin
    variables x(n) y;
    minimize( y );
    subject to
        { A*x-b, y } <In> lorentz(m);
cvx_end
对偶变量

最优对偶变量，每一个都与原始问题中的约束相关联。 为了访问CVX中的最佳对偶变量，只需声明它们，并将它们与约束关联即可。 考虑，例如，LP
线性问题
对偶变量 y没有给出尺寸; 它们是根据它所关联的约束自动确定的

n = size(A,2);
cvx_begin
    variable x(n);
    dual variable y					//对偶变量声明
    minimize( c' * x );
    subject to
    	y : A * x <= b;				//声明对偶变量所在的的约束函数
    	//也可写成A * x <= b ： y
cvx_end

该LP的最优原始和双重变量必须满足互补松弛条件：
互补松弛条件

y .* (b-A*x)						
//可用此在matlab中检验，此必须放在cvx_end后检验是否为0
赋值和表达式定义

使用**=进行赋值操作，使用expression**命令进行定义表达式。
以下区分=，==,下代码为错误示范

cvx_begin
	variable X(n,n) symmetric;
	X = semidefinite(n);
	//可能看起来像约束X是正半定的,但由于使用的是赋值运算，所以X直接被覆盖了，所		 	以运行到此CVX会出现警告
	...
cvx_end

尽管有这个警告，任务还是真正有用的，所以我们鼓励他们适当的使用

variables x y
z = 2 * x - y;	//这里意义不在是作为等式，而是作为一个储存中间值的一个变量
square( z ) <= 3;
quad_over_lin( x, z ) <= 1;

将一组表达式累加到一个单独的Matlab变量中通常是有用的。 不幸的是，在这种情况下，Matlab对象模型的一些技术细节可能会导致问题，需要显示的声明表达式

variable u(9);
x(1) = 1;
for k = 1 : 9,
    x(k+1) = sqrt( x(k) + u(k) );
    //此将会报错,因为这里将赋值x（1）= 1时，在CVX模型中Matlab变量x被初始化为一个数值数组; 而Matlab将不允许随后将CVX对象插入数值数组中
end

//因此需要显示的声明x变量是表达式持有者，即
variable u(9);
expression x(10);	//显示的声明x为表达式
x(1) = 1;
for k = 1 : 9,
    x(k+1) = sqrt( x(k) + u(k) );
end

参考指南

针对运算符，函数，集合和命令的描述。在某些情况下，底层求解器的限制对其使用有某些限制或警告：

  • CVX使用的手动解算器本身不支持标有匕首（†）的函数。包含这些功能的模型将由Mosek最有效地求解。对于所有其他求解器，这些函数使用逐次逼近方法处理，该方法对基础求解器进行多次调用，从而获得相同的最终精度。如果您的问题需要使用逐次逼近方法，则会发出警告。
  • 涉及次方（功能例如，X ^ P）和p-norms（例如，范数（X，P） ）标有双匕首（‡）。CVX恰好在什么时候代表了这些功能p是一个有理数。对于p的无理值，将选择附近的有理数。
算术运算符

Matlab用于加法，减法，乘法,除法/ ./ ,和幂指数.的标准算术运算已经被重载在CVX中适用 。也就是说，只要它们的使用符合标准的数学和Matlab惯例以及DCP规则集：

1,如果两个CVX表达式具有相同的尺寸（或一个是标量）并且具有相同的曲率（即，它们都是凸，凹或仿射），则可以将它们加在一起。
表达式可以乘以或除以标量常量。如果常数为正，则保留曲率；如果为负，则曲率反转。
3.仿射列向量CVX表达式可以乘以适当尺寸的常数矩阵；也可以用适当尺寸的非奇异常数矩阵左除

Matlab的基本矩阵操作和算术运算也扩展为可与CVX表达式一起使用，包括：

连接：[A，B; C，D]
索引：x（n + 1：结尾），X（[3,4]，:)等
索引分配，包括删除：y（2：4）= 1，Z（1：4，:) = []等
转置和共轭转置：Z.'，y'
内置函数
Linear线性函数

多Matlab的基本线性和双线性函数或者自动地用cvx表达式工作，或者扩展到cvx表达式，包括：conj, conv, cumsum, diag, dot, find, fliplr, flipud, flipdim, horzcat, hankel, ipermute, kron, mean, permute, repmat, reshape, rot90, sparse, sum, trace, tril, triu, toeplitz, vertcat.大多数应该像使用数字表达式一样来处理CVX表达式。 执行诸如conv，dot或kron之类的cumsum，sum或multiplication之类的某种求和的那些只能按照有纪律的凸规划规则来使用。 例如，kron（X，Y）只有在X或Y是常量时才有效; 而轨迹（Z）只有沿着对角线的元素具有相同的曲率才有效。

Nonlinear非线性函数
abs
//求实数和复数数组的绝对值，凸函数

† exp
//求指数。 凸和不减

†log
//求对数。 凹而不减

max
//求最大值，凸而不减

min
//求最小值, 凹而不减

norm
//范数，凸函数norm(x,p)
//*‡对于向量，所有值p≥1都被接受。
//对于矩阵，p必须为1,2，Inf或者'Fro'

polyval
/*多项式评估。 polyval（p，x），其中p是一个长度为n的向量，计算p(1) * x.^(n-1) + p(2) * x.^(n-2) + ... + p(n-1) * x + p(n)
注意：
1.如果p是变量，x是常量，则polyval（x，p）计算p的元素的线性组合。该组合必须满足DCP规则的添加和缩放。
2.如果p是常数而x是变量，则polyval（x，p）构造变量x的多项式函数。 多项式必须是仿射的，凸的或凹的，并且x必须是真实的和仿射的。*/

‡power（x，p）
//x ^ p和x.^ p，其中x是一个实数变量，而p是一个实常数。 对于x ^ p，x和p都必须是标量。 只有那些合理而明确地解释为凸或凹的p值才被接受：
P =0           //不变。 x.^p被相同地处理1。
0<P<1       // 凹，参数x必须是凹的（或仿射的），并且被隐含地约束为非负的。
P =1          //仿射。 x.^ p简单地是x。
p∈{2,4,6,8，...}   //凸，参数x必须是仿射的。
p> 1 ，p∉{2,3,4,5，...}  //凸。 参数x必须是仿射的，并且被隐含地约束为非负的。

† power(p,x)
//p.^ x和p ^ x，其中p是一个实常数，x是一个实变量。 对于p ^ x，p和x必须是标量。 p的有效值包括：
p∈{0,1} 		//不变。
0<P<1			//凸和不增加; x必须凹的。
P>1			    // 凸和不减 x必须是凸的。p不可取负数

std
//标准偏差,凸。

sqrt
//平方根,隐含地限制它的定义域是非负的。 凹而不减。

var
//方差,凸。
new function

即使这些函数是专门为CVX开发的，但它们在CVX规范之外也可以使用数字参数。CVX新函数

相关文章