李瑤　劉紅衛(wèi)　呂佳敏　游海龍

摘要： 提出一種改進的近似最優(yōu)梯度法， 求解圖劃分問題中的無約束目標函數(shù). 先用修正的BFGS更新公式及選取BB類步長的線性組合作為標量矩陣得到近似最優(yōu)步長， 再引入參數(shù)對經典的Zhang-Hager線搜索形式進行改進， 構建算法框架并給出R線性收斂性證明. 實驗結果表明， 改進算法提高了原算法的性能.

關鍵詞： 修正的BFGS更新公式； 近似最優(yōu)步長； 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 數(shù)值實驗

目前， 解決電路劃分問題的一種有效策略是將超圖轉化為圖模型， 再使用數(shù)學方法對其進行抽象. 王曉瑜等[19]對電路劃分問題進行數(shù)學建模， 將其松馳為無約束優(yōu)化問題， 并設計了求解圖劃分問題的啟發(fā)式框架. IBM公司Austin實驗室設計轉換了ISPD98電路測試基準， 是目前公認的電路測試樣例[20]. 本文在文獻［19］算法框架的基礎上， 將其中求解無約束優(yōu)化問題的內點法替換為近似最優(yōu)梯度法[19]以及本文改進的近似最優(yōu)梯度法， 解決其圖劃分問題. 通過選取文獻［20］的兩組數(shù)據(jù)（每組18個電路劃分問題）， 對比文獻［9］中的近似最優(yōu)梯度法和本文改進的近似最優(yōu)梯度法的性能. 由于圖多分問題是在圖二分問題基礎上多次迭代重復使用算法得出， 涉及隨機數(shù)據(jù)的選取及調整策略， 故數(shù)據(jù)結果不具有說服力. 為此， 本文僅使用圖二分問題進行對比實驗， 但本文的改進算法也適用于圖多分問題.

使用兩組數(shù)據(jù)關于目標函數(shù)值、 迭代次數(shù)、 函數(shù)值計算次數(shù)、 算法運行時間對兩種算法進行對比， 結果分別列于表1和表2. 選取初始點x0為圓上的均勻分布， 其他參數(shù)選取如下（其中共有參數(shù)選取策略相同）：

由表1和表2可見： 標***的電路劃分問題改進算法的函數(shù)值和迭代次數(shù)均優(yōu)于文獻［9］算法的結果， 占問題總數(shù)的33.33%， 標**的電路劃分問題改進算法的函數(shù)值結果優(yōu)于文獻［9］算法的結果， 占問題總數(shù)的25%； 此外由于本文在圖劃分問題中處理的是大規(guī)模問題， 故本文改進算法在函數(shù)值未改善的情況下減少了迭代次數(shù)， 也節(jié)省了總劃分問題的運行時間， 用*標記這部分問題的結果， 其數(shù)量占問題總數(shù)的16.7%. 未標記的數(shù)據(jù)表示未改善的問題， 占問題總數(shù)的25%. 結合以上實驗結果和數(shù)據(jù)分析可見， 本文改進的近似最優(yōu)梯度法的效率總體優(yōu)于文獻［9］近似最優(yōu)梯度法.

綜上所述， 本文對近似最優(yōu)梯度法進行了改進， 并將其應用于圖劃分問題中. 首先， 選取二次模型或錐模型對目標函數(shù)進行近似， 使用修正的BFGS更新公式更新Hesse矩陣的近似矩陣， 同時選取線性組合的形式作為標量矩陣， 分析得到了對應的近似最優(yōu)步長； 其次， 提出了一種改進的ZH非單調線搜索， 結合得到的近似最優(yōu)步長構建改進的近似最優(yōu)梯度法； 再次， 對改進的近似最優(yōu)梯度算法進行收斂性分析， 并給出了收斂性證明； 最后， 選取圖劃分問題的兩組數(shù)據(jù)進行對比實驗， 結果表明， 改進的近似最優(yōu)梯度法的性能優(yōu)于原近似最優(yōu)梯度法.

參考文獻

［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］孫文瑜， 徐東. 解無約束最優(yōu)化的基于錐模型的過濾集-信賴域方法 ［J］. 中國科學： 數(shù)學， 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］王曉瑜， 劉紅衛(wèi)， 王婷， 等. 基于半定規(guī)劃的多約束圖劃分問題 ［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）.