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

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

基于DC分解的非凸二次规划SDP近似解

本文提出一类基于DC分解的非凸二次规划问题SDP松弛方法,并通过求解一个二阶锥问题得到原问题的近似最优解.我们首先对非凸二次目标函数进行DC分解,然后利用线性下逼近得到一个凸二次松弛问题,而最优的DC分解可通过求解一个SDP问题得到.数值试验表明,基于DC分解的SDP近似解平均优于经典SDP松弛和随机化方法产生的近似解。     

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

邻近点算法(PPA)是一类求解凸优化问题的经典算法, 但往往需要精确求解隐式子问题,于是近似邻近点算法(APPA)在满足一定的近似规则下非精确求解PPA的子问题, 降低了求解难度. 本文利用近似规则的历史信息和随机数扩张预测校正步产生了两个方向, 通过随机数组合两个方向获得了一类凸优化的混合下降算法.在近似规则满足的情况下, 给出了混合下降算法的收敛性证明. 一系列的数值试验表明了混合下降算法的有效性和效率性.     

一类DC规划问题的分支定界算法

本文针对一类带有箱子和线性不等式约束的特殊DC规划问题,提出了一种分支定界算法.首先将原问题转化为其等价问题,然后利用目标函数的特点将等价问题松弛为凸规划问题,通过求解一系列凸规划问题得到原问题的最优解,最后给出算法的收敛性证明.数值实验表明该算法是可行有效的.     

存零约束优化问题的序列二次方法北大核心CSCD

存零约束优化(MPSC)问题是近年来提出的一类新的优化问题,因存零约束的存在,使得常用的约束规范不满足,以至于现有算法的收敛性结果大多不能直接应用于该问题.应用序列二次规划(SQP)方法求解该问题,并证明在存零约束的线性独立约束规范下,子问题解序列的聚点为原问题的Karush-Kuhn-Tucker点.同时为了完善各稳定点之间的关系,证明了强平稳点与KKT点的等价性.最后数值结果表明,序列二次规划方法处理这类问题是可行的.     

线性等式与不等式组稀疏解的唯一性条件

近年来,稀疏优化广泛应用在信号处理、机器学习、图像去噪和计算机视觉等方面,得到了深入的研究和快速的发展.本文考虑含有一般线性等式和不等式约束的广义l_(0-)最小化问题.尽管l_(0-)最小化问题是NP-困难的,但已有多种计算方法可以用来克服这一计算上的困难,其中一种常用的方法是,通过一个凸优化问题来近似求解原问题.具体地,用l_(1-)范数代替l_(0-)范数得到l_(0-)最小化问题的一个凸松弛.在这类方法中,研究什么条件可以保证两个问题等价是非常重要的.基于值域空间性质(RSP)的分析方法,本文提出广义l_(0-)最小化问题的RSP性质,并且证明在某些条件下,RSP性质可以保证l_(0-)最小化问题与它的凸松弛l_(1-)最小化问题是等价的.最后,本文对所使用的条件给出一些说明.     

非凸约束优化的随机近似算法

在人工智能、科学计算等领域,众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂,同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来,结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类:基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结,简要地介绍相关算法的设计思想和基本的理论性质,如渐近收敛性理论、复杂度理论等。     

求解互补约束优化问题的乘子松弛法

利用互补问题的Lagrange函数, 给出了互补约束优化问题\,(MPCC)\,的一种新松弛问题. 在较弱的条件下, 新松弛问题满足线性独立约束规范. 在此基础上, 提出了求解互补约束优化问题的乘子松弛法. 在MPCC-LICQ条件下, 松弛问题稳定点的任何聚点都是MPCC的M-稳定点. 无需二阶必要条件, 只在ULSC条件下, 就可保证聚点是MPCC的B-稳定点. 另外, 给出了算法收敛于B-稳定点的新条件.     

不等式约束优化基于新型积极识别集的SQCQP算法

本文提出一个新的求解非线性不等式约束优化问题的罚函数型序列二次约束二次规划(SQCQP)算法.算法每次迭代只需求解一个凸二次约束二次规划(QCQP)子问题,且通过引入新型积极识别集技术,QCQP子问题的规模显著减小,从而降低计算成本.在不需要函数凸性等较弱假设下,算法具有全局收敛性.初步的数值试验表明算法是稳定有效的.     

带阀点效应水火联合调度问题的一种半定凸松弛求解法

水火联合调度问题是电力系统中一类复杂的优化问题。合理安排调度周期内的水火电出力,确定一个最优发电计划,可以带来巨大的经济效益。在实际系统中,汽轮机调汽阀开启时出现的拔丝现象会使机组耗量特性产生阀点效应。忽略阀点效应,在一定程度上降低求解的精度。本文考虑带阀点效应的水火联合调度问题。该问题非凸非光滑,且带有非线性约束,直接使用确定性全局优化方法求解是相当困难的。本文使用高效的半定规划求解此问题。首先用耗量特性函数的初始周期代替其余有限的周期,并对其进行二次拉格朗日插值拟合。再通过引进0-1变量,得到整个耗量特性函数的近似,进而把问题松弛为半定规划模型。最后,采用凸规划应用软件包CVX求解一个仿真算例,得到一个近似全局最优解。     

