那么这一节我们希望介绍一些与凸函数(convex functions)有关的性质。作为凸优化的核心性质,我们多花一些篇幅来写它,也是理所应当。 首先我们给出最简单的凸函数的定义。...Definition 1: (Strictly) Convex Functions 若满足是凸集,且,那么称它是一个凸函数。如果等号处处不成立,则称它是一个严格凸函数。...比方说对于线性函数,你会发现它既是凸函数,又是凹函数。 关于凹凸其实不同的人的看法会很不一样。这里我们要统一一下说法:所有的凸函数都是下面图中展示的那样,有的书上会翻译凸为下凸,翻译凹为上凸。...而且没有凹集的说法,比方说,这个函数就不是一个凸函数,但是如果只看左半边和右半边,它都是凸函数(感兴趣的可以自己画图看看)。这种奇怪的现象出现的原因就是它的定义域为,这个定义域并不是一个凸集。...可以看出凸是非常重要的一个主题,函数有不同的性质,就会有不同的凸函数刻画。
定义 1.1 上凸函数 如果对任意 、 总有 ,其中 ,则称 为上凸函数。...1.2 下凸函数 如果对任意 、 总有 ,其中 ,则称 为下凸函数。 如果对任意 、 且 ,总有 ,其中 ,则称 为严格下凸函数。...对于下凸函数, 或 ,其中 为正实数(或非负实数,后者去除无影响的 的项即为前者,故二者等价)且 ;对于严格下凸函数,上述等号成立当且仅当 。...而根据上文对于上凸函数对于 不等式推导过程可知,若上凸函数为严格上凸函数,则第一个 处等号成立当且仅当: ;第二个 处等号成立当且仅当: ; ;第 个 处等号成立当且仅当...而根据上文对于下凸函数对于 不等式推导过程可知,若下凸函数为严格下凸函数,则第一个 处等号成立当且仅当: ;第二个 处等号成立当且仅当 ; ;第 个 处等号成立当且仅当
凸函数在优化问题中有着很好的性质,本文记录相关概念。...凸集与凸函数 凸集 定义:设集合 C⊂Rn ,若对 ∀x,y∈C ,有: \theta x+(1-\theta) y \in C, \theta \in[0,1] 则称 C 为 凸集 几何意义:若...f:C→R 二阶连续可微, 则: f(x) 是凸函数当且仅当对∀x∈C, Hesse矩阵 G(x) 半正定 若对 ∀x∈C, Hesse矩阵 G(x) 正定,则 f 是严格凸函数。...凸函数判定条件证明 凸函数(一元)的定义是: 任意属于定义域的两个自变量x1和x2,且对于任意0≤θ≤1,如果函数f(⋅)满足: f\left(\theta x_{1}+(1-\theta) x_{2...}\right) \leq \theta f\left(x_{1}\right)+(1-\theta) f\left(x_{2}\right) 那么函数f(⋅)是凸函数。
读文章和学习过程中经常会遇到concave,convex以及down,up的组合。怎样区分呢?
在机器学习领域,我们经常会听到凸函数和非凸函数,简单来讲,凸函数指的是顺着梯度方向走,函数能得到最优解 ,大部分传统机器学习问题都是凸的。...,但研究者对非凸函数的随机梯度下降的理论尚未完全了解(目前仅对凸函数的随机梯度下降有了解); 现阶段随机梯度下降要求对梯度的一致有界性施加一个假设; 论文作者建立了非凸函数随机梯度下降理论基础,使有界假设可以消除而不影响收敛速度...发帖人表示:基于这些文献,我们是否真的能够证明(随机)梯度下降有潜力在非凸函数上显示类似的全局收敛性质,达到之前仅在凸函数上显示收敛程度?...但是我们仍然有理由相信(随机)梯度下降与凸函数相比在非凸函数上收敛更困难。 网友:问题改成「梯度下降在什么条件下会收敛于非凸函数」更好 针对发帖者的这一问题 —— 随机梯度下降能否收敛于非凸函数?...所以,ta 建议发帖者将问题改成「梯度下降在什么条件下会收敛于某类非凸函数」,然后将每类函数作为子问题进行研究,并消除打破传统梯度下降方法的非凸函数反例。
它给出积分的凸函数值和凸函数的积分值间的关系。...简介 琴生不等式(Jensen’s inequality)以丹麦技术大学数学家约翰·延森(John Jensen)命名 ,它给出积分的凸函数值和凸函数的积分值间的关系。...琴生不等式有以下推论:过一个下凸函数上任意两点所作割线一定在这两点间的函数图象的上方,即: t f\left(x_ {1}\right)+(1-t) f\left(x_ {2}\right) \geq...f\left(t x_ {1}+(1-t) x_ {2}\right), 0 \leq t \leq 1 该不等式与凸函数关系密切 Jensen不等式 根据凸函数性质,凸集C上的凸函数f上的两点x_1,...,证明对于凸函数 f(x) 来说,对任意 \lambda_ {j}>=0 \sum_ {j=1}^ {J} \lambda_ {j}=1 ,如下不等式成立: \sum_ {j=1}^
凸函数 在微积分中我们学习过凸函数的定义,下面来回忆一下。在函数的定义域内,如果对于任意的x和y,以及实数0≤θ ≤1,都满足如下条件: ? 则函数为凸函数。这个不等式和凸集的定义类似。...对于多元函数,如果它是凸函数,则其Hessian矩阵为半正定矩阵。如果Hessian矩阵是正定的,则函数是严格凸函数。 Hessian矩阵是由多元函数的二阶偏导数组成的矩阵。...一个重要结论是凸函数的非负线性组合是凸函数,假设fi是凸函数,并且wi ≥0,则: ? 是凸函数。可以根据凸函数的定义进行证明,非常简单,读者可以自己实现。...下水平集 给定一个凸函数以及一个实数α,函数的α下水平集(sub-level set)定义为函数值小于等于α的点构成的集合: ? 根据凸函数的定义,很容易证明该集合是一个凸集。...其中是gi (x)不等式约束函数,为凸函数;hi (x)是等式约束函数,为仿射函数。上面的定义中不等式的方向非常重要,因为一个凸函数的0-下水平集是凸集。
,对数函数\(\log x\)是非凸函数 仿射函数(Affine function): \({a^T}x + b\)既是凸函数又是非凸函数 二次函数(Quadratic function): \(\frac...最大值函数(Max function): \(f(x) = max({x_1}, \ldots ,{x_n})\)为凸函数 凸函数的特性 上镜特性(Epigraph characterization):...函数f为凸函数当且仅当其上镜图\(epi(f) = \left\{ {(x,t) \in dom(f) \times R:f(x) \le t} \right\}\)为凸集,如下图: ?...逐点最大化 如果\({f_s}\)对于任意\(s \in S\)均为凸,那么\(f(x) = \max {f_s}(x),s \in S\)是凸函数。...部分最小化 如果\(g(x,y)\)在任意x,y处为凸函数,并且C是凸的,那么\(f(x) = \min g(x,y),y \in C\)为凸函数。
优化问题是机器学习的核心,而凸函数在优化中又起着重要的作用。...一个函数的 epigraph 凸函数(Convex Function) 好了,现在你们知道什么是凸集和 epigraph 了,我们可以讨论凸函数了。 ?...一个凸函数及其 epigraph 如果一个函数 f 的 epigraph 是凸集(如左下方绿色图所示)),则称该函数为凸函数。...如果函数 f 的二阶导数大于或等于0,则称该函数 f 为凸函数。 ? 凸函数的条件 凸函数的例子: y=eˣ, y=x²。这两个函数都是二次可微的。...MSE 方程 现在让我们考虑一个非凸的成本函数,在这种情况下,取一个任意的非凸函数,如下图所示。 ? 非凸函数的梯度下降法 你可以看到梯度下降法将停止在局部极小值,而不是收敛到全局极小值。
矩估计和最大似然估计 区间估计 Jacobi 矩阵 矩阵乘法 矩阵分解 RQ 和 SVD 对称矩阵 凸优化 微积分与梯度 常数 e 的计算过程 常见函数的导数 分部积分法及其应用 梯度 上升/下降最快方向 凸函数...凸函数与 Jsnsen 不等式 简而言之,即是函数的割线永远位于函数图像的上方. ?...一阶可微 简而言之,即是函数如果是一个凸函数,且一阶可微,则过函数任意一点做函数的切线,函数的切线永远在函数的下方. ? 二阶可微 ? 凸函数举例 ?...Jensen 不等式 Jensen 不等式相当于把凸函数的概念反过来说,即是如果 f 是一个凸函数,任意取一个在 f 定义域上的(x,y)点, 属于[0,1]....PS:这都是在 f 是凸函数的状况下! Jensen 不等式是所有不等式的基础,所有不等式都能看做是 Jensen 不等式利用不同的凸函数推导出来的. ?
我们知道,梯度下降法和牛顿法都是通过逼近的方式到达极值点,如何使损失函数的极值点成为它的最值点就是凸函数和凸优化关注的内容。 凸优化,即在一系列以凸函数为条件的限制下,求解目标凸函数的最小值。...即使目标函数本身是非凸函数,我们也可以使用一个凸函数去逼近它,以图寻找到一个最优的初始点来求解非凸函数的最小值问题。...对于凸函数,任意n个 ? 所对应 ? 构成的凸组合要大于等于 ? 本身凸组合 ? 所对应的 ? ,直观上的理解就是凸函数的上镜图肯定都位于凸函数上方,这就是Jesen不等式。...凸集合和凸函数有各种各样的性质,但这些性质都可由上镜图对应和联系起来。比如,任意多个凸集合的交集仍是凸集合,那么以这些凸集合为上镜图的凸函数逐点上确界仍是凸函数。...同时,凸函数向任意一个低维空间的投影也是一个凸函数,因为其投影的上镜图仍然是个凸集。
定义 凸优化问题(OPT,convex optimization problem)指定义在凸集中的凸函数最优化的问题。尽管凸优化的条件比较苛刻,但仍然在机器学习领域有十分广泛的应用。...凸函数 2.1定义: 定义在 ? 上的函数 ? 是凸函数,如果它的定义域 ? 是一个凸集且对任意的 ? 和 ? , ? 恒成立 2.2几何意义: ?...凸函数几何意义 2.3凸函数的一阶充要条件: 假设定义在 ? 上的函数 ? 可微(即对于所有 ? ,梯度 ? 均存在)。则函数 ? 是凸函数当且仅当函数定义域 ? 是一个凸集,且对于所有 ?...凸函数一阶充要条件的几何意义 2.4 凸函数的二阶充要条件: 记函数的一阶导数和二阶导数分别为 ? 和 ? : ? 假设定义在 ? 上的函数 ? 二阶可微(即对于所有 ?...是凸函数当且仅当函数定义域 ? 是一个凸集,且对于所有 ? 均满足: ? 注意:这里的 ? 表示的是半正定。 3.
要是一个土丘(凸函数)那没问题,如果要是连绵不断的群山(非凸函数),只能保证到达一个小山峰(极值),而这个不一定是所有山峰中最高的(最值)。...由于凸函数的极值点就是最值点,相对于非凸函数,我们更喜欢凸函数。这里不但要求目标函数是凸的,其定义的空间也必须是凸的集合。正如要求地形是凸的,能走的路构成的集合也必须是凸的。...凸凸凸,到底啥是凸集合,啥是凸函数??? 凸集合:满足集合内任意两点的连线也在这个集合里的就是凸集合。...凸函数:下面两个图画出了凸函数,也给出了凸函数的两个性质: 两点永远太高;如下面第一个图,用凸函数两点之间的连线上的一点R来估计函数值L,永远有R>L。...一点永远太低;如下面第二个图,用凸函数的切线上的一点R来估计函数值L,永远有R<L。
凸优化问题是指 是闭合的凸集且 是 上的凸函数的最优化问题,这两个条件任一不满足则该问题即为非凸的最优化问题。...Concave Function指凸函数。但在中国大陆涉及经济学的很多书中,凹凸性的提法和其他国家的提法是一致的,也就是和数学教材是反的。...为什么要求是凸函数呢?因为如果是下图这样的函数,则无法获得全局最优解。?为什么要求是凸集呢?因为如果可行域不是凸集,也会导致局部最优?...如果不是凸函数,则不是凸优化问题之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解,这个特性使凸优化问题在一定意义上更易于解决,而一般的非凸最优化问题相比之下更难解决。...非凸优化问题如何转化为凸优化问题的方法: 1)修改目标函数,使之转化为凸函数 2)抛弃一些约束条件,使新的可行域为凸集并且包含原可行域
所以上图不是凸函数,相反,它叫凹函数。凹凸函数定义如下图: 在2维空间内,凸函数类似于这样的二次函数 其中: 显然,实际问题若符合凸函数性质,往往方便求出其极小值。...而损失函数,如对数损失函数、平方损失函数,都是凸函数,探求凸函数的“谷底”,就是我们追求的目标。 但是机器学习处理的往往是高维数据,所以,将上述一元二次函数,扩展到多维空间的多元二次型。...标量x被向量X(x1,x2,x3....xn)替代,系数a被代替矩阵A,依然得到一个凸函数: 其中 即:A为正定矩阵(特征值全部大于0) 考虑多元二次型的实际意义,我们先从包含两个变量(x,y)的二次型出发...我们已经知道上述二次型符合凸函数性质,实际中凸函数的极值问题,往往是带约束的求极值问题,也就是说我们要在求极值的同时加上一个条件——凸优化问题 比如在X的2范式——X的长度——为1的情况下,求上述二次型的极值
”凸优化“ 是指一种比较特殊的优化,是指求取最小值的目标函数为凸函数的一类优化问题。其中,目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。...而目标函数和不等式约束函数均为凸函数,等式约束函数为仿射函数,并且定义域为凸集的优化问题为约束优化问题。
图3 误差函数的第一个模型 从上方的3D图来看,人们会本能地猜测该函数为凸函数。凸函数的优化(找到最小值)比一般数学优化简单得多,因为任何局部最小值都是整个凸函数的最小值。...(简单来讲,就是凸函数只有一个最小点,例如“U”的形状)由于凸函数的这种特性,通过简单求解如下的偏微分方程,便可得到使函数最小化的参数。 下面解下之前的例子吧。...该模型的可视化图像如下: 图5 误差函数的第二个模型 两个模型的形状看起来也很相似,仍然是凸函数。...误差函数的第二个模型也是凸函数,因此可通过与前一示例完全相同的过程找到最佳参数。 通过求解上面的等式,得到a = 61/618、b = 331/206。...上面2个模型非常简单,但一般而言,模型与其参数的线性假设,可保证RSS始终为凸函数。通过求解简单偏微分方程,得到最优参数,这就是线性假设至关重要的原因。
线性回归 线性回归预测函数: 逻辑回归预测函数: 线性回归损失函数: 逻辑回归损失函数: MSE直接应用到LR中会导致损失函数变成非凸函数,所以我们加入log让损失函数变成了凸函数...是收敛之后得到的结果 根据sigmoid曲线,h_{\theta}≥0时,置为1;否则置为0 1.1.1.1 决策边界 1.1.2 代价函数 当我们把线性回归的代价函数放到逻辑回归上使用时,会发现代价函数J由凸函数...(convex)变成了有很多局部最大值的非凸函数,导致寻找最小值变得困难,所有我们选择了另一种能使LR变成凸函数的代价函数。...而对数函数log的曲线,能让代价函数变为凸函数的方程吗?...分析 化简 得到如下结果,使用了==极大似然法==(能够在统计学中能为不同模型快速寻找参数),并且结果是凸函数 参数梯度下降: ==可以发现,求导后线性回归和逻辑回归的公式是一样的,但是他们的假设函数
凸函数 在前面,我们讲到,每一个机器学习模型都有一个目标函数,而学习的目标,就是最小化目标函数。是不是所有函数都能够在自变量取值范围内找到因变量最小值呢?显然不是。...不过我们要学习的几个经典机器学习模型的目标函数都有最小值,也就是我们常说的凸函数。...数学定义:某个向量空间的凸子集(区间)上的实值函数,如果在其定义域上的任意两点 ,有 f(tx + (1-t)y) <= tf(x) + (1-t)f(y),则称其为该区间上的凸函数。...如果自变量本身是二维的(二元函数),则凸函数在三维空间中的图象是这样的: ? 同样有个“弯儿”,只不过这个弯儿不再是一段曲线,而是成了一个碗状的曲面,“碗底儿”就是区域内的极值点。...什么是梯度下降法 既然已经知道了学习的目标就是最小化目标函数的取值,而目标函数又是凸函数,那么学习的目标自然转化成了寻找某个凸函数的最小值。 求凸函数的最小值最常用的一种方法,就是梯度下降法。
梯度下降只能优化凸函数或凸集的目标函数,这是一定要注意的,可以翻看所有使用梯度下降的机器学习算法,进一步体会验证。 如果目标函数不是凸函数,那么就不能使用梯度下降。...凸函数 凸函数的数学定义: ? 知道这些后,让我们回忆梯度下降的实施步骤。 ? ? ? 以上 J 就是逻辑回归的目标函数,求出对每一个参数的偏导并求反,此为梯度下降的方向: ?
领取专属 10元无门槛券
手把手带您无忧上云