优化是对各种实际问题作出有效决策或预测的技术。简言之，作出决策的过程要先从为具体问题建立合适的数学模型开始，然后通过应用有效的数值算法来求解模型。一个优化设计是在满足该问题所有的约束条件下，给出尽可能最优的目标值。

本章将介绍优化问题的主要概念和构成部分，本章的许多概念并没有给出正式的定义，将在后面的章节中提供更加严谨的定义表述。

优化问题

定义

优化问题的标准形式。这将主要处理可以写成如下标准形式的优化问题：

其中，

  • 向量$x\in\mathbb{R}^n$是决策变量；
  • $f_0$：$\mathbb{R}^n\to\mathbb{R}$是目标函数或成本函数；
  • $f_i$：$\mathbb{R}^n\to\mathbb{R}，i=1,···，m$，表示约束函数；
  • $p^*$表示最优值。

带等式约束的优化问题。在有些情况下，问题可能会出现明确的等式约束和不等式约束，即：

其中$h_i$是给定的函数。

带集合约束的优化问题。在有些情况下，问题的约束条件是通过$x\in\chi$这种集合元素约束的抽象形式表示的，其中$\chi$为$\mathbb{R}^n$的子集，相应的数学表示为：

或也可以表示为

最大值形式的优化问题。一些优化问题以求目标函数最大值（而不是最小值）的形式出现，也就是：

这种问题很容易转化为求最小值的标准问题，事实上，对于任意$g_0$,都有：

因此，求最大值问题可以重新表述为如下求最小值问题,其中$f_0(x)=-g_0(x)$

可行集。问题（1.1）的可行集定义如下：

如果点$x$属于可行集$\chi$，也就是说，它满足约束条件，那么称$x$对于问题（1.1）是可行的。如果不可能同时满足所有约束条件，那么可行集就是空集，在这种情况下称该问题是不可行的。为了方便起见，对于不可行的最小化问题，记其最优值为$p^=+\infty$；对于不可行问题的最大值问题，记其最优值$p^=-\infty$。

问题的解是什么

对于一个优化问题，我们通常对计算目标函数的最优值及相应的最小值点感兴趣，这里的最小值点是使目标函数达到最优值的点且满足约束条件的向量。

可行性问题。在一些情况下并没有提供目标函数，这意味着我们只是对找到一个可行点感兴趣，或者是想要确定问题不可行。通常若问题是可行的，我们一般将$f_0$设置为常数以表示对点$x$的选择并不重要。对于具有标准形式（1,1）的问题的求解，等价于寻找一个满足不等式$f_i(x)\leq0(i=1,···,m)$的点。

最优集。问题（1,1）的最优集或解集被定义为目标函数达到最优解的可行点集：

为了表示最优集，其标准的符号是使用argmin：

最优集何时为空集。最优集可能会不存在，因此最优集也可能是空集。这有两个原因，一个是该问题是不可行的，即$\chi$本身是空集（没有满足约束条件的点）；另一个原因更加微妙，虽然$\chi$不是空集，但是最优值只能在极限条件下达到。例如，如下优化问题：

就没有最优点，因为其最优值$p^*=0$只能在$x\to+\infty$的极限情况下达到。另一个例子是当约束条件包括严格不等式时，例如：

次最优性。如果一个点$x$对于问题（1,1)是可行的且满足如下条件：

则称它是$\epsilon$次最优的。换言之，点$x$是$\epsilon$接近达到最优值$p^*$的，通常，数值计算只能计算次最优解，永远无法实现真正的最优解。

局部与全局最优点

称点$z$为问题（1.1）的一个局部最优点，如果存在R>0使得$z$对于以下问题是最优的：

换言之，局部最小值点$x$只能在可行集中的领域内最小化$f_0(x)$。

全局最优（或简称最优）这一概念用于区分最优集$\chi_{opt}$中的点和局部最优点。

可处理和不可处理的问题

