至于松弛问题和对偶问题如何求解这里只是简单提一句，松弛问题的形式一般来讲是不确定的，但是若要让LR方法效果比较好松弛问题不宜过于复杂，因为在实际问题的求解中一般我们不会把所有的约束都放到目标函数上去，我们只是把复杂的难以处理的约束放到目标函数上去，选择那些约束放到目标函数上去这个要结合具体问题，甚至要结合具体的应用场景去设计。如果松弛之后得到的松弛问题是线性规划（LP），二次规划（QP）那就是最好不过的了。对偶问题的求解相对固定一些，因为前面说了无论原问题怎么样，对偶问题是一个凸优化，严格来讲是一个不可微的凸优化问题，针对不可微的凸优化问题一般采用次梯度方法来求解，可以理解为是把梯度的概念进行了推广，次梯度往往不唯一，这一点和梯度不同。研究如何选取次梯度也是LR中一个重要的方面，相关研究也有很多论文
链接：https://zhuanlan.zhihu.com/p/28958014