最优化原理与方法之（一）开篇

1 引言

最优化理论与方法是一门应用性很强的年轻学科，本质上它是研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。

虽然最优化可以追溯到十分古老的求极值的问题。但是，它称为一门独立的学科是在十九世纪的40年代末，即在1947年Dantzig提出求解一般线性规划问题的单纯形法之后。现在，解线性规划、非线性规划、随机规划、非光滑规划、多目标规划等最优化问题的理论研究发展迅猛，新的方法不断出现，并且实际应用日新月异。尤其是在互联网软件技术的推动下，最优化里面在机器学习与深度学习领域发挥巨大的作用，称为一门十分活跃的热门的学科。

但是这门学科亦属于多学科的交叉领域，是多个领域的集大成者的强强组合。

2 定义

最优化问题的一般形式为

​ $$minf(x)$$

​ $$s_{.}{t}_{.}x\in X$$

其中$x\in R^n$是决策变量，$f(x)$为目标函数，$X\subset R^n$为约束集或可行域。

• 无约束最优化问题

如果约束集$X=R^n$，则最优化问题称为无约束最优化问题。公式如下

​ $$\underset{x\in R^n}{\min }f(x)$$

• 有约束最优化问题

约束最优化问题通常写为，这里的E和I分别是等式约束和不等式约束的指标集，$C_i(x)$是约束函数。

​ $$minf(x)$$

​ $$s_{.}{t}_{.}{C}_i(x)=0,i\in E,$$

​ $$s_{.}{t}_{.}{C}_i(x)>=0,i\in I,$$

3 划分

• 根据函数的性质划分：

  • 线性划分：当目标函数和约束函数为线性函数的时候，问题是线性规划。
  • 非线性划分：当目标函数和约束函数中至少有一个是变量x的非线性函数的时候，问题是非线性规划。
  • 二次规划：若目标函数是二次函数，约束函数是线性函数

• 根据可行域（约束集）的性质划分：

  • 若可行域内点的个数是有限的时候，则称问题为离散最优化问题。
    • 若变量为整数，则称其为整数规划问题。
    • 若部分变量是整数，而另外一部分变量是连续变化，则称其为混合整数规划问题。
  • 若可行域内点的个数是无穷的时候，则称问题为连续最优化问题。

• 根据函数的向量性质划分：

  • 若目标函数为向量函数，则称问题为多目标规划问题。
  • 若目标函数为数量函数，则称问题为单目标规划问题。

• 根据规划问题有关信息的确定性划分：

  • 若目标函数或约束函数具有随机性，也就是说问题的表述形式随着时间的变化而变化，具备不确定性，则这样的优化问题称为随机优化。
  • 如果优化问题的变量（函数）具有模糊性，则这样的优化问题为模糊优化。
  • 如果目标函数和约束函数都是确定的，则这样的优化问题称为确定性规划问题。