基于Zhang-Hager线搜索的改进近似最优梯度法

李瑶　刘红卫　吕佳敏　游海龙

摘要： 提出一种改进的近似最优梯度法， 求解图划分问题中的无约束目标函数. 先用修正的BFGS更新公式及选取BB类步长的线性组合作为标量矩阵得到近似最优步长， 再引入参数对经典的Zhang-Hager线搜索形式进行改进， 构建算法框架并给出R线性收敛性证明. 实验结果表明， 改进算法提高了原算法的性能.

关键词： 修正的BFGS更新公式； 近似最优步长； Zhang-Hager线搜索； R线性收敛性； 图划分问题

中图分类号： O221.7文献标志码： A文章编号： 1671-5489（2024）02-0263-10

Improved Approximate Optimal Gradient Method Based on Zhang-Hager Line Search

LI Yao1， LIU Hongwei1， L Jiamin1， YOU Hailong2

（1. School of Mathematics and Statistics， Xidian University， Xian 710126， China;2. School of Microelectronics， Xidian University， Xian 710071， China）

Abstract： [HQK]We proposed an improved approximate optimal gradient method to solve the unconstrained objective function in the graph partition problem. We first used  the modified BFGS updating formula and selected the linear combination of BB class step sizes as scalar matrices to obtain  the approximate optimal step sizes， then we introduced parameters to improve the classical Zhang-Hager line search form， construced the algorithm framework  and gave the proof of R-linear convergence. The experimental results show that the improved algorithm improves the performance of the original algorithm.

Keywords： modified BFGS updating formula;  approximate optimal step size; Zhang-Hager line search; R-linear convergence; graph partition problem

3 数值实验

目前， 解决电路划分问题的一种有效策略是将超图转化为图模型， 再使用数学方法对其进行抽象. 王晓瑜等[19]对电路划分问题进行数学建模， 将其松驰为无约束优化问题， 并设计了求解图划分问题的启发式框架. IBM公司Austin实验室设计转换了ISPD98电路测试基准， 是目前公认的电路测试样例[20]. 本文在文献［19］算法框架的基础上， 将其中求解无约束优化问题的内点法替换为近似最优梯度法[19]以及本文改进的近似最优梯度法， 解决其图划分问题. 通过选取文献［20］的两组数据（每组18个电路划分问题）， 对比文献［9］中的近似最优梯度法和本文改进的近似最优梯度法的性能. 由于图多分问题是在图二分问题基础上多次迭代重复使用算法得出， 涉及随机数据的选取及调整策略， 故数据结果不具有说服力. 为此， 本文仅使用图二分问题进行对比实验， 但本文的改进算法也适用于图多分问题.

使用两组数据关于目标函数值、 迭代次数、 函数值计算次数、 算法运行时间对两种算法进行对比， 结果分别列于表1和表2. 选取初始点x0为圆上的均匀分布， 其他参数选取如下（其中共有参数选取策略相同）：

由表1和表2可见： 标***的电路划分问题改进算法的函数值和迭代次数均优于文献［9］算法的结果， 占问题总数的33.33%， 标**的电路划分问题改进算法的函数值结果优于文献［9］算法的结果， 占问题总数的25%； 此外由于本文在图划分问题中处理的是大规模问题， 故本文改进算法在函数值未改善的情况下减少了迭代次数， 也节省了总划分问题的运行时间， 用*标記这部分问题的结果， 其数量占问题总数的16.7%. 未标记的数据表示未改善的问题， 占问题总数的25%. 结合以上实验结果和数据分析可见， 本文改进的近似最优梯度法的效率总体优于文献［9］近似最优梯度法.

综上所述， 本文对近似最优梯度法进行了改进， 并将其应用于图划分问题中. 首先， 选取二次模型或锥模型对目标函数进行近似， 使用修正的BFGS更新公式更新Hesse矩阵的近似矩阵， 同时选取线性组合的形式作为标量矩阵， 分析得到了对应的近似最优步长； 其次， 提出了一种改进的ZH非单调线搜索， 结合得到的近似最优步长构建改进的近似最优梯度法； 再次， 对改进的近似最优梯度算法进行收敛性分析， 并给出了收敛性证明； 最后， 选取图划分问题的两组数据进行对比实验， 结果表明， 改进的近似最优梯度法的性能优于原近似最优梯度法.

参考文献

［1］CAUCHY A. Méthode Générale Pour la Résolution des Systéms Déquations Simultanées ［J］. Comptes Rendus， 1847， 25： 536-538.

