5.4.1. 半定规划建模¶
Note
本页公式多,打开慢,请等待公式显示正常后阅读。
关于半定规划(Semi-Definite Programming,SDP)问题,可参看 官网 了解更详细介绍和应用场景与求解方法。
其数学表达形式,为了方便理解,我们从最基础的线性规划讲起,慢慢推广到半定规划。
对于线性规划,它是一个在线性等式和不等式约束下的最小化 (有时或最大化) 线性目标函数的优化问题,同 线性规划建模,将该线性规划公式转为标准形式,则数学公式如下:
其中
是优化变量,
是目标函数向量,
是线性等式约束矩阵,
是线性等式约束的常数项, 最后,不等式
表示 。即, 处于坐标的非负象限。
简单地说,这个线性规划问题是:我们要从所有非负向量与线性等式解的交集中找到具有最小值
半定规划是线性规划的推广,具有非常相似的数学标准形式:
其中
为优化变量,这里 表示所有的 对称矩阵的集合。
是线性等式约束的常数项。
是线性等式约束中的算子,其定义为: 这里
是给定的系数矩阵。 因此线性等式约束
即为 , 。 最后,不等式
表示 是半正定 (Positive semidefinite, PSD) 对称矩阵, 即
这里 表示所有 半正定对称矩阵的集合。 具体来说给定
若满足下面任意条件则 :
所有的特征值皆为非负;
所有的二次式皆为非负:
。
同理,半定规划是从