项目github地址：bitcarmanlee easy-algorithm-interview-and-practice
欢迎大家star，留言，一起学习进步
1.优化问题的一般形式
最优化问题的一般数学形式为:
m i n f ( x ) s . t . x ∈ X min f(x) \\ s.t. \quad x \in Xminf(x)s.t.x∈X
其中，x ∈ R n x \in R^nx∈Rn为自变量，f ( x ) f(x)f(x)为目标函数，x ⊂ R n x \subset R^nx⊂Rn为约束集或者说可行域。
如果上面的优化问题中，s . t . x ∈ X s.t. x \in Xs.t.x∈X这部分约束内容没有，这个优化问题就叫做无约束优化。如果有，那这个优化问题叫有约束优化。如果约束内容里面包含的全是等式，那就叫做等式约束。如果包含不等式，则叫做不等式约束。
2.最优化方法的定义
一般优化问题的解法就叫做最优化方法。
实际中的问题一般都比较复杂，不太可能有直接的解析解。所以通常的解法都是采用迭代的方式求它的最优解。基本的步骤是:给定一个初始点x 0 ∈ R n x_0 \in R^nx0∈Rn，按照某一个迭代规律产生一个点序列x k x_kxk，使得当x k x_kxk是有穷点序列时，最后的点就是最优化问题的最优解。而当x k x_kxk是无穷序列点时，它有极限点，而且该极限点就是最优化问题的最优解。
好的算法应该具备的典型特征为：迭代x k x_kxk能稳定地接近局部极小值点x ∗ x_*x∗的邻域，然后迅速收敛于x ∗ x_*x∗。当给定的某个收敛准则满足时，迭代终止。
如果用数学语言来描述，设x k x_kxk为第k次迭代点，d k d_kdk为第k次的搜索方向，α k \alpha_kαk为第k次步长因子，那么第k次迭代的表达式为:
x k + 1 = x k + α k d k x_{k + 1} = x_k + \alpha_kd_kxk+1=xk+αkdk
接下来的工作就是调整α k d k \alpha_kd_kαkdk这一项，不同的步长α k \alpha_kαk与不同的搜索方向d k d_kdk就分别构成了不同的最优化方法。
当然α k \alpha_kαk与搜索方向d k d_kdk需要满足一些条件。毕竟是求极小值，不能越迭代越大。比如下面是一些条件
∇ f ( x k ) T d k < 0 f ( x k + α k d k ) < f ( x k ) \nabla f(x_k) ^ T d_k < 0 \\ f(x_k + \alpha_kd_k) < f(x_k)∇f(xk)Tdk<0f(xk+αkdk)<f(xk)
上面的式子说明搜索方向必须跟梯度方向的夹角大于90度。因为梯度的方向一般是使目标函数增大。如果不增大，说明目标函数已经到了极值。所以当搜索的方向与梯度方向大于90度的时候，就能保证是向目标函数值更小的方向搜索。
而下面那个式子的意义就很明确了，迭代的下一步的目标函数必须比上一步要小。
最后总结一下最优化方法的基本结构为:
先给点初始点x 0 x_0x0
1.按照一定规则，确实搜索方向d k d_kdk，构造目标函数f在x k x_kxk点处的下降方向为搜索方向。
2.确定步长因子α k \alpha_kαk，使目标函数值具有某种意义的下降。
3.令x k + 1 = x k + α k d k x_{k + 1} = x_k + \alpha_k d_kxk+1=xk+αkdk
若x k + 1 x_k+1xk+1满足某种终止条件，则停止迭代，得到近似最优解x k + 1 x_{k + 1}xk+1。否则重复上述步骤。
而能不能收敛到最优解是衡量最优化算法的有效性的一个重要方面。
3.收敛速度
除了能不能收敛，收敛速度也是最优化方法有效性的一个重要因素。
设有相邻的两个迭代点分别为x k x_kxk与x k + 1 x_{k+1}xk+1，假设最优解为x ∗ x^*x∗，弱存在实数q>0，且有:
lim k → ∞ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ = q \lim\limits_{k\rightarrow\infty}\frac{\|x_{k+1}-x^{*}\|}{\|x_{k}-x^{*}\|}=qk→∞lim∥xk−x∗∥∥xk+1−x∗∥=q
如果0<q<1，表示算法线性收敛。
如果q=0，表示算法超线性收敛。
举个例子，有如下数列：
a 1 = 1 , a 2 = 1 2 , a 3 = 1 4 , ⋯ , a k = 1 2 k − 1 , ⋯ , a ∞ = 0 a_1 = 1, a_2 = \frac{1}{2}, a_3 = \frac{1}{4}, \cdots, a_k = \frac{1}{2 ^ {k-1}}, \cdots, a_{\infty} = 0a1=1,a2=21,a3=41,⋯,ak=2k−11,⋯,a∞=0
根据上面的计算公式，易知q = 1 2 q = \frac{1}{2}q=21，因此该数列为线性收敛。
参考文献:
1.袁亚湘. 非线性优化计算方法