与拉格朗日乘数法比较理解
 
 惩罚因子是一个充分大的确定的数，而拉格朗日乘子是个不确定的参数，在求最小值时确定

 转自：彬彬有礼的专栏
 
 题目：最优化问题简介
 
 
 
         一年多学习以来，无论是前面学习压缩感知，还是这半年学习机器学习，一直离不开最优化，比如压缩感知的基追踪类重构算法，核心问题就是一个优化问题，而机器学习中的很多算法也需要最优化的知识，比如支持向量机算法。看来必须得把最优化的基本内容学习一下了，不求理解的有多么深，至少要知道怎么用。其实前面已经写过一篇与最优化相关的内容了，就是《压缩感知中的数学知识：凸优化》这篇。
 
         从本篇起，开始学习一些有关最优化的基础知识，重点是了解概念和如何应用。本篇是参考文献第1.1节的一个摘编或总结，主要是把一些概念集中起来，可以随时查阅。
 
 1、一般形式
 
         最优化问题的数学模型的一般形式为（以下称为最优化数学模型）：
 
 
 
 
 其中，和为连续函数，通常还要求连续可微。称为决策变量，为目标函数，为约束函数，为等式约束，为不等式约束，并记等式约束的指标集为，不等式约束的指标集为。和分别是英文单词minimize(极小化)和subject to(受约束)的缩写。
 
 
 
 2、概念
 
        如果点

满足最优化数学模型中的所有约束条件就称为
可行点(Feasible Point)
，所有可行点的全体称为
可行域(Feasible Region)
，用

表示。在一个可行点

考虑不等式约束

，如果有

，就称不等式约束

在点

考虑不等式约束是
有效约束
或
起作用约束(active constraint)
，并称可行点

位于约束

的边界；如果有

，就称不等式约束

在点

是
无效约束
或
不起作用约束(inactive constraint)
；对于一个可行点

，如果没有一个不等式约束是有效的，就称

是可行域的
内点
，不是内点的可行点就是可行域的
边界点
。显然在边界点至少有一个不等式约束是有效约束，当存在等式约束时，任何可行点都要满足等式约束，因此不可能是等式约束的内点。

 
        如果一个可行点

满足

，则称为最优化问题的
全局最优解
（或总体最优解）；如果可行点

满足

，则称为最优化问题的
严格全局最优解
（或严格总体最优解）；对于可行点

，如果存在一个邻域

使得

成立，则称为最优化问题的
局部最优解
，其中

是一个小的正数；对于可行点

，如果存在一个邻域

使得

成立，则称为最优化问题的
严格局部最优解
。如下图所示，点

是严格全部极小解，

和

则是局部极小解，其中

是严格局部极小解，而

是非严格局部极小解。（注：

附近有一段线是水平的）

 
 
 
 
 
 
         一般常见的最优化方法只适用于确定最优化问题的局部最优解，有关确定全局最优解的最优化方法属于最优化问题的另一个领域——全局最优化。然而，如果最优化问题的目标函数是凸的，而可行域是凸集，则问题的任何最优解（不一定唯一）必是全局最优解，这样的最优化问题又称为凸规划。进一步，对于凸集上的严格凸函数的极小化问题，存在唯一的全局最优解。
 
 3、分类
 
 1）约束最优化问题
 
         只要在问题中存在任何约束条件，就称为约束最优化问题。
 
         只有等式约束时，称为等式约束最优化问题，数学模型为：
 
 
 
 
         只有不等式约束时，称为不等式约束最优化问题，数学模型为：
 
 
 
 
 
 
 
         既有等式约束，又有不等式约束，则称为混合约束优化问题（或一般约束优化问题）；
 
         把简单界约束优化问题称为盒式约束优化问题（或有界约束优化问题），数学模型为：
 
 
 
 
 
 
 2）无约束最优化问题
 
         如果问题中无任何约束条件，则称为无约束最优化问题，数学模型为：
 
 
 
 
 
 
 3）连续与离散最优化问题
 
         决策变量的取值是连续的，称为连续最优化问题；
 
         决策变量的取值是离散的，称为离散最优化问题，又称为组合最优化问题。如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子，求解难度比连续最优化问题更大。
 
 4）光滑与非光滑最优化问题
 
         如果最优化数学模型中的所有函数都连续可微，则称为光滑最优化问题；
 
         只要有一个函数非光滑，则相应的优化问题就是非光滑最优化问题。
 
 5）线性规划问题
 
        对于连续光滑最优化问题，如果最优化数学模型中的所有函数都是决策变量的线性函数，则称为
