查看“︁次梯度法”︁的源代码

{{noteTA
|G1=Math
|G2=IT
}}

'''次梯度法'''是求解[[凸函数]][[最优化]]（[[凸优化]]）问题的一种[[迭代法]]。次梯度法能够用于不可微的目标函数。当目标函数可微时，对于无约束问题次梯度法与[[梯度下降法]]具有同样的搜索方向。

虽然在实际的应用中，次梯度法比[[内点法]]和[[最优化中的牛顿法|牛顿法]]慢得多，但是'''次梯度法'''可以直接应用于更广泛的问题，'''次梯度法'''只需要很少的存储需求。然而，通过将次梯度法与分解技术结合，有时能够开发出问题的简单分配算法。

==基本次梯度算法==

记<math>f:\mathbb{R}^n \to \mathbb{R}</math>为定义在<math>\mathbb{R}^n</math>上的[[凸函数]]。次梯度算法使用以下的迭代格式
:<math>x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)} \ </math>
其中<math>g^{(k)}</math>表示函数<math> f \ </math>在<math>x^{(k)} \ </math>的[[次梯度]].  如果  <math>f \  </math>可微，他的次梯度就是梯度向量<math>\nabla f</math>
，有时<math>-g^{(k)}</math>不是函数<math>f \  </math>在<math>x^{(k)}</math>处的下降方向。因此采用一系列可能的<math>f_{\rm{best}} \ </math>来追踪目标函数的极小值点，即
:<math>f_{\rm{best}}^{(k)} = \min\{f_{\rm{best}}^{(k-1)} ,  f(x^{(k)}) \}</math>。

===步长的选取===

次梯度方法有许多可采用的步长。以下为5种能够保证收敛性的步长规则

*恒定步长，<math>\alpha_k = \alpha</math>。
*恒定间隔，<math>\alpha_k = \gamma/\lVert g^{(k)}  \rVert_2</math>，得出<math>\lVert x^{(k+1)} - x^{(k)}  \rVert_2 = \gamma</math>。
*步长平方可加，但步长不可加，即步长满足
:<math>\alpha_k\geq0,\qquad\sum_{k=1}^\infty \alpha_k^2 <  \infty,\qquad \sum_{k=1}^\infty \alpha_k = \infty</math>。
*步长不可加但步长递减，即步长满足
:<math>\alpha_k\geq0,\qquad \lim_{k\to\infty} \alpha_k = 0,\qquad  \sum_{k=1}^\infty \alpha_k = \infty</math>。
*间隔不可加但间隔递减，即<math>\alpha_k = \gamma_k/\lVert g^{(k)}  \rVert_2</math>，其中
:<math>\gamma_k\geq0,\qquad \lim_{k\to\infty} \gamma_k = 0,\qquad  \sum_{k=1}^\infty \gamma_k = \infty</math>。注意：上述步长是在算法执行前所确定的，不依赖于算法运行过程中产生的任何数据。这是与标准梯度下降法的显著区别。

===收敛结果===

对于恒定间隔的步长以及恒定步长，次梯度算法收敛到最优值的某个邻域，即
:<math>\lim_{k\to\infty} f_{\rm{best}}^{(k)} - f^*  <\epsilon</math>。基本次梯度算法的性能较差，因此一般的优化问题并不推荐使用。

==有约束最优化==
===投影次梯度算法===
次梯度法的一个扩展版本是'''投影次梯度法'''，该方法用于求解有约束最优化问题
:最小化<math>f(x) \ \quad x\in\mathcal{C}</math>

其中<math>\mathcal{C}</math>为凸集。投影次梯度算方法的迭代公式为

:<math>x^{(k+1)} = P \left(x^{(k)} - \alpha_k g^{(k)} \right)  </math>

其中<math>P</math>是在<math>\mathcal{C}</math>上的投影，<math>g^{(k)}</math>是在点<math>x^{(k)}</math>处<math>f \   </math>的次梯度。

===一般约束问题===

次梯度法可扩展到求解不等式约束问题

:最小化<math>f_0(x) \quad f_i (x) \leq 0,\quad i = 1,\dots,m</math>

其中<math>f_i</math>为凸函数。该算法与无约束优化问题具有相同的形式

:<math>x^{(k+1)} = x^{(k)} - \alpha_k g^{(k)} \ </math>

其中<math>\alpha_k>0</math>是步长，<math>g^{(k)}</math>是目标函数或约束函数在<math>x</math>处的次梯度
:<math>g^{(k)} =
\begin{cases} 
  \partial f_0 (x)  & \text{ if } f_i(x) \leq 0 \; \forall i = 1  \dots m \\
  \partial f_j (x)  & \text{ for some } j \text{ such that } f_j(x)  > 0 
\end{cases}</math>

其中<math>\partial f</math>代表<math>f \ </math>的次微分。如果当前点为可行点，算法采用目标函数的次梯度，否则采用任一违反约束的函数的次微分。

==参考资料==
* {{cite book
  | last = Bertsekas
  | first = Dimitri P.
  | authorlink = Dimitri P. Bertsekas
  | title = Nonlinear Programming
  | publisher = Athena Scientific
  | date = 1999
  | location = Cambridge, MA.
  | isbn = 1-886529-00-0 
}}

* {{cite book
  | last = Shor
  | first = Naum Z.
  | authorlink = Naum Z. Shor
  | title = Minimization Methods for Non-differentiable Functions
  | url = https://archive.org/details/minimizationmeth0000shor
  | publisher = [[Springer-Verlag]]
  | isbn = 0-387-12763-1
  | date = 1985
}}

==外部链接==
* [http://www.stanford.edu/class/ee364a/ EE364a] {{Wayback|url=http://www.stanford.edu/class/ee364a/ |date=20210308072304 }} and  [http://www.stanford.edu/class/ee364b/ EE364b] {{Wayback|url=http://www.stanford.edu/class/ee364b/ |date=20210308004036 }}, a Stanford course  homepage

[[Category:最优化算法]]