一种求解大规模非光滑优化问题的共轭梯度法

针对大规模非光滑优化问题,利用Moreau-Yosida正则化技术和Armijo-type线搜索技术,设计了一种修正LS共轭梯度算法.算法的搜索方向不仅满足充分下降条件,而且具有信赖域性质.可以证明新算法在适当条件下全局收敛.初步的数值实验表明,新算法在求解大规模非光滑无约束凸优化问题方面比LMBM方法和MPRP方法更有效.

一种非精确非光滑信赖域算法

Aravkin等人提出了求解非光滑优化问题min_(x∈R^(d))f(x)+h(x)的非光滑信赖域算法(采用f的精确梯度),其中f是连续可微函数,h是邻近有界且下半连续的真函数。文章研究当该问题中f:=1/n ∑_(i=1)^(n)f_(i)(n很大且每个分量函数fi是连续可微)时,求解这类大规模可分离非光滑优化问题的有效算法。结合非精确算法和非光滑信赖域算法的思想,提出了用非精确梯度代替精确梯度的非精确非光滑信赖域算法。与非光滑信赖域算法(采用精确梯度)相比,该算法降低了每次迭代的计算量。在一定的假设条件下,证明了算法的迭代复杂度。

一种基于共轭次梯度算法的非光滑布图规划方法

针对只有硬模块的布图规划问题,通常将其构建成组合优化模型,但求解过程时间成本高。为提高求解效率,提出了一种基于非光滑解析数学规划的布图规划算法。基于布图中器件的坐标表示,构建了一个泛化的非光滑解析数学规划模型,将不同场景下的布图规划问题的不同优化阶段处理为该泛化模型的特例,并利用共轭次梯度算法(conjugate sub-gradient algorithm,CSA)对其进行求解。针对固定轮廓布图规划问题,通过统一框架下的全局布图规划、合法化、局部优化三个阶段,实现了在固定轮廓约束下的线长优化。针对无固定轮廓约束问题,提出了带黄金分割策略的共轭次梯度算法(conjugate sub-gradient algorithm with golden section strategy,CSA_GSS),利用黄金分割策略缩小固定轮廓的面积,达到面积和线长双优化的效果。实验在GSRC测试电路上与基于B*-树表示的布图规划算法进行比较,该算法对于大规模电路在线长和时间方面均占据优势。实验结果表明,该算法能以更低的时间复杂度获得更优的线长。

非凸非光滑不可分离优化的线性对称邻近ADMM收敛性分析

交替方向乘子法(ADMM)是一种求解可分离优化问题的简单有效的方法,相关研究已经较为完善.然而,当目标函数存在耦合项时,对ADMM算法收敛性的研究还处于初期.文章针对非凸非光滑不可分离优化问题,基于对称交替方向乘子法(SADMM),结合线性化技术,提出了一种新的线性对称邻近ADMM.在一定的假设条件下,证明了算法生成的序列有界并收敛至增广拉格朗日函数的稳定点.其次,当辅助函数满足Kurdyka-Lojasiewicz性质时,证明了算法的强收敛性.最后,数值实验的结果表明了算法的有效性.

求解大规模非光滑问题的一种修正DY共轭梯度算法

设计了一种针对大规模非光滑优化问题的修正DY共轭梯度算法.新算法的搜索方向不仅自动满足充分下降条件,而且属于信赖域.新算法在适当条件下全局收敛.初步的数值实验显示,新算法能够求解高达50 000维的非光滑凸和非凸优化问题,表明其在求解大规模非光滑无约束凸优化问题方面是有效的.

求解非光滑优化问题的一种修正FR共轭梯度算法

为了提高求解大规模非光滑问题的效率,设计一种求解非光滑优化问题的修正的Fletcher-Reeves三项非线性共轭梯度算法.该算法使用一种新的搜索方向.并利用Moreau-Yosida正则化技术和Armijo-type线搜索技术进行设计.新算法具有以下特点:一是搜索方向自动满足充分下降条件,二是算法的搜索方向具有信赖域性质;三是在适当条件下,证明了新算法全局收敛.初步的数值实验也表明新算法在求解大规模非光滑优化问题方面比传统LMBM算法更有竞争力.因此新算法能够更加高效地求解大规模非光滑优化问题.