动力下降制导问题的两阶段序列凸化方法

可重复使用火箭技术是近五年来航天工程领域的焦点话题.以三自由度燃料最优控制问题为具体模型,本文研究火箭回收中的关键问题—动力下降制导问题的求解.由于此模型中包含非凸动力学约束(带空气阻力项)、非凸推力大小和方向控制约束等,直接求解方法难以满足工程上实时性的需求.为了消除非凸性带来的困难,本文通过无损凸化、时间离散化和线性化技术将问题转化为一类凸规化问题,即二阶锥规划问题进行求解.此外,为了避免传统的序列凸化策略在求解本文模型时的数值不稳定现象,本文提出一个新的两阶段序列凸化方法.数值结果表明所提方法仅需求解少量的凸规化问题,且拥有比单阶段方法更稳定和高效的数值表现.     

鲁棒凸优化问题拟近似解的刻划

本文研究鲁棒凸优化问题拟近似解的最优性条件和对偶理论.首先利用鲁棒优化方法,在由约束函数的共轭函数的上图给出的闭凸锥约束规格条件下,建立了拟近似解的最优性充要条件.其次给出了鲁棒凸优化问题拟近似解在Wolf型和Mond-weir型对偶模型下的强(弱)对偶定理.最后给出具体实例验证了本文获得的结果.     

基于并行计算的多方向强次可行模松弛SQP算法

本文研究求解非线性约束优化问题.利用多方向并行方法,提出了一个新的强次可行模松弛序列二次规划(SQP)算法.数值试验表明,迭代次数和计算时间少于只取单一参数的传统算法.     

复合凸优化的快速邻近点算法

在大数据时代,随着数据采集手段的不断提升,大规模复合凸优化问题大量的出现在包括统计数据分析,机器与统计学习以及信号与图像处理等应用中.本文针对大规模复合凸优化问题介绍了一类快速邻近点算法.在易计算的近似准则和较弱的平稳性条件下,本文给出了该算法的全局收敛与局部渐近超线性收敛结果.同时,我们设计了基于对偶原理的半光滑牛顿法来高效稳定求解邻近点算法所涉及的重要子问题.最后,本文还讨论了如何通过深入挖掘并利用复合凸优化问题中由非光滑正则函数所诱导的非光滑二阶信息来极大减少半光滑牛顿算法中求解牛顿线性系统所需的工作量,从而进一步加速邻近点算法.     

二次比式和问题的加速分枝定界算法

本文给出非凸二次约束上二次比式和问题(P)的一个新的加速分枝定界算法.该算法利用线性化技术建立了问题(P)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列线性规划问题,不断更新(P)的全局最优值的上下界.为了提高收敛速度,从最优性和可行性两方面,提出了新的删除技术,理论上证明该算法是收敛的,数值试验表明了算法的有效性和可行性.     

并行技术在约束凸规划化问题的对偶算法中的应用

用 Rosen(196 1)的投影梯度的方法求解约束凸规划化问题的对偶问题 ,在计算投影梯度方向时 ,涉及求关于原始变量的最小化问题的最优解 .我们用并行梯度分布算法 (PGD)计算出这一极小化问题的近似解 ,证明近似解可以达到任何给定的精度 ,并说明当精度选取合适时 ,Rosen方法仍然是收敛的     

凸可行问题的平行近似次梯度投影算法

对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点． 上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收 敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.     

不等式约束优化的一个超线性收敛FSSLE算法

本文针对不等式约束优化问题,提出了一个可行序列线性方程组(FSSLE)算法.该算法每次迭代只需求解四个具有相同系数矩阵的线性方程组,因而计算量较小.在没有假设算法产生的聚点是孤立点和近似乘子列有界的条件下,证明了算法具有全局收敛性.在一般条件下,证明了算法具有超线性收敛性.     

一般单调变分不等式的近似邻近外梯度算法

近似邻近点算法是求解单调变分不等式的一个有效方法,该算法通过解决一系列强单调子问题,产生近似邻近点序列来逼近变分不等式的解,而外梯度算法则通过每次迭代中增加一个投影来克服一般投影算法限制太强的缺点,但它们均未能改变迭代步骤中不规则闭凸区域上投影难计算的问题.于是,本文结合外梯度算法的迭代格式,构造包含原投影区域的半空间,将投影建立在半空间上,简化了投影的求解过程,并对新的邻近点序列作相应限制,使得改进的算法具有较好的收敛性.     

随机二阶锥二次规划逆问题的SAA方法

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。