- 综合排序
- 最热优先
- 最新优先
- 来自专栏机器学习与统计学
凸优化
”凸优化“ 是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。 而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题。 之所以要研究凸优化问题是因为其有一套非常完备的求解算法，如果将某个优化问题确认或者转化为凸优化问题，那么能够快速给出最优解。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
79830发布于 2019-04-10 - 来自专栏懂点编程的数据分析师
凸优化
定义 凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化的问题。尽管凸优化的条件比较苛刻，但仍然在机器学习领域有十分广泛的应用。 凸优化问题的优势 凸优化问题的局部最优解就是全局最优解 很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题（例如拉格朗日对偶问题） 凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题， 恒成立 1.2 几何意义： 直观来说，任取一个集合中的两点练成一条线段，如果这条线段完全落在该集合中，那么这个集合就是凸集。 ? 凸集的几何意义 2. 凸函数 2.1定义： 定义在 ? 上的函数 ? 二元半正定二次型图像 凸优化问题 1. 定义： ? 当 ? 和 ? 均为凸函数，而 ? 均为仿射函数时, 上述的优化问题即凸优化问题。 2. 凸优化问题的一般求解过程 由于凸优化问题具有局部最优解即全局最优解的优良特性，因此求解过程可以简化为：找到一个点列使得目标函数值持续减少，直到触发停止条件或达到一个最小值。 设 ? 为第 ?
1.9K30发布于 2020-06-09 - 来自专栏计算机视觉理论及其实现
凸优化和非凸优化的区别
凸优化问题是指 是闭合的凸集且 是 上的凸函数的最优化问题，这两个条件任一不满足则该问题即为非凸的最优化问题。 为什么要求是凸集呢？因为如果可行域不是凸集，也会导致局部最优? 实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点：目标函数 如果不是凸函数，则不是凸优化问题决策变量 中包含离散变量（0-1变量或整数变量），则不是凸优化问题约束条件写成 时， 如果不是凸函数，则不是凸优化问题之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决，而一般的非凸最优化问题相比之下更难解决。 非凸优化问题如何转化为凸优化问题的方法： 1）修改目标函数，使之转化为凸函数 2）抛弃一些约束条件，使新的可行域为凸集并且包含原可行域
4.7K30编辑于 2022-09-03 - 来自专栏SIGAI学习与实践平台
理解凸优化
Hessian矩阵简写为∇2 f (x)。对于如下多元函数： ? 它的Hessian矩阵为： ? 上图中优化变量的可行域是整个实数集，显然是凸集，目标函数不是凸函数，有两个局部最小值，这不能保证局部最小值就是全局最小值。 情况2：可行域不是凸集，函数是凸函数。这样的例子如下图所示： ? 在上图中可行域不是凸集，中间有断裂，目标函数还是凸函数。在曲线的左边和右边各有一个最小值，不能保证局部最小值就是全局最小值。可以很容易把这个例子推广到3维空间里的2元函数（曲面）。 加上L2正则化之后，训练时优化的问题变为： ? 同样的，我们可以证明这个函数的Hessian矩阵半正定，事实上，如果正则化项的系数大于0，它是严格正定的。限于篇幅，我们在这里不给出详细证明。 加上L2正则化项之后，训练时求解的问题为： ? 这是一个不带约束的优化问题，我们可以证明这个函数的Hessian矩阵半正定。如果读者对证明过程感兴趣，我们以后的公众号文章中会给出。
1.5K20发布于 2018-08-07 - 来自专栏算法之名
凸优化整理
凸集 在最优化范畴中，凸优化问题是一类比较常见的，性质很好，很多时候可以帮助我们解决非凸问题的工具。 如果一个凸函数min f(x),它的可行集x∈S，S是一个凸集合，如此一般来说我们就认为这是一个凸优化的问题。 在图2中满足这个条件的点并不是唯一的，它有两个点都满足，但只有一个最优解，也就是\(x^*\)。这里是由S集本身的性质决定的，图1的S集是一个凸集，图2的S集是一个非凸集。 凸组合 凸组合(convex combination):有k个点\(x^1\),\(x^2\),\(x^3\)... 对于一个非凸集来说，如果对该集合产生一个凸包，那么就会将该非凸集转化成一个凸集。 凸包的作用主要用于解非凸优化问题的时候，会对一个非凸的问题进行凸化的作用。
81240编辑于 2023-03-01 - 来自专栏算法之名
凸优化整理(二)
接凸优化整理 基于线搜索的下降算法基本思路 给定初始点\(x^0\)，k=0； 判断\(x^k\)是否满足终止条件：是，则终止； 寻找\(x^k\)处的下降方向\(d^k\)； 选择合适的步长\(α_k 这里的终止条件一般为∇f(\(x^k\))=0，但是在实际计算的时候，我们不会直接判断为0，而是二范数小于一个非常小的数，如\(10^{-4}\)或者\(10^{-6}\) \(||∇f(x^k)||_2\ 终止条件也可以是如果\(||x^k-x^{k+N}||_2\)≤ɛ，说明又经过了N次迭代(N会根据实际的问题来取)，并没有发生太大的改变，依然还是在一个非常小的邻域中，此时也可以终止。 由于H正定，则f(x)为一个凸函数，将f(x)代入 Φ(α)有 Φ(α)=\(1\over 2\)\((x^k+αd^k)^TH\)(\(x^k+αd^k\))+\(c^T\) (\(x^k+αd^k\ ))+b =\(1\over 2\)\((d^k)^TH\)\(d^k\)\(α^2\)+(\((d^k)^TH\)\(x^k\)+\(c^T\)\(d^k\))α+b 进行线搜索，就是求
57230编辑于 2023-03-01 - 来自专栏null的专栏
优化算法——凸优化的概述
一、引言 在机器学习问题中，很多的算法归根到底就是在求解一个优化问题，然而我们的现实生活中也存在着很多的优化问题，例如道路上最优路径的选择，商品买卖中的最大利润的获取这些都是最优化的典型例子，前面也陆续地有一些具体的最优化的算法 三、三类优化问题 主要有三类优化问题： 无约束优化问题 含等式约束的优化问题 含不等式约束的优化问题 针对上述三类优化问题主要有三种不同的处理策略，对于无约束的优化问题，可直接对其求导 正则化主要有两种： L1-Regularization，见“简单易学的机器学习算法——lasso” L2-Regularization，见“简单易学的机器学习算法——岭回归(Ridge Regression )” 常见的描述L1和L2正则化的图如下： ? 左图中的正方形代表的是L1约束，绿色的是损失函数的等高线，最优解出现在坐标轴上的概率较大(注意：主要是区分是否求出的是全局最优解)；而右图中黑色的圆代表的是L2约束。
2.8K100发布于 2018-03-19 - 来自专栏算法之名
凸优化整理(三)
接凸优化整理(二) 约束优化 约束优化问题 考虑如下一般形式约束优化问题： 记可行集为 假设问题(P)中的函数f(x)，\(g_i\)(x)，\(h_i\)(x)均为连续可微函数； 注意几类非光滑函数的转化 x≤t \(x^2\)≤t 这样就都满足了处处可微的条件进行求解。 例：约束优化最优解的特征 min f(x) x∈\(R^n\) s.t. \(g_1\)(x)≤0 \(g_2\)(x)≤0 \(g_3\)(x)≤0 在上图中，S是由 \(g_1\)(x)≤0， \(g_2\)(x)≤0， \(g_3\)(x)≤0组成的可行集，虚线是 _2\)≥0 变形有 ∇f(\(x^*\))+\(λ_1\)∇\(g_1\)(\(x^*\))+\(λ_2\)∇\(g_2\)(\(x^*\))=0 为了让 \(g_3\)(\(x^*\))参与其中，我们可以写为 0，\(λ_2\)≥0，\(λ_3\)≥0 \(λ_1\)\(g_1\)(\(x^*\))=0，\(λ_2\)\(g_2\)(\(x^*\))=0，\(λ_3\)\(g_3\)(\(x^*\))=0 最优解的一阶必要条件
56120编辑于 2023-03-01 - 来自专栏算法之名
凸优化整理(四)
接凸优化整理(三) 对偶理论 考虑如下一般形式约束优化问题： 记可行集为 这里跟之前不同的地方在于x∈X。 鲁棒优化，锥优化跟对偶问题在某些前提下具有一定的等价关系。 ,l均为线性函数；即原问题P是一个凸优化问题。 假设存在 ∈X使得 (严格可行点)，且0∈int h(X)，其中h(X)={\((h_1(x),... ,l，x∈X} 由f(x)是凸函数，\(g_i(x)\)是凸函数，X是凸集合，可知H是凸集合，且\((0,0,0)^T\)∉H，这里第一个0是1维，第二个0是m维，第三个0是l维 根据凸集分离定理(见凸优化整理 {i=1}^m\) \(g_i(x)\)+\(\sum_{i=1}^l\) \(h_i(x)\)≥γ，∀x∈X 可得d( , )≥γ=v(P) 故v(D)=d( , )=v(P) 得证 凸优化问题
1K30编辑于 2023-03-01 - 来自专栏AI启蒙研究院
【通俗理解】凸优化
今天介绍一点凸优化方面的知识～内容可能有点无聊，看懂了这篇文章，会对求极值和收敛有进一步理解，比如： 了解为什么向量机（SVM）等的推导中，求极值时可以把约束条件加在目标函数后面来变成一个无约束的优化问题 之前文章有介绍过，一个算法有效至少要满足两个条件：1）极值存在，2）收敛。极值不存在说明模型无效，算法无意义。算法不能收敛意味着找不到极值，也没有价值。这两个问题凸优化都可以帮我们回答。 其中supporting定理通过函数上镜图的概念和凸函数联系起来了，这构成了凸优化中对偶性duality的基石。在凸优化中的对偶，和信号处理里的傅里叶变换一样重要。 很多实际问题的目标函数都是二次函数，因为二次函数可以代表欧式距离（回想距离公式x^2+y^2），可以代表能量（x^2），是一个好的error/cost function。 总结 对偶是凸优化的基石，延伸出各种优化方法。正如信号处理中时域上不好解决的问题变换到频域去解决。遇到目标函数是二次函数的，直接看看KKT条件能不能用。
2.1K30发布于 2018-07-20 - 来自专栏null的专栏
优化算法——凸优化的概述
三、三类优化问题 主要有三类优化问题： 无约束优化问题 含等式约束的优化问题 含不等式约束的优化问题 针对上述三类优化问题主要有三种不同的处理策略，对于无约束的优化问题，可直接对其求导 ，并使其为0，这样便能得到最终的最优解；对于含等式约束的优化问题，主要通过拉格朗日乘数法将含等式越是的优化问题转换成为无约束优化问题求解；对于含有不等式约束的优化问题，主要通过KKT条件(Karush-Kuhn-Tucker 正则化主要有两种： L1-Regularization，见“简单易学的机器学习算法——lasso” L2-Regularization，见“简单易学的机器学习算法——岭回归(Ridge Regression )” 常见的描述L1和L2正则化的图如下： ? 左图中的正方形代表的是L1约束，绿色的是损失函数的等高线，最优解出现在坐标轴上的概率较大(注意：主要是区分是否求出的是全局最优解)；而右图中黑色的圆代表的是L2约束。
1.5K70发布于 2019-02-13 - 来自专栏海风
凸优化和机器学习
（实际上就是太一般的优化问题讨论不来） 2.凸优化的定义 首先明确两个定义: ---- (1) 如果 ? 中任意两点之间的线段任在 ? 中，那么集合 ? 被称为凸集。即对任意 ? (2) 函数 ? 是凸函数，则 ? 是凸集，且对于任意 ? 在任 ? 下有 ? ---- Stephen Boyd在他的《convex optimization》中定义凸优化问题是形如 ? 也就是说，凸优化问题是指需要最小化的函数（代价函数）是凸函数，而且定义域为凸集的问题。 3.凸优化问题的一般求解方法 有些凸优化问题比较简单，是可以直接求解的，譬如二次规划，这里不做说明。 《convex optimization》这本书中，将凸优化问题分为无约束优化、等式约束优化和不等式约束优化分别介绍了其算法，然其本质并无区别。下降方法即产生一优化点列 ? 其中 ? 并且 ? 。 (1)初始点可行：在可行域内迭代 (2)初始点不可行：迭代过程中逐步靠近可行域 不等式约束 如果我们不能解决一个问题，那么就消除这个问题。
1.2K30发布于 2019-09-11 - 来自专栏MyBlog
凸优化笔记(1) 引言
凸优化笔记(1) 引言 1. 引言 1.1 数学优化 优化问题可以写成如下形式 ? 凸优化即讨论约束函数和目标函数是凸函数的优化问题，即 ? 1.3 凸优化 凸优化问题具有以下形式化 ? 其中需要满足 ? 且 ? 1.3.1 求解凸优化问题 凸优化问题没有一个确定的解析解，但是和线性规划类似，存在许多算法求解凸优化问题，实际意义中内点法就比较有效 1.3.2 使用凸优化 同线性规划和最小二乘类似，我们可以将某个问题转化为凸优化问题进而将其求解 在全局优化中，人们致力于搜索问题的全局最优解，付出的代价是效率 1.4.3 非凸问题中凸优化的应用 局部优化中利用凸优化进行初始值的选取 非凸优化中的凸启发式算法 随机化算法 搜索带约束条件的稀疏向量
96810发布于 2019-03-15 - 来自专栏闪电gogogo的专栏
凸优化之基追踪
范数问题，因为L1范数与L0范数等价，所以将L0范数转换为L1范数问题来求解，基追踪是将L1范数问题转为成为线性规划问题来进行求解，博主还提到了基追踪降噪问题，是转换为二次规划问题来进行求解的，但是这类凸优化问题计算复杂度高 压缩感知重构算法之基追踪(Basis Pursuit, BP),http://blog.csdn.net/jbb0523/article/details/51986554 [2] 彬彬有礼.
1.8K111发布于 2018-04-02 - 来自专栏学弱猹的精品小屋
凸优化（1）——引入，优化实例分析，凸集举例与相关性质
对于凸优化，我们最容易产生的疑惑就是它与最优化（数值优化）有什么区别？虽然它们俩本质上都是优化，但是凸优化的研究范围更窄，可以看出对“凸”的要求更高。 Example 2: Shortest-Path Problem (Source: USTC) 考虑最短路问题，严格来说可以把它写成一个优化问题，即 , 这里 表示是起点（Source）， 表示是终点 Problem 2: 设 ，证明如果 是一个凸集，那么 也是一个凸集。 这个题也不是很困难。我们取 ，那么会有 。取 ，那么会有 （因为 是凸的）。这就可以推出 ，也就证明完毕了。 事实上引出Problem 2也是出于特有的目的，也即下面这个例子。 这个集合当然是凸集，因为它是一个凸集在线性映射下的原象集，也就是利用上了Problem 2的结论。 接下来我们给出一个凸集的加和性质，它的证明方法也是很巧妙的。
1.9K10发布于 2021-08-09 - 来自专栏学弱猹的精品小屋
凸优化（2）——凸函数，强凸函数及相关拓展
上一节笔记：凸优化（1）——引入，优化实例分析，凸集举例与相关性质 —————————————————————————————————————————————————— 大家好！ 虽然这一节依然还不会进入到具体的算法，但我们还需要再强调的一点是：凸优化本身其实就有非常多的偏分析的内容。我们不会去涉及与算法毫无关联的部分，而更多的希望以算法为主轴来考虑不同的凸优化问题。 作为凸优化的核心性质，我们多花一些篇幅来写它，也是理所应当。 首先我们给出最简单的凸函数的定义。 Definition 2: (Strictly) Concave Functions 若是一个凸函数，那么定义是一个凹函数。如果等号处处不成立，则称它是一个严格凹函数。 Proposition 2: 证明Definition 4与其它两个定义的等价性。 我们证明一下这个结论。
3.2K11发布于 2021-08-09 - 来自专栏AINLP
凸优化及无约束最优化
很多年前，我的师兄 Jian Zhu 在这里发表过一个系列《无约束最优化》，当时我写下了一段话: 估计有些读者看到这个题目的时候会觉得很数学，和自然语言处理没什么关系，不过如果你听说过最大熵模型、条件随机场 ，并且知道它们在自然语言处理中被广泛应用，甚至你明白其核心的参数训练算法中有一种叫LBFGS，那么本文就是对这类用于解无约束优化算法的Quasi-Newton Method的初步介绍。 事实上，无论机器学习还是机器学习中的深度学习，数值优化算法都是核心之一，而在这方面，斯坦福大学Stephen Boyd教授等所著的《凸优化》堪称经典：Convex Optimization – Boyd
1.2K70发布于 2019-10-11 - 来自专栏杨熹的专栏
凸优化有什么用
本文结构： 凸优化有什么用？ 什么是凸优化？ ---- 凸优化有什么用？ 鉴于本文中公式比较多，先把凸优化的意义写出来吧，就会对它更有兴趣。 凸优化的价值也在于思维转变，当我们在现实生活中遇到计算量接近无穷大的问题时，我们要想办法将模型转换成“凸优化问题”，因为凸优化已经相对嚼得比较烂，所以只要问题转化成凸优化，我们就可以分布迭代去运算。 当然现实中绝大部分优化问题并不是凸优化问题，但是凸优化非常重要, 因为： 还是有相当一部分问题是或等价于凸优化问题，例如下面会举例说明 SVM，最小二乘等。 大部分凸优化问题解起来比较快。 如果可以证明 θx+(1−θ)y 仍然属于这个集合，那么它就是凸集 ---- 2. 所以这是个凸优化问题， 当然了我们可以简单地根据 SVM 具有二次的优化目标，以及线性的限制条件来判断，而无需转化成标准形式。 2. 最小二乘的优化目标： ?
4.9K80发布于 2018-04-03 - 来自专栏gojam技术备忘录
非凸优化与梯度下降
首先抛一个知乎的回答：在数学中一个非凸的最优化问题是什么意思？
1.9K60发布于 2019-05-14 - 来自专栏一点人工一点智能
书籍分享-《Convex Optimization（凸优化）》
《Convex Optimization（凸优化）》从理论、应用和算法三个方面系统地介绍凸优化内容。 凸优化在数学规划领域具有非常重要的地位。 从应用角度看，现有算法和常规计算能力已足以可靠地求解大规模凸优化问题，一旦将一个实际问题表述为凸优化问题，大体上意味着相应问题已经得到彻底解决，这是非凸的优化问题所不具有的性质。 从理论角度看，用凸优化模型对一般性非线性优化模型进行局部逼近，始终是研究非线性规划问题的主要途径，因此，通过学习凸优化理论，可以直接或间接地掌握数学规划领域几乎所有重要的理论结果。 本书理论部分由4章构成，不仅涵盖了凸优化的所有基本概念和主要结果，还详细介绍了几类基本的凸优化问题以及将特殊的优化问题表述为凸优化问题的变换方法，这些内容对灵活运用凸优化知识解决实际问题非常有用。 本书算法部分也由3章构成，依次介绍求解无约束凸优化模型、等式约束凸优化模型以及包含不等式约束的凸优化模型的经典数值方法，以及如何利用凸优化理论分析这些方法的收敛性质。
84430编辑于 2022-12-27
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号