梯度投影算法线性收敛吗

① 为什么随机梯度下降方法能够收敛

梯度下降法是一个一阶最优化算法，通常也称为最速下降法。要使用梯度下降法找到一个困孝函数的局部极小值，必须向函数上当前隐陪点对应梯度（或者是近似梯度）的反方向的规定步长距离点进行迭代搜索。

• 梯度下降最优解

梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。

② 什么是梯度法为什么在接近目标函数的极值点时，梯度法的收敛速度会变慢

梯度下降法是一个最优化算法，通常也称为最速下降法。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向的，最速下降法越接近目标值，步长越小，前进越慢。

③ 堵丁柱的研究成果

1986-1987年是伯利克数学所的代数数论年，搞计算复杂性的学者们便各奔东西了。堵丁柱接受麻省理学的聘请，以访问助理教授的身份开始了与克拉依曼教授的合作。事隔4年从不能接收作正式研究生到可以作助理教授，变化之大，令人感慨万端。
麻省理工学院是一所举世闻名的大学，它坐落在查理士河畔，与波士顿的高大建筑群隔河相望。楼内走廊的墙上，挂满了为科学技术作出重大贡献的教授们的历史图片，这使人一进其中，就体验到它的历史悠久和硕果累累。在应用数学方面享有很高声望的林加翘教授就在这里工作。幸运的是，堵丁柱的办公室被安排在林教授的斜对面，使他有机会经常当面聆听先生的教诲。在教书之余，堵丁柱充分利用业余时间，同这里的教授和访问学者们探讨问题。在此期间，他完成了9篇论文，并在另外的项目上也取得了有意义的进展。
在麻省理工学院期间，堵丁柱和章祥荪合作的罗素梯度投影收敛的论文刊印出来了。
罗素梯度投影方法是解决带约束非线性规划问题的基本方法。自1960年罗素提出这个方法以来，收敛问题一直没有解决。此后，几乎每个讨论该方法的教科书都要提及这个问题，使这个问题成为非线性规划领域中较有名的长期未解决的问题之一。早在1980年，在越民义教授和韩继业教授的指导下，堵丁柱对罗素投影法曾作过较系统的学习和研究，在硕士毕业论文中，又解决了梯度投影的退化处理问题。在此此闭后的工作中，他又简化了由泡拉克提出、章祥荪教授改进的一种罗素梯度投影法的变形，并且以反例证实了在某种特殊情况下，原算法是可以不收敛的。1986年刊出的与章祥荪教授合作的论文是在1984年完成的，这篇论文的主要结论是，一般说来，罗素算法提供的技巧是可以使算法收敛的。因此，基本解决了这个问题。罗素本人在后来的一封信中肯定了他们的和塌工作。他写道，我想祝贺你们，你们最森棚裂近的工作，最终解决了和我的原始论文相关联的收敛性问题。
在堵丁柱的论文目录分类中有可靠性理论题目。他对这方面的研究是从证明德曼·勒伯曼和罗斯猜测开始的。他们的猜测是关一种概率模型中几个性质相同但工作概率不同的部件的最优分配。堵丁柱与黄光明合作，在1982年年初得出完全的证明，并且建立了一些较一般的定理用于解决最优分配的问题。在纽约期弟文斯工学院举办的可靠性会议上，他被邀请报告了该问题及有关成果。
在麻省理学院的研究工作中，堵丁柱给克拉依曼教授印象最深的是关于他本人的一个猜测的证明。这个猜测是关于曼哈顿格中具有给定直径最大的集约性质。教授万没有想到，这位中国学者在证明中使用了与他提出猜测论文中相同的技巧，在不长的时间里却获得了出人意外的成功。

④ 为什么随机梯度下降方法能够收敛

其实这个还是要好好的看看论文，然后让导师再给你好好的讲解一下吧，我这里只能说我自己的理解。

随机梯度下降算法