［2］BARZILAI J， BORWEIN J M. Two-Point Step Size Gradient Methods ［J］. IMA J Numer Anal， 1988， 8（1）： 141-148.

［3］RAYDAN M. The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem ［J］. SIAM J Optimiz， 1997， 7（1）： 26-33.

［4］DAI Y H， LIAO L Z. R-Linear Convergence of the Barzilai and Borwein Gradient Method ［J］. IMA J Numer Anal， 2002， 22（1）： 1-10.

［5］DAI Y H， YUAN J Y， YUAN Y X. Modified Two-Point Stepsize Gradient Methods for Unconstrained Optimization ［J］. Comput Optim Appl， 2002， 22（1）： 103-109.

［6］XIAO Y H， WANG Q Y， WANG D. Notes on the Dai-Yuan-Yuan Modified Spectral Gradient Method ［J］. J Comput Appl Math， 2010， 234（10）： 2986-2992.

［7］BIGLARI F， SOLIMANPUR M. Scaling on the Spectral Gradient Method ［J］. J Optim Theory Appl， 2013， 158（2）： 626-635.

［8］MILADINOVI[KG-*4]C[DD（-1〗＇M， STANIMIROVI[KG-*4]C[DD（-1〗＇P， MILJKOVI[KG-*4]C[DD（-1〗＇ S. Scalar Correction Method for Solving Large Scale Unconstrained Minimization Problems ［J］. J Optim Theory Appl， 2011， 151（2）： 304-320.

［9］LIU Z X， LIU H W. An Efficient Gradient Method with Approximate Optimal Stepsize for Large-Scale Unconstrained Optimization ［J］. Numer Algor， 2018， 78（1）： 21-39.

［10］ZHANG H C， HAGER W W. A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization ［J］. SIAM J Optim， 2004， 14（4）： 1043-1056.

［11］LIU Z X， LIU H W， DONG X L. An Efficient Gradient Method with Approximate Optimal Stepsize for the Strictly Convex Quadratic Minimization Problem ［J］. Optimization， 2018， 67（3）： 427-440.

［12］ZHANG J Z， DENG N Y， CHEN L H. New Quasi-Newton Equation and Related Methods for Unconstrained Optimization ［J］. J Optimiz Theory Appl， 1999， 102（1）： 147-167.

［13］WEI Z X， LI G Y， QI L Q. New Quasi-Newton Methods for Unconstrained Optimization Problems ［J］. Appl Math Comput， 2006， 175（2）： 1156-1188.

［14］HELMBERG C， RENDL F， WEISMANTEL R. Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming ［C］//International Conference on Integer Programming and Combinatorial Optimization. Berlin： Springer， 1996： 175-189.

［15］WIEGELE A， ZHAO S D. SDP-Based Bounds for Graph Partition via Extended ADMM ［J］. Comp Optim Appl， 2022， 82（1）： 251-291.

［16］孫文瑜， 徐东. 解无约束最优化的基于锥模型的过滤集-信赖域方法 ［J］. 中国科学： 数学， 2012， 42（5）： 527-543. （SUN W Y， XU D. A Filter Trust-Region Method Based on Conic Model for Unconstrained Optimization ［J］. Scientia Sinica： Mathematica， 2012， 42（5）： 527-543.）

［17］LIU H W， LIU Z X， DONG X L. A New Adaptive Barzilai and Borwein Method for Unconstrained Optimization ［J］. Optim Lett， 2018， 12（4）： 845-873.

［18］LIU Z X， LIU H W. Several Efficient Gradient Methods with Approximate Optimal Stepsizes for Large Scale Unconstrained Optimization ［J］. J Comput Appl Math， 2018， 328： 400-413.

［19］王曉瑜， 刘红卫， 王婷， 等. 基于半定规划的多约束图划分问题 ［J］. 吉林大学学报（理学版）， 2023， 61（3）： 540-546. （WANG X Y， LIU H W， WANG T， et al. Multi-constraint Graph Partitioning Problem Based on Semidefinite Programming ［J］. Journal of Jilin University （Science Edition）， 2023， 61（3）： 540-546.）

［20］BUSTANY I， KAHNG A B， KOUTIS I， et al. SpecPart： A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement ［C］//Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design. New York： Association for Computing Machinery， 2022： 13-1-13-9.

（责任编辑： 李 琦）

收稿日期： 2023-07-06.

第一作者简介： 李 瑶（1997—）， 女， 汉族， 硕士研究生， 从事图划分问题的研究， E-mail： ly818400@163.com.

基金项目： 国家自然科学基金（批准号： 12261019）.