线性规划问题
。线性规划问题的一般形式为：

 
 
 
 
 其中。矩阵向量形式为
 
 
 
 
 
 其中，
 
 ，
 
 
 
 
 6）二次规划问题
 
         对于连续光滑最优化问题，如果最优化数学模型中的目标函数是决策变量的二次函数，而所有约束都是决策变量的线性函数，则称为二次规划问题。二次规划问题的一般形式为：
 
 
 
 
 其中，为纯量，为阶对称矩阵。如果为半正定矩阵，则称此规划为凸二次规划，否则为非凸规划。对于非凸规划，由于存在比较多的驻点，求解比较困难。
 
 7）非线性最优化问题
 
         只要最优化数学模型中的函数有一个关于决策变量是非线性的，则称为非线性最优化问题。
 
         非线性最优化问题是最一般的最优化问题，而线性规划和二次规划问题却是相当重要的特殊的最优化问题，因为在实际中形成的许多最优化问题都是线性规划问题或二次规划问题，而且在用迭代法求非线性最优化问题的最优解时我们常常用线性规划或二次规划来局部近似原非线性最优化问题，并通过求所得近似问题的最优解来对已有最优解的估计进行改进。

优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。归纳而言，最优化问题分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间的连续变量，而组合优化的对象则是解空间中的离散状态。 
 
一、函数优化问题
 
函数优化问题通常可描述为：令$S$为$R^n$上的有界子集（即变量的定义域），$f:S\rightarrow R$为$n$维实值函数，所谓函数$f$在$S$域上全局最小化就是寻求点$X_\min\in S$使得$f(X_\min)$在$S$域上全局最小，即$\forall X\in S:f(X_\min)\leq f(X)$。
 
算法的性能比较通常是基于一些称为Benchmark的典型问题展开的，常用的BenchMark问题如下： 
 （1）Sphere Model 
 
 $$f_1(X)=\sum_{i=1}^nx_i^2,       |x_i|\leq100$$  

 其最优状态和最优值为

$\min(f_1(X^*))=f_1(0,0,...,0)=0$，图像如下： 

 
 

 （2）Schwefel’s Problem 2.22 

 

 $$f_2(X)=\sum_{i=1}^n|x_i|+\prod_{i=1}^n|x_i|,|x_i|\leq10$$  

 其最优状态和最优值为

$\min(f_2(X^*))=f_2(0,0,0...,0)=0$，图像如下： 

 
 

 （3）Schwefel’s Problem 1.2 

 

 $$f_3(X)=\sum_{i=1}^n(\sum_{j=1}^ix_j)^2,|x_i|\leq100$$  

 其最优状态和最优值为

$\min(f_3(X^*))=f_3(0,0,0,...,0)=0$，图像如下： 

 
 

 （4）Schwefel’s Problem 2.21 

 

 $$f_4(X)=\max_{i=1}^n{|x_i|},|x_i|\leq100$$  

 其最优状态和最优值为

$\min(f_4(X^*))=f_4(0,0,0,...,0)=0$，图像如下： 

 
 

 （5）Generalized Rosenbrock’s Function 

 

 $$f_5(X)=\sum_{i=1}^n[100(x_{i+1}-x_i^2)^2+(1-x_i)^2],|x_i|\leq30$$  

 其最优状态和最优值为

$\min(f_5(X^*))=f_5(1,1,1,...,1)=0$，图像如下： 

 
 

 鉴于许多工程问题存在约束条件，受约束函数的优化问题也一直是优化领域关注的主要对象。常用的受约束测试函数包括： 

 （1）

$\min g_1(X)=5\sum_{i=1}^4(x_i-x_i^2)-\sum_{i=5}^{13}x_i$，约束条件为： 

 

$2x_1+2x_2+x_{10}+x_{11}\leq10$ 

 

$2x_1+2x_3+x_{10}+x_{11}\leq10$ 

 

$2x_2+2x_3+x_{11}+x_{12}\leq10$ 

 

$-8x_1+x_{10}\leq0$ 

 

$-8x_2+x_{11}\leq0$ 

 

$-8x_3+x{12}\leq0$ 

 

$-2x_4-x_5+x_{10}\leq0$ 

 

$-2x_6-x_7+x_{11}\leq0$ 

 

