组合最优化(参考资料)

最优化问题

​ 最优化问题涉及的应用领域很广，问题的种类与性质繁多，归纳起来，可分为函数优化问题和组合优化问题两大类。其中函数最优化问题的解是一定区域内连续取值的量，而组合优化问题的解则是离散取值的量。

线性规划问题

​ 首先要确定一组具有明确含义的变量，称之为决策变量。问题的目标是选取这些决策变量的值使得一个函数取得最大值和最小值，此函数称之为目标函数。并且利用决策变量把问题的条件表示成等式或不等式，并称这些等式或不等式为约束条件。如果目标函数是决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。

常用解决方法 图解法单纯形法

非线性规划问题

​ 非线性问题也是一类优化问题。在这类问题中，目标函数或约束函数至少有一个不是决策变量的线性函数。

常用解决方法无约束问题:变量轮换法、模式搜索法、可变单纯形法、最速下降法、牛顿法、共轭梯度法、拟牛顿法等有约束问题：近似规划法、可行方向法、罚函数法、乘子法等

对比：线性规划是理论和求解方法都比较成熟，且具有广泛应用的一个运筹学分支；非线性规划问题相对于线性规划问题而言更具一般性，求解难度更大，在工程实际中也更普遍。

组合最优化问题

概念

​ 组合优化是数学优化的一个子领域，与运筹学、算法理论和计算复杂性理论有关。组合优化是一个主题，包括从有限的对象集中找到最佳对象。在许多这样的问题中，穷举搜索是难以处理的。它适用于那些可行解集是离散的或可以简化为离散的优化问题的域，其目标是找到最佳解。

​从广义上讲，组合优化问题是涉及从有限的一组对象中找到"最佳"对象的问题。“最佳”是通过给定的评估函数来测量的，该函数将对象映射到某个分数或者成本，目标是找到最高评估分数和最低成本的对象。组合优化往往涉及排序、分类、筛选等问题。以离散的组合优化问题来讲，目标就是从所有可行解中寻找一个集合、一个排列或者一个图(参考)。如下图所示，旅行商问题(TSP)就是一个经典的组合优化问题。

数学形式

​ 组合优化问题的数学表达形式如下：

maxf(x)s.t.g(x)≥0x∈D\large max\;f(\pmb x)\\\large s.t.\;g(\pmb x)\geq0\\\large \pmb x\in D maxf(xxx)s.t.g(xxx)≥0xxx∈D

​ 它由目标函数f(x)\;f(x)\;f(x),约束函数g(x)\;g(x)\;g(x)和决策变量x\;x\;x及其取值范围D\;D\;D等构成，这里D\;D\;D为有限个点的集合。若令F={x∣x∈D,g(x)≥0}\;F=\{\pmb x\vert \pmb x\in D,g(\pmb x)\geq0\}\;F={xxx∣xxx∈D,g(xxx)≥0},则一个组合优化问题可用三元组(D,F,f)\;(D,F,f)\;(D,F,f)表示，如果x∗∈F\pmb x^\ast\in Fxxx∗∈F使得f(x∗)=max{f(x)∣x∈F}\;f(\pmb x^\ast)=max\;\{f(x)\vert \pmb x\in F\}\;f(xxx∗)=max{f(x)∣xxx∈F},则称x∗\;\pmb x^\ast\;xxx∗为该问题的全局最优解。

分类

​ 一般来说，组合优化问题可分为无约束组合优化问题和有约束组合优化问题。实际上，我们很容易看到，无约束组合优化问题是有约束组合优化问题的一个子集（约束函数g(x)\;g(x)\;g(x)对取值范围D\;D\;D无影响，即D=FD=FD=F）

经典问题示例

旅行商问题（Travelling salesman problem,TSP）

经典旅行商问题

​ 假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

​ 该问题于 1930 年首次提出，是优化中研究最深入的问题之一。它被用作许多优化方法的基准。尽管这个问题在计算上很困难，但许多启发式和精确算法是已知的，因此可以完全解决一些具有数万个城市的实例，而针对数百万个城市规模的tsp问题，uwaterloo.ca 官网上也一直更新目前所能找到的最优解(最近于.2.15更新记录)，颇有一种“军备竞赛”的感觉。

对称和非对称性

