Question

而世之奇伟、瑰怪、非常之观，常在于险远，

而人之所罕至焉，故非有志者不能至也。《王安石．游褒禅山记》

楔子

电脑是计算机，只会计算数字。要让电脑代替人脑处理真实世界的问题，首先要将人脑的抽象想法，一一对应到电脑的实际数值。

人脑考虑的“效果最好”与“效果最差”，放到了电脑就被设定成“数字最大”与“数字最小”。人脑考虑的“问题”与“各种可能性”，放到了电脑就被设定成“函数”与“各种输出入”。

于是乎，人脑考虑的“最好作法”与“最差作法”，放到了电脑就是“最佳化”！

Optimization

求根找到零，最佳化找到极值。找到确切的输入数值与输出数值，输出数值是最大值（最小值），称作“最佳化”。

以函数图形表达函数的极值：最大值就是最高的地方，最小值就是最低的地方。有时候最大值、最小值会在无限远的地方。

中学数学谈过一点点多项式函数的最佳化，比如一元二次多项式函数的最佳化（求抛物线的顶点）。大学微积分课程也谈过多项式函数最佳化，比如一阶导数等于零。

以下则是谈一般的函数的最佳化。

特殊函数类型

容易找到极值的函数类型

Unimodal Function：单峰函数。先严格递增、再严格递减的函数。只有递增或者只有递减，也算是单峰函数。

Convex Function：凸函数。随便划一道割线，函数曲线总是凹下去的函数。凸函数是单峰函数。凸函数的斜率是递增函数。

Concave Function：凹函数。凸函数上下颠倒。注意到凸函数看起来是凹的，凹函数看起来是凸的，不要问我为什麽。

Lipschitz Function：平缓函数。任意割线的斜率的绝对值，小于等于一个定值。

Polynomial Function：多项式函数，无限可微的函数。“梯度等于零”的地方是极值、鞍点，可以手工推导公式解。

Ternary Search

求根可用二分搜寻，求极值可用三分搜寻。函数必须是单峰函数、凹函数、凸函数。

地面勘查类型

概论

