将二次约束转换为二阶锥约束

此例说明如何将二次约束转换为二阶锥约束形式。二次约束的形式为

$x^{T} Q x + 2 q^{T} x + c \leq 0 .$

二阶锥规划具有以下形式的约束

$‖ A_{s c} (i) \cdot x - b_{s c} (i) ‖ \leq d_{s c} (i) \cdot x - γ (i)$ .

为了转换二次约束，矩阵 $Q$ 必须是对称且半正定的。令 $S$ 为 $Q$ 的平方根，即 $Q = S * S = S^{T} * S$ 。您可以使用 sqrtm 计算 $S$ 。假设方程 $b$ 有一个解 $S^{T} b = - q$ ，当 $Q$ 为正定方程时，该解恒为真。使用 b = -S\q 计算 $b$ 。

$\begin{array}{l} x^{T} Q x + 2 q^{T} x + c & = x^{T} S^{T} S x - 2 {(S^{T} b)}^{T} x + c \\ = {(S x - b)}^{T} (S x - b) - b^{T} b + c \\ = {‖ S x - b ‖}^{2} + c - b^{T} b . \end{array}$

因此，如果 $b^{T} b > c$ ，则二次约束等同于二阶锥约束，其中

$A_{s c} = S$
$b_{s c} = b$
$d_{s c} = 0$
$γ = - \sqrt{b^{T} b - c}$

数值示例

指定一个五元素向量 f 来表示目标函数 $f^{T} x$ 。

f = [1;-2;3;-4;5];

将二次约束矩阵 Q 设置为 5×5 随机正定矩阵。将 q 设置为随机的 5 元素向量，并取加法常数 $c = - 1$ 。

rng default % For reproducibility
Q = randn(5) + 3*eye(5);
Q = (Q + Q')/2; % Make Q symmetric
q = randn(5,1);
c = -1;

要创建 coneprog 的输入，请创建矩阵 S 作为 Q 的平方根。

S = sqrtm(Q);

按照本例第一部分的规定，创建二阶锥约束的其余输入。

b = -S\q;
d = zeros(size(b));
gamma = -sqrt(b'*b-c);
sc = secondordercone(S,b,d,gamma);

调用 coneprog 以求解问题。

[x,fval] = coneprog(f,sc)

Optimal solution found.

fval = 
-4.6148

将此结果与使用 fmincon 求解同一问题返回的结果进行比较。按照匿名非线性约束函数所述写出二次约束。

x0 = randn(5,1); % Initial point for fmincon
nlc = @(x)x'*Q*x + 2*q'*x + c;
nlcon = @(x)deal(nlc(x),[]);
[xfmc,fvalfmc] = fmincon(@(x)f'*x,x0,[],[],[],[],[],[],nlcon)

Local minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

<stopping criteria details>

xfmc = 5×1

   -0.7196
    0.2672
   -0.6312
    0.2541
   -0.0902

fvalfmc = 
-4.6148

这两个解几乎相同。

另请参阅

coneprog | quadprog | secondordercone

将二次约束转换为二阶锥约束

数值示例

另请参阅

主题