​ 在对称 TSP 中，两个城市之间的距离在每个相反方向上都相同，形成一个无向图。这种对称性使可能的解决方案数量减半。在非对称 TSP 中，两个方向可能不存在路径或距离可能不同，从而形成有向图。交通碰撞、单向街道以及不同出发和到达费用的城市的机票都是体现这种非对称性的例子。

数据集

​ 研究人员常用的经典数据集是TSPLIB95数据集，我们做相关实验也会经常采用该数据集。在实际使用过程中，可以去TSPLIB95数据集官网进行下载相关数据源文件，自行编写代码进行读取数据文件等处理；也可以使用Python安装tsplib包，然后导包进行相关操作，这里给出tsplib包的官网,相关安装使用文档如有需要可自取。

背包问题(Knapsack Problem,KP)

经典0-1背包问题

​ 设有一个容积为V\;V\;V的包，n\;n\;n件体积分别为vi\;v_i\;vi​、价值分别为ci\;c_i\;ci​的物品，i=1,2,...,n\;i=1,2,...,n\;i=1,2,...,n,如何在所装物品的总体积不超过容积V\;V\;V的情况下，使得所装物品的价值最大？

这个问题的数学形式为：

max∑cixii=1ns.t∑vixii=1n≤Vxi∈{0,1}\large max\;\overset n{\underset{i=1}{\sum c_ix_i}}\\\large s.t\;\overset n{\underset{i=1}{\sum v_ix_i}}\leq V\\\large x_i\in\{0,1\} maxi=1∑ci​xi​​n​s.ti=1∑vi​xi​​n​≤Vxi​∈{0,1}

​ 值得一提的是，对于经典的0-1背包问题（问题规模较小的情况下），一个很有名的解法就是采用动态规划（DP）的方式，采用空间换时间的思想,具体算法思想如下：

​ f[i][j]f[i][j]f[i][j]表示只考虑前i\;i\;i个物品，总容积是j\;j\;j的情况下的最大价值。则 result=max(f[n][0∼V])f[i][j]:result = max(f[n][0\sim V]) f[i][j]:result=max(f[n][0∼V])f[i][j]:

不选第i\;i\;i个物品：f[i][j]=f[i−1][j]f[i][j]=f[i-1][j]f[i][j]=f[i−1][j];（第i\;i\;i个物品的体积超过容积j\;j\;j,无法放入第i\;i\;i个物品）选第iii个物品：f[i][j]=f[i−1][j−v[i]]+c[i]f[i][j] = f[i-1][j-v[i]] + c[i]f[i][j]=f[i−1][j−v[i]]+c[i]（第i\;i\;i个物品的体积不超过容积j\;j\;j,可以放入第i\;i\;i个物品，其中v[i]\;v[i]\;v[i]是第i\;i\;i个物品的体积）此时f[i][j]f[i][j]f[i][j]值为f[i−1][j−v[i]]+c[i]f[i-1][j-v[i]] + c[i]f[i−1][j−v[i]]+c[i]和f[i−1][j]f[i-1][j]f[i−1][j]两者之间取最大。初始化：$f[0\sim n][0] = 0;;f[0][0\sim V] = 0 $（啥都不选或者容量是0的情况下，最大价值都是0）

​ 综上，其状态转移方程如下：

