非光滑凸优化问题的一个非精确梯度镜面下降算法

本文提出一个求解非光滑凸优化问题非精确梯度镜面下降算法.该算法是Allen-Zhu2016年提出求解光滑凸优化问题梯度镜面下降算法的推广,而且该算法允许目标函数中光滑部分梯度计算和非光滑部分邻近算子计算都存在误差,并且在适当条件下分析了该算法函数值序列的O(1/(k²))收敛速度,这里k表示迭代数.最后关于Lasso问题和Logistic问题的数值结果表明该算法是有效的.     

一种推广的求解可分离凸优化问题的黄金比率邻近ADMM算法

ADMM算法是求解可分离凸优化问题的经典算法之一,但其无法保证原始迭代序列的收敛性且其子问题计算量很大.为了保证该算法所有迭代点列的全局收敛性及提高计算效率,采用凸组合技术的黄金比率邻近ADMM算法被提出,其中凸组合因子Ψ是关键参数.本文在黄金比率邻近ADMM算法的基础上,扩大了凸组合因子Ψ的取值范围,提出了收敛步长范围更广的推广黄金比率邻近ADMM算法.并在一定的假设下,证明了算法的全局收敛性及函数值残差和约束违反度在遍历意义下的O(1/N)次线性收敛速度.以及,当目标函数中任意一个函数强凸时,证明了算法在遍历意义下的O(1/N²)收敛率.最后,本文通过数值试验表明推广算法的有效性.     

凸集图像重建问题的加速下松弛平行投影算法

平行投影算法是求解凸集图像重建问题的常用工具之一,它包括迭代复杂度O (1/k)收敛性的上松弛和下松弛两种形式.本文受Nesterov加速方法的启发,首先针对凸集图像重建问题提出一种加速的下松弛并行投影算法,并在某些合适的条件下证明了其迭代复杂度O(1/k2)的收敛性.然后又提出了一种基于Arimijo技术的自适应加速...     

一个结构型凸优化问题的分裂算法

考虑带线性约束的三块变量的凸优化模型,目标函数是可分的三个函数和.给出了一个新的分裂算法.首先,对每个块变量解极小化增广拉格朗日函数.然后,通过一个校正步得到新的迭代点.证明了新算法的整体收敛性和O(1/t)的收敛阶.     

非凸多分块优化的Bregman ADMM的收敛率研究

Wang等提出了求解带线性约束的多块可分非凸优化问题的带Bregman距离的交替方向乘子法(Bregman ADMM),并证明了其收敛性.该文将进一步研究求解带线性约束的多块可分非凸优化问题的Bregman ADMM的收敛率,以及算法产生的迭代点列有界的充分条件.在效益函数的Kurdyka-Lojasiewicz (KL)性质下,该文建立了值和迭代的收敛速率,证明了与目标函数相关的各种KL指数值可获得Bregman ADMM的三种不同收敛速度.更确切地说,该文证明了如下结果:如果效益函数的KL指数θ=0,那么由Bregman ADMM生成的序列经过有限次迭代后收敛;如果θ∈(0,1/2],那么Bregman ADMM是线性收敛的;如果θ∈(1/2,1),那么Bregman ADMM是次线性收敛的.     

一种带有不定性邻近项的广义Peaceman-Rachford分裂法

针对带有线性约束的可分离凸优化问题,提出一种带有不定邻近项的广义Peaceman-Rachford (PR)分裂法.在较弱假设条件下,证明该算法迭代序列的全局收敛性和建立起在遍历情况下的最坏O(1/t)收敛速率.最后,通过数值实验验证了所提算法的有效性.     

求解凸规划及鞍点问题定制的PPA 算法及其收敛速率

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式. 在变分不等式框架下求解这些问题, 选取适当的矩阵G, 采用G- 模下的PPA 算法, 会使迭代过程中的子问题求解变得相当容易. 本文证明这类定制的PPA 算法的误差界有1/k 的收敛速率.     

基于全牛顿求解P*(κ)阵水平线性互补问题的内点算法

提出一种求解P_*(k)阵水平线性互补问题的全牛顿内点算法,全牛顿算法的优势在于每次迭代中不需要线性搜寻.当给定适当的中心路径邻域的阈值和更新势垒参数,证明算法中心邻域的全牛顿是局部二次收敛的,最后给出算法迭代复杂性O(√n)log(n+1+k)/εμ₀.     

一种新的求解线性方程组的外推加速方法

本文提出两种优化模型, 通过在子空间{x^(k),…, x^(k-m)}上寻找最优解, 建立了一种新的外推加速方法. 讨论了该方法的收敛性和收敛速度. 最后, 通过三个数值实例展示了算法是可行的和有效的.     

一类非光滑凸优化问题的邻近梯度算法

考虑求解目标函数为光滑损失函数与非光滑正则函数之和的凸优化问题的一种基于线搜索的邻近梯度算法及其收敛性分析,证明了在梯度局部Lipschitz连续条件下该算法是R-线性收敛的,并在非光滑部分为稀疏块LASSO正则函数情况下给出了误差界条件成立的证明,得到了线性收敛率.最后,数值实验结果验证了方法的有效性.     

一种连续的谱聚类优化模型

