梯度的负方向是函数下降最快的方向，但是常用的梯度下降必须要求函数的连续可导，对于某些连续不可导的问题，则需要次梯度下降和近端梯度下降。
假设 f ( x ) f(x) f(x)可微且凸, 满足 ∇ f \nabla f ∇f满足L- L i p s c h i t z Lipschitz Lipschitz ,即存在常数L>0,使得 ∣ ∣ ∇ f ( x ′ ) − ∇ f ( x ) ∣ ∣ 2 2 < = L ∣ ∣ x ′ − x ∣ ∣ 2 2 . . . . . . . ( ∀ x , x ′ ) ||\nabla f(x')-\nabla f(x)||_2^2<=L||x'-x||_2^2.......(\forall x,x') ∣∣∇f(x′)−∇f(x)∣∣22<=L∣∣x′−x∣∣22.......(∀x,x′) 则在x附近能将 f ( x ) f(x) f(x)通过二阶泰勒展开近似为: 这里用 1 t I \frac{1}{t}I t1I 替换掉 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x)，不是两者相等 使得 f ( x ) f(x) f(x)最小的值 求导后: 对于梯度下降而言，这里的 t k t_k tk可以是我们设置的一个固定步长。 梯度下降的另一种证明
这里对于梯度下降主要讨论其步长选择的问题， 最简单直接的方式是固定每次的步长为一个恒定值，但是如果步长过大或过小时，可能会导致结果难以收敛或者收敛速度很慢。因此提出了可变长步长的方法，可变长步长的方法指的是根据每次迭代依照一定的规则改变步长.
t k t_k tk同时表示步长，优化中步长过长和过短，会导致结果难以收敛和收敛过慢，故:
解决的方法就是当步长过大（跨越了最优点）的时候，减小步长，否则保持步长不变。 梯度下降，故 ∇ f ( x ) T △ x < 0 \nabla f(x)^T\triangle x<0 ∇f(x)T△x<0，将 f ( x + t △ x ) f(x+t\triangle x) f(x+t△x)泰勒展开， 0 < α < 0.5 0<\alpha<0.5 0<α<0.5，有： 这里 △ x \triangle x △x就是梯度的方向， △ x = − ∇ f ( x ) T \triangle x=-\nabla f(x)^T △x=−∇f(x)T 当上述条件不满足时，说明我们步子跨大了，前进的多反而值变小了，所以需要后退一点点，后退的大小为： t = β t , 0 < β < 1 t=\beta t,0<\beta<1 t=βt,0<β<1
https://zhuanlan.zhihu.com/p/37190315
我们知道，函数下降最快的方向是负梯度方向， x k + 1 = x k − α ∇ f ( x k ) x^{k+1}=x^{k}-\alpha \nabla f(x^{k}) xk+1=xk−α∇f(xk) 此时对步长 α \alpha α进行搜索，找出其导数为0时的 α \alpha α值 f ( x ( k + 1 ) ) = f ( x ( k ) − α ( k ) ∇ f ( x k ) ) = m i n f ( x ( k ) − α ∇ f ( x k ) ) = m i n φ ( α ) f(x^{(k+1)})=f(x^{(k)} - \alpha^{(k)}\nabla f(x^{k})) =min\; f(x^{(k)} - \alpha \nabla f(x^{k})) = min\;\varphi(\alpha) f(x(k+1))=f(x(k)−α(k)∇f(xk))=minf(x(k)−α∇f(xk))=minφ(α) φ ′ ( α ) = ∇ f ( x ( k + 1 ) ) − ∇ f ( x k ) = 0 \varphi '(\alpha)= \nabla f(x^{(k+1)})-\nabla f(x^{k})=0 φ′(α)=∇f(x(k+1))−∇f(xk)=0 故 ∇ f ( x ( k + 1 ) ) = ∇ f ( x k ) \nabla f(x^{(k+1)})=\nabla f(x^{k}) ∇f(x(k+1))=∇f(xk)，也就是说相邻两点的梯度方向是正交的，就会呈现下图的锯齿状。 直到其二阶范数 ∣ ∣ ∇ f ( x ( k ) ) ∣ ∣ < ϵ ||\nabla f(x^{(k)})|| \lt \epsilon ∣∣∇f(x(k))∣∣<ϵ，停止收敛 这种方法也叫最速下降法，特点是一开始下降速度很快，但越接近收敛点则越慢。
函数 f ( x ) = ∣ ∣ x ∣ ∣ 1 f(x)=||x||_1 f(x)=∣∣x∣∣1 其次梯度如下： 而 subgradient descent 与 gradient descent 的不同地方就是当函数不可微的时候，将 gradient descent 中更新公式中的 gradient 换成 subgradient。 例如下列优化问题： 对目标函数求导且等于0，有： 则解为： LASSO: 解为: 可以看出,当 β i ≠ 0 \beta_i \neq0 βi̸=0上式并没有一个明确的解.
在上面梯度下降中, f ( x ) f(x) f(x)泰勒展开,假设 f ( x ) f(x) f(x)是可微且凸的,但是假如 f ( x ) f(x) f(x)可以不可微,但可以分成两个函数 f ( x ) = g ( x ) + h ( x ) f(x)=g(x)+h(x) f(x)=g(x)+h(x), h ( x ) h(x) h(x)不可微但是凸.则可以表示成下面的形式 由于 g ( x ) g(x) g(x)是常数,且在 x + = z k + 1 = z k − t ∇ g ( z k ) x^{+}=z^{k+1}= z_{k}-t\nabla g(z^{k}) x+=zk+1=zk−t∇g(zk)时, g ( z ) g(z) g(z)是最小的,故 ∇ g ( x + ) \nabla g(x^{+}) ∇g(x+)为0,所以: 上式就是近端算子的形式: z i = { x i − λ t x i > λ t 0 − λ t ≤ x i ≤ λ t x i + λ t x i < − λ t z_i= \begin{cases} x_i - \lambda t & x_i > \lambda t \\ 0 & -\lambda t \le x_i \le \lambda t \\ x_i + \lambda t & x_i< -\lambda t \end{cases} zi=⎩⎪⎨⎪⎧xi−λt0xi+λtxi>λt−λt≤xi≤λtxi<−λt 有点复杂绕,但还是能推出来的.以后补上. 近端梯度下降比subgradient的优势在于:
对于绝大部分的 h 是易求的,有解析解. p r o x t prox_t proxt仅仅依赖于h，因此可以被用于不同的g函数g可以式任意复杂的函数,只要能求梯度.实际上在上面的梯度下降那里，梯度下降是用常量替换掉二阶导数，但牛顿法保留了二阶导数， t = ∇ 2 f ( x ) t=\nabla^2f(x) t=∇2f(x)就是牛顿法的更新策略，其引入了海森矩阵，所以牛顿法式一种二阶方法。海森矩阵在遇到大矩阵时非常难算。 梯度下降： 牛顿法： 黑线为梯度下降，蓝线为牛顿法。
绿线：最优的梯度下降；红线：共轭梯度下降 若 A A A是对称正定阵，若有 u , v ∈ R u,v\in R u,v∈R， u T A v = 0 u^TAv=0 uTAv=0，则 u , v u,v u,v是关于 A A A共轭的。当 A = I A=I A=I时， u T v = 0 u^Tv=0 uTv=0，所以共轭实际上是正交的一种推广。 设 P = [ p 1 , . . . , p n ] P=[{p_1,...,p_n}] P=[p1,...,pn]，如果它们两两关于 A A A共轭，则 P P P是 A A A的一组共轭方向向量，并且可以证明这个向量组线性无关。 等值面该点的切向量与其法向量正交，与指向极小值点的向量共轭，法向量不一定指向极小点，这可能是共轭的核心意义。
定理：若有函数 f ( x ) = 1 2 x T A x + b T x + c f(x)=\frac{1}{2}x^TAx+b^Tx+c f(x)=21xTAx+bTx+c，若有一组共轭向量 d = [ d 1 , . . . , d n ] d=[d_1,...,d_n] d=[d1,...,dn]，以任意一点 x ( 1 ) x^{(1)} x(1)开始依次沿着 d = [ d 1 , . . . , d k ] d=[d_1,...,d_k] d=[d1,...,dk]搜索，并得到 f ( x ) f(x) f(x)在 x ( 2 ) , . . . , x ( k ) x^{(2),...,x^{(k)}} x(2),...,x(k)，则 x ( k + 1 ) x^{(k+1)} x(k+1)是 x ( 1 ) + B k x^{(1)}+B_k x(1)+Bk上的极小点，其中 B k = { x ∣ x = ∑ i = 1 k λ i d ( i ) , λ i ∈ R } B_k = \{{x|x=\sum_{i=1}^{k}\lambda_id^{(i)},\lambda_i\in R}\} Bk={x∣x=i=1∑kλid(i),λi∈R}是 d = [ d 1 , . . . , d k ] d=[d_1,...,d_k] d=[d1,...,dk]生成的子空间。sure，当 k = n k=n k=n， x ( k + 1 ) x^{(k+1)} x(k+1)是 f ( x ) f(x) f(x)在 R n R^n Rn上唯一的极小点。
推论：由上面的共轭的几何意义和此定理可以推出， ∇ f ( x ( k + 1 ) ) T d ( i ) = 0 , i = 1 , 2 , . . . , k \nabla f(x^{(k+1)})^T d^{(i)}=0,i=1,2,...,k ∇f(x(k+1))Td(i)=0,i=1,2,...,k 下面我们考虑一个最优化的问题： m i n f ( x ) = 1 2 x T A x + b T x + c min f(x)=\frac{1}{2}x^TAx+b^Tx+c minf(x)=21xTAx+bTx+c 其中A为正定矩阵
取一组共轭方向 x ( k + 1 ) = x ( k ) + λ k d ( k ) x^{(k+1)}=x^{(k)}+\lambda_kd^{(k)} x(k+1)=x(k)+λkd(k) m i n λ f ( x ( k + 1 ) ) min_{\lambda} f(x^{(k+1)}) minλf(x(k+1)) 知道某个 x k x^{k} xk满足 ∇ f ( x k ) = 0 \nabla f(x^{k})=0 ∇f(xk)=0 共轭梯度下降 基本思想是将最速下降法（锯齿形下降）结合共轭性，利用已知迭代点的梯度方向造成一组共轭方向，并沿此方向搜索，求出极小值点。 任取初始点 x ( 1 ) x^{(1)} x(1)，第一个搜索方向取为： d ( 1 ) = ∇ f ( x ( 1 ) ) d^{(1)}=\nabla f(x^{(1)}) d(1)=∇f(x(1))当 ∇ f ( x ( k + 1 ) ) ! = 0 \nabla f(x^{(k+1)})!=0 ∇f(x(k+1))!=0时，确定搜索方向 d ( k + 1 ) = − ∇ f ( x ( k ) ) + β k d ( k ) d^{(k+1)}=-\nabla f(x^{(k)})+\beta_kd^{(k)} d(k+1)=−∇f(x(k))+βkd(k) β k \beta_k βk的确定需要引入 d ( k ) , d ( k ) + 1 d^{(k)},d^{(k)+1} d(k),d(k)+1是共轭的， 0 = d ( k ) T A d ( k + 1 ) = − d ( k ) T A ∇ f ( x ( k ) ) + d ( k ) T A β k d ( k ) 0=d^{(k)^T}Ad^{(k+1)}=-d^{(k)^T}A\nabla f(x^{(k)})+d^{(k)^T}A\beta_kd^{(k)} 0=d(k)TAd(k+1)=−d(k)TA∇f(x(k))+d(k)TAβkd(k) 解得： β k = d ( k ) T A ∇ f ( x ( k ) ) d ( k ) T A d ( k ) \beta_k=\frac{d^{(k)^T}A\nabla f(x^{(k)})}{d^{(k)^T}Ad^{(k)}} βk=d(k)TAd(k)d(k)TA∇f(x(k))确定搜索步长 m i n λ f ( x k + λ k d ( k ) ) min_{\lambda}f(x^{k}+\lambda_kd^{(k)}) minλf(xk+λkd(k))，用一维搜索即可。（求导）： λ k = − ∇ f ( x ( k ) ) d ( k ) d ( k ) T A d ( k ) \lambda_k=-\frac{\nabla f(x^{(k)})d^{(k)}}{d^{(k)^T}Ad^{(k)}} λk=−d(k)TAd(k)∇f(x(k))d(k)如上，就是共轭梯度下降的过程。 总结下来就是： 利用变形的正交方向的共轭方向，能快速定位极值，因此在最速下降（特殊的梯度下降）的基础上选取共轭方向，能够在每一次迭代都找到这个方向的最优解。
特别感谢: http://wulc.me/2017/05/20/凸优化总结/ https://blog.csdn.net/zbwgycm/article/details/83060251 http://www.stat.cmu.edu/~ryantibs/convexopt/ https://keson96.github.io/2016/11/27/2016-11-27-Conjugate-Gradient-Method/ https://alkane0050.fun/2019/05/18/共轭梯度法初步/