f[i,j]={0ifi=0orj=0,f[i−1,j]ifvi>j,max(ci+f[i−1,V−vi],f[i−1,j])ifi>0andV≥vi\large f\lbrack i,j\rbrack=\left\{\begin{array}{cc}0&if\;\;i=0\;or\;j=0,\\f\lbrack i-1,j\rbrack&if\;\;v_i>j,\\max(c_i+f\lbrack i-1,V-v_i\rbrack,f\lbrack i-1,j\rbrack)&if\;\;i>0\;and\;V\geq v_i\end{array}\right. f[i,j]=⎩⎪⎨⎪⎧​0f[i−1,j]max(ci​+f[i−1,V−vi​],f[i−1,j])​ifi=0orj=0,ifvi​>j,ifi>0andV≥vi​​

​ Python代码如下，仅供参考：

n, v = map(int, input().split())goods = []for i in range(n):goods.append([int(i) for i in input().split()])# 初始化，先全部赋值为0，这样至少体积为0或者不选任何物品的时候是满足要求 dp = [[0 for i in range(v+1)] for j in range(n+1)]for i in range(1, n+1):for j in range(1,v+1):dp[i][j] = dp[i-1][j] # 第i个物品不选if j>=goods[i-1][0]:# 判断背包容量是不是大于第i件物品的体积# 在选和不选的情况中选出最大值dp[i][j] = max(dp[i][j], dp[i-1][j-goods[i-1][0]]+goods[i-1][1])print(dp[-1][-1])

背包问题变种

多重背包问题：设有一个容积为V\;V\;V的包，n\;n\;n种体积分别为vi\;v_i\;vi​、价值分别为ci\;c_i\;ci​、**数量分别为qi\;\pmb{q_i}\;qi​​qi​​​qi​**的物品，i=1,2,...,n\;i=1,2,...,n\;i=1,2,...,n,如何在所装物品的总体积不超过容积V\;V\;V的情况下，使得所装物品的价值最大？

完全背包问题:设有一个容积为V\;V\;V的包，n\;n\;n种体积分别为vi\;v_i\;vi​、价值分别为ci\;c_i\;ci​、数量无限的物品，i=1,2,...,n\;i=1,2,...,n\;i=1,2,...,n,如何在所装物品的总体积不超过容积V\;V\;V的情况下，使得所装物品的价值最大？

分组背包问题:设有一个容量为V\;V\;V的包，n\;n\;n件体积分别为vi\;v_i\;vi​、价值分别为ci\;c_i\;ci​的物品，这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

依赖背包问题：设有一个容量为V\;V\;V的包，n\;n\;n件体积分别为vi\;v_i\;vi​、价值分别为ci\;c_i\;ci​的物品.这种背包问题的物品间存在某种“依赖”的关系。也就是说物品i\;i\;i依赖于j\;j\;j,表示若选物品i\;i\;i，则必须选物品j\;j\;j。求解将哪些物品装入背包,使得这些物品的体积总和不超过背包容量且满足依赖关系的情况下，使得价值总和最大。

车辆路径问题(Vehicle routing problem,VRP)

经典车辆路径问题描述：

​ 车辆路线问题（VRP）是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。

​ 车辆路线问题一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。例如：设有一场站（depot），共有M\;M\;M辆货车，车辆容量为Q\;Q\;Q，有N\;N\;N位顾客（customer），每位顾客有其需求量D\;D\;D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。

​ 值得一提的是，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于TSP问题是NP-hard问题，因此，VRP也属于NP-hard问题。

车辆路径问题类型

一般而言车辆路线问题大致可以分为以下三种类型：

相异的单一起点和单一终点。相同的单一起点和终点。多个起点和终点。

车辆路径问题变种

有利润的车辆路线问题(Vehicle Routing Problem with Profits, VRPP)[1],[2],[3]：一个最大化问题，其中不强制访问所有客户。目的是访问一次客户，在遵守车辆时间限制的同时最大化收集的利润总和。车辆必须在车站开始和结束。

取货和送货的车辆路线问题(Vehicle Routing Problem with Pickup and Delivery, VRPPD)：许多货物需要从某些取货地点转移到其他交货地点。目标是为车队找到前往接送地点的最佳路线。

后进先出的车辆路线问题(Vehicle Routing Problem with LIFO)：类似于 VRPPD，除了对车辆的装载施加了额外的限制：在任何交付地点，交付的物品必须是最近提取的物品。该方案减少了交货地点的装卸时间，因为除了应该放下的物品之外，不需要临时卸载物品。

具有时间窗的车辆路线问题(Vehicle Routing Problem with Time Windows, VRPTW)：交付地点具有必须在其中进行交付（或访问）的时间窗。

具有承载量的车辆路线问题(Capacitated Vehicle Routing Problem, CVRP/CVRPTW)。车辆对必须交付的货物的承载能力有限。

多路线的车辆路线问题(Vehicle Routing Problem with Multiple Trips, VRPMT)：车辆可以执行多条路线。

开放式车辆路线问题(Open Vehicle Routing Problem, OVRP)：车辆不需要返回站点。

库存路由问题(Inventory Routing Problem, IRP)[4]：车辆负责满足每个交付点的需求。

多站点车辆路由问题(Multi-Depot Vehicle Routing Problem, MDVRP)[5]：存在多个站点，车辆可以从这些站点开始和结束。

​ 下图展示了常见VRP子问题之间关系：

求解方法（参考资料）

求解方法演进

​ 综合过去有关车辆路线问题的求解方法，可以分为精确算法（exact algorithm）与启发式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法（Greedy）等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。

启发式算法

​ 由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。

​简单启发式方法包括节省法或插入法、路线内／间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法（savings or insertion）是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright首先提出一种启发式节省法（savings methods）来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。

​两阶段方法包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。

​人工智能方法自1990年来，在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP ，随后亦有许多位学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和Van Hentenryck则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。

总结几种人工智能方法可以看出：

TS算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的2～3倍，SA算法的近20倍；

GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法；

SA算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。

经典问题小结

​ 对三类经典组合优化问题进行简单总结，表格如下：

​ 通过对以上的经典问题进行简单的总结，有助于更深刻地理解组合优化问题。实际上，生活场景中的很多组合优化问题可以规约到以上三种问题或者相关变种(或者说问题具有同质性)，而上述问题已被证明是NPHard\;NP\;Hard\;NPHard难度，这也是论文中常用的一种证明方法：将不常见的问题规约到大家熟知的问题上，用以说明两类问题具有相同的难度。

常见处理技巧：

​ 在处理最优化问题上，我们在使用一些常用的演化计算或深度学习框架外，也会经常对我们实际需要解决的问题进行一些处理，其中包括问题的抽象化简、问题公式化描述以及目标函数的设计与求解等。当然，具体问题的抽象化简和公式化描述与待优化的具体问题相关，可根据上述提到的规约的方式进行类比，这里不作赘述。这里介绍常用的一些与目标函数的设计与求解相关的常见处理技巧。

1.罚函数法

基本原理

​ 考虑非线性规划问题：

minf(x)s.t.hi(x)=0(i=1,2,...,m)gj(x)≥0(j=1,2,...,l)x∈D⊂Rn\large min\;f(\pmb{x})\\\large s.t.\;h_i(\pmb{x})=0\;\;(i=1,2,...,m)\\\large g_j(\pmb{x})\geq 0\;\;(j=1,2,...,l)\\\large\pmb{x}\in D\subset R^n minf(xxx)s.t.hi​(xxx)=0(i=1,2,...,m)gj​(xxx)≥0(j=1,2,...,l)xxx∈D⊂Rn

​ 其中，f(x)\;f(\pmb{x})\;f(xxx)、hi(x)h_i(\pmb{x})\;hi​(xxx)和gj(x)\;g_j(\pmb{x})\;gj​(xxx)是Rn\;R^n\;Rn上的连续函数，D\;D\;D是可行域。

​ 由于上述问题的约束为非线性，不能用消元法将该问题转化为无约束问题，所以在求解时必须同时考虑既使目标函数值下降，又要满足约束条件。为此，可以通过构造一个由目标函数与约束函数组成的罚函数的办法，将有约束问题转化为无约束问题，对罚函数实行极小化来实现这一目的。例如，上述的非线性规划问题中既含有等式约束，又含有不等式约束，可将罚函数的形式定义如下：

p(x,M)=f(x)+M{∑j=1l[min(0,gi(x))]2+∑i=1m[(hi(x)]2}\large p(\pmb{x},M)=f(\pmb{x})+M\{\;\sum_{j=1}^l{\lbrack \;min(\;0,\;g_i(\pmb{x})\;)\rbrack\;}^2+\sum_{i=1}^m{\lbrack \;(h_i(\pmb{x})\;\rbrack}^2\;\} p(xxx,M)=f(xxx)+M{j=1∑l​[min(0,gi​(xxx))]2+i=1∑m​[(hi​(xxx)]2}

​ 其中，称函数p(x,M)\;p(\pmb{x},M)\;p(xxx,M)为惩罚函数（或罚函数），其中第二项

M{∑j=1l[min(0,gi(x))]2+∑i=1m[(hi(x)]2}\large\;M\{\;\sum_{j=1}^l{\lbrack \;min(\;0,\;g_i(\pmb{x})\;)\rbrack\;}^2+\sum_{i=1}^m{\lbrack \;(h_i(\pmb{x})\;\rbrack}^2\;\}\; M{j=1∑l​[min(0,gi​(xxx))]2+i=1∑m​[(hi​(xxx)]2}

为惩罚项，称M\;M\;M为惩罚因子。惩罚函数只对不满足约束条件的点实行惩罚。当x∈D\;\pmb{x}\in D\;xxx∈D时，若所有的约束不等式都满足（即hi(x)=0(i=1,2,...,m),gj(x)≥0(j=1,2,...,l)\;h_i(\pmb{x})=0\;\;(i=1,2,...,m)\;,\;g_j(\pmb{x})\geq 0\;\;(j=1,2,...,l)\;hi​(xxx)=0(i=1,2,...,m),gj​(xxx)≥0(j=1,2,...,l)），此时惩罚项等于0，不受惩罚；当x∉D\;\pmb{x}\notin D\;xxx∈/​D时，至少有一个约束条件不满足，故此时惩罚项大于0，对极小化罚函数的问题，就要受惩罚。

注意事项

​ 需要说明的是，罚函数的形式不是唯一的。在实际计算中，罚因子M\;M\;M的值选的过小或过大都不好。如果选得过小，则罚函数的极小点远离约束问题的最优解，计算效率很差；如果M\;M\;M过大，则给罚函数的极小化增加计算上的困难。因此，一般策略是取一个趋向于无穷大的严格递增的正数列{Mk}\;\{M_k\}\;{Mk​},从M1\;M_1\;M1​开始，对每个Mk\;M_k\;Mk​求解：

p(x,Mk)=f(x)+Mk{∑j=1l[min(0,gi(x))]2+∑i=1m[(hi(x)]2}\large p(\pmb{x},M_k)=f(\pmb{x})+M_k\{\;\sum_{j=1}^l{\lbrack \;min(\;0,\;g_i(\pmb{x})\;)\rbrack\;}^2+\sum_{i=1}^m{\lbrack \;(h_i(\pmb{x})\;\rbrack}^2\;\} p(xxx,Mk​)=f(xxx)+Mk​{j=1∑l​[min(0,gi​(xxx))]2+i=1∑m​[(hi​(xxx)]2}

​ 随着Mk\;M_k\;Mk​值的增加，罚函数中的罚项所起的作用越来越大，即对点远离可行域D\;D\;D的惩罚越来越重，这就迫使罚函数的极小点x(k)\;\pmb{x}^{(k)}\;xxx(k)与可行域D\;D\;D的“距离”越来越近。当Mk\;M_k\;Mk​趋向于正无穷大时，点列{x(k)}\;\{\pmb{x}^{(k)}\}\;{xxx(k)}就从可行域外部趋向于原问题的极小点（可以证明，在适当条件下，这个点列{x(k)}\;\{\pmb{x}^{(k)}\}\;{xxx(k)}收敛于约束问题的最优解），“外点法”正是因此得名。

​ “外点法”是对罚函数p(x,M)\;p(\pmb{x},M)\;p(xxx,M)在整个空间Rn\;R^n\;Rn内进行优化，因此，初始点可以任意给定，它给计算提供了方便，这也是外点法的另一优点。

2.牛顿法

​ 牛顿法是一种函数逼近法，它的基本思想就是：在极小点附近用二阶Taylor\;Taylor\;Taylor多项式近似代替目标函数f(x)\;f(x)\;f(x)，从而求出f(x)\;f(x)\;f(x)极小点的估计值。在数值分析中，牛顿法用于求方程的根，而求函数极值点等价于求导函数的根（如果函数可微的话）。因此，牛顿法作为一种优化方法，其实质就是将一个求函数极值点的问题转化为求另一个函数（目标函数的导函数）的根的问题。

基本原理

用二阶Taylor\;Taylor\;Taylor多项式φ(x)\;\varphi(x)\;φ(x)来近似f(x)\;f(x)\;f(x)

将f(x)\;f(x)\;f(x)在点xk\;x_k\;xk​处展开成Taylor\;Taylor\;Taylor级数，取其前三项，即得到φ(x)\;\varphi(x)\;φ(x)：

φ(x)=f(xk)+f′(xk)(x−xk)+12f′′(xk)(x−xk)2≈f(x)\large\varphi(x)=f(x_k)+f^{'}(x_k)(x-x_k)+\frac{1}{2}f^{''}(x_k)(x-x_k)^2\approx f(x) φ(x)=f(xk​)+f′(xk​)(x−xk​)+21​f′′(xk​)(x−xk​)2≈f(x)

​ 上述φ(x)\;\varphi(x)\;φ(x)在点xk\;x_k\;xk​处的φ(xk)\;\varphi(x_k)\;φ(xk​)、φ(xk′)\;\varphi(x^{'}_k)\;φ(xk′​)、φ(xk′′)\;\varphi(x^{''}_k)\;φ(xk′′​)分别与f(x)\;f(x)\;f(x)在点xk\;x_k\;xk​处的f(xk)\;f(x_k)\;f(xk​)、f(xk′)\;f(x^{'}_k)\;f(xk′​)、f(xk′′)\;f(x^{''}_k)\;f(xk′′​)相等。

用φ(x)\;\varphi(x)\;φ(x)的极小点近似f(x)\;f(x)\;f(x)的极小点

​ 令

φ′(x)=f′(xk)+f′′(xk)(x−xk)=0\large\varphi^{'}(x)=f^{'}(x_k)+f^{''}(x_k)(x-x_k)=0 φ′(x)=f′(xk​)+f′′(xk​)(x−xk​)=0

​ 得到φ(x)\;\varphi(x)\;φ(x)的驻点xk+1\;x_{k+1}\;xk+1​:

xk+1=xk−f′(xk)f′′(xk)\large x_{k+1}=x_k-\frac{f^{'}(x_k)}{f^{''}(x_k)} xk+1​=xk​−f′′(xk​)f′(xk​)​

​ 因为在xk\;x_k\;xk​附近，φ(x)≈f(x)\varphi(x) \approx f(x)\;φ(x)≈f(x),故可用φ(x)\;\varphi(x)\;φ(x)的极小点作为f(x)\;f(x)\;f(x)的极小点的估计值。如果xk\;x_k\;xk​是f(x)\;f(x)\;f(x)的极小点的一个估计值，则可以利用上述公式得到极小点的一个进一步的估计值xk+1\;x_{k+1}\;xk+1​.

判断精度

​ 若xk+1\;x_{k+1}\;xk+1​满足允许精度，则停止计算。否则，在点xk+1\;x_{k+1}\;xk+1​处，利用上述公式计算出xk+2......\;x_{k+2}\;......xk+2​......如此继续下去，则可以得到一个点列（数列）。可以证明，在一定条件下，这个点列收敛于f(x)\;f(x)\;f(x)的极小点。

算法步骤

给定初始点x1\;x_1\;x1​，给定允许精度ε>0\varepsilon \gt 0ε>0，并令k=1\;k=1\;k=1;计算f(xk′)\;f(x^{'}_k)\;f(xk′​)与f(xk′′)\;f(x^{''}_k)\;f(xk′′​);若KaTeX parse error: Undefined control sequence: \abs at position 1: \̲a̲b̲s̲{f(x^{'}_k)}\lt…,则停止迭代，得到近似极小点xk\;x_k\;xk​.否则转下一步.计算xk+1=xk−f′(xk)f′′(xk)x_{k+1}=x_k-\frac{f^{'}(x_k)}{f^{''}(x_k)}xk+1​=xk​−f′′(xk​)f′(xk​)​.令k=k+1\;k=k+1\;k=k+1,返回步骤2\;2\;2

补充说明

​ 实际上，上述的迭代公式是牛顿法求**f(x)\;f(x)\;f(x)极小点的估计值的一个应用，另一常见应用是牛顿法求f(x)\;f(x)\;f(x)​的根**，两者思路相同。我们将f(x)\;f(x)\;f(x)在点xk\;x_k\;xk​处展开成Taylor\;Taylor\;Taylor级数，取其前两项，即得到φ(x)\;\varphi(x)\;φ(x)：

φ(x)=f(xk)+f′(xk)(x−xk)≈f(x)=0\large\varphi(x)=f(x_k)+f^{'}(x_k)(x-x_k)\approx f(x)=0 φ(x)=f(xk​)+f′(xk​)(x−xk​)≈f(x)=0

​ 得到φ(x)\;\varphi(x)\;φ(x)的零点xk+1\;x_{k+1}\;xk+1​的迭代公式:

xk+1=xk−f(xk)f′(xk)\large x_{k+1}=x_k-\frac{f(x_k)}{f^{'}(x_k)} xk+1​=xk​−f′(xk​)f(xk​)​

​ 其几何意义如下图所示：

3.最速下降法

基本原理

​ 考虑无约束优化问题

minf(x),x∈Rn\large min\;f(\pmb{x})\;,\;\;\pmb{x}\in R^n minf(xxx),xxx∈Rn

其中f(x)\;f(\pmb{x})\;f(xxx)具有一阶连续偏导数。

​ 在求解上述问题时，人们希望选择一个使目标函数值下降速度最快的方向，以迅速达到极小点。正是基于这一点，法国数学家于1847年首先提出了最速下降法(Steepest Descent Method)。最速下降法的基本思想正是在每一次迭代中，选择最速下降方向(负梯度方向)作为搜索方向,正因为如此，最速下降法又被称为一阶梯度法或梯度法。最速下降法是许多非线性规划算法的一个基础，例如，著名的人工神经网络反向传播算法(即BP算法)就是基于最速下降法原理的。

算法步骤

给定初始点x(1)∈Rn\;\pmb{x}^{(1)}\in R^n\;xxx(1)∈Rn,允许误差ε>0\;\varepsilon>0\;ε>0,并令k=1\;k=1\;k=1.

求x(k)\;\pmb{x}^{(k)}\;xxx(k)处梯度向量的模的值∥∇f(x(k))∥\;\parallel \nabla f(\pmb{x}^{(k)})\parallel\;∥∇f(xxx(k))∥,并判断精度。若∥∇f(x(k))∥<ε\;\parallel \nabla f(\pmb{x}^{(k)})\parallel\lt \varepsilon\;∥∇f(xxx(k))∥<ε，则停止计算，输出x(k)\;\pmb{x}^{(k)}\;xxx(k)作为近似极小点，否则转下一步.

选择x(k)\;\pmb{x}^{(k)}\;xxx(k)处的负梯度方向作为搜索方向，即取

d(k)=−∇f(x(k))\large \pmb{d}^{(k)}=-\nabla f(\pmb{x}^{(k)}) ddd(k)=−∇f(xxx(k))

从x(k)\;\pmb{x}^{(k)}\;xxx(k)点出发，沿d(k)\;\pmb{d}^{(k)}\;ddd(k)方向进行一维搜索，即求最优步长λk\;\lambda_k\;λk​，使得

f(x(k)+λkd(k))=minλf(x(k)+λd(k))\large f(\pmb{x}^{(k)}+\lambda_k\pmb{d}^{(k)})=\underset\lambda{min}\;f(\pmb{x}^{(k)}+\lambda\pmb{d}^{(k)}) f(xxx(k)+λk​ddd(k))=λmin​f(xxx(k)+λddd(k))

令x(k+1)=x(k)+λkd(k)\;\pmb{x}^{(k+1)}=\pmb{x}^{(k)}+\lambda_k\pmb{d}^{(k)}\;xxx(k+1)=xxx(k)+λk​ddd(k)，置k=k+1\;k=k+1\;k=k+1,转步骤2\;2\;2.

​ 下图是二维情况下的最速下降法的直观示例：

计算复杂性与问题分类

计算复杂性

​ 由组合优化问题的定义可知，每一个组合最优化问题的解集都是有限集,因而都可以通过枚举的方法求得最优解。枚举是以时间为代价的，有的枚举时间还可以接受，有的则不能接受。

相关定义

给定一个组合优化问题，当问题中的参数赋予具体值时，称为问题的一个实例，这些具体参数值称为数据，这些数据输入计算机所占空间称为实例的输入长度。

假设问题和解决该问题的一个算法已经给定。若对给定问题的一个实例I\;I\;I，存在多项式函数g(x)\;g(x)\;g(x)使得：

C(I)≤αg(d(I))\large C(I)\leq \alpha g(d(I)) C(I)≤αg(d(I))

其中，C(I)\;C(I)\;C(I)是求解实例I\;I\;I的算法的基本运算总次数，d(I)\;d(I)\;d(I)表示对于实例I\;I\;I的计算机的实例输入长度，α\;\alpha\;α是一个正常数。如上述不等式成立，则称该算法是实例I\;I\;I的多项式时间算法；若存在多项式函数g(x)\;g(x)\;g(x)，对该问题的每个实例都有上述不等式成立，则称该算法是解决该问题的多项式时间算法。

对于给定的一个优化问题，若存在一个求解该问题最优解的算法、一个多项式函数g(x)\;g(x)\;g(x)和常数α\;\alpha\;α，使得上述不等式对于给定优化问题的任意一个实例成立，则称给定的优化问题是多项式时间可解问题，或简称为多项式问题，所有多项式问题的集合记为P\;P\;P(polynomial)

问题分类

​ 迄今为止，许多组合优化问题还没有找到求解最优解的多项式时间算法，比多项式问题（即P\;P\;P问题）更广泛的一类是非多项式问题(Nondeterministic Polynomial，简记NP\;NP\;NP)。

​定义：如果A∈NP\;A \in NP\;A∈NP且NP\;NP\;NP中的任何一个问题可在多项式时间内规约为问题A\;A\;A，则称判定问题A\;A\;A属于NPC\;NPC\;NPC或者称为NP−CompleteNP-Complete\;NP−Complete。另外，若NP\;NP\;NP中的任何一个问题可在多项式时间内规约为问题A\;A\;A,则称问题A\;A\;A是NP\;NP\;NP难或NP−Hard\;NP-Hard\;NP−Hard。

​ 对NP−Hard\;NP-Hard\;NP−Hard问题和NP−Complete\;NP-Complete\;NP−Complete问题的一个直观的理解就是指那些很难（很可能是不可能）找到多项式时间算法的问题。因此一般初学算法的人都会问这样一个问题： NP−Hard\;NP-Hard\;NP−Hard和NP−Complete\;NP-Complete\;NP−Complete有什么不同？简单的回答是根据定义，如果所有NP\;NP\;NP问题都可以多项式归约到问题A\;A\;A，那么问题A\;A\;A就是NP−Hard\;NP-Hard\;NP−Hard；如果问题A\;A\;A既是 NP−Hard\;NP-Hard\;NP−Hard又是NP\;NP\;NP，那么它就是NP−Complete\;NP-Complete\;NP−Complete。从定义我们很容易看出， NP−Hard\;NP-Hard\;NP−Hard问题类包含了NP−Complete\;NP-Complete\;NP−Complete类。但进一步的我们会问，是否有属于 NP−Hard\;NP-Hard\;NP−Hard但不属于NP−Complete\;NP-Complete\;NP−Complete的问题呢？答案是肯定的。例如停机问题，也即给出一个程序和输入，判定它的运行是否会终止。停机问题是不可判的，那它当然也不是NP\;NP\;NP问题。但对于SAT\;SAT\;SAT(可满足性问题)这样的NP−Complete\;NP-Complete\;NP−Complete问题，却可以多项式归约到停机问题。因为我们可以构造程序A，该程序对输入的公式穷举其变量的所有赋值，如果存在赋值使其为真，则停机，否则进入无限循环。这样，判断公式是否可满足便转化为判断以公式为输入的程序A是否停机。所以，停机问题是NP−Hard\;NP-Hard\;NP−Hard而不是NP−Complete\;NP-Complete\;NP−Complete。（参考资料）

​ 示意图表示P⊂NP\;P\subset NP\;P⊂NP,NPC⊂NP−Hard\;NPC\subset NP-Hard\;NPC⊂NP−Hard,NP\;NP\;NP与NP−Hard\;NP-Hard\;NP−Hard的公共部分为NPC\;NPC\;NPC.在NP\;NP\;NP中，除P\;P\;P和NPC\;NPC\;NPC，还有一部分问题的复杂性是未知的。

启发式算法

概念

​ 启发式算法是相对于最优算法提出的，一个问题的最优算法求得该问题每个实例的最优解。但在某些情况下，特别是在实际问题中，最优算法的计算时间使得人们无法忍受或者因问题的难度使其计算时间随问题规模的增加以指数速度增加，例如前文中提到的TSP的枚举解法就是如此，因而人们想到基于直观或经验构造一种算法，去求问题的一个可行解，这种方法就是所谓的启发式算法。

​ 启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间、占用空间等）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。

​ 另一种定义为：启发式算法是一种技术。这种技术使得在可接受的计算费用内去寻找最好的解，但不一定能保证所得解的可行性与最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。启发式方法是对启发式算法的综合应用。

分类

一步算法：改进算法数学规划算法解空间松弛算法现代优化算法

性能分析

最坏情形分析概率分析大规模计算分析