聚类与图的划分问题在大数据分析中有着重要的应用.这类问题一般被描述为组合优化问题,因此较难快速求解.本文设计了一种新的连续优化模型,并提出了一种块坐标下降算法,数值实验显示我们的新方法在求解聚类与图的划分问题上很有潜力.我们还更进一步分析了我们的连续优化模型和组合优化模型的关系.     

通信噪音条件下非光滑优化问题的分布式derivative-free方法（英文）

本文研究了时变有向图上的非光滑分布式优化.在这样的图中,网络拓扑不仅是强连通的,而且还存在通信噪音.每个节点只能访问其非平滑的局部成本函数.本文给出了一种derivative-free分布式方法来最小化该网络中所有节点的成本函数之和.然后建立了所提出方法的收敛性分析,并获得了收敛速度的显式复杂性界限.当每个局部成本函数都是凸的时,我们的分析表明,所提出的算法以■的速率收敛,收敛速率取决于噪声的上限、光滑参数以及网络信息传播速度和节点间不平衡影响.当每个局部成本函数fi是强凸时,我们得到了O(lnt/t)的更快的收敛速度.最后,用一个数值实验来展示所提出方法的收敛性.     

非光滑凸规划不可行拟牛顿束方法的收敛性分析

利用改进函数将非光滑凸约束优化问题转化成无约束优化问题,构造了一个具有迫近形式的不可行拟牛顿束算法.值得注意的是,随着每次迭代的进行,该算法的无约束优化子问题的目标函数可能发生改变(取零步目标函数不改变,取下降步则更新目标函数),为此必须做必要的调整以保证算法的收敛性.本文主要采用了Sagastizabal和So1odov的不可行束方法的思想,在每个迭代点不一定是原始可行的情况下,得出了算法产生序列的每一个聚点是原问题最优解的收敛性结果.进一步,本文针对目标函数强凸情况下的BFGS拟牛顿算法,得到了全局收敛结果中保证拟牛顿矩阵有界的条件以及迭代序列的R-线性收敛结果.     

一类凸优化的加速混合下降算法

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术,结合邻近点算法和近似邻近点算法的思想,构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想,利用已有近似规则信息改善了混合下降算法的下降方向,得到了一类凸优化问题的加速混合下降算法.随后利用Markov不等式、凸函数性质和投影的基本性质等,实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.     

推广AS-GN混合共轭梯度算法

本文提出了一种求解无约束优化问题的新算法,使Touati-Ahmed, Storey提出的混合共轭梯度法(以下简称AS)和Gilbert, Nocedal提出的混合共轭梯度法(以下简称GN)成为新算法在精确线性搜索下的特例.通过构造新的$\beta_{k}$计算公式,新算法自然满足下降性条件,且这个性质与线性搜索和目标函数的凸性均无关.在一般的条件下,我们证明了新算法的全局收敛性.数值结果表明该算法对测试函数是有效的.     

非凸优化带松弛步的对称ADMM局部线性收敛率分析

基于对称交替方向乘子法(ADMM),结合松弛步技巧,该文提出一种带松弛步的对称ADMM用于求解两分块线性约束非凸优化问题.同时,新算法乘子更新步采用不同的松弛因子.常规假设下,给出新算法子序列的收敛性证明.误差界条件下,分析并获得由新算法产生的迭代点列以线性收敛的速率局部趋于问题稳定点,相应增广拉格朗日函数序列亦线性收敛.最后,初步试验结果表明新算法是有效的.     

一道解析几何试题的多视角探析

<正>已知椭圆C:x²/a2/a²+y2+y²/b2/b²=1(a>b>0)的离心率为32=1(a>b>0)的离心率为3^(1/2)/2,一个顶点在抛物线:x(1/2)/2,一个顶点在抛物线:x²=4y的准线上.(Ⅰ)求椭圆C的方程;(Ⅱ)设O为坐标原点,M,N为椭圆上的两个不同的动点,直线OM,ON的斜率分别为k1和k2,当k1k2=-1/4时,探讨△MON的面积是否为定值,若为定值,求出该定值.若不为定值,说明理由.     

初中数学竞赛综合训练题(三)

一、选择题 1.任意调动五位数12345各数位上的数字位置,所得五位数中质数的个数是( )。 (A)6 (B)4 (C)2 (D)10 2.一次函数y=x/2 k的图象与x轴、y轴的交点是A、B,如果△AOB(O是坐标原点)有面积S≤1,那么k的范围是( )。     

求一类非凸规划问题全局解的确定性算法

本文对一类非凸规划问题(NP)给出一确定性全局优化算法.这类问题包括:在非凸的可行域上极小化有限个带指数的线性函数乘积的和与差,广义线性多乘积规划,多项式规划等.通过利用等价问题和线性化技巧提出的算法收敛到问题(NP)的全局极小.     

Banach空间中有限个增生算子公共零点的迭代强收敛定理

令E为实自反Banach空间具一致Gteaux可微范数,AiE×E(i=1,2,…,k)为增生算子且满足∩ki=1Ai-1(0)≠φ.令C为E的非空闭凸子集并满足■C∩r>0R(I+rAi),i=1,2,…,k.将引入一种带误差项的迭代算法,并证明迭代序列强收敛于{Ai}ki=1的公共零点.