首先要知道什么是随机并行梯度下降算法。其实等于没有模型的优化的算法，就是更加的适用于那种控制变量比较多的，但是系统比较复杂的，又没有办法准确的去建立数学模型的优化控制的过程。

总结

其实我觉得我说这么多，不一定说明白啥，基本上我个人是觉得对于这种随机梯度下降的方法是期望收敛而已，真的是没有办法确定是否收敛的。

毕竟我没有论文专业，更没有导师专业，我只是用我自己的知识能力去回答的问题，所以说我由衷的建议你去看论文，看不懂就去问导师了，那才是正道啊，像我们这种人，毕竟没有那么专业，我害怕让你误入歧途。

⑤ 关于Logistic Regression对于线性可分的数据集的不收敛性的分析

最近我在进行斯坦福cs229的题目练习时候，碰到了一个不容易理解的case：即当面对线性可分的数据集的时候，Logistic Regression算法将永远无法收敛。

刚碰到的时候，心想stanford的题目真不是盖的，尽然百思不得其解。经过了各种google出来的帖子，文章，slides的阅读，目前算是有了一点点了解，但是还没真正理解透彻。所以目前先就理解的这部分按照逻辑叙述一下。

先从几个基本概念的介绍开始。

官方得说，就是有一堆标签数据，分别标为“1”，“0”两种。在其分布的坐标空间中，洞模存在一个超平面可以正好将两种标签的数据分开，就叫做线性可分的数据集。一般情况下，只要这个数据是线性可分的，就存在无数个超平面可以将两类数据分开。

我们用更严格的数学语言描述一下，有一份数据项的数目为m的数据集：

如果这个数据是线性可分(Linear separability)，则存在一个超平面：

使得上面的数据集有如下不等式组成立：

其中 x向量中有一项为1 ，即 ，这个处理主段悄要是为了包含超平面的常数项，即

为了更好理解线性可分的概念，我们可以看一个直观一点的二维数据图：

Logistic Regression中文叫逻辑回归，通俗得说就是二元线性回归或者多元线性回归后加上sigmoid函数，输出为二值分类。主要计算公式是损失函数：

整个逻辑回归就是通过梯度下降法或者牛顿法来求出一个最优的向量， ，使得上式中的J取最小值。所谓梯度下降法为：

假设我们做Logistic Regression所用的是梯度下降法。即刚开始 值都是随机的，或者都是0。所以在运用迭代法之前， 所取的值组成的超平面，是无法将数据正好分成标记正确的两部分，所以迭代可以一直进行下去, 直到迭代出一个线性可分的 。此时继续迭代，我们的目标函数将不能继续收敛了。

首先因为当前 已经满足线性可分，所以损失函数 将简化成如下式子：

我们再分析一下当 增加时， 函数的趋势：

又因为之前的关于 与 的分析，可知上面两个式子的各自的两种情况是一一对应的，即从 可推出 ，所以可以知道 在随着 增加，而单调减，最终减小为0，但是这个过程是当 取无限大的时候， 的极限才减小到0，所以 在这种情况下没有最小值， 会永远增加下去而无法收敛。

这篇收敛性的分析写得还是比较匆忙，仅纳燃缓仅是流水账地做了一点推理，很难做到逻辑缜密。而且我的思路的正确性有有待验证。

⑥ 最优化方法及其Matlab程序设计的目录

