对于梯度下降等凸函数优化方法，我们都是给定一个初始点，然后每次计算当前点的梯度，然后沿着逆梯度方向去寻找最优点，所以最终找到的点都可以表示成初始点和一系列导数的线性组合，形式如下：
解的形式，x0为初始点
本节要证明的主要定理是：满足一阶利普希茨连续的凸函数，通过一阶方法进行优化，经过k（1<=k<=(n-1)/2）次迭代之后，误差的下界是：
误差下界
注意：因为要求的是下界，所以f(x)应该是最难解的函数，书中给出的f(x)二次函数族的形式是（为什么只考虑二次函数族，又为什么这种形式最难解？），这个证明实际上给出了这个二次函数族的下界：
f(x)的形式
这个函数可以构造出如下解：
构造解
将构造解带入方程可以得到方程的最优解：
方程最优解
固定某个k，假设我要求的是f2k+1(x)的最优解，则
第一个式子证明
第二个式子证明
对于梯度下降等凸函数优化方法，我们都是给定一个初始点，然后每次计算当前点的梯度，然后沿着逆梯度方向去寻找最优点，所...
了解机器学习的人应该都知道，在优化非凸函数的时候，希望用一个凸函数来代替这个非凸函数，以获取凸函数在优化过程中良好...
笔记主要内容 凸集、凸函数、凸优化 凸优化理论 若干算法
写在前头 凸优化问题（OPT，convex optimization problem）指定义在凸集中的凸函数最优化...
概述 凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化...
〇、说明 凸优化主要学习《凸优化》(Stephen Boyd等著，王书宁等译)[1]这本书。学习过程中，对其内容的...
期望值最大化 背景图：要解决凸函数空间上的（比如抛物线就是一个凸函数，如图所示）一个最优化问题［说明：机器学习，各...
凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义...
凸优化是很多机器学习算法的基础，绝大部分的优化算法都是适用在凸函数上的。18年的京东算法岗考的基本都是凸优化的基本...
算法复杂度分析中的符号（Θ、Ο、ο、Ω、ω）简介Θ，读音：theta、西塔；既是上界也是下界(tight)，等于的...
本文标题：凸函数一阶优化的复杂度下界
本文链接：https://www.haomeiwen.com/subject/pfstkftx.html
网友评论