【最优化理论】人工智能与最优化理论的联系

1.最优化理论的主要分支

最优化理论的主要分支有两类，包括针对一般问题的数学规划模型以及针对特定问题的数学规划模型，其各自涵盖的范围如下：

一般问题的数学规划模型：

• 线性规划
• 整数规划
• 非线性规划
• 动态规划
• 网络流优化
• …

特定问题的数学模型：

• 网络计划
• 排队论
• 存储论
• 决策论
• 对策论
• …

2.优化方法简述

例如优化问题为 $\max f(x)$，其函数图像如下：

优化的基本方法是：从 a, b 之间的任一点出发，朝着能改进目标函数的方向搜索前进：$X_{k+1}=X_k+{\lambda }_k{D}_k$，直到不能改进目标函数。这种方法最终一定能够收敛到一个局部最优解，但不能保证全局最优。

走出局部最优解的唯一途径：在搜索过程中允许前进到目标函数值变差的点，但是由此产生的新问题是无法保证算法收敛！

为了使算法收敛，只能引入不确定性，让算法在任何一点以一定的概率前进到临近的某点，移动概率和相应点的目标函数值正相关，即目标函数值大的地方，其移动概率大，反之则移动概率小，由此产生的算法是结果不确定的算法。

2.1 确定型搜索与不确定型搜索

上面的例子简单介绍了优化方法最基本的类型：确定型搜索与不确定型搜索。

前者是经典的最优化、运筹学教材介绍的主要内容，而后者包括模拟退火、禁忌搜索、遗传算法、免疫算法、蚂蚁算法等，一般统称为智能算法。

3.人工智能与优化理论的联系

当前非常火的人工智能与优化理论有着非常紧密的联系，人工智能的一系列问题，如回归、辨识、估计、训练、学习、拟合、逼近等问题都有与其对应的优化模型。

3.1 机器学习中的优化问题

已知某个标量 $y$ 和某个向量 $X=(x_1,x_2,...,x_n{)}^T$ 之间若干个一一对应的样本数据：

{ y ( t ) , X ( t ) }       X ( t ) = ( x 1 , x 2 , . . . , x n ) T , t = 1 , 2 , . . . , N \{y(t), X(t)\}\qquad\qquad\qquad\qquad\qquad~~~~~\\ X(t) = (x_1, x_2, ..., x_n)^T, t =1, 2, ..., N {y(t),X(t)}     X(t)=(x1​,x2​,...,xn​)T,t=1,2,...,N

待确定一个函数 $f(X)$，使在包含所有样本数据的某个集合 $\Omega$ 里能够用 $f(X)$ 描述 $y$ 和某个向量 $X$ 之间的对应关系，即使误差 $|y-f(X)|$ 对任意的 { y , X } ∈ Ω \{y, X\} \in \Omega {y,X}∈Ω 都尽量小。

3.2 基本优化方法

为了解决3.1中的优化问题，基本方法是选择含有待定参数的函数 $\hat{f}(X,\theta )$，通过极小化某种样本误差，确定待定参数，得到所需要的函数。

常用的样本误差有 $l_1,l_2,l_{\infty }$ 范数：

于是最终要解决的问题就是以下的优化问题：

$$\underset{\theta }{\min }{E}_p(\theta )$$

这属于连续变量无约束优化问题。

3.3 线性规划问题与 $l_{\infty }$ 范数的联系

对于采用 $l_{\infty }$ 范数形成的优化问题：

$$\underset{\theta }{\min }\underset{1\le t\le N}{\max }|y(t)-\hat{f}(X(t),\theta )|$$

为了克服目标函数不可导的问题，可以等价转换为以下的连续变量约束优化问题：

$$\begin{gathered} \min \lambda \\ s.t.-\lambda \le y(t)-\hat{f}(X(t),\theta )\le \lambda ,\forall 1\le t\le N \end{gathered}$$

特别地，当 $\hat{f}(X(t),\theta )$ 是 $\theta$ 的线性函数时，即

$$\hat{f}(X(t),\theta )=\sum _{i=1}^m{\theta }_i{\phi }_i(X)$$

上面的优化问题就属于线性规划问题！

3.4 基函数

在上述线性规划问题中，${\phi }_i(X)$ 称为基函数，通常可以选择足够多的基函数使优化问题

的样本误差任意小，但这样得到的模型在样本集以外往往会产生很大的误差，即所谓的过拟合或过训练问题。解决过拟合问题的根本途径是同时极小化基函数的个数，因此最终要解决的是连续和离散变量混合的优化问题：

其中 $\omega$ 是设定的正的权值。

考虑基函数是否给定，以及数量是否给定，可以分为以下情况：

• 给定基函数及数量：线性规划问题。求解容易且可以找到最优解；
• 数量给定，基函数待优化：非线性规划问题。求解困难且只能获得局部最优解；
• 基函数和数量同时待优化：非线性优化。这种情况是为了解决过拟合问题，求解很困难，且只能获得较好的解。