目录 将有约束问题转化为无约束问题 拉格朗日法 KKT条件 拉格朗日法更新方程 凸优化问题下的拉格朗日法 罚函数法 对梯度算法进行修改，使其运用在有约束条件下 投影法 梯度下降法 to 投影梯度法 正交投影算子 References 相关博客 梯度下降法、最速下降法、牛顿法等迭代求解方法，都是在无约束的条件下使用的，而在有约束的问题中，直接使用这些梯度方法会有问题，如更新后的值不满足约束条件。 那么问题来了，如何处理有约束的优化问题？大致可以分为以下两种方式： 将有约束的问题转化为无约束的问题，如拉格朗日乘子法和KKT条件； 对无约束问题下的求解算法进行修改，使其能够运用在有约束的问题中，如对梯度下降法进行投影，使得更新后的值都满足约束条件。 将有约束问题转化为无约束问题 拉格朗日法 仅含等式约束的优化问题 minimize subject to f(x)h(x)=0 其中，x∈Rn，f:Rn→R，h:Rn→Rm,h=[h1,…,hm]⊤, and m≤n。 该问题的拉格朗日函数为： l(x,λ)=f(x)+λ⊤h(x) FONC：对拉格朗日函数 l(x,λ) 求偏导数，令偏导数都等于 0，求得的解必然满足原问题的等式约束，可以从这些解里面寻找是否有局部最优解。这是求得局部最优解的一阶必要条件。 拉格朗日条件：（分别对 x 和 λ 求偏导） Dxl(x∗,λ∗)=0⊤Dλl(x∗,λ∗)=0⊤ 上式中，对 λ 求偏导数得到的就是等式约束。 拉格朗日条件是必要而非充分条件，即满足上述方程的点 x∗ 不一定是极值点。 KKT条件 既含等式约束又含不等式约束的优化问题： minimize subject to f(x)h(x)=0g(x)≤0 其中，f:Rn→R，h:Rn→Rm,m≤n，并且 g:Rn→Rp。 将该问题转化为拉格朗日形式： l(x,λ)=f(x)+λ⊤h(x)+μ⊤g(x) 设 x∗ 是原问题的一个局部极小点，则必然存在 λ∗⊤∈Rm，μ∗⊤∈Rp，使得下列KKT条件成立： μ∗≥0 Df(x∗)+λ∗⊤Dh(x∗)+μ∗⊤Dg(x∗)=0⊤ μ∗⊤g(x∗)=0 h(x∗)=0 g(x∗)≤0 KKT条件中，λ∗ 是拉格朗日乘子向量，μ∗ 是KKT乘子向量，λ∗ 和 μ∗ 的元素分别称为拉格朗日乘子和KKT乘子。 拉格朗日法更新方程 将含约束的优化问题转化为拉格朗日形式后，我们可以用更新方程对该问题进行迭代求解。 这也是一种梯度算法，但拉格朗日乘子、KKT 乘子的更新和自变量 x 的更新不同，自变量 x 继续采用梯度下降法更新，而拉格朗日乘子、KKT 乘子的更新方程如下： λ(k+1)=λ(k)+βkh(x(k)),μ(k+1)=[μ(k)+βkg(x(k))]+ 其中，[⋅]+=max{⋅,0}。 凸优化问题下的拉格朗日法 拉格朗日乘子法和KKT条件在一般的含约束条件的优化问题中，都只是一阶必要条件，而在凸优化问题中，则变成了充分条件。 凸优化问题指的是目标函数是凸函数，约束集是凸集的优化问题。线性规划、二次规划（目标函数为二次型函数、约束方程为线性方程）都可以归为凸优化问题。 凸优化问题中，局部极小点就是全局极小点。极小点的一阶必要条件就是凸优化问题的充分条件。 罚函数法 updating... 对梯度算法进行修改，使其运用在有约束条件下 投影法 梯度下降法、最速下降法、牛顿法等优化算法都有通用的迭代公式： x(k+1)=x(k)+αkd(k) 其中，d(k) 是关于梯度 ∇f(x(k)) 的函数。 考虑优化问题： minimize subject to f(x)x∈Ω 在上述有约束的优化问题中，x(k)+αkd(k) 可能不在约束集 Ω 内，这是梯度下降等方法无法使用的原因。 而投影法做的是，如果 x(k)+αkd(k) 跑到约束集 Ω 外面去了，那么将它投影到约束集内离它最近的点；如果 x(k)+αkd(k)∈Ω，那么正常更新即可。 投影法的更新公式为： x(k+1)=Π[x(k)+αkd(k)] 其中 Π 为投影算子，Π[x] 称为 x 到 Ω 上的投影。 梯度下降法 to 投影梯度法 梯度下降法的迭代公式为： x(k+1)=x(k)−αk∇f(x(k)) 将投影算法引入梯度下降法，可得投影梯度法，迭代公式如下： x(k+1)=Π[x(k)−αk∇f(x(k))] 正交投影算子 updating... References Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition 相关博客 【机器学习之数学】01 导数、偏导数、方向导数、梯度 【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 【机器学习之数学】03 有约束的非线性优化问题——拉格朗日乘子法、KKT条件、投影法 作者：wuliytTaotao 出处：https://www.cnblogs.com/wuliytTaotao/ 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。 分类: machine learning 标签: optimization, machine learning 好文要顶 关注我 收藏该文 wuliytTaotao 关注 - 11 粉丝 - 32 +加关注 0 0 « 上一篇：【tf.keras】tf.keras使用tensorflow中定义的optimizer posted @ 2019-06-24 20:14 wuliytTaotao 阅读(85) 评论(0) 编辑 收藏 目录 将有约束问题转化为无约束问题 拉格朗日法 KKT条件 拉格朗日法更新方程 凸优化问题下的拉格朗日法 罚函数法 对梯度算法进行修改，使其运用在有约束条件下 投影法 梯度下降法 to 投影梯度法 正交投影算子 References 相关博客 梯度下降法、最速下降法、牛顿法等迭代求解方法，都是在无约束的条件下使用的，而在有约束的问题中，直接使用这些梯度方法会有问题，如更新后的值不满足约束条件。 那么问题来了，如何处理有约束的优化问题？大致可以分为以下两种方式： 将有约束的问题转化为无约束的问题，如拉格朗日乘子法和KKT条件； 对无约束问题下的求解算法进行修改，使其能够运用在有约束的问题中，如对梯度下降法进行投影，使得更新后的值都满足约束条件。 将有约束问题转化为无约束问题 拉格朗日法 仅含等式约束的优化问题 minimize subject to f(x)h(x)=0 其中，x∈Rn，f:Rn→R，h:Rn→Rm,h=[h1,…,hm]⊤, and m≤n。 该问题的拉格朗日函数为： l(x,λ)=f(x)+λ⊤h(x) FONC：对拉格朗日函数 l(x,λ) 求偏导数，令偏导数都等于 0，求得的解必然满足原问题的等式约束，可以从这些解里面寻找是否有局部最优解。这是求得局部最优解的一阶必要条件。 拉格朗日条件：（分别对 x 和 λ 求偏导） Dxl(x∗,λ∗)=0⊤Dλl(x∗,λ∗)=0⊤ 上式中，对 λ 求偏导数得到的就是等式约束。 拉格朗日条件是必要而非充分条件，即满足上述方程的点 x∗ 不一定是极值点。 KKT条件 既含等式约束又含不等式约束的优化问题： minimize subject to f(x)h(x)=0g(x)≤0 其中，f:Rn→R，h:Rn→Rm,m≤n，并且 g:Rn→Rp。 将该问题转化为拉格朗日形式： l(x,λ)=f(x)+λ⊤h(x)+μ⊤g(x) 设 x∗ 是原问题的一个局部极小点，则必然存在 λ∗⊤∈Rm，μ∗⊤∈Rp，使得下列KKT条件成立： μ∗≥0 Df(x∗)+λ∗⊤Dh(x∗)+μ∗⊤Dg(x∗)=0⊤ μ∗⊤g(x∗)=0 h(x∗)=0 g(x∗)≤0 KKT条件中，λ∗ 是拉格朗日乘子向量，μ∗ 是KKT乘子向量，λ∗ 和 μ∗ 的元素分别称为拉格朗日乘子和KKT乘子。 拉格朗日法更新方程 将含约束的优化问题转化为拉格朗日形式后，我们可以用更新方程对该问题进行迭代求解。 这也是一种梯度算法，但拉格朗日乘子、KKT 乘子的更新和自变量 x 的更新不同，自变量 x 继续采用梯度下降法更新，而拉格朗日乘子、KKT 乘子的更新方程如下： λ(k+1)=λ(k)+βkh(x(k)),μ(k+1)=[μ(k)+βkg(x(k))]+ 其中，[⋅]+=max{⋅,0}。 凸优化问题下的拉格朗日法 拉格朗日乘子法和KKT条件在一般的含约束条件的优化问题中，都只是一阶必要条件，而在凸优化问题中，则变成了充分条件。 凸优化问题指的是目标函数是凸函数，约束集是凸集的优化问题。线性规划、二次规划（目标函数为二次型函数、约束方程为线性方程）都可以归为凸优化问题。 凸优化问题中，局部极小点就是全局极小点。极小点的一阶必要条件就是凸优化问题的充分条件。 罚函数法 updating... 对梯度算法进行修改，使其运用在有约束条件下 投影法 梯度下降法、最速下降法、牛顿法等优化算法都有通用的迭代公式： x(k+1)=x(k)+αkd(k) 其中，d(k) 是关于梯度 ∇f(x(k)) 的函数。 考虑优化问题： minimize subject to f(x)x∈Ω 在上述有约束的优化问题中，x(k)+αkd(k) 可能不在约束集 Ω 内，这是梯度下降等方法无法使用的原因。 而投影法做的是，如果 x(k)+αkd(k) 跑到约束集 Ω 外面去了，那么将它投影到约束集内离它最近的点；如果 x(k)+αkd(k)∈Ω，那么正常更新即可。 投影法的更新公式为： x(k+1)=Π[x(k)+αkd(k)] 其中 Π 为投影算子，Π[x] 称为 x 到 Ω 上的投影。 梯度下降法 to 投影梯度法 梯度下降法的迭代公式为： x(k+1)=x(k)−αk∇f(x(k)) 将投影算法引入梯度下降法，可得投影梯度法，迭代公式如下： x(k+1)=Π[x(k)−αk∇f(x(k))] 正交投影算子 updating... References Edwin K. P. Chong, Stanislaw H. Zak-An Introduction to Optimization, 4th Edition 相关博客 【机器学习之数学】01 导数、偏导数、方向导数、梯度 【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 【机器学习之数学】03 有约束的非线性优化问题——拉格朗日乘子法、KKT条件、投影法 作者：wuliytTaotao 出处：https://www.cnblogs.com/wuliytTaotao/ 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。 分类: machine learning 标签: optimization, machine learning 好文要顶 关注我 收藏该文 wuliytTaotao 关注 - 11 粉丝 - 32 +加关注 0 0 « 上一篇：【tf.keras】tf.keras使用tensorflow中定义的optimizer posted @ 2019-06-24 20:14 wuliytTaotao 阅读(85) 评论(0) 编辑 收藏 https://www.cnblogs.com/wuliytTaotao/p/11077353.html