- 综合排序
- 最热优先
- 最新优先
- 来自专栏机器学习与统计学
凸优化
”凸优化“ 是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。 而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题。 之所以要研究凸优化问题是因为其有一套非常完备的求解算法，如果将某个优化问题确认或者转化为凸优化问题，那么能够快速给出最优解。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
78230发布于 2019-04-10 - 来自专栏懂点编程的数据分析师
凸优化
定义 凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化的问题。尽管凸优化的条件比较苛刻，但仍然在机器学习领域有十分广泛的应用。 凸优化问题的优势 凸优化问题的局部最优解就是全局最优解 很多非凸问题都可以被等价转化为凸优化问题或者被近似为凸优化问题（例如拉格朗日对偶问题） 凸优化问题的研究较为成熟，当一个具体被归为一个凸优化问题， 是一个凸集，且对于所有 ? 均满足： ? 注意：这里的 ? 表示的是半正定。 3. 正定矩阵 3.1 从二次型出发理解正定矩阵 正定矩阵的概念是从正定二次型引入的，对称矩阵 ? 二元半正定二次型图像 凸优化问题 1. 定义： ? 当 ? 和 ? 均为凸函数，而 ? 均为仿射函数时, 上述的优化问题即凸优化问题。 2. 其中目标函数和不等式约束都是凸二次型。 2.4 半正定规划（SDP, Semidefinite Program） ? 其中需要最优化的变量 ? 是一个对称的半正定矩阵，且 ? 为对阵矩阵。 3.
1.9K30发布于 2020-06-09 - 来自专栏计算机视觉理论及其实现
凸优化和非凸优化的区别
凸优化问题是指 是闭合的凸集且 是 上的凸函数的最优化问题，这两个条件任一不满足则该问题即为非凸的最优化问题。 为什么要求是凸集呢？因为如果可行域不是凸集，也会导致局部最优? 实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点：目标函数 如果不是凸函数，则不是凸优化问题决策变量 中包含离散变量（0-1变量或整数变量），则不是凸优化问题约束条件写成 时， 如果不是凸函数，则不是凸优化问题之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决，而一般的非凸最优化问题相比之下更难解决。 非凸优化问题如何转化为凸优化问题的方法： 1）修改目标函数，使之转化为凸函数 2）抛弃一些约束条件，使新的可行域为凸集并且包含原可行域
4.6K30编辑于 2022-09-03 - 来自专栏算法之名
凸优化整理
凸集 在最优化范畴中，凸优化问题是一类比较常见的，性质很好，很多时候可以帮助我们解决非凸问题的工具。 如果一个凸函数min f(x),它的可行集x∈S，S是一个凸集合，如此一般来说我们就认为这是一个凸优化的问题。 凸组合 凸组合(convex combination):有k个点\(x^1\),\(x^2\),\(x^3\)... \(x^k\) 当\(λ_1x^1\)+\(λ_2x^2\)+\(λ_3x^3\)+...+\(λ_kx^k\)， 其中\(λ_1\),\(λ_2\),\(λ_3\),... 对于一个非凸集来说，如果对该集合产生一个凸包，那么就会将该非凸集转化成一个凸集。 凸包的作用主要用于解非凸优化问题的时候，会对一个非凸的问题进行凸化的作用。
77940编辑于 2023-03-01 - 来自专栏SIGAI学习与实践平台
理解凸优化
第二个问题更严重，我们找到了梯度为0的点，但它连局部极值都不是，典型的是x3这个函数，在0点处，它的导数等于0，但这根本不是极值点： ? 根据多元函数极值判别法，假设多元函数在点M的梯度为0，即M是函数的驻点，则有： 1.如果Hessian矩阵正定，函数在该点有极小值 2.如果Hessian矩阵负定，函数在该点有极大值 3. 3.矩阵合同于单位阵I。 类似的，如果一个n阶矩阵A，对于任何非0的n维向量x，都有： ? 则称矩阵A为负定矩阵。如果满足： ? 则称矩阵A为半正定矩阵。 凸优化 有了凸集和凸函数的定义之后，我们就可以给出凸优化的定义。如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。凸优化问题可以形式化的写成： ? 在上图中可行域不是凸集，中间有断裂，目标函数还是凸函数。在曲线的左边和右边各有一个最小值，不能保证局部最小值就是全局最小值。可以很容易把这个例子推广到3维空间里的2元函数（曲面）。
1.5K20发布于 2018-08-07 - 来自专栏算法之名
凸优化整理(二)
接凸优化整理 基于线搜索的下降算法基本思路 给定初始点\(x^0\)，k=0； 判断\(x^k\)是否满足终止条件：是，则终止； 寻找\(x^k\)处的下降方向\(d^k\)； 选择合适的步长\(α_k
52230编辑于 2023-03-01 - 来自专栏null的专栏
优化算法——凸优化的概述
一、引言 在机器学习问题中，很多的算法归根到底就是在求解一个优化问题，然而我们的现实生活中也存在着很多的优化问题，例如道路上最优路径的选择，商品买卖中的最大利润的获取这些都是最优化的典型例子，前面也陆续地有一些具体的最优化的算法 ，如基本的梯度下降法，牛顿法以及启发式的优化算法(PSO,ABC等)。 三、三类优化问题 主要有三类优化问题： 无约束优化问题 含等式约束的优化问题 含不等式约束的优化问题 针对上述三类优化问题主要有三种不同的处理策略，对于无约束的优化问题，可直接对其求导 ，并使其为0，这样便能得到最终的最优解；对于含等式约束的优化问题，主要通过拉格朗日乘数法将含等式越是的优化问题转换成为无约束优化问题求解；对于含有不等式约束的优化问题，主要通过KKT条件(Karush-Kuhn-Tucker Condition)将其转化成无约束优化问题求解。
2.8K100发布于 2018-03-19 - 来自专栏算法之名
凸优化整理(三)
接凸优化整理(二) 约束优化 约束优化问题 考虑如下一般形式约束优化问题： 记可行集为 假设问题(P)中的函数f(x)，\(g_i\)(x)，\(h_i\)(x)均为连续可微函数； 注意几类非光滑函数的转化 例：约束优化最优解的特征 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组成的可行集，虚线是 现已知\(x^*\)是局部最优解，由 \(g_1\)(x)和\(g_2\)(x)共同作用而成， \(g_3\)(x)未参与，且\(g_3\)(\(x^*\))<0。 )(\(x^*\))参与其中，我们可以写为 ∇f(\(x^*\))+\(λ_1\)∇\(g_1\)(\(x^*\))+\(λ_2\)∇\(g_2\)(\(x^*\))+\(λ_3\)∇ \(g_3\)(
51520编辑于 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) 得证 凸优化问题
95030编辑于 2023-03-01 - 来自专栏AI启蒙研究院
【通俗理解】凸优化
今天介绍一点凸优化方面的知识～内容可能有点无聊，看懂了这篇文章，会对求极值和收敛有进一步理解，比如： 了解为什么向量机（SVM）等的推导中，求极值时可以把约束条件加在目标函数后面来变成一个无约束的优化问题 这两个问题凸优化都可以帮我们回答。 在开始之前，我们先来回顾一下支持向量机（SVM）的推导过程。 SVM的任务就是寻找这样一个超平面H把样本无误地分割成两部分，并且使H1和H2的距离最大。 其中supporting定理通过函数上镜图的概念和凸函数联系起来了，这构成了凸优化中对偶性duality的基石。在凸优化中的对偶，和信号处理里的傅里叶变换一样重要。 求解这个最优化问题（quadratic programing）就用了Lagrangian dual。有人说了，好像没有看到有求所谓的h(y)啊，是不是打开方式不对？ 总结 对偶是凸优化的基石，延伸出各种优化方法。正如信号处理中时域上不好解决的问题变换到频域去解决。遇到目标函数是二次函数的，直接看看KKT条件能不能用。
2.1K30发布于 2018-07-20 - 来自专栏null的专栏
优化算法——凸优化的概述
一、引言 在机器学习问题中，很多的算法归根到底就是在求解一个优化问题，然而我们的现实生活中也存在着很多的优化问题，例如道路上最优路径的选择，商品买卖中的最大利润的获取这些都是最优化的典型例子 ，前面也陆续地有一些具体的最优化的算法，如基本的梯度下降法，牛顿法以及启发式的优化算法(PSO,ABC等)。 三、三类优化问题 主要有三类优化问题： 无约束优化问题 含等式约束的优化问题 含不等式约束的优化问题 针对上述三类优化问题主要有三种不同的处理策略，对于无约束的优化问题，可直接对其求导 ，并使其为0，这样便能得到最终的最优解；对于含等式约束的优化问题，主要通过拉格朗日乘数法将含等式越是的优化问题转换成为无约束优化问题求解；对于含有不等式约束的优化问题，主要通过KKT条件(Karush-Kuhn-Tucker Condition)将其转化成无约束优化问题求解。
1.5K70发布于 2019-02-13 - 来自专栏MyBlog
凸优化笔记(1) 引言
凸优化笔记(1) 引言 1. 引言 1.1 数学优化 优化问题可以写成如下形式 ? 凸优化即讨论约束函数和目标函数是凸函数的优化问题，即 ? 1.3 凸优化 凸优化问题具有以下形式化 ? 其中需要满足 ? 且 ? 1.3.1 求解凸优化问题 凸优化问题没有一个确定的解析解，但是和线性规划类似，存在许多算法求解凸优化问题，实际意义中内点法就比较有效 1.3.2 使用凸优化 同线性规划和最小二乘类似，我们可以将某个问题转化为凸优化问题进而将其求解 在全局优化中，人们致力于搜索问题的全局最优解，付出的代价是效率 1.4.3 非凸问题中凸优化的应用 局部优化中利用凸优化进行初始值的选取 非凸优化中的凸启发式算法 随机化算法 搜索带约束条件的稀疏向量
94310发布于 2019-03-15 - 来自专栏海风
凸优化和机器学习
优化问题，就是把你考虑的各个因素表示成为一组函数（代价函数），解决这个问题就是在一集备选解中选择最好的解。 那么，为什么我们要讨论凸优化而不是一般的优化问题呢？ （实际上就是太一般的优化问题讨论不来） 2.凸优化的定义 首先明确两个定义: ---- (1) 如果 ? 中任意两点之间的线段任在 ? 中，那么集合 ? 被称为凸集。即对任意 ? 也就是说，凸优化问题是指需要最小化的函数（代价函数）是凸函数，而且定义域为凸集的问题。 3.凸优化问题的一般求解方法 有些凸优化问题比较简单，是可以直接求解的，譬如二次规划，这里不做说明。 求解凸优化问题，就要利用该问题的“凸”性——只要我一直朝着代价函数减小的方向去，那么我一定不会走错！这就是下降方法的基本思想。 《convex optimization》这本书中，将凸优化问题分为无约束优化、等式约束优化和不等式约束优化分别介绍了其算法，然其本质并无区别。下降方法即产生一优化点列 ? 其中 ? 并且 ? 。
1.2K30发布于 2019-09-11 - 来自专栏闪电gogogo的专栏
凸优化之基追踪
范数问题，因为L1范数与L0范数等价，所以将L0范数转换为L1范数问题来求解，基追踪是将L1范数问题转为成为线性规划问题来进行求解，博主还提到了基追踪降噪问题，是转换为二次规划问题来进行求解的，但是这类凸优化问题计算复杂度高 压缩感知重构算法之基追踪降噪(Basis Pursuit De-Noising, BPDN),http://blog.csdn.net/jbb0523/article/details/52013669 [3]
1.8K111发布于 2018-04-02 - 来自专栏学弱猹的精品小屋
凸优化（1）——引入，优化实例分析，凸集举例与相关性质
对于凸优化，我们最容易产生的疑惑就是它与最优化（数值优化）有什么区别？虽然它们俩本质上都是优化，但是凸优化的研究范围更窄，可以看出对“凸”的要求更高。 Example 3: 2d-fused LASSO (Source: CMU) 考虑问题 ，其中 是数据点。 如果去掉后面的罚项部分，那么就是一个最小二乘回归问题。 相对来说比较陌生的是下面的这几个 Definition 3: Polyhedron, Simplex 定义多面体为 ，定义单纯形为 。其中这些点是仿射独立的（简单来说，三个点不在一条直线上）。 Problem 3: Linear Matrix Inequality Solution Set (Source: USTC, CMU) 给定 ，那么所有满足不等式 的点构成的集合为凸集。 我们要证明这个，是为了用到下面这个凸多面体的性质。 Proposition 3: 证明在一个有界多面体作为可行域的情况下，凸函数的最大值在这个多面体的顶点上取到。
1.9K10发布于 2021-08-09 - 来自专栏学弱猹的精品小屋
凸优化（3）——梯度与次梯度：方法，性质与比较
上一节笔记：凸优化（2）——凸函数，强凸函数及相关拓展 —————————————————————————————————————————————————— 大家好！ 回顾一下《数值优化》的概念，梯度下降法解决的依然是一个无约束优化问题，也就是 这里我们多加一个条件就是 凸且一阶可微。 Proposition 2: 证明带约束优化的一阶最优性条件，也即 。其中 是可行域，为凸集。 这个性质的证明要观察到可以通过指标函数，把带约束优化问题变成无约束优化问题。 下面放出了CMU的课程课件中，对于岭回归和LASSO问题的时候的优化算法迭代曲线，可以看出梯度方法到达了数值误差（关于数值误差可以参考《数值优化》第3节：数值优化（3）——线搜索中的步长选取方法，线性共轭梯度法 Definition 3: Polyak Step-size 定义步长 为波利亚步长。
2.2K10发布于 2021-08-09 - 来自专栏AINLP
凸优化及无约束最优化
很多年前，我的师兄 Jian Zhu 在这里发表过一个系列《无约束最优化》，当时我写下了一段话: 估计有些读者看到这个题目的时候会觉得很数学，和自然语言处理没什么关系，不过如果你听说过最大熵模型、条件随机场 ，并且知道它们在自然语言处理中被广泛应用，甚至你明白其核心的参数训练算法中有一种叫LBFGS，那么本文就是对这类用于解无约束优化算法的Quasi-Newton Method的初步介绍。 事实上，无论机器学习还是机器学习中的深度学习，数值优化算法都是核心之一，而在这方面，斯坦福大学Stephen Boyd教授等所著的《凸优化》堪称经典：Convex Optimization – Boyd class.stanford.edu/courses/Engineering/CVX101 提示是：A MOOC on convex optimization, CVX101, was run from 1/21/14 to 3/
1.1K70发布于 2019-10-11 - 来自专栏一点人工一点智能
书籍分享-《Convex Optimization（凸优化）》
《Convex Optimization（凸优化）》从理论、应用和算法三个方面系统地介绍凸优化内容。 凸优化在数学规划领域具有非常重要的地位。 从应用角度看，现有算法和常规计算能力已足以可靠地求解大规模凸优化问题，一旦将一个实际问题表述为凸优化问题，大体上意味着相应问题已经得到彻底解决，这是非凸的优化问题所不具有的性质。 本书理论部分由4章构成，不仅涵盖了凸优化的所有基本概念和主要结果，还详细介绍了几类基本的凸优化问题以及将特殊的优化问题表述为凸优化问题的变换方法，这些内容对灵活运用凸优化知识解决实际问题非常有用。 本书应用部分由3章构成，分别介绍凸优化在解决逼近与拟合、统计估计和几何关系分析这三类实际问题中的应用。 本书算法部分也由3章构成，依次介绍求解无约束凸优化模型、等式约束凸优化模型以及包含不等式约束的凸优化模型的经典数值方法，以及如何利用凸优化理论分析这些方法的收敛性质。
82530编辑于 2022-12-27 - 来自专栏gojam技术备忘录
非凸优化与梯度下降
首先抛一个知乎的回答：在数学中一个非凸的最优化问题是什么意思？
1.9K60发布于 2019-05-14 - 来自专栏杨熹的专栏
凸优化有什么用
本文结构： 凸优化有什么用？ 什么是凸优化？ ---- 凸优化有什么用？ 鉴于本文中公式比较多，先把凸优化的意义写出来吧，就会对它更有兴趣。 凸优化的价值也在于思维转变，当我们在现实生活中遇到计算量接近无穷大的问题时，我们要想办法将模型转换成“凸优化问题”，因为凸优化已经相对嚼得比较烂，所以只要问题转化成凸优化，我们就可以分布迭代去运算。 当然现实中绝大部分优化问题并不是凸优化问题，但是凸优化非常重要, 因为： 还是有相当一部分问题是或等价于凸优化问题，例如下面会举例说明 SVM，最小二乘等。 大部分凸优化问题解起来比较快。 ---- 什么是凸优化？ 关于凸优化，有几个基础概念：凸集，凸函数，凸优化问题，局部最优和全局最优。以及一个很重要的性质，就是所有局部最优点都是全局最优的 1. Let f : Rn → R be some norm on Rn Nonnegative weighted sums of convex functions ---- 3.
4.8K80发布于 2018-04-03
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号