Show[ Plot3D[BesselJ[0, Norm[{x, y}]], {x, -4Pi, 4Pi}, {y, -4Pi, 4Pi}, PlotRange -> {-1, 1}, Boxed -> False, Mesh -> None, Axes -> False, PlotPoints -> 50, ColorFunction -> (ColorData["CherryTones"][Rescale[#3, {-4, 4}]] &)], ParametricPlot3D[{{-5, u, BesselJ[0, Norm[{-5, u}]]}, {u, -8, BesselJ[0, Norm[{u, -8}]]}}, {u, -4Pi, 4Pi}, PlotStyle -> {Red, Red}] ]

ParametricPlot3D[{v Cos[u], v Sin[u], 5 Cos[Pi/10] BesselJ[0, v]}, {u, 0, 4 (Pi/2)}, {v, 0, 15}, Boxed -> False, Axes -> False, Mesh -> None]

选一个起点，一步一脚印，走向极值。

Hill Climbing（登山法）

沿著函数图形的表面前进。随便往某个方向跨出一步，确定是往上，就直直走；确定是往下，就不走。最后成功登顶。

步伐太大，会越过山峰，走往低处。只要步伐持续变小，仍可攻顶。但是步伐变小太快，便会在山腰挣扎，无法登顶。取捨两难。

选择各种起点，登上各个山峰。由于无法预测最高峰的位置，只好随机尝试多种起点、实施多次登山法，依赖运气寻找最高峰。尝试越多起点，越能找到最高峰，越能避免落入区域极值。

适用：连续函数。缺陷：可能停在山腰。可能只找到区域极值。

Simulated Annealing（模拟退火法）

登山法改良版。允许往下走，以便翻山越岭。

随便往某个方向跨出一步，确定是往上，就走；确定是往下，以机率 exp(Δf⋅t) 决定走或不走，其中Δf 是上升高度（往下走时是负值），t 是时刻（大于等于 1）。大致上来说，往下越陡就越不想往下，年纪越大就越不想往下。

注：原论文只找山谷、未找山峰。原论文没有时刻 t，而是温度 T；温度不断下降，因此机率公式是 exp(Δf/T) 。

适用：连续函数。缺陷：可能停在山腰。可能只找到区域极值。

UVa 10228 ICPC 5102

Gradient Descent（梯度下降法）

登山法改良版。直接朝著梯度方向走，不必试误。

X 座标、Y 座标、……分开处理，互不干涉。当前位置，求得相邻高度差，座标大的高度减去座标小的高度，正负值可判别相对高低。当前位置座标，加上相邻高度差，就是往上走。若相邻高度差越多，则前后座标差越多。坡越陡、跨越远、走越快。

Plot[BesselJ[0, Norm[{-5, y}]], {y, -4Pi, 4Pi}, PlotRange -> {-1,1}] Plot[BesselJ[0, Norm[{x, -8}]], {x, -4Pi, 4Pi}, PlotRange -> {-1,1}]

梯度是相邻高度差再除以 dx，功效差不多。因为数学家喜欢梯度，所以採用梯度。为了得到梯度，函数必须一次可微。

梯度大小是倾斜程度。梯度方向是最陡的方向，是等高线的垂直方向。沿梯度方向走会上升、得极大值，沿梯度反方向走会下降、得极小值。步伐太大，会走之字路线，无伤大雅。

注：原论文只找山谷、未找山峰，因而取名为“下降”。

适用：一次可微函数。优点：方向明确，不必随机乱走试误，攻顶速度快。缺陷：可能停在山腰。可能只找到区域极值、鞍点。

Nonlinear Conjugate Gradient Method（非线性共轭梯度法）

梯度下降法改良版。前进方向是“本次的梯度”与“上次的前进方向”的加权平均。权重有许多种选择，每个人自有一套理论：

http://people.cs.vt.edu/~asandu/Public/Qual2011/Optim/Hager_2006_CG-survey.pdf

http://sebastianruder.com/optimizing-gradient-descent/

最近走红的演算法有 AdaDelta、ADAM，层出不穷。

注：演算法名称虽源自“ Conjugate Gradient Method ”，内容却毫无关联。古代数学家考虑欠周的结果。

Fixed Point Iteration（不动点递推法）

可微函数，“极值与鞍点”总是出现在“梯度等于零”的地方。不考虑无限远的地方。

stationary points of f(x) = roots of ∇f(x)

结合梯度下降法，求根变成求不动点。

stationary points of f(x) = fixed points of x + λ ∇f(x)

全域极值是特例。

argmax f(x) ⊆ stationary points of f(x)

极值与鞍点总是出现在梯度等于零的地方，即是求根。等式两侧加 x，即是求不动点。等式两侧乘λ加 x，仍是求不动点。

不动点递推法的收敛条件：函数梯度乘λ加 x 是平缓函数。大家习惯令函数是凹函数、凸函数，再自订适当的λ大小。

乘λ加 x 的情况下，不动点递推法即是梯度下降法！不动点递推法是梯度下降法的正统根源，拥有清楚的收敛条件。

max f(x)
∇f(x) = 0
λ ∇f(x) = 0
λ ∇f(x) + x = x
let ∇g(x) = λ ∇f(x) + x
    g(x) = λ f(x) + 0.5 x²
then find fixed point of ∇g(x).

Proximal Point Algorithm（邻近点演算法）

不动点递推法改良版。故事本应划下句点，有人却故意创造了 prox 函数：额外创造维度 z，令抛物线 x²自由平移，取最小值位置；又除以λ，不影响最小值位置。最后把不动点递推法等价换成 prox 函数，重新称作邻近点演算法。应该是为了装逼。

                            1
prox  (z) = argmin { f(x) + —— ‖x - z‖² }
    λf         x            2λ

let ∇g(x) = prox(x) = λ ∇f(x) + x
then find fixed point of ∇g(x).

Newton's Method（牛顿法）

牛顿法原先是求根的方法，找到函数等于零的地方。由于极值与鞍点总是出现在梯度等于零的地方，因此只要事先求得梯度，就可以套用牛顿法求得极值（连同鞍点）了。

求得梯度需要一次微分，牛顿法的过程需要再一次微分，前后合计两次，等同二次微分。

输入变数只有一个的情况下，牛顿法非常实用。牛顿法可以视作梯度下降法的改良版，步伐大小是二次微分的倒数（曲率半径越大、路线越直、步伐越大），攻顶速度更快。

输入变数有许多个的情况下，牛顿法不太实用。当函数有 N 个输入变数，其梯度有 N 个方向，得到 N 个函数。N 个函数同时实施牛顿法，每一步需时 O(N^2)，计算时间更久。

适用：二次可微函数。缺陷：继承全部缺陷，计算时间更久。

Quasi-Newton Method（拟牛顿法）（类牛顿法）

牛顿法改良版。二次微分的部分，改成其他类似的东西。有许多种选择，每个人自有一套理论：

https://en.wikipedia.org/wiki/Quasi-Newton_method

最近走红的演算法有 BHHH、BFGS，层出不穷。

注：古时候尚未发明程式语言。古人遇到迴圈，习惯写成向量运算、矩阵运算、级数。简单明瞭的数学概念，经过古人的转换，往往让现代人摸不著头绪。请读者好自为之。

空中勘查类型

概论

地面勘查经常瘫在山腰、卡在山丘，只好改为飞行模式。像侦察机一样飞来飞去，不被山峰峡谷阻挡。

这类的演算法，完全凭感觉，一个比一个唬烂，连一个数学性质都不必证明。但是我们也没有更好的方法了。面对乱七八糟的函数，只好用乱七八糟的算法。

Particle Swarm Optimization（粒子演算法）

https://www.youtube.com/watch?v=_bzRHqmpwvo

一、散佈 N 个粒子。一个粒子对应一个可行解。
　　position[1...N];	// x
　　solution[1...N];	// f(x)
二、以个人过去最佳解、团体过去最佳解，决定粒子的速度。
　　然后移动粒子，让粒子飞往最佳解。
　　velocity[i] =
　　　2.0 * rand(0 ~ 1) * (best_position[i] - position[i]) +
　　　2.0 * rand(0 ~ 1) * (best_position[best_particle_index] - position[i]);
三、更新个人最佳解、团体最佳解。
　　best_solution[i] = max(best_solution[i], solution[i])
  　　and record best_position[i];
　　best_particle_solution = max_arg(best_solution[1...N])
　　  and record best_particle_index;
四、重複二三，直到解够好。

附带一提，这与粒子的真实行为完全无关。

Bee Colony Optimization（蜜蜂演算法）

https://www.youtube.com/watch?v=zxcb6ZBj5PE

一、散佈 N 个食物。一个食物对应一个可行解。
　　position[1...N];	// x
　　solution[1...N];	// f(x)
二、N 隻蜜蜂分头前往 N 个食物并返回，但是脑中记得的位置会有偏差。
　　position[i] +=
　　　rand(-1 ~ +1) * position[rand(1 ~ N expect i)];
三、每隻蜜蜂皆从 N 个食物中挑一个去，机率由解的好坏决定。
　　probability[i] = solution[i] / ( solution[1] + ... + solution[N] )
　　返回时脑中记得的位置一样会有偏差。公式同二。
四、如果某个食物连续 K 个回合没去，食物自动消灭。
　　随机散佈食物，补足食物直到 N 个。
五、重複二三四，直到解够好。

附带一提，这与蜜蜂的真实行为完全无关。

Fruit Fly Optimization（果蝇演算法）

《果蝇最佳化演算法：最新演化式计算技术》

排列组合类型

概论

随意拼凑函数输入，试著让函数输出是极值。

这类的演算法，不仅凭感觉，而且还是随机乱猜的，唬烂无上限。一个演算法，就能开一学期的课，令人不得不啧啧称奇。

Genetic Algorithm（基因演算法）

https://www.youtube.com/watch?v=ejxfTy4lI6I

灵感来自于染色体减数分裂的过程，优良的基因不断遗传下去，逐代演化出更适应环境的基因。基因演算法把答案比拟成染色体，把好的答案不断分裂再结合，成为更好的答案。

附带一提，这与基因的真实行为完全无关。

1.
[初始化]
一开始先随便弄出几个 x。本例是四个。

	1010101010
	1011001011
	1110101011
	0010101000

2.
[fitness function]
根据问题特性，定义好坏程度。

	f(1010101010) = 678

3.
[selection]
随便找个位置切一刀，每个 x 都被分成两段。

	1010101  010
	1011001  011
	1110101  011
	0010101  000

4.
[crossover]
随便找两组你觉得够优良的 x，交叉相接变成新答案。
重複一直做，直到 x 数目跟原先一样多。本例是四个。

	1010101 \/ 010  ->  1010101 -- 011
	1011001 /\ 011      1011001 -- 010 


	1010101011
	1011001010
	1110101010
	1010101000

5.
[mutation]
每个 x 都随便找一个地方把数字改掉，也可以不改。

	1010111011
	1011001000
	1110101010
	1010101001

6.
重複 3. 4. 5.，直到裡面有一个 x 是你满意的，令 f(x) 最大的那个 x。

1. 随机产生 N 个 x。
2. 计算 fitness function。
3. 重複以下步骤，直到有一个 x 让人满意。
　甲、selection。
　乙、crossover。
　丙、mutation。
　丁、计算 fitness function。

演算法的过程，大致就是如此。细部的实作方式、参数的调校方式，随人话虎烂。

一开始的 x 的足够丰富，多演化几次，就可以得到不错的结果。一开始的 x 足够丰富，可以避免进入区域极值。mutation 用于增加 x 的丰富性，以跳脱区域极值。

范例：0/1 Knapsack Problem

N 个物品。选出其中几个。

[初始化]
答案设计成 N 个二进位数字，
0 代表对应的物品不在背包内，
1 代表对应的物品在背包内。

[fitness function]
是背包内物品总价值，数值越大越好。

当“特定组合”具有深邃的影响力，造成最佳解、次佳解们都包含著同一（几）套“特定组合”，此时就适合使用基因演算法。以 0/1 背包问题为例，一套好的物品组合方式可以有效节省背包空间，只要依赖几套好的物品组合方式，就留有足够的背包空间，能够随心所欲的放入其他物品；所有接近最佳解的答案，答案的其中一小段，都会是那几套固定的物品组合方式──这种情况就非常适合使用基因演算法。

UVa 10715

范例：Minimum Spanning Tree

E 条边。选出 V-1 条。

[初始化]
答案设计成 E 个二进位数字，
0 代表对应的边不是 MST。
1 代表对应的边是 MST。

[fitness function]
是 MST 的权重，数值越大越好。

用人眼观察，很直觉的就能在小区域找出最佳的子树，那便是一套“特定组合”。

范例：Travelling Salesman Problem

N 个城市，C(N,2) 条路。选出 N 条。

[初始化]
答案被迫设计成 0 到 N-1 的数字，代表一条路径。

[fitness function]
是路径的权重，数值越小越好。

[crossover]
哈哈哈，很难搞。

[mutation]
可以有好几种方式：
1. 随便交换两个数字。
2. 随便找一段数字，颠倒前后顺序。
3. 随便拿出一个数字，随便插入到其他地方。

旅行推销员问题也具有“特定组合”的性质，只不过它的答案并不适合分裂再结合，最好不要坚持使用基因演算法，自寻烦恼。

Ant Colony Optimization（蚂蚁演算法）

https://www.youtube.com/watch?v=hXUCCRiNBOc

灵感来自于蚂蚁觅食的过程，蚂蚁发现食物后会沿途留下强烈的费洛蒙，驱使其他蚂蚁沿著路线前进，不断留下更多费洛蒙，吸引更多蚂蚁；也有蚂蚁会另闢新路，而找到更简洁的路线。蚂蚁演算法把答案比拟成蚂蚁觅食的路径，把好的答案不断做局部调整，成为更好的答案。

蚂蚁演算法有各式各样的版本，这裡介绍其中一个经典版本 Ant Colony System，主要是计算一条最短的觅食路径。

附带一提，这与蚂蚁的真实行为完全无关。

1.
[初始化]
一开始先建立一个地图，地图上有 P 个地点。
有一些地点是食物，有一个地点是蚁窝。

地点与地点间皆有道路，
所有道路的费洛蒙都预设为 1.0。

2.
[state transition rule]
一隻蚂蚁从蚁窝出发。
每次踏上一个地点，蚂蚁有两种选择，
　　◎探索：随便走一条路。机率为 q。
　　◎追踪：走费洛蒙最强的道路。机率为 1-q。

q 是蚂蚁选择探索的机率，自行设定在 0 到 1 之间。

为了不让蚂蚁打转绕圈，所以会让蚂蚁避开去过的地点。
在探索和追踪前，要先过滤掉去过的地点。

所有食物都找到后就直接回蚁窝，
没找到所有食物就不准回蚁窝。
总之就是要刻意弄出一条“尝遍天下美食”的路线。

3.
[local updating rule]
蚂蚁回巢之后，
刚刚走过的每一条道路，费洛蒙都会加强，
道路的费洛蒙会变成下列两者相加后的数值，
　　◎自然蒸发，馀下：原本费洛蒙值，乘上 1-ρ。
　　◎蚂蚁路过，添加：道路起点所连接的道路当中，最大的那个费洛蒙值，乘上 p。

ρ是费洛蒙蒸发的程度，自行设定在 0 到 1 之间。
通常会把参数设的很好，让相加之后，费洛蒙会比原本增加一些，而不是变更少。

4.
有 N 隻蚂蚁，依序做 2. 3.这件事。

5.
[global updating rule]
N 隻蚂蚁回巢之后，
地图上所有道路的费洛蒙都会蒸发一定比例。
　　◎自然蒸发，馀下：原本费洛蒙值，乘上 1-α。

而目前的最佳路线，在蒸发之后，竟会神奇地额外增加一些费洛蒙。
　　◎最佳路线，添加：目前最佳解的数值，倒数后，再乘上α。

α是费洛蒙蒸发的程度，自行设定在 0 到 1 之间。

6.
2. 3. 4. 5.，重複执行 R 次。
途中不断记录最好的路线。

1. 初始化地图与费洛蒙。
2. 以下动作执行 R 次：
　　1. N 隻蚂蚁依序找路线，不是同时找路线：
　　　　1. state transition rule，一隻蚂蚁找一条路线。 
　　　　   此路线是由蚁窝出发，经过所有食物各一次，然后回到蚁窝。
　　　　2. 记录目前最佳路线。
　　　　3. local updating rule，更新路线费洛蒙。
　　2. global updating rule，更新所有道路费洛蒙。

演算法的过程，大致就是如此。细部的实作方式、参数的调校方式，随人话虎烂。

蚂蚁数量足够丰富，可以避免进入区域极值。随机探索用于增加答案丰富性，跳脱区域极值。

范例：Travelling Salesman Problem

N 个城市，C(N,2) 条路。选出 N 条。

[初始化]
答案设计成 0 到 N-1 的数字，代表一条路径。
地图上每个地点都有食物。
地图上可以任意挑一地点作为蚁窝。

当答案具有“特定排列”的性质，就适合採用蚂蚁演算法。

Online Optimization

故兵无常势，水无常形﹔能因敌变化而取胜者，谓之神。《孙子》

概论【尚无专有名词】

针对时时变化的函数。函数有如波浪。

照理应该取名为 Dynamic Optimization，不过这个标题通常是指控制系统最佳化，例如运动规划、轨迹规划。因此我只好暂且取名为 Online Optimization 了。

Mean Shift（平均值移动）

一、均匀散布粒子。
二、以上次最佳解的座标为中心，
　　取得邻近范围内所有粒子。（范围自订，通常是规定半径长度。）
三、范围内所有粒子各自求函数值。
四、范围内所有粒子的座标，求加权平均（权重是函数值），得到新的最佳解的座标。

另一种观点是取样。样本（粒子）的密度，当作是函数值的大小。可以想成是找到粒子密度最高的地方。【待补文字】

Particle Filter（粒子滤波器）

一、以上次最佳解的座标为中心，
　　散布 n 个粒子，呈高斯分布。（范围自订，范围即变异数）
　　粒子不用飞来飞去了，直接散布。
二、n 个粒子各自求函数值。
三、n 个粒子的座标，求加权平均（权重是函数值），得到新的最佳解的座标。
四、或者不採用加权平均。
　　想像 n 个粒子各有磁场（高斯分布），强弱由函数值大小决定，
　　形成 joint distribution（高斯混和分布）。
　　下一回合依此分布散布粒子。

Graphical Optimization

万物并作，吾以观复。夫物芸芸，各复归其根。《老子》

概论【尚无专有名词】

函数层层複合，甚至形成阶层架构、网路架构。

照理应该取名为 Network Optimization，不过这个标题通常是指组合最佳化，例如最短路径、最大流。因此我只好暂且取名为 Graphical Optimization 了。

演算法正在发展中。以下整理一些可能相关的概念：

计算 computational graph derivative
物理 spring network
机械 inverse kinematics / graph optimization
统计 markov process
计算 greedy method
摺纸 https://zhuanlan.zhihu.com/p/23186434

Backpropagation（反向传播法）

梯度下降法。走一步时，从最外层的函数，由外往内一层层剥开，反向递推得到每一层的步伐大小。

缺陷是 vanishing gradient problem 与 exploding gradient problem。

梯度是“f(x) 变化”和“x 变化”的比值，想要从 f(x) 变成 x，只需计算函数梯度。函数複合和函数梯度有著抵销效果。

Multi-Objective Optimization

鱼，我所欲也，熊掌，亦我所欲也；

二者不可得兼，舍鱼而取熊掌者也。《孟子》

概论

找到一个输入，同时最佳化多个函数。

通常不存在如此完美的输入，所以只好折衷。

Scalarization

多个函数，极值位置通常不相等。多个函数的加减乘除，极值位置毫无规律。我们难以制定任何策略。这种情况下，大家只好寻求心灵励志书籍、感恩师父感恩上人了。

{ minimize f(x)
{ minimize g(x)

然而值得一提的是，两个凸函数相加之后，仍是凸函数；而且新极值位置，夹在原极值位置之间，不会歪太多。得到折衷方案：最佳化两个凸函数的和，找到极值位置。

{ minimize f(x)   f,g are convex
{ minimize g(x)  ---------------->  minimize f(x) + g(x)

为了调整极值位置，可以添上权重。为了保持是凸函数，权重不能是负数。权重可以自由设定，没有所谓最适当的权重。

注意到，除了权重，函数本身的斜率变化也会影响极值位置。即使权重各 0.5，极值位置也通常不在正中央。因此这个手法是任凭感觉、碰碰运气。

minimize α f(x) + β g(x)   (α ≥ 0, β ≥ 0)

可以推广成多个凸函数。max 只要加上负号就变成 min。

Constraint Satisfaction

概论

只有约束条件。

Branch and Bound（分支定界法）

这是一个过时的演算法，观念陈旧，已被淘汰。

n 个变数 x1…xn，找 f(x) 的可行解。

在线性规划问题当中，b&b 每次将其中一个变数 xi 的“边界（可能是上限或者是下限）”给确定下来。由于 x 的大小与 f(x) 的大小有直接关连，所以藉由调整每个变数 xi 的上下限，就能夹挤出 f(x) 的极值。

https://www.youtube.com/watch?v=BbrZsG7zesE

在离散组合问题当中，b&b 又不一样了。b&b 每次将其中一个变数 xi 的“确切数值”给确定下来。由于 x 的大小与 f(x) 的大小没有直接关连，所以採用了比较複杂的策略：一开始设定 f(x) 的极值的下限是零，随著已知变数越来越多，逐步增加 f(x) 的极值的下限，以逼近 f(x) 的极值。至于 f(x) 的极值的上限，并没有用来寻找极值，主要是用来阻止多馀的分支。

https://www.youtube.com/watch?v=nN4K8xA8ShM

在离散组合问题当中，b&b 跟 state space search 基本相同。唯一的差异在于，作业研究（工管）讲到 b&b 的时候，通常会简化矩阵的 row 和 column，只拿不为零的数值来分支。人工智慧（资工）讲到 state space search 的时候，是使用原本矩阵。

Constrained Optimization（Under Construction!）

天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，

行拂乱其所为，所以动心忍性，曾益其所不能。《孟子》

概论

施加限制，以求得更对味的答案。

纳入约束条件，约束条件是好几道等式、不等式。约束条件的几何意义是边界范围，彷彿包围网。

Lagrange Multiplier（拉格朗日乘数）

仅适合可微函数。将问题转换成微分方程式。

可行解所在之处，目标函数与约束条件，梯度方向一致、梯度大小不明（设定成未知倍率）。

http://www.vision.rwth-aachen.de/media/course/SS/2016/machine-learning/ml16-part08-linear_svms.pdf

约束条件是等式。

minimize f(x)   subject to g(x) = 0
---> ∇f(x) = λ ∇g(x)

约束条件是不等式。有个鸡肋的称呼“ KKT Conditions ”。

minimize f(x)   subject to h(x) ≥ 0
---> ∇f(x) = μ ∇h(x)   (μ ≤ 0)

约束条件推广成任意个。併入目标函数，通通相加即可。

minimize f(x)   subject to g(x) = 0, h(x) ≥ 0
---> ∇f(x) = λ ∇g(x) + μ ∇h(x)   (μ ≤ 0)

进一步整理成“梯度等于零”、“求驻点”的格式。

∇f(x) = λ ∇g(x) + μ ∇h(x)       (μ ≤ 0)
∇f(x) - λ ∇g(x) - μ ∇h(x) = 0   (μ ≤ 0)   移项
∇f(x) + λ ∇g(x) + μ ∇h(x) = 0   (μ ≥ 0)   变数替换，方便起见不改名
∇[f(x) + λ g(x) + μ h(x)] = 0    (μ ≥ 0)   先微后加等同先加后微

注意，求驻点不等同求极值！正解通常位于鞍点、而非极值。

optimize [f(x) + λ g(x) + μ h(x)]   ✘

几何观点：

[level set, aka contour line]
consider the function with unity(?), continuity and differentiability.
1. all level sets has no intersection and fill the whole space. (unity)
2. each component of a level set must keep inflating or deflattening. (continuity)
3. each point on level set has an unique tangent. (differentiability)

[lagrange multiplier]
find the intersection of level set and g(x) = 0. 
at the intersection, they have same tangent.
consider the gradient at the intersection.
 { bi-direction is the same. being perpendicular to the tangent.
 { magnitude is unknown. so give it a proper scalar.

[kkt conditions]
now find the intersection of level set and g(x) <= 0.="" g(x)="" <="0" forms="" a="" region,="" that="" usually="" not="" being="" connected.="" case="" 1.="" f(x)'s="" optimum="" is="" inside="" the="" region.="" at="" optimum,="" gradient="" so="" give="" g(x)'s="" zero="" scalar.="" 2.="" outside="" find="" intersection="" of="" level="" set="" and="" boundary.="" because="" outward="" flux="" positive.="" 2a.="" when="" maximum,="" moves="" via="" gradient.="" (膨胀或收缩)="" approaching="" from="" (外切或内切)="" intersection,="" f(x)="" has="" different="" sign.="" it="" proper="" scalar="" with="" -="" aka="" 2b.="" minimum.="" bala="" oppsite="" direction="" indentical=""> 0.

                       | ∇f(x) = u ∇g(x) | ∇f(x) + u ∇g(x) = 0
max f(x) st g(x) <= 0="" |="" u="" <="0">=
max f(x) st g(x) >= 0  | u >= 0           |  <= min="" f(x)="" st="" g(x)="" <="0" |="" u="">= 0           |  <= min="" f(x)="" st="" g(x)="">= 0  | u <= 0="" |="">=

解析观点：

f(x,y) 求极值，x y 必须满足 g(x,y) = 0。

因为 g(x,y) = 0
凑得 f(x,y) = f(x,y) - λ g(x,y)   for all (x,y) : g(x,y) = 0

观察 h(x,y) = f(x,y) - λ g(x,y) 这一个 h 函数。
观察 λ ，可以发现不管 λ 怎麽变，
符合 g(x,y) = 0 的 (x,y) ，其函数值 h(x,y) 永远不变；
但是其他地方的函数值就会一直变。
欲求永远不变的地方：
对 λ 进行偏微分，让斜率是 0。

另外一方面， f(x,y) - λ g(x,y) 的极值，也就是 f(x,y) 的极值。
欲求 f(x,y) - λ g(x,y) 的极值：
对 x 进行偏微分，让斜率是 0。
对 y 进行偏微分，让斜率是 0。

三条偏微分方程式联立之后，就得到符合条件的极值。
{ ∂h(x,y)/∂λ = 0
{ ∂h(x,y)/∂x = 0
{ ∂h(x,y)/∂y = 0

也就是
{ g(x,y) = 0
{ ∂f(x,y)/∂x + λ × ∂g(x,y)/∂x = 0
{ ∂f(x,y)/∂y + λ × ∂g(x,y)/∂y = 0

概念上也可以看作是增加一个λ变量、增加一个维度来解决问题。

附带一提，二式三式合起来，即是梯度。梯度恰是λ倍。
∇f(x,y) - λ ∇g(x,y) = 0
∇f(x,y) = λ ∇g(x,y)

一开始凑式子的时候改成加法 h(x,y) = f(x,y) + λ g(x,y)
结果相差一个负号，但是意义上等价 ∇f(x,y) = -λ ∇g(x,y)

Regularization（正则化）

minimize f(x)   subject to g(x) = 0, h(x) ≥ 0, ...

根据 Lagrange Multiplier，约束条件併入目标函数，变成梯度等于零（求鞍点、而非极值）。

d/dx [f(x) + α g(x) + β h(x) + ...] = 0  (α ≥ 0, β ≥ 0, ...)

α β ...自订实际数值。如果运气非常好，将变成最佳化问题。

minimize f(x) + α g(x) + β h(x) + ...   (α ≥ 0, β ≥ 0, ...)

α β ...理应是未知数，不过此处改成了自订数值。我们视问题需要，订立适当数值。数值越小，约束条件的影响力就越小，类似于加权平均的概念。

g(x) h(x) ...是约束条件，从可行解之中，挑出偏爱的解。我们视问题需要，订立适当函数，例如 x 的长度越小越好 g(x) = ‖x‖；物理学的做功越少越好 g(x) = F x。

明定准则、施予规范，故称之为“正则化”。优点是可以微调，缺点是全凭运气。

加个二次抛物线函数，让原本函数变更窄，但是靠近极值地方比较平。

regularization 和 scalarization 式子相似，但是背后原理不同。

Linear Programming（线性规划）

仅适合线性函数。将问题转换成线性方程组。

请见本站文件“ Linear Programming ”。

Alternating Direction Method of Multipliers

http://stanford.edu/class/ee364b/lectures/admm_slides.pdf

目标函数是凸函数们的线性函数，约束条件是线性函数。

min u f(x) + v g(x)   subject to a x + b y = 0

Convex Duality（Under Construction!）

Legendre Duality（Convex Conjugate）

凸函数的对偶。画个切线求截距。

动态规划有一个技巧是：最佳解位于直线们的包络线，经过点线对偶，最佳解位于凸包切线的截距。正是此对偶。

maximum: largest value
minimum: smallest value
supremum: least upperbound function
infimum: most lowerbound function
epigraph: upper area (of convex function)
hypograph: below area (of concave function)

https://en.wikipedia.org/wiki/Fenchel's_duality_theorem
let f is convex, g is concave, f*(y) = sup { xᵀy - f(x) }
inf { f(x) - g(x) } = sup { g*(y) - f*(y) }

f(x) + f*(y) = ⟪x,y⟫
Moreau decomposition: x = prox f(x) + prox f*(x)
infimal convolution: (f ◇ g)* = f* + g*

Lagrange Duality

可微函数的对偶。制造新维度，穷举斜率λ，求最高截距。

http://www.eng.newcastle.edu.au/eecs/cdsc/books/cce/Slides/Duality.pdf
http://www.onmyphd.com/?p=duality.theory
http://www.cnblogs.com/90zeng/p/Lagrange_duality.html

Linear Programming Duality

线性函数的对偶。线性规划必有拉格朗日对偶。

max cx   subject to Ax ≤ b
min by   subject to Aᵀy ≥ c