$-2x_8-x_9+x_{12}\leq0$ 

 

$0\leq x_i\leq 1,i=1,2,....,9,13$ 

 

$0\leq x_i \leq100,i=10,11,12$ 

 其全局最优点和最优值为

$g_1(X^*)=g_1(1,1,1,1,1,1,1,1,1,3,3,3,1)=1$ 

 （2）

$\max g_2(X)=(\sqrt{n})^n\prod_{i=1}^nx_i$，约束条件为： 

 

 $$\sum_{i=1}^nx_i^2=1,0\leq x_i\leq1,i=1,2,...,n$$  

 其全局最优点和最优值为： 

 

 $$g_2(X^*)=g_2(\frac{1}{\sqrt{n}},...,\frac{1}{\sqrt{n}})=1$$  

 （3）

$\min g_3(X)=(x_1-10)^3+(x_2-20)^3$，约束条件为： 

 

 $$(x_1-5)^2+(x_2-5)^2\geq100,13\leq x_1\leq100,0\leq x_2\leq100$$  

 其已知最优点和最优值为： 

 

 $$g_3(X^*)=g_3(14.095,0.84296)=-6961.81381$$  

 对于受约束问题，除了局部极小解的存在，影响最优化性能的因素主要包括： 

 （1）目标函数所对应曲面的拓扑性质，比如在相同约束下，线性或凸函数比无规律的函数要容易求解。 

 （2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量，同时，约束在可行区域边界上的变化强度与惩罚项的确定也大有关系。 

 （3）采用惩罚的方法来处理约束越界问题。这种方法比较通用，适当选择惩罚函数的形式可得到较好的结果。比如采用罚函数： 

 

 $$\{_{X\in S}^{\min f(X)+\lambda h^2(X)+\beta [\min\{0,g(X)\}]^2}$$  

 因此对函数优化的讨论通常以无约束问题为主。 

 二、组合优化问题 

 组合优化问题通常可描述为：令

$Ω=\{s_1,s_2,...,s_n\}$为所有状态构成的解空间，

$C(s_i)$为状态

$s_i$对应的目标函数值，要求寻找最优解

$s^*$，使得

$\forall s_i \in Ω,C(s^*)=\min C(s_i)$.组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个分支。 

 典型的组合优化问题有旅行商(Traveling salesman problem,TSP)问题、加工调度问题(Scheduling problem,如Flow-shop,Job-shop)、0-1背包问题(Knapsack problem)、装箱问题(Bin packing problem)、图着色问题(Graph coloring problem)、聚类问题(Clustering problem)等。
 
（1）旅行商问题 
 给定$n$个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路径。其图论描述为：给定图$G=(V,A)$，其中$V$为顶点集，$A$为各顶点相互连接组成的边集，一直各顶点间的连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路。 
 
 
（2）加工调度问题 
 Job-shop问题是一类较TSP更为复杂的典型加工调度问题，是许多实际问题的简化模型。一个Job-shop可描述为：$n$个工件在$m$台机器上加工，$O_{ij}$表示第$i$个工件在第$j$台机器上的操作，相应的操作时间$T_{ij}$为已知，事先给定各工件在各机器上的加工次序（称为技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优（通常是最小完工时间Makespan）。在Job-shop问题中，除技术约束外，通常还假定每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断。若各工件的技术约束条件相同，一个Job-shop问题就转化为简单的Flow-shop问题。进而，若各机器上各工件的加工次序也相同，则问题进一步转化为置换Flow-shop问题。 
 
 
（3）0-1背包问题 
 对于$n$个体积分别为$a_i$，价值分别为$c_i$的物品，如何将它们装入总体积为$b$的背包中，使得所选物品的总价值最大。 

 

（4）装箱问题 

如何以个数最少的尺寸为$l$的箱子装入$n$个尺寸不超过$l$的物品。
 
（5）图着色问题 
 对于$n$个顶点的无环图$G$，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。 
  
 （6）聚类问题 
 $m$维空间上的$n$个模式$\{X_i|i=1,2,...,n\}$，要求聚成$k$类，使得各类本身内的点最相近，比如要求 

 $$\chi^2=\sum_{i=1}^n||X_i^{(p)}-R_p||$$  
 最小，其中$R_p$为第$p$类中的点数。 



显然，上述问题描述均非常简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是所谓的“组合爆炸”。比如，聚类问题的可能划分方式有$k^n/k!$个，Job-shop的可能排列方式有$(n!)^m$个，基于置换排列描述的$n$城市TSP问题有$n!$种可行排列，即便对无方向性和循环性的平面问题仍有$(n-1)!/2$种不同排列，显然状态数量随问题规模呈指数增长。因此，解决这些问题的关键在于寻求有效的优化算法。 
 （3）优化算法及其分类 
 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解。 
 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造型算法、改进型算法，基于系统动态演化的算法和混合型算法等。 
 1）经典算法。包括线性规划、动态规划、整数规划和分支定界法等运筹学中的传统算法，其算法计算复杂性一般很大，只适合于求解小规模问题，在工程中往往不实用。 
 2）构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足工程需要。比如调度问题中的典型构造方法有：Johnson法、Palmer法、Gupta法、CDS法、Daunenbring的快速接近法、NEH法等 
 3）改进型算法，或称领域搜索算法。从任一解出发，对其领域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性搜索法。
 
局部搜索法。以局部优化策略在当前解的领域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；接受当前邻域中的最好解作为下一当前解的最陡下降法等
指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索，如SA、GA、EP、ES和TS等
 
4）基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等。 
 5）混合型算法。指上述各算法从结构或操作上相混合而产生的各类算法。 
 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等。
 
（4）邻域函数与局部搜索 
 邻域函数是优化中的一个重要概念，其作用就是指导如何由一个（组）解来产生一个（组）新的解。邻域函数的设计往往依赖于问题的特性和解的表达方式（编码）。由于优化状态表征方式的不同，函数优化与组合优化中的邻域函数的具体方式明显存在差异。 
 函数优化中邻域函数的概念比较直观，利用距离的概念通过附加扰动来构造邻域函数是最常用的方式，如$x'=x+\eta\xi$，其中$x'$为新解，$x$为旧解，$\eta$为尺度参数，$\xi$为满足某种概率分布的随机数或白噪声或混沌系列或梯度信息等。显然，采用不同的概率分布（如高斯分布、柯西分布、均匀分布等）或下降策略，将实现不同性质的状态转移。 
 在组合优化中，传统的距离概念显然不再适用，但其基本思想仍旧是通过一个解产生另一个解。下面对邻域函数给出一般性定义，并以TSP为例进行解释。 
 定义1 令（$S,F,f$）为一个组合优化问题，其中$S$为所有解构成的状态空间，$F$为$S$上的可行域，$f$为目标函数，则一个邻域函数可定义为一种映射，即$N:S\rightarrow 2^s$。其含义是，对于每个解$i\in S$，一些邻近$i$的解构成$i$的领域$S_i\subset S$，而任意$j \in S_i$称为$i$的邻域解或邻居。通常约定，$j \in S_i\Leftarrow \Rightarrow i\in S_j$。 
 通常，TSP问题的解可用置换排列来表示，如排列(1,2,3,4)可表示4个城市TSP的一个解，即旅行顺序为1,2,3,4.那么，$k$个点交换就可认为是一种邻域函数。比如，不考虑由解的方向性和循环性引起的重复性，上述排列的2点交换对应的邻域函数将产生新解(2,1,3,4)、(3,2,1,4)、(4,2,3,1)、(1,3,2,4)、(1,4,3,2)、(1,2,4,3)。 

基于邻域函数的概念，就可以对局部极小和全局极小进行定义。 

定义2  若$\forall j\in S_i\cap F$，满足$f(j)\geq f(i)$，则称$i$为$f$在$F$上的局部极小解；若$\forall j\in F$，满足$f(j)\geq f(i)$，则称$i$为$f$在
  
   F 
  <script id="MathJax-Element-31195" type="math/tex">F</script>上的全局最小解。 
 局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，它通常可描述为：从一个初始解出发，利用邻域函数持续的在当前解的邻域中搜索比它好的解，若能够找到如此的解，就以之称为新的当前解，然后重复上述过程，否则结束搜索过程，并以当前解作为最终解。可见，局部搜索算法尽管具有通用易实现的特点，但搜索性能完全依赖于邻域函数和初始解，领域函数设计不当或初值选取不合适，则算法最终的性能将会很差。同时，贪婪思想无疑将使算法丧失全局优化的能力，也即算法在搜索过程中无法避免陷入局部极小。因此，若不在搜索策略上进行改进，那么要实现全局优化，局部搜索算法采用的邻域函数必须是“完全的”，即邻域函数将导致解的完全枚举，而这在大多数情况下是无法实现的，而且穷举的方法对于大规模问题在搜索时间上是不允许的。 
 鉴于局部搜索算法的上述缺点，智能优化算法，如模拟退火算法、遗传算法、禁忌搜索、神经网络优化算法和混沌搜索等，从不同的角度利用不同的搜索机制和策略实现对局部搜索算法的改进，来取得较好的全局优化性能。

1 优化问题分类
 
优化问题一般可分为两大类：无约束优化问题和约束优化问题，约束优化问题又可分为含等式约束优化问题和含不等式约束优化问题。
 
 
无约束优化问题 
含等式约束的优化问题 
含不等式约束的优化问题
 


 
 

 
 
2 求解策略
 

 针对以上三种情形，各有不同的处理策略：
 

  
 
 
 
无约束的优化问题：可直接对其求导，并使其为0，这样便能得到最终的最优解；
含等式约束的优化问题：主要通过拉格朗日乘数法将含等式约束的优化问题转换成为无约束优化问题求解；
含有不等式约束的优化问题：主要通过KKT条件(Karush-Kuhn-Tucker Condition)将其转化成无约束优化问题求解。
 
 
 
 
3 求解算法
 
 
3.1 无约束优化算法
 
ref:http://www.cnblogs.com/maybe2030/p/4751804.html
 

  
 
3.1.1 梯度下降法
 
 
 
  
梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。梯度下降法的搜索迭代示意图如下图所示：
 
  

 
 
  
　　牛顿法的缺点：
 
  
　　（1）靠近极小值时收敛速度减慢，如下图所示；
 
  
　　（2）直线搜索时可能会产生一些问题；
 
  
　　（3）可能会“之字形”地下降。
 
  

 
 
  
　　从上图可以看出，梯度下降法在接近最优解的区域收敛速度明显变慢，利用梯度下降法求解需要很多次的迭代。
 
  
　　在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。
 
  
　　比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J(theta)为损失函数，theta是参数，要迭代求解的值，theta求解出来了那最终要拟合的函数h(theta)就出来了。其中m是训练集的样本个数，n是特征的个数。
 
  

 
 
  
 
  
 
  
　　1）批量梯度下降法（BatchGradient Descent，BGD）
 
  
　　（1）将J(theta)对theta求偏导，得到每个theta对应的的梯度：
 
  

 
 
  
 
  
　　（2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：
 
  

 
 
  
 
  
　　（3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。
 
  
　　对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。
 
  
　　2）随机梯度下降（StochasticGradient Descent，SGD）
 
  
　　（1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：
 
  

 
 
  
　　（2）每个样本的损失函数，对theta求偏导得到对应梯度，来更新theta：
 
  

 
 
  
 
  
　　（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
 
  
　　随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
 
  
　　对批量梯度下降法和随机梯度下降法的总结：
 
  
　　批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
 
  
随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
 
  
 
 
 
 
3.1.2 牛顿法和拟牛顿法
 
 
 
  
 　1）牛顿法（Newton's method）
 
  
 　　牛顿法是一种在实数域和复数域上近似求解方程的方法。方法是用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。
 
  
 　　具体步骤：
 
  
 　　首先，选择一个接近函数 f (x)零点的 x0，计算相应的 f (x0) 和切线斜率f  ' (x0)（这里f ' 表示函数 f  的导数）。然后我们计算穿过点(x0,  f  (x0)) 并且斜率为f '(x0)的直线和 x 轴的交点的x坐标，也就是求如下方程的解：
 
  
 
 
  
 　　我们将新求得的点的 x 坐标命名为x1，通常x1会比x0更接近方程f  (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示：
 
  
 
 
  
 　　已经证明，如果f  ' 是连续的，并且待求的零点x是孤立的，那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果f  ' (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。
 
  
 由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
 
  
 　　牛顿法搜索示例图：
 
  
 
 
 
  
 
 
  
 　　关于牛顿法和梯度下降法的效率对比：
 
  
 　　从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
 
  
 　　根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
 
  
 
 
  
 注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
 
  
 　　牛顿法的优缺点总结：
 
  
 　　优点：二阶收敛，收敛速度快；
 
  
 　　缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
 
  
 　　2）拟牛顿法（Quasi-Newton Methods）
 
  
 　　拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。
 
  
 　　拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。
 
  
 　　具体步骤：
 
  
 　　拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：
 
  
 
   

    
   
 
   　　这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：
  
 
  
 
   

    
   
 
   　　
   其中我们要求步长ak  
   
 
    满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk  
    
 
     代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk
    
  
   
 
   
 
    
 
     
 
      的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：
     
   
     

        
     
   
     

        
     
   
     

        
     
   
     

        
     
 
    
 
   
 
  
 
  
 
   

    
   
 
  
 
  
 
   　　我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求
  
 
  
 
   

     
   
 
   

    
   
 
   　　从而得到
  
 
  
 
   
  
 
  
 
   　　这个公式被称为割线方程。
   常用的拟牛顿法有DFP算法和BFGS算法。
  
 
  

   
 
  
 
  

   
 
  
 
 
 
 
3.1.3 共轭梯度法
 
 
 
  
 
   共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。
  
 
  
 
   　　具体的实现步骤请参加wiki百科共轭梯度法。
  
 
  
 
   　　下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：
  
 
  
 
   
  
 
  

     
   
  
 
  
 
   注：绿色为梯度下降法，红色代表共轭梯度法
  
 
  
 
   　　MATLAB代码：
  
 
  
 
 
 
 

  
function [x] = conjgrad(A,b,x)
    r=b-A*x;
    p=r;
    rsold=r'*r;

    for i=1:length(b)
        Ap=A*p;
        alpha=rsold/(p'*Ap);
        x=x+alpha*p;
        r=r-alpha*Ap;
        rsnew=r'*r;
        if sqrt(rsnew)<1e-10
              break;
        end
        p=r+(rsnew/rsold)*p;
        rsold=rsnew;
    end
end
  
 
  
 
 
 
 
3.2 约束优化算法
 
3.2.1 含等式约束优化算法——拉格朗日乘数法
 

  
 
ref:  http://www.cnblogs.com/zhangchaoyang/articles/2726873.html#3592012
 
 

  
 
 
 
3.2.2 含不等式约束优化算法——KKT条件
 

 
 
 

 
 
 

 
 
 
4 智能优化算法 
 

 ref: http://blog.csdn.net/hp910315/article/details/51221657
 
 
 
 
 
4.1、遗传算法 
 
 遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。 
 
 
 
 
 
4.2、模拟退火算法 
 
 是用来求解最优化问题的算法。比如著名的TSP问题，函数最大值最小值问题等等。 
 
 
 
 
 
4.3、粒子群优化算法 
 
 和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。 
 
 
 
 
 
4.4、蚁群算法 
 
 蚁群算法(antcolony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。 
 
 
 
 
 
4.5、免疫算法 
 
 免疫算法是一种具有生成+检测 (generate andtest)的迭代过程的搜索算法。从理论上分析，迭代过程中，在保留上一代最佳个体的前提下，遗传算法是全局收敛的。 
 
 
 
 
 
4.6、克隆选择算法 
 
 根据克隆选择原理设计的免疫算法。解决问题时，一般把问题定义为抗原，而问题的解就是抗体集合。在特定的形态空间中，随机产生的抗体试图与抗原发生匹配，即尝试解决问题。匹配度高的抗体有可能产生更好的解，被赋予更大的克隆概率参与下一次匹配。 
 
 
 
 
 
4.7、和声搜索算法 
 
 和声搜索（HarmonySearch, HS）算法是一种新颖的智能优化算法。类似于遗传算法对生物进化的模仿、模拟退火算法对物理退火的模拟以及粒子群优化算法对鸟群的模仿等，和声算法模拟了音乐演奏的原理。 
 
 
 
 
 
4.8、禁忌搜索算法 
 
 禁忌（TabuSearch）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 
 
 
 
 
 
4.9、差分进化算法 
 
 它是由Storn等人于1995年提出的，和其它演化算法一样，DE是一种模拟生物进化的随机模型，通过反复迭代，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。 
 
 
 
 
 
4.10、BP神经网络算法 
 
 BP神经网络是一种基于有监督的学习，使用非线性可导函数作为传递函数的前馈神经网络。 
 
 
 

 
 
 
5 算法比较
 
 
 
 
5.1 无约束优化算法
 
  
 
Ø  坐标轮换法具有不需要导数信息的优点，计算过程比较简单，程序实现也比较容易，但存在算法收敛速度较慢、计算效率低等缺点。坐标轮换法主要用来解决优化问题设计变量数目小于10的小规模无约束优化问题;另外，坐标轮换法还可解决目标函数的等值线为圆或平行于坐标轴的优化问题。
 
 
Ø  与其他无约束优化算法相比，最速下降法具有方法简单等优点，计算效率在最初几步迭代时较高，且对初始点不敏感，因而常与其他方法一起使用，但最速下降法需要目标函数的一阶导数信息。
 
 
Ø  求解无约束优化问题的牛顿法对给定的初始点比较敏。如果初始点选择的比较好，则其解决优化问题的收敛过程会很快;如果选择不当，则可能会出现收敛失败的情况。另外，牛顿法存在计算过程复杂、计算量特别大等缺点，因此主要适合于设计变量数目小的优化问题及目标函数阶次较低的优化问题。
 
 
Ø  共轭梯度法具有收敛速度快等优点，其收敛速度远快于最速下降法。共轭梯度法计算简单，所需要的存储空间少，适合于优化变量数目较多的中等规模优化问题。
 
 
Ø  在无约束优化方法中，Powell法是计算效率比较高的优化算法之一，它不需要目标函数的导数，是求解中小型规模优化问题的有效方法。
 
 
Ø  变尺度法也是计算效率比较高的优化算法之一，可用来解决高阶目标函数的优化问题，但存在程序实现比较复杂、存储空间比较大等缺点。
 
 
Ø  单纯形法具有不需目标函数导数信息、程序实现简单、计算效率比较高等优点。
 
 
 
 
5.2 约束优化算法
 
  
 
 
 
Ø  Monte Carlo法具有方法简单、不需要导数信息等优点，但存在求解高维优化问题时计算量大等不足;
 
 
Ø  随机方向搜索法具有优化求解过程收敛快，但存在局部寻优的不足，因而在使用时需采用选择多个不同初始点的策略;
 
 
Ø  复合形法具有程序实现简单等优点，但在解决设计变量和约束条件多的优化问题时优化效率比较低;
 
 
Ø  可行方向法是解决约束优化问题的有效方法之一，适合求解中等规模化问题，但存在程序实现复杂等不足;
 
 
Ø  广义简约梯度法具有算法收敛快、计算精度高等优点，但也存在程序实现复杂等不足;
 
 
Ø  罚函数优化方法包括内点法、外点法、混合法等，具有方法实现简单等优点，但存在优化过程不稳定、收敛速度较慢等缺点，适宜于解决中小规模优化问题;
 
 
Ø  序列线性规划法收敛较慢，只适用于非线性程度不是很强的优化问题;
 
 
Ø  序列二次规划法是收敛速度较快、优化比较有效的方法之一，比较适合于中等规模优化问题;
 
 
5.3 智能算法
 
 

  
 
 
  
遗传算法：优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间长，且容易受参数的影响。
 
  
遗传算法适合求解离散问题，具备数学理论支持，但是存在着汉明悬崖等问题。
 
  
 
 
  
模拟退火：优点是局部搜索能力强，运行时间较短；缺点是全局搜索能力差，容易受参数的影响。
 
  
 
 
  
爬山算法：显然爬山算法较简单，效率高，但是处理多约束大规模问题时力不从心，往往不能得到较好的解。
 
  
 
 
  
粒子群算法适合求解实数问题，算法简单，计算方便，求解速度快，但是存在着陷入局部最优等问题。
 
  
 
 
  
蚁群算法适合在图上搜索路径问题，计算开销会大。
 
  
 
 
  
要将三种算法进行混合，就要针对特定问题，然后融合其中的优势，比如将遗传算法中的变异算子加入粒子群中就可以形成基于变异的粒子群算法。
 
 
 
 

 
 
 
6 参考资料及文档
 

  
 
优化方法：http://wenku.baidu.com/view/435728f032d4b14e852458fb770bf78a64293a53
 
 
矩阵计算：http://wenku.baidu.com/view/4da1a2eda0c7aa00b52acfc789eb172dec639950
 
 
更多课件参考：http://www.cnblogs.com/zhangchaoyang/articles/2600491.html
 
 
 
 
 
斯坦福大学Ng课件：http://cs229.stanford.edu/section/cs229-cvxopt.pdf
 
 
大牛博客：http://www.cnblogs.com/maybe2030/category/709560.html
 
 
五大经典算法系列：http://www.cnblogs.com/steven_oyj/category/246990.html
 
 

 
 
 
整合于互联网，侵删。