5.4.1. 半定规划建模

Note

本页公式多,打开慢,请等待公式显示正常后阅读。

关于半定规划(Semi-Definite Programming,SDP)问题,可参看 官网 了解更详细介绍和应用场景与求解方法。

其数学表达形式,为了方便理解,我们从最基础的线性规划讲起,慢慢推广到半定规划。

对于线性规划,它是一个在线性等式和不等式约束下的最小化 (有时或最大化) 线性目标函数的优化问题,同 线性规划建模,将该线性规划公式转为标准形式,则数学公式如下:

minc,xs.t.Ax=bx0

其中

  • x=[x1,x2,,xn]TRn 是优化变量,

  • c=[c1,c2,,cn]TRn 是目标函数向量,

  • ARm×n 是线性等式约束矩阵,

  • bRm 是线性等式约束的常数项,

  • 最后,不等式 x0 表示 xk0,k[n]。即,xR+n 处于坐标的非负象限。

简单地说,这个线性规划问题是:我们要从所有非负向量与线性等式解的交集中找到具有最小值 c,x=cTx 的最优解 x

半定规划是线性规划的推广,具有非常相似的数学标准形式:

minC,Xs.t.A(X)=bX0

其中

  • XSn 为优化变量,这里 Sn 表示所有的 n×n 对称矩阵的集合。

  • bRm 是线性等式约束的常数项。

  • A:SnRm 是线性等式约束中的算子,其定义为:

    A(X)=[A1,XAm,X]

    这里 AkSn,k[m] 是给定的系数矩阵。

    因此线性等式约束 A(X)=b 即为 Ak,X=bk, k[m]

  • 最后,不等式 X0 表示 X 是半正定 (Positive semidefinite, PSD) 对称矩阵,

    XS+n 这里 S+n 表示所有 n×n 半正定对称矩阵的集合。

    具体来说给定 XSn, 若满足下面任意条件则 XS+n:

    1. 所有的特征值皆为非负;

    2. 所有的二次式皆为非负: aTXa0,aRn;

    3. X=UUT,URn×n

同理,半定规划是从 S+n 与线性等式解的交集中找到具有最小值 C,X=trace(CTX) 的最优解 X

5.4.1.1. 半定规划问题示例

我们将考虑两个SDP问题例子,分别为只有一块和多块变量的半定规划问题。我们将展示如何使用 MindOpt 来建模和优化这两个问题。

5.4.1.1.1. SDP示例1

maxC,X s.t. A,X=1X0

其中,

C=[301020103],

以及

A=[301040105].

5.4.1.1.2. SDP示例2

maxC0,X0+C1,X1 s.t. A00,X0+x0=1A11,X1+x1=2X0,X10x0,x10

其中,

  • C0=[2112],
  • C1=[301020103],
  • A00=[3113],
  • A11=[301040105].

我们将分别给出不同编程语言下的示例,来展示如何使用 MindOpt 建模和求解上述优化问题。