好的,我们来聊聊在 MATLAB 中使用 CVX 工具包求解凸优化问题时,遇到一些常见问题以及如何应对。这确实是一个非常实用的技能,掌握了能帮你事半功倍。
核心问题:CVX 报“Cannot convert ... to a constrained convex form.”
当你使用 CVX 建立优化模型,并尝试调用 `cvx_end` 来求解时,最常遇到的一个报错就是:“Cannot convert ... to a constrained convex form.” (无法将…转换为受约束的凸形式)。这个错误提示非常关键,它直接指出了你的模型不满足 CVX 对凸优化问题的定义,或者说,CVX 无法将其理解为一个标准的凸优化问题。
为什么会出现这个错误? CVX 的“禁忌”
CVX 是一个强大的工具,但它也有自己的“规矩”。它只能处理凸优化问题。这意味着:
1. 目标函数必须是凸函数(对于最小化问题)或凹函数(对于最大化问题)。
2. 约束条件必须是凸约束。
如果你在模型中引入了非凸的成分,CVX 就会“罢工”。那么,哪些常见的操作会导致非凸性呢?
乘积项: 变量与变量相乘(如 `xy`)。除非其中一个变量是标量,或者你使用了 CVX 的一些特定函数(如 `quad_form`),否则这通常是非凸的。
非凸函数: 使用了 CVX 不支持的非凸函数,比如 `inv_pos`(非正数的倒数)、`log_det`(当矩阵变量不是半正定时)、`norm(x, p)` 当 `p < 1`。
除法: 变量之间的除法(如 `x/y`)。这本质上是乘法(`x inv(y)`),如果 `y` 不是一个正标量,通常是非凸的。
指数函数: `exp(x)` 是凸的,但 `exp(x)` 是凸的,而 `xexp(y)` 这种形式通常是非凸的。
max/min 的变量组合: 比如 `cvx_begin ... max(xy) ... cvx_end`。
如何“对症下药”? 详细的排查与解决思路
当遇到这个错误时,不要慌张,这是一个很好的机会去审视你的模型。以下是一些排查和解决问题的步骤:
步骤一:仔细阅读错误信息,定位问题所在
CVX 的错误信息通常会指出具体是哪个表达式导致了问题。例如,你可能会看到类似这样的信息:
```
Error using cvx_check_convexity (line 107)
Cannot convert (x y) to a constrained convex form.
```
或者
```
Error using cvx_check_convexity (line 107)
Cannot convert inv_pos(z) to a constrained convex form.
```
重点: 关注错误信息中指出的表达式(比如 `x y` 或 `inv_pos(z)`)以及涉及的变量。
步骤二:检查目标函数和约束条件
逐一检查你 CVX 模型中的每一行,特别是目标函数和约束条件。
1. 目标函数:
如果是最小化问题: 目标函数是否是凸函数?
常见的凸函数:`sum`, `norm(x, 2)`, `quad_form(x, P)` (当 P 半正定时), `inv_pos(x)` (当 x > 0 时), `log(x)` (当 x > 0 时), `square(x)`。
反例: `sum(x . y)` (如果 x, y 是向量), `norm(x, 1)` (L1 范数是凸的,但 `norm(x, p)` 当 `p<1` 是非凸的), `inv_pos(x)` (如果 x 允许为非正)。
如果是最大化问题: 目标函数是否是凹函数?
常见的凹函数:`sum`, `norm(x, 2)`, `quad_form(x, P)` (当 P 半正定时), `log_det(X)` (当 X 半正定时)。
反例: `sum(x . y)`。
2. 约束条件:
是否使用了非凸的约束?
乘积约束: `x y <= c` (非凸,除非 x, y 是标量且满足特定条件)。
除法约束: `x / y <= c` (等价于 `x inv(y) <= c`,非凸)。
非凸函数约束: `square(x) + square(y) == 1` (这是圆,不是凸的)。
二次约束: `x' Q x <= b` (如果 Q 不是半正定的,则约束是非凸的)。
步骤三:处理非凸部分 —— 常见的“CVX 化”技巧
这是解决问题的核心。如果你的模型包含了非凸项,你需要尝试用 CVX 支持的凸函数来重写它们,或者寻找近似方法。
场景一:变量乘法
情况 1:变量与常数乘法。
`c x` (c 是常数): 这是线性的,是凸的。CVX 可以直接处理。
情况 2:标量变量与向量/矩阵变量乘法。
`a x` (a 是标量,x 是向量/矩阵变量): 这是线性的,是凸的。CVX 可以处理。
`x a` (a 是标量,x 是向量/矩阵变量): 同上,是凸的。CVX 可以处理。
情况 3:两个变量相乘 (`x y`)
如果是最小化问题,且 `xy` 是目标函数的一部分(例如 `min(xy)`):
如果 `x` 和 `y` 都必须是正数,则 `xy` 是凸的,但 CVX 不直接支持 `xy`。你可以考虑使用 对数变换 (如果允许的话),或者使用 McCormick 包络 等方法,但这会增加复杂性。
更常见的情况是 `xy` 出现在其他凸函数的内部,例如 `sum(x.y)`。如果 `x` 是一个固定已知的向量/矩阵,而 `y` 是变量,那么 `x . y` 是线性的,CVX 可以处理。
如果 `x` 和 `y` 都是变量,并且它们都是正的,并且你要求 `xy >= c` (最小化 `xy` 对应的约束) 或者 `xy <= c` (最大化 `xy` 对应的约束),你可能需要使用 `geo_mean` 或 `inv_pos` 配合 `quad_form` 来重写,这取决于具体的结构。
一种常见的技巧是,如果 `x` 和 `y` 都是正的,并且你想要 `xy` 作为一个项,但不能直接写,可以尝试引入一个新的变量 `z = xy`,然后添加约束 `cvx_accept_nonconvex(z == xy)`。 但请注意,`cvx_accept_nonconvex` 允许非凸项,这可能导致求解器无法找到全局最优解,或者根本无法求解,所以这是最后的手段。
如果 `xy` 是约束的一部分(例如 `x y <= c`):
如果 `x` 是已知的正标量: `x y <= c` => `y <= c / x`。这是线性的。
如果 `x` 是已知的标量,但可以是负的: `x y <= c` => 如果 `x > 0`, `y <= c / x`;如果 `x < 0`, `y >= c / x`。这需要根据 `x` 的符号进行分情况讨论,CVX 不会自动处理。
如果 `x` 和 `y` 都是变量,并且都必须是正的: `x y <= c` 是非凸约束。你可能需要寻找其他方法,例如使用Benson's algorithm 的变体,或者将问题近似为线性约束。
对数变换: 如果 `x > 0` and `y > 0` and `c > 0`,那么 `xy <= c` 等价于 `log(x) + log(y) <= log(c)`。你可以引入新的变量 `u = log(x)` 和 `v = log(y)`,然后用 `u + v <= log(c)` 作为约束。但要注意,`log(x)` 不是线性项,CVX 会将其转换为几何规划(Geometric Programming),这是一种特殊的凸优化问题,但需要一些转换。
通过二次形式重写: 在某些情况下,可以使用 `quad_form`。例如,如果你的变量是 `z`,并且你想约束 `z`,而 `z` 和 `xy` 是等价的,并且 `x` 和 `y` 满足某些条件,这可能可以通过SProcedure 的思想来处理,但非常复杂。
情况 4:两个向量/矩阵变量的乘积(`A B`)
这是最棘手的情况,因为向量/矩阵乘法本身是非线性的。
Schur Complement (舒尔补): 很多时候,非凸的二次项 `x' P x` 可以通过引入辅助变量和使用舒尔补转化为凸的二次约束。例如,`x'Px <= y` (当 P 半正定时) 可以用 `[ P, x; x', y ] >= 0` 来表示(但请注意这里的 `x` 是列向量,`x'` 是行向量)。
SDP (半定规划): 如果你的问题可以转化为 SDP,CVX 可以处理。SDP 的核心是处理半正定矩阵约束,这通常涉及到将非凸的乘积项“嵌入”到一个半正定矩阵中。例如,`x'Px <= y` 可以写成 `[P, x; x', y]` 是半正定。
SOCP (二阶锥规划): `norm(x, 2) <= y` 是一种二阶锥约束。有些非线性项可以通过转换为二阶锥约束来处理。
场景二:非凸函数
`inv_pos(x)`: 这个函数要求 `x` 必须为正数。如果你的约束是 `inv_pos(x) <= c`,那么 `x` 必须是正的。如果 `c` 也是正的,那么 `1/x <= c` => `1 <= cx` => `x >= 1/c`。这是一个线性约束。CVX 内部会处理 `inv_pos` 的凸性(当输入为正时)。
`log(x)`: 要求 `x` 为正。`log(x)` 是凹函数。`log_det(X)` 要求 `X` 为半正定。
`square(x)`: 这是凸函数。
`abs(x)`: 这是凸函数。
`norm(x, p)`:
`p=1` (L1 范数): 凸的。
`p=2` (L2 范数): 凸的。
`p=Inf` (Linfinity 范数): 凸的。
`p < 1`: 非凸。绝对不要在 CVX 中直接使用 `norm(x, p)` 当 `p < 1`。如果你需要处理 Lq 范数(q < 1),通常需要更高级的技术,例如通过将问题分解,或者使用特定的求解器(而不是 CVX)。
场景三:约束中的 Max/Min
`max(x, y)`: `max(x, y)` 是凸函数。`max(x, y) <= c` 等价于 `x <= c` and `y <= c`。CVX 可以处理。
`min(x, y)`: `min(x, y)` 是凹函数。`min(x, y) >= c` 等价于 `x >= c` and `y >= c`。CVX 可以处理。
`max(expr1, expr2, ..., exprN)`: CVX 支持。
`min(expr1, expr2, ..., exprN)`: CVX 支持。
`sum(x)` / `norm(x)`: CVX 支持。
步骤四:使用 CVX 提供的“辅助”函数
CVX 提供了一些非常有用的函数来帮助你构建凸模型:
`quad_form(x, P)`: 用于表示二次型 `x' P x`。关键是 `P` 必须是半正定的 (PSD),CVX 才会将其识别为凸的(如果是最小化问题)。如果 `P` 不是 PSD,CVX 会报错。
`norm(x, p)`: 如前所述,`p=1, 2, Inf` 是凸的。
`inv_pos(x)`: 1/x,要求 x > 0。
`log(x)`: 要求 x > 0。
`log_det(X)`: 要求 X 是半正定的。
`square(x)`: x^2,是凸的。
`sum_square(x)`: sum(x.^2),是凸的。
`real(z)`: 对于复数变量 `z`,`real(z)` 是凸的,`imag(z)` 也是凸的。
`norm_sq(x)`: `sum(x.^2)` 的简写。
`lambda_min(A)`: A 的最小特征值。`lambda_min(A) >= 0` 是一个 SDP 约束。
`trace(X)`: X 的迹。
`rel_entr(x, y)`: 相对熵 `xlog(x/y)`。CVX 支持,是凸的。
步骤五:检查变量的定义和维度
维度不匹配: 确保所有向量和矩阵的维度在你进行运算时是匹配的。例如,`xy'` (x 是列向量,y 是列向量) 是一个矩阵,而 `x'y` 是一个标量。
复数变量: 如果你的变量是复数,CVX 有专门的处理方式。
Hermitian 矩阵: `X` 是 Hermitian 矩阵时,`X` 的虚部必须为零,即 `imag(X) == 0`。
PSD 约束: 对于复数变量,PSD 约束写为 `X >= 0`。
处理复数乘积: `z conj(z)` (当 z 是复变量) 是 `norm(z, 2)^2`,这是凸的。CVX 会自动处理。但是 `z1 z2` (z1, z2 是复变量)则是非凸的。
步骤六:使用 CVX 的“可视化”和调试功能
CVX 的 `verbose` 模式: 在 `cvx_begin` 后面加上 `cvx_solver ...` (例如 `cvx_solver sedumi`),然后 `cvx_begin ... cvx_verbose(true) ... cvx_end`。这会输出更多关于 CVX 如何尝试转换模型的信息,有时候能提供线索。
逐步构建模型: 如果模型很复杂,可以先从一个简单的版本开始,逐步添加约束和目标函数项,每次都尝试求解,这样更容易定位是哪个部分引入了非凸性。
检查中间结果: 如果你怀疑某个变量的定义或某个中间计算结果有问题,可以尝试在 CVX 求解前打印出来(虽然 CVX 求解函数本身并不直接支持打印内部变量,但你可以先进行一些 MATLAB 运算来验证)。
实际案例:一个常见的错误场景
假设你在做一个信号处理问题,需要最小化一个目标函数,其中包含了 `sum(x . y)`,并且 `x` 是一个已知的常数向量,`y` 是待优化的变量向量。
错误的写法(可能引起 CVX 报错):
```matlab
cvx_begin
variable y(N)
% 假设 x 是一个已知的 N x 1 的常数向量
% 错误地认为 x.y 可能是非凸的
minimize( sum(x . y) + some_other_convex_term );
cvx_end
```
正确的写法:
CVX 可以直接处理一个已知常数向量与变量向量的逐元素乘积。`x . y` 在这种情况下是线性的,是凸的。
```matlab
cvx_begin
variable y(N)
% 假设 x 是一个已知的 N x 1 的常数向量
% x.y 是线性的,CVX 可以直接处理
minimize( sum(x . y) + some_other_convex_term );
cvx_end
```
另一个例子: 假设你的模型是 `minimize sum(square(y) ./ x)`,其中 `x` 是一个已知的正数常数。
错误的写法:
```matlab
cvx_begin
variable y(N)
% 假设 x 是一个已知的正数常数
minimize( sum(square(y) / x) ); % CVX 可能报错 'Cannot convert ... to a constrained convex form.'
cvx_end
```
正确的写法:
将常数 `1/x` 提取出来,或者将除法转换为乘法:
```matlab
cvx_begin
variable y(N)
% 假设 x 是一个已知的正数常数
minimize( sum(square(y)) / x ); % 这样写更清晰,CVX 可以处理
% 或者
% minimize( (1/x) sum(square(y)) );
cvx_end
```
总结
遇到“Cannot convert ... to a constrained convex form.”错误,核心在于理解 CVX 只处理凸优化问题,并仔细检查模型的非凸部分。
1. 定位问题:错误信息是你的向导。
2. 审视模型:目标函数和所有约束条件的凸性。
3. 识别非凸项:变量乘法、非凸函数、除法等。
4. “CVX 化”:
利用 CVX 支持的凸函数(`quad_form`, `norm`, `log_det` 等)。
将问题转化为 SDP 或 SOCP(如果可能)。
使用数学技巧(如对数变换、舒尔补)来重写非凸项,使其变成凸的。
谨慎使用 `cvx_accept_nonconvex`,它不保证收敛性或最优性。
5. 变量检查:维度、取值范围(如 `inv_pos` 要求正数)。
解决这类问题通常需要对凸优化理论有一定的理解,以及耐心和细致的模型调试。多尝试,多查阅 CVX 的官方文档和示例,你会越来越熟练的!