一、迭代法

迭代法是从一个初始估计出发，获得一系列近似解的方法。

包括但不限于牛顿法、梯度下降法、共轭梯度法、单纯型法、遗传算法、模拟退火。

牛顿法

关键词：泰勒展开、零点、驻点

算法描述：
1、用于零点估计：
设所求解方程为 $f(x)=0$
1）设定初始值$x_0$
2）计算$f(x_0),f^{\prime }(x_0)$
3）求解$f(x_0)+f^{\prime }(x_0)(x-x_0)=0$，获得$x$
4）令$x$作为初始值，重复1~3

一个公式概括之：$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$
2、用于最优化：
将最优化问题等效成求解$f^{\prime }(x)=0$
由用于零点估计的牛顿法可得出更新公式：$$x_{n+1}=x_n-\frac{f^{\prime }(x_n)}{f^{\prime \prime }(x_n)}$$

使用条件：
$f(x)、f^{\prime }(x)$连续且在求解区间内可导

梯度下降法

关键词：梯度、步长

算法描述：
设待求极值的函数为$f(x)$
1）设定初始值$x_0$
2）求梯度$\nabla f(x_0)$（极小-负梯度；极大-梯度）
3）更新点$x=x_0-lr\nabla f(x_0)$
4）重复1~3

因为可能陷入局部极值，梯度下降法不能保证获得最值。

相比于牛顿法，梯度下降法的速度更慢，因为牛顿法包括了二阶导，这意味着在优化过程中，牛顿法不仅关注下降的方向，还关注下降后的坡度，这使得牛顿法的优化过程跟实际下降过程拟合得更好。但是从复杂度上来看，牛顿法大于梯度下降法，所以在求解问题规模大时用的更多的是梯度下降。

共轭梯度法

算法描述：
设问题为求多元二次函数$f(x)$ 的极值点
其中$f(x)={\lambda }_1{x}_1^2+\cdots +{\lambda }_n{x}_n^2+{\alpha }_1{x}_1{x}_2+\cdots +{\alpha }_{n-1}{x}_1{x}_n+\cdots +{\beta }_1{x}_n{x}_1+{\beta }_2{x}_n{x}_2+\cdots +{\gamma }_1{x}_1+\cdots +{\gamma }_n{x}_n+c$

将$x$变成向量形式
则有$f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x+c$
求极值点的问题可以转化为求$f^{\prime }(x)=0$的问题
即求解$x$令$Ax=b$

绿色向量 $r$ 表示该问题的真实解向量，蓝色向量 $p$ 表示当前求出的解向量，红色向量 $e$ 表示当前求出的解向量与真实解向量间的误差向量。
如果误差向量 $e$ 与当前向量 $p$ 正交，则说明之后不用再朝 $p$ 的方向迭代，也就是这个方向走到极致了。因此，可以让下一步就走误差向量的方向，这样在迭代步骤中就不会有重复的迭代方向，设下一步向量为 $n$ ，则有 $$n^{T}e=0$$but，如果我们知道误差向量的方向，那岂不是可以根据当前向量直接得到解向量的方向？所以这个问题至此并没有结束：/
然而接下来的共轭正交过程实在是复杂，我无法承受线性代数的回马枪，因此在这里留个链接，共轭梯度法的部分也是借鉴了这篇文章，感谢作者。
如何理解共轭梯度法？

二、蛮力法

蛮力法的原理很简单，就是一个一个试。把问题的所有可能答案列出来，逐一测试是否是符合要求的答案。
优点：

• 几乎可以解决所有问题
• 在实际应用中可以用来解决小规模问题
• 作为标准来衡量算法性能

缺点：费时

因为这个算法没有啥特殊的步骤，下面我会记录 1 道例题，只用最普通的蛮力法，不涉及蛮力法的各种优化。

百鸡百钱问题

问题描述：
公鸡 1 只 5 元，母鸡 1 只 3 元，鸡仔 3 只 1 元
问如何用100元恰好买100只鸡？

蛮力法求解：

1.'''
2.加减消元2个方程：
3.x + y + z = 100
4.x*5 + y*3 + z/3 = 100
5.得：
6.y = (100 - 7 * x) / 4
7.z = (300 + 3 * x) / 4
8.另：
9.y = (100 -7 * x) / 4 >= 0
10.得：
11.x <= 15
12.'''
13.
14.cocks = hens = chicks = 0
15.flag = 0
16.
17.while cocks <= 15:
18.	hens = (100 - 7 * cocks) / 4
19.	chicks = (300 + 3 * cocks) / 4
20.	if (chicks % 3 == 0) and \
21.		(cocks + hens + chicks == 100) and \
22.		(cocks * 5 + hens * 3 + chicks / 3) == 100:
23.		flag = 1
24.		print("cocks:{} hens:{} chicks:{}".format(cocks, hens, chicks))
25.	cocks = cocks + 1
26.
27.if flag == 0:
28.	  print("no solution")