1.1　数学规划模型的分类

数学规划与数学优化密不可分，这里先来介绍数学优化。数学优化是数学中一个重要的学科方向，是应用数学的重要组成部分。按照是否有约束条件，数学优化可以分为无约束优化和约束优化[1]。无约束优化的一般形式为：

max或minf（x）

其中，x=［x1，x2，…，xn］T∈Rn（Rn为n维实数集），为决策变量；f（x）：Rn→R，为目标函数。f（x）可以为凸函数、凹函数或者非凸非凹函数。无约束优化的主要方法包括线搜索方法、梯度类算法、牛顿法、次梯度算法、拟牛顿算法等。若优化问题的解（即决策变量x的取值）必须满足一定的限制条件，则问题变化为约束优化问题。约束优化问题是本章探讨的重点。

约束优化问题是指决策变量取值受到一定限制的优化问题，其一般形式为：

其中，x=［x1，x2，…，xn］T∈X⊂Rn，表示n×1维的决策变量。f（x）、gi（x）、hi（x）均是关于x的函数。式（1.2）和式（1.3）分别被称为等式约束和不等式约束。gi（x）和hi（x）叫作约束的左端项，bi和ci叫作约束的右端项或者右端常数。记号s.t.是“subject to”的缩写，用于表示约束条件。任意满足等式约束式（1.2）、不等式约束式（1.3）和式（1.4）的解被称为可行解。所有可行解构成的集合被称为可行域。在可行域内，函数f（x）的最大值/最小值不一定总是存在的。幸运的是，函数f（x）在可行域内的上/下确界一定存在（如约束为严格大于或者小于约束）。若式（1.1）～式（1.4）的最大值/最小值不存在，可以将问题转换为求f（x）在可行域内的上/下确界。此时，上述模型中的“max（min）”就需要相应地改为“sup（inf）”。

介绍完基本概念之后，回到本章的主题：数学规划。根据中国运筹学会发布的《中国数学规划新近进展及展望》[2]，数学规划又叫数学优化，是运筹学的一个重要分支。形如式（1.1）～式（1.4），由目标函数、约束条件和决策变量构成的数学优化模型也被称为数学规划模型。

根据f（x）、g（x）和h（x）以及决策变量x的类型，可以将数学规划模型划分为若干不同的种类，见表1.1。

表1.1　数学规划模型的种类

由图1.1可见，数学规划模型之间是存在相互包含关系的。当锥规划（Cone Programming，CP）的目标函数为线性表达式，且约束包含半正定约束时，CP退化为SDP。由于二阶锥约束可以被等价地写成线性矩阵不等式（Linear Matrix Inequalities，LMI）。换言之，二阶锥约束是半正定约束的一个特例。因此，SOCP是SDP的一个特例，即SOCP包含于SDP。注意，半正定约束不一定可以转换为二阶锥约束。QP可以通过模型重构等价转换为特殊的SOCP，因此，QP是SOCP的一个特例。当QP的目标函数退化为线性表达式时，QP退化为LP。

图1.1　各种数学规划模型之间的关系