一些类型的问题，如寻找有限的线性等式或不等式组的解，可以用数值方法可靠有效地求解；相反，对于其他某些优化问题，目前没有可靠有效的解决方法。我们的重点是聚焦可处理的模型，特别地，可以用线性代数问题的形式或凸形式表述的模型通常都是可处理的。此外，如果一个凸模型有一些特殊的结构，那么人们通常可以使用现有的非常可靠的数值计算包找到最优解，如CVX、Yalmip等。

我们需要注意可处理性通常不是问题本身的特性，而是由我们对问题的表述和建模所决定的。如果在建模阶段投入更多的精力和智慧，一个在某种表述下看起来很难处理的问题可能会变得容易处理。

问题的变换

由问题（1.1）所表述的优化形式非常灵活，允许我们作很多变换，有助于将给定的问题转化为可处理的形式。例如，如下优化问题：

与如下优化问题

具有相同的最优集，这样的好处是目标函数是可微的。在其他情形下，变量代换往往也是有用的方法，例如对数变换。

优化问题的重要类型

最小二乘和线性方程

一个线性最小二乘问题可以用以下形式来描述：

其中$A_{ij},b_i(1\le i\le m,1\le j\le n)$是给定的常数，$x\in\mathbb{R}^n$为变量。最小二乘问题出现在许多情形下，如线性回归等统计估计问题中。

最小二乘法在求解一组线性方程系统中有重要作用。假设我们想找到一个向量$x\in\mathbb{R}^n$使得：

这类问题可以归结为形式（1.3）的最小二乘问题。如果式（1.3）的最优值为0，则找到了对应方程的解；否则，式（1.3）的最优解给出了线性方程组的近似解。

低秩近似与最大方差

对于给定矩阵（矩阵元素为$A_{ij}(1\le i\le m,\ 1\le j\le n)$）的秩一近似问题形式如下：

上述问题可以解释为最小二乘问题（1.3）的一个变形，其中平方项内的函数是非线性的，这是因为存在变量$zix_j$，目标函数越小，意味着$A{ij}$可以更好地被$z_jx_i$近似。因此，“行”都是相同向量（$x_1,···,x_m$）经过以（$z_1,···,z_m$）为尺度的尺度变换后的向量。

线性规划与二次规划

线性规划（LP）问题具有如下形式：

其中$cj,\ b_i$和$A{ij}(1\le i\le m,\ 1\le j\le n)$是给定的实数。该问题是一般问题（1.1）的特例，其中函数$f_i(i=0,···,m)$都是仿射的（即线性项加常数项）。线性规划是优化领域中使用最广泛的模型。

二次规划问题（QP）是线性规划的进一步扩展，其对应的目标为二次函数，二次规划是将上述线性规划问题修改如下：

其中$C_{ij}(1\le i\le r,1\le j\le n)$是给定的常数。QP可以被认为是最小二乘和线性规划问题的进一步推广。

凸优化

凸优化是形如式（1.1）的优化问题，其中目标函数和约束函数具有凸性这种特殊性质。粗略地说，凸函数呈现出一个“碗形”图。

最小二乘、LP和（凸）QP模型是可处理的凸优化的例子。

组合优化

在组合优化问题中，其决策变量是布尔类型（0或1），或更一般的整数，它反映了要做出的离散选择。许多实际问题还涉及整数和实值变量的混合，因此称这种问题为混合整数规划（MIP），组合问题或更一般的MIP往往属于计算比较困难的问题。

非凸优化

非凸优化对应于标准形式（1.1）中的一个或多个目标或约束函数不具有凸性的优化问题。

一般来说这类问题很难求解，原因之一是他们可能存在局部极小值点。然而，应该注意的是，不是每个非凸优化问题都很难求解。例如，前文中的最大方差和低秩近似问题尽管都是非凸问题，但他们可以用线性代数中的特殊算法很好地求解。