第1章 最优化理论基础
1.1 最优化问题的数学模型
1.2 向量和矩阵范数
1.3 函数的可微性与展开
1.4 凸集与凸函数
1.5 无约束问题的最优性条件
1.6 无约束优化问题的算法框架
习题1
第2章 线搜索技术
2.1 精确线搜索及其Matlab实现
2.1.1 黄金分割法
2.1.2 抛物线法
2.2 非精确线搜索及其Matlab实现
2.2.1 Wolfe准则
2.2.2 Armijo准则
2.3 线搜索法的收敛性
习题2
第3章 最速下降法和牛顿法
3.1 最速下降方法及其Matlab实现
3.2 牛顿法及其Matlab实现
3.3 修正牛顿法及其Matlab实现
习题3
第4章 共轭梯度法
4.1 共轭方向法
4.2 共轭梯度法
4.3 共轭梯度法的Matlab程序
习题4
第5章 拟牛顿法
5.1 拟牛顿法及其性质
5.2 BFGS算法及其Matlab实现
5.3 DFP算法及其Matlab实现
5.4 Broyden族算法及其Matlab实现
5.5 拟牛顿法的收敛性
习题5
第6章 信赖域方法
6.1 信赖域方法的基本结构
6.2 信赖域方法的收敛性
6.3 信赖域子问题的求解
6.4 信赖域方法的Matlab程序
习题6
第7章 非线性最小二乘问题
7.1 Gauss-Newton法
7.2 Levenberg-Marquardt方法
7.3 L-M算法的Matlab程序
习题7
第8章 最优性条件
8.1 等式约束问题的最优性条件
8.2 不等式约束问题的最优性条件
8.3 一般约束问题的最优性条件
8.4 鞍点和对偶问题
习题8
第9章 罚函数法
9.1 外罚函数法
9.2 内点法
9.2.1 不等式约束问题的内点法
9.2.2 一般约束问题的内点法
9.3 乘子法
9.3.1 等式约束问题的乘子法
9.3.2 一般约束问题的乘子法
9.4 乘子法的Matlab实现
习题9
第10章 可行方向法
10.1 Zoutendijk可行方向法
10.1.1 线性约束下的可行方向法
10.1.2 非线性约束下的可行方向法
10.2 梯度投影法
10.2.1 梯度投影法的理论基础
10.2.2 梯度投影法的计算步骤
10.3 简约梯度法
10.3.1 Wolfe简约梯度法
10.3.2 广义简约梯度法
习题10
第11章 二次规划
11.1 等式约束凸二次规划的解法
11.1.1 零空间方法
11.1.2 拉格朗日方法及其Matlab程序
11.2 一般凸二次规划的有效集方法
11.2.1 有效集方法的理论推导
11.2.2 有效集方法的算法步骤
11.2.3 有效集方法的Matlab程序
习题11
第12章 序列二次规划法
12.1 牛顿一拉格朗日法
12.1.1 牛顿一拉格朗日法的基本理论
12.1.2 牛顿一拉格朗日法的Matlab程序
12.2 SQP方法的算法模型
12.2.1 基于拉格朗日函数Hesse矩阵的SQF·方法
12.2.2 基于修正Hesse矩阵的SQP方法
12.3 SQP方法的相关问题
12.3.1 二次规划子问题的Hesse矩阵
12.3.2 价值函数与搜索方向的下降性
12.4 SQP方法的Matlab程序
12.4.1 SQP子问题的Matlab实现
12.4.2 SQP方法的Matlab实现
习题12
参考文献
附录 Matlab优化工具箱简介
A.1 线性规划
A.2 二次规划
A.3 无约束非线性优化
A.4 非线性最小二乘问题
A.5 约束条件的非线性优化命令
A.6 最小最大值的优化问题

⑦ 投影梯度下降（Projected gradient descent）

对于上面有条件的歼知闷优化问题，可以采用这样的的一种思路：

采用梯度下降的思路，更新 ，再将这样的更新值 向定义域C 作投影，以此来获得该优化问题在一定条件下的优化。猛盯

投影梯度下降的收敛性：

对于u-strongly convex 和 L-smooth 的函数f(x)

如果步长 取为 ，那么我们有这样的式子：氏弯

对于投影梯度递降法来说：

1）如果处理的是一个convex&smooth 问题，那们一般设置步长是

收敛速率是 ，循环的复杂度是

2）对于strongly-convex&smooth 问题，其步长依旧是 ，收敛速率是 ，循环复杂度是