数学表达
$x$ 变量集合，也叫未知参数
$f$ 目标函数
$c_i$ 约束函数，即$x$必须满足的特定等式和不等式的标量函数
使用上述定义，优化问题可以描述为
$$ \underset{x \in R^n}{\text{min}} \quad \text{subject to} \quad
\begin{array}{c}
{c_i(x)=0,\quad i \in \varepsilon ,}\\
{c_i(x) \geqslant 0,\quad i \in \tau .}\\
\end{array}
$$
这里$\varepsilon$和$\tau$分别是等式和不等式约束的下标。
分类
连续优化与离散优化
如果输入$x_i \in Z$，Z是整数集或二元约束($x_i \in {0,1}$)，这种类型的问题称为整数规划问题(Integer Programming)。
如果其中一些变量并不只限于整数集或二元约束，这种称为混合整数规划问题(Mixed Integer Programming)。
整数规划问题是一种离散的优化问题。通常离散优化问题并不只包含整数或二元变量，还包含更多的抽象的变量对象，例如有序集合的组合。离散优化问题的基本特征是$x$取自有限集合。相反地，连续优化问题的可行集合通常是无穷的。连续优化问题一般更容易求解，因为函数的平滑性可以让我们使用特定点$x$的目标和约束信息来推断$x$周围点的信息。而离散有问题则相反，其可行集合可以认为是去证明非凸的极限形式，而两个可行点的凸组合通常是不可行的。连续优化问题通常在解决离散优化问题上发挥了重要作用。例如，解决整数线性规划问题的分支定界 (branch and bound) 算法，这个算法需要线性规划松弛得多重解，其中一些整数变量固定为整数值，而另外一些整数变量的完整性约束被临时忽略。这些子问题通常用单纯形法(simplex method)解决。
全局优化与局部优化
很多非线性问题的算法只能求得局部最优解，在目标函数中该点的值小于附近的可行点的值。凸规划问题的局部最优解也是全局最优解。一般的非线性问题，不管是有约束还是无约束，局部最优解未必是全局最优解。然而，许多成功的全局优化算法也需要局部优化问题的解。
随机优化与确定优化
在许多优化问题中，因为依赖时间相关的未知量，模型不能够完全确定。例如许多经济学发展模型，可能依赖未来的利率、未来商品的需求量和定价，所有这种类型的应用天然带有不确定性。模型建立者通常将关于这些不确定量的知识包含在模型之中，而不是用猜的方式。例如，可事先建立商品需求的随机数集合，随着评估每个随机数的可能性，他们也就可能知道一些可行的随机数。随机优化使用这些不确定的量来产生解，再用这些解来优化模型的预期性能。很多随机优化的算法，是通过分解成一个或多个确定优化的子问题来求解的。
凸
凸的概念是优化的基础。许多实际的问题都有这个属性，使得它们能够容易地被解决。术语“凸”可以应用在集合和函数上。一个集合$S\in R^n$，如果$S$中任意两点之间的线段上的点全部都在$S$中，那么就是凸集合。概括成公式，对于任意两个点$x \in S$ 和$y \in S$有，我们有
$$\alpha x+(1-\alpha x)y \in S ,\alpha \in [0,1]$$
值域$S$是凸集合的函数$f$是凸函数，即：
(1) $$ f(\alpha x+(1-\alpha)y) \leqslant \alpha f(x)+(1-\alpha )f(y) ,\alpha \in [0,1]$$
凸集合的一个简单例子是单位球$\{y \in R^n | \lVert y \rVert _2 \leqslant 1\}$
当中$x \neq y$ 而且$\alpha$在开区间$(0,1)$时，在(1)中是严格不等的，我们说$f$是严格凸的。如果$-f$是凸的，称$f$是凹的。
如果目标函数和可行域都是凸的，那么问题的局部最优解就是全局最优解。
术语“凸优化”用来描述通用有约束优化问题的一个特例：
- 目标函数是凸的
- 等式约束函数$c_i(·),i \in \varepsilon$是线性的
- 不等式约束函数$c_i(·),i \in \tau$是凹的
优化算法
优化算法是迭代的。算法使用初始的$x$的猜测值，产生一系列改进的估计，直到停止。许多算法是是同目标函数的值$f$，约束函数$c_i$，或许还用目标函数的一阶导数或二阶导数。一些算法通过收集之前迭代的信息来加速，另外的则仅使用当前点的局部信息。好的算法应该满足以下属性：
- 鲁棒。
- 高效。
- 精确。
不过这些目标可能冲突。
总结
本章大体介绍了最优化的一些基本概念以及分类，为以后的学习打下基础。
原创文章，转载请注明出处。
刘文武 2016年9月5日 于 电子科大航空航空学院
