CPLEX C++学习笔记(3) - 二次约束 (QCP) 问题求解

原文 ^[1]

1. 识别二次约束规划

该章节定义CPLEX可求解的二次约束规划的类型.

1.1. 二次约束规划的特征

区别QCP的特征是: 二次项可能出现在问题的一个或多个约束中. 但 此类问题的目标函数可能包含也可能不包含二次项. 因此QCP的最一般形式如下:

Minimize \frac{1}{2} x^T Q x + c^T x

subject to Ax \sim b

with these bounds l \leq x \leq u

符号 \sim 可以是等于, 小于等于, 大于等于, 甚至是范围约束的任意组合. l 和 u 分别表示上下限. Q 是目标函数系数的矩阵. 也就是说, 元素 Q_{jj} 是二次项 x_j^2 的系数, 元素 Q_{ij} 和 Q_{ji} 加在一起作为项 x_i x_j 的系数. CPLEX区分下面两种 Q 矩阵:

• 在可分离问题中, 仅有矩阵的对角项被定义了, 所有的非对角项都为0.
• 在不可分离的问题中, 矩阵中至少一个有一个非对角项为非零值.

CPLEX可以求解有着 凸二次目标函数的 最小化 问题. 同样, 它可以求解有着 凹二次目标函数 的 最大化 问题. 对于最小化和最大化, 所有线性目标函数都满足这一属性. 但是对于二次目标函数并非总是如此.

CPLEX也可以计算局部最优点, 也就是满足具有任意二次目标函数的模型的 一阶最优条件 (也就是局部最优) . 这些模型包括有着凹目标函数的最小化问题, 有着凸目标函数的最大化问题, 以及有着既不凸也不凹的目标函数最小化或者最大化问题. 这样的点也许不是模型的全局最优解.

连接目标函数上任意两点的连续线段不会低于最小化问题的目标; 同理, 该线段不会高于最大化问题的目标. 如下图所示:

更正式地说, 二次目标函数是凸还是凹的问题等价于矩阵 Q 是正半定还是负半定的问题. 对于凸QPs, Q 必须是正半定(也就是对于每个向量 x 都满足 x^T Q x \geq 0 ). 对于凹最大化问题, 要求 Q 必须是负半定 (也就是对于每个向量 x 都满足 x^T Q x \leq 0 ).

对于可分离函数, 要确定问题的凸性, 检查矩阵 Q 的各个对角元素是否有正确符号来保证其正或负半定 就已足够. 对于不可分离函数, 事先确定 Q 的凸性可能不太容易, 但CPLEX会在优化的前期检测这一属性. 默认情况下, 当CPLEX发现QP中的二次目标项为 非半正定 时终止.

作为一个二次目标函数, 凸性对二次约束至关重要. 每一项约束都必须定义一个凸域. 为确保凸性, CPLEX 要求每个 P_i 矩阵都为正半定, 或者 约束可以被转换为 二阶锥 (second order cone) .

1.2. 凸性

不等式 x^2 + y^2 \leq 1 是凸的. 下图显示了不等式的图形:

如果将 a 和 b 视作该约束的域中的任意值, 不难发现, 它们之间的任何连续线段都完全包含在该域中.

而不等式 x^2 + y^2 \geq 1 是凹的. 下图显示了不等式的图形:

显然, cd的连续线段可能会经过此约束的域的外部. 同理, x^2 + y^2 = 1 也是非凸的.

1.3. 半定性

根据章节1.1的说明, 为保证凸性, 每项约束中的二次矩阵都必须为正半定. 对于每个向量 x , 无论 x 是否可行, 如果满足 x^T Q_i x \geq 0 , 则矩阵 Q_i 为正半定.

1.4. 二阶锥规划 (SOCP) 和 非半正定

半正定需求有一个例外情况: 有一种额外的二次约束, 该约束未被包含在章节1.1的一般形式中. 技术上来说, barrier优化器求解的二次约束问题是一个 二阶锥规划(SOCP). CPLEX可以通过其预处理功能来执行转换到SCOP, 并返回原始formulation的解. 如果约束可以转换为下面的凸二阶锥约束, 那么barrier优化器将接受该约束以求解:

-c_0 x_0^2 + \sum c_i x_i^2 \leq 0

CPLEX自动换这些类型的二次约束至二阶锥约束:

x^T Q x \leq y^2 , 其中 y \geq 0 且 Q 为正半定

x^T Q x \leq y z , 其中 y \geq 0, z \geq 0 且 Q 为正半定

注意, 当 Q 为单位矩阵时, 这个formulation被称为旋转锥.

1.5. 以拉格朗日表示SOCP

SOCP是特殊的因为任意QCP都可以被转换成等价的SOCP. CPLEX利用这一等价性来返回更多信息, 例如对偶值, 和缩减代价. 一个SOCP是一个优化问题, 其中 x_i 是一对对不相交的向量 x_i = (x_{i, 1}, ..., x_{i, i_n}) :

min c_1^T x_1 + ... + c_r^T x_r

s.t. A_1 x_1 + ... + A_r x_r = b

x_i \succeq 0

其中对变量 x_i 的二阶锥约束定义如下:

x_i \succeq 0 \quad \Longleftrightarrow \quad x_{i, 1} \geq ||(x_{i, 2}, ..., x_{i, n_i})||

|| \cdot || 表示向量的欧几里得范数. 且当 n_i = 1 时, x_i \succeq 0 将缩减至 x_{i,1} \succeq 0 的形式. 也就是说, 一个二阶锥约束, 如下不等式:

x_{i, 1} \geq ||(x_{i, 2}, ..., x_{i, n_i})||

等价于这两个约束:

-x_{i, 1}^2 + \sum_{k = 2}^{n_i} x_{i,k}^2 \leq 0

x_{i, 1} \geq 0

有了二阶锥约束的标准形式, 我们可以指定目标函数, 以及SOCP的线性约束. 然后, 还可以为模型中的每个二阶锥约束另外指定上述两个相等的约束.

为了阐明指定 SOCP 的过程，我们考虑以下模型：

min x_1 + x_2 + x_3 + x_4 + x_5 + x_6

s.t. x_1 + x_2 + x_5 = 8

x_3 + x_5 + x_6 = 10

(x_1, x_2, x_3) \geq 0

(x_4, x_5) \geq 0

(x_6) \geq 0

上面的模型中有两个普通的线性约束:

x_1 + x_2 + x_5 = 8

x_3 + x_5 + x_6 = 10

乍看之下, 似乎有三个要考虑的二阶锥:

(x_1, x_2, x_3) \geq 0

(x_4, x_5) \geq 0

(x_6) \geq 0

根据过程, 必须对模型中的每个二阶锥约束指定两个等同的约束. 对于第一个二阶锥, 考虑 x_1 \geq ||(x_2, x_3)|| , 则会产生如下约束:

-x_1^2 + x_2^2 + x_3^2 ≤ 0 且 x_1 ≥ 0

同样地, 根据这一过程, 考虑第二个二阶锥:

-x_4^2 + x_5^2 \leq 0 且 x_4 \geq 0

第三个二阶锥仅有一个变量, 这意味着 x_6 有下限0. 最终结果如下所示:

Minimize
   obj: x1 + x2 + x3 + x4 + x5 + x6
Subject To
    c1: x1 + x2 +           x5      = 8
    c2:           x3 +      x5 + x6 = 10
    q1: [ -x1^2 + x2^2 + x3^2 ] <= 0
    q2: [ -x4^2 + x5^2 ] <= 0
Bounds
    0 <= x1