当前位置：文档之家 › 无约束优化的一个充分下降共轭梯度算法

无约束优化的一个充分下降共轭梯度算法

  • 格式：pdf
  • 大小：210.51 KB
  • 文档页数：4

第２８卷　２　Ｏ　１　１　第２期　年６月　经　济　数　学　ｊｏＵＲＮＡＬ（）Ｆ　ＱＵＡＮＴＩＴＡＴＩＶＥ　ＥＣ（）Ｎ０ＭＩＣＳ　Ｖｏ１．２８，Ｎｏ．２　Ｊｕｎ．２　０　１　１　

无约束优化的一个充分下降共轭梯度算法　

黄　海　

（广西民族师范学院数学与计算机科学系，广西崇左５３２２００）　

摘　要　在修正ＰＲＰ共轭梯度法的基础上，提出了求解无约束优化问题的一个充分下降共轭梯度算　法，证明了算法在Ｗｏｌｆｅ线搜索下全局收敛．并用数值实验表明该算法具有较好的数值结果．　关键词　无约束优化；共轭梯度法；Ｗｏｌｆｅ线搜索；充分下降性；全局收敛性　中图分类号０２２４　文献标识码Ａ　

Ａ　Ｓｕｆｆｉｃｉｅｎｔ　Ｄｅｓｃｅｎｔ　Ｃｏｎｊ　ｕｇａｔｅ　Ｇｒａｄｉｅｎｔ　Ａｌｇｏｒｉｔｈｍ　

ｆｏｒ　Ｕ　‘　ｄ　ＯｐｔｉｍｉｚａｔｉｏｎＵ　ｎｃｏｎｓｔｒａｉｎｅ　ｄ　

ＨＵＡＮＧ　Ｈａｉ　

（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｇｕａｎｇｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｃｈｏｎｇｚｕｏ。Ｇｕａｎｇｘｉ　５３２２００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ａ　ｓｕｆｆｉｃｉｅｎｔ　ｄｅｓｃｅｎｔ　ｃｏｎｊ　ｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｕｎｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ　ｏｎ　ｔｈｅ　ｂａｓｉｓ　ｏｆ　

ｍｏｄｉｆｉｅｄ　ＰＲＰ　ｃｏｎｊｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ｍｅｔｈｏｄ．Ｉｔ　ｉｓ　ｐｒｏｖｅｄ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｇｌｏｂａｌｌｙ　ｃｏｎｖｅｒｇｅｎｔ　ｗｉｔｈ　ｔｈｅ　Ｗｏｌｆｅ　ｌｉｎｅ　ｓｅａｒｃｈ　ｃｏｎ—　ｄｉｔｉｏｎｓ．Ｔｈｅ　ｎｕｍｅｒｉｃａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｅｆｆｉｃｉｅｎｔ．　

Ｋｅｙｗｏｒｄｓ　ｕｎｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｃｏｎｊ　ｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ｍｅｔｈｏｄ；Ｗｏｌｆｅ　ｌｉｎｅ　ｓｅａｒｃｈ；Ｓｕｆｆｉｃｉｅｎｔ　ｄｅｓｃｅｎｔ　ｐｒｏｐｅｒｔｙ；　

ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　

引　言　

共轭梯度法具有迭代简单、存储需求少等特点，　

是大型无约束优化问题的有效计算方法之一，被广　

泛应用于科学、工程、经济和社会系统等许多领域．　

本文研究用共轭梯度法求解无约束优化问题　

｛　（　）Ｉ　Ｘ∈Ｒ”｝，其中ｘ为决策变量，厂：　

Ｒ　一Ｒ为连续可微的目标函数，＿厂（　）的梯度　

Ｖｆ（ｘ）记为ｇ（　），＾表示ｆ（ｘ　），ｇ　表示ｇ（：　）．　

共轭梯度法的迭代格式为　

Ｘｋ＋１一ｘ　＋ａ＋ｄ＾，　（１）　Ｉ～ｇ　，　ｋ一１，　ｄ　：＝＝　（２）　Ｉ—ｇ　＋　ｄｋ－・，ｋ≥２．　

其中，ｄ　为搜索方向，ａ　为由线搜索产生的步长因　

子，　为标量参数．不同的参数　对应不同的共轭　

梯度法，关于　的著名公式有多种Ⅲ，本文关注其　

中的两个公式　

一　一　，　

它们对应的共轭梯度法分别称为ＦＲ方法和ＰＲＰ　

方法．　

＊　收稿日期：２０１０—１２－２７　基金项目：广西壮族自治区教育厅科研项目（２０１０１２ＭＳ２１５），广西民族师范学院科研项目（２００９０９）　作者简介：黄海（１９６９一），男，广西武鸣人，副教授．　Ｅ—ｍａｉｌ：ｈｕａｎｇｈａｉ

ｓｈ＠１６３．ｃｏｍ　一２６一　经济数学　第２８卷　

Ａｌ—Ｂａａｌｉ［２　证明了ＦＲ方法在强ｗｏ１ｆｅ线搜索　

下具有全局收敛性，然而ＦＲ方法的数值结果较差．　虽然ＰＲＰ方法被认为是数值结果最好的共轭梯度　

法之一，但如Ｐｏｗｅｌｌ【３　指出的，原始ＰＲＰ方法对一　

般目标函数不能建立其收敛性，Ｇｉｌｂｅｒｔ和Ｎｏｃｅｄ—　

ａｌⅢ对　取值非负的情形（　＝ｍａｘ｛０，　）），　建立了ＰＲＰ　方法的全局收敛性．为了得到不但收　

敛性好而且数值结果优秀的共轭梯度法，人们在经　典共轭梯度法的基础上提出各种　的改进方　

案　］，文献［５］提出基于ＦＲ方法的修正参数　

一　，　＞０，　＞　・　ＩＩ　ｌ　ＩＩ。＋　ｌ　ｇ丁ｄ　１　Ｉ　”　一一　‘　

文献［６３提出基于ＰＲＰ方法的修正参数：　

ｆ　，　ｌ　ｚ≥　ｌ　＝｛ｌｌ　ｇ卜　ｌｌ。＋　ｌ　ｇ［ｄ卜　ｌ’”　“　。，　

１　０，　其他，　

（３）　＞１．文献［９３提出基于ＰＲＰ方法的参数修正方　

案：　一ｍａｘ｛０，　），　

其中，　一　，　＞。．　

这些相应的修正方法均具有　≥０的特点，具　有全局收敛性，且取得较好的数值结果．　共轭梯度法的迭代计算过程保持目标函数的充　

分下降对收敛性有着很重要的作用，要求的充分下　

降条件为：　ｇＴｄ　≤一Ｃ　ｌ】ｇ　Ｉｌ。，Ｃ＞０．　（４）　

共轭梯度法步长搜索常用的Ｗｏｌｆｅ线搜索条件为：　

ｆｆ（ｘｋ＋ａｋｄ　）一ｆ（ｘ　）≤堙　＾，　…　１　

ｌ　ｇ（　＾十ａｋｄ＾）Ｉ　ｄ　≥　ｄ　．　

其中，　∈（ｏ，÷），　∈（　，１）．式（５）中第二个式子　

改成Ｉ　ｇ（‰）＋ａｋｄ　）　ｄ　ｌ≤一　＾，即为强Ｗｏｌｆｅ　

线搜索条件．　

本文在文献［６］提出的修正ＰＲＰ方法基础上，　

允许　取负值，扩大参数的取值范围，考虑采用　

Ｗｏｌｆｅ线搜索，提出改进的算法，并分析了算法的全　

局收敛性，比较算法的数值表现．　

２算法及假设　

由式（３）可看出文献［６］中的参数０≤　≤　，　

下面改进使得～　≤　≤　，提出求解无约束问　

题的新共轭梯度算法描述：　算法１　

步骤１　给定ｚ　∈Ｒ　，　∈（ｏ，＿去＿），口∈（　，１），　

ｅ≥０，ｄ　＝＝＝～ｇ　，是：一１．若ｌｌ　ｇ　ＩＩ≤￡，停止．　

步骤２　计算满足ｗｏｌｆｅ线搜索条件（５）的步　

长ａ　．　

步骤３　计算　抖ｌ：一　＋ａｋｄ＾，ｇ胂１：一　

ｇ（　抖　）．若ｌＩ　ｇ外　ＩＩ≤ｅ，停止．　

步骤４　由式（２）计算搜索方向ｄ　，其中参数　

为：若２　ｌｌ　ｇ　ｌＩ　≥Ｉ　ｇ　ｌ，　

一—ｉｎａｘ　厨　，　＞。；｛ＩＩ　ｇ卜。１Ｉ。，　ｌ　。Ｉ｝＋Ｉ　ｇ丁ｄ　，ｌ’Ｐ　’　

（６）　

否贝０，　一ｏ．　

步骤５　忌：一忌＋１，转步骤２．　

根据算法１的步骤４，对任意给定的　＞０，由　

式（６）易得如下关系．　

引理１算法１中　满足　

一　≤　≤　．　（７）　

为了分析算法的收敛性，下面给出一般共轭梯　

度法收敛性分析中常用的基本假设条件：　

假设　（ｉ）目标函数，（　）在水平集Ｑ一（ｚ∈　

Ｒ”ｌ厂（ｚ）≤ｆ（ｘ　））内有下界．　

（ｉｉ）在水平集Ｑ内，目标函　连续可微且其导函　

数ｇ满足Ｌｉｐｓｃｈｉｔｚ条件，即存在常数Ｌ＞０，使得　

ｌ】ｇ（　）～ｇ（　）ｌｌ≤Ｌ　ｌｌ　—Ｙ　ＩＩ，Ｖ　，Ｙ∈Ｑ．　

３全局收敛性　

下面的定理说明算法１满足充分下降条件（４）．　

定理１　考虑算法１生成的序列｛ｇ　）和　

（ｄ　），则　

Ｃｚ　ＩＩ　ｇ　ｌｌ　≤ｇ　≤一Ｃ　ｇ　ＩＩ　，Ｖ是≥１．　

（８）　

其中，ｃｌ一　∈（０，１），ｃ２＝　ｚ－ｔ．－／￣∈（１，２）．　１　１－　１　１－　证明　（ａ）点一１时，ｄ　一一ｇ　，有ｇ　一　

一ｌｌ　ｇ　ＩＩ　，显然满足式（８）．　

（ｂ）是＞１时，由（２）可得ｇ丁ｄ　＝一ｌＪ　ｇ　Ｉｌ。＋　

ｇ　扣　，分两种情形来讨论：　

若　Ｔｄ｝一　一０，显然ｇｉｒｌ　：＝＝一［１　ｇ　ＩＩ　，式（８）　满足．　

若ｇ　≠０，由式（６）可得Ｉ　ｌ≤　

，

从而可得　第２期　黄海：无约束优化的一个充分下降共轭梯度算法　一２７一一　

ｇ　≤～Ｊ　Ｊ　ｇ　ＪＩ。＋ｊ　Ｉｌ　ｇｒｄｖ＿　Ｊ　

１　≤～（１一『÷．）ＩＩ　ｇ　１ｌ。一一ｃ　ＩＩ　ｇ　ＩＩ　，　上一Ｉ“　ｇ　ｄ　≥～Ｉｌ　ｇ　一Ｉ　ｌＩ　ｇ　ｄ　ｌ　

１　≥一（１十专）Ｉ｛ｇ　ｌ１。一一ｃ。ｆｆ　ｇ　『Ｉ。．　』—广　即ｋ＞１时，式（８）满足．综上即知定理成立．　

证毕　根据定理１及文献Ｅ１］的引理１．４．１，易得算法　

Ｉ满足Ｚｏｕｔｅｎｄｉｊｋ条件．　引理２假设（ｉ），（ｉｉ）成立．考虑算法１生成的　

序列｛ｇ　）和　

∑　≥１　ｇ　ｄ　），则　

２　＜＋ｏＯ．　（９）　

定理２假设（ｉ），（ｉｉ）成立．考虑算法产生序列　

｛ｇ　），则　

ｌｉｍ　ｉｎｆ［Ｉ　ｇ女Ｉｆ一０．　１＝ｌＯ）　

证明　采用反证法，若式（１Ｏ）不成立，必：　在　

常数’，＞ｏ，使得　Ｉ１　ｇ　ｌ＿≥），，Ｖ　ｋ≥１．　（１１）　

由式（２）可得　ｌＩ　ｄ　ＩＩ。＝ＩＩ　ｌＩ。＋２ｇ［ｄ　十　

ｆｆ　ｄ　，进而由式（７）和式（８），得到　

１Ｉ　ｄ　１ｌ。一　ｌｌ　ｄ卜　ｌｌ　一ｌｌ　ｇ　ｌｌ　一２ｇ　ｄ　

≤（　）　ＩＩ　ＩＩ　一Ｊｌ　ＩＩ。十２　ＩＪ　Ｉ　Ｊ　

［　＋击（ｚ　

ｇ≤　≤　，ｌｆ　｝ｌ　ｇ　一。　’　

其中，ｆ３一ｍａｘ｛　（２ｃｚ～１）｝＞　１＞ｏ．　

由上式可得　

≥　０３　ｋ　￣＞ｌ丢一　

这与式（９）产生矛盾．从而定理成立．　

｛　

４数值实验　表１数值实验结果　

ＲＯｓＥ　ＦＲＯＴＨ　ＢＡＤＳＣＰ　ＢＡＤＳＣＢ　ＢＥＡＬＥ　ＪＥＮＳＡＭ　ＨＥＬＩＸ　ＢＡＲＤ　ＧＡＵＳＳ　ＭＥＹＥＲ　ＧＵＬＦ　ＢＯＸ　ＳＩＮＧ　Ｗ０ＯＤ　ＫＯＷ０ＳＢ　ＢＤ　ＯＳＢ１　ＢＩＧＧＳ　ＯＳＢ２　ＯＳＢ３　ＲＯＳＥＸ　

ＳｒＮＧＸ　ＰＥＮ１　ＰＥＮ２　

Ｃ２～１）］．　ＶＡＲＤ　Ｍ　

在这一部分中，测试算法１的数值表现，并与　

ＰＲＰ方法及文献Ｅ６］方法进行比较，数值实验结果　

如表１，计算效能比较结果见表２．所用的算例来自　

文献［１Ｏ］，数学软件为Ｍａｔｌａｂ７．３，运行环境为　

１．６０ＧＨｚ　ＣＰＵ，１Ｇ　ＲＡＭ，Ｗｉｎｄｏｗｓ　ＸＰ系统，算法　

线搜索参数　一０．０１，　一０．１，精度参数ｅ＝＝１０　

．表中相关的符号表示为：　ＴＲ１Ｇ　

ＢＶ　

ＴＲＩＤ　

ＢＡＮＤ　

ＬＩＮ　

ＬＩＮ１　

ＬＩＮＯ　２９／５０２／６５　１２／３０／２０　

ｌ３／８０／２２　９／１ｚ６／ｚｌ　

４９／２５５／８３　２３／９８／３７　４／５７／６　

１／２／２　

２５６／８０９／４２２　２３２／ｉ４１３／４１４　５６／３９８／９３　２９／３９９／４９　１８／８５／２４　２７／１３ｌ／５７　２０／１３５／２９　１　７／４１／２８　１８／７８／Ｉ９　４ｌ／ｌ２９／５７　２４／１００／３６　３　

１／２／２　

７２／２４５／１　１０　２０／３８６／３０　８２／２０８／１２２　３１／３６０／５８　１　４／３２／２２　３０／１２８／５５　１４／１２５／２１　１　７／８６／２７　ｌ　ｌ／２８／１８　７３／１８ｉ／１０７　３５／６５／５０　３／７／４　

１／２／２　

６４／２３８／１０８　１７／３３３／２７　５４／１５６／８１　３０／１１２／４６　

１５６／６１４／２５８　１４３／３２０／２０９　１２９／４９９／１９７　２４０／１２２７／３９４　５６５／１　５７７／７７０　３９６／１Ｏ１１／５４３　２４６３／７２３６／３９４５ｌ１５１／２４７６／１　７１１１　７０２／３７ｌ５／２５１７　２３／４０２／５９　２７／２１９／５７　３１／１７８／５０　３１／５３３／７８　２８／２２３／５５　３０／１７５／５７　２５／２８３／６９　２７／１７４／５７　３０／１２７／５７　１０７／５７１／１８３　８Ｚ／Ｓｌ５／１３２　７１／ｔｓｅ／ｚ　１６　５／ｔ８／１２　５１１８／１２　５／１８／ｉ２　１２／１３４／２８　１２／２８／１８　１６／３６／２５　６３２／２６６３／１０４１　１１５／４６１／２０２　１２６／５２１／２０５　３／９／７　１０／５２／３６　１２／８１／２４　４１／２７９／７２　４６／３４２／８７　１２／２５／１　６　７５／２４１／１１７　５／１２／７　５／１３／７　６／１３／８　６／１３／８　６／１３／８　ｌｏ／７５／１６　２６／５５／３１　３０／６７／３６　３０／６６／３６　９／６８／１３　１８／１８３／２４　Ｉ８／１８３／２４　１９／２８３／２７　１／８／３　１／３／３　１／３／３　１／３／３　１／５１／２　１／３／３　１／３／３　３／９／７　１０／５２／３６　１２／１２６／ｌ７　４３／７３／５４　５２／２３１／６３　９／ｌ８／ｌ２　８３／３３ｌ／１１０　５／１２／７　５／¨／６　６／１３／８　６／ｌ２／７　６／ｌ３／８　ｌ６／３１／ｌ７　２８／５４／３１　２９／５７／３２　２９／５８／３３　７／１７／１０　ｌ６，／２７６／２ｌ　１９／２３６／２６　１７／２７９／２２　

合集下载

一种改进的共轭梯度法及全局收敛性

一种改进的共轭梯度法及全局收敛性

第８卷第４期２０１０年ｌ２月　１６７２－６５５３／２０１０／０８（４｝／３４２－４　动力学与控制学报　ＪＯＵＲＮＡＬ　ＯＦ　ＤＹＮＡＭ／ＣＳ　ＡＮＤ　ＣＯＮＴＲＯＬ　Ｖｏ１．８　Ｎｏ．４　Ｄｅｅ．２０１０　一种改进的共轭梯度法及全局收敛性术　朱铁锋　刘雪英　（１．内蒙古工业大学数学系，呼和浩特市０１００５１）（２．内蒙古师范大学青年政治学院计算机系，呼和浩特市０１００５１）　摘要在ＤＹ共轭梯度法的基础上对解决无约束最优化问题提出一种改进的共轭梯度法．该方法在标准　ｗｏｌｆｅ线搜索下具有充分下降陛，且算法全局收敛．数值结果表明了该算法的有效性．最后将算法用于ｓＯ　氧化反应动力学模型的非线性参数估计，获得满意效果．　关键词　共轭梯度法，　充分下降性，　ｗｏｌｆｅ线搜索，　全局收敛　引言　考虑如下无约束优化问题　ｍｉｎｆ（　），　∈Ｒ”　（１）　其中，：Ｒ　一Ｒ为连续可微函数，在解决这类问题时　的方法中，共轭梯度法因无需计算目标函数的二阶　导数矩阵，所以是一类非常有效的算法　．当目标　函数连续可微时，其迭代格式为：　＋Ｉ＝　＋　ｄ　，矗＝１，２…，　（２）　＝－…ｇｋ，＋卢　ｄ　—ｌｋ，　＝≥ｌ２　（３）　其中ｇ　＝　＿厂（　），ｄ　为搜索方向，一般情况下，要　求ｄ　满足ｇ　（ｚ　＜０，这样的方向ｄ　为函数　（　）在　处的下降方向ｉ　３１，更进一步要求ｄ　满足充分下　降性　＜一ｃ　ｌｊ　』』　（４）　其中ｃ＞０为常数．　为步长因子，可通过Ａｒｍｉｊｏ　线搜索或ｗｏｌｆｅ线搜索求得．常用的一种非精确线　搜索是标准ｗｏｌｆｅ线搜索，其形式如下：　．／　＋Ｏ／ｋｄ　）≤乏厂（　）＋ｐｏｚ　ｄｄ　（５）　ｇ（ｘ　＋ａｋｄ　）　ｄ　≥　Ｔ　（６）　其中０＜ｐ＜　＜１．　是一标量，著名的计算公式　有：　（［４］＇ｌ９６４）　（［５］，ｌ９６９）　２０１０￣４－２８收到第１稿，２０１０￣８－３１收到修改稿　内蒙古工业大学重点科学研究项目（ＺＤ２００８１５）　／３￣ｒ＝　ｇ（［６］Ｉ９９５）　＾一１（　一ｇ　—Ｉ　文献［７］中，作者提出了一个新的参数　的取法，　即：　ｃ　ｇ　１　㈩　２　Ｉ　一｝＋　３｝Ｊ　一ｌ　ＪＩ　其中　１∈（０，＋∞），　２∈［　ｌ＋　ｌ，＋∞），／ｘ３∈（０，　＋∞）和　是任给的正常数．该方法具有充分下降　性和全局收敛性，同时取得了比较好的数值结果．　受到文献［７］的启发本文在ＤＹ方法的基础　上，给出了一个新的参数　的取法，即：　，＝　㈣　其中　，∈（一１，０），　∈［１，＋∞）．本文在标准　ｗｏｌｆｅ条件下证明了此方法具有搜索方向充分下降　性和全局收敛性．　１　新的共轭梯度算法及公式的充分下降性　算法１．１　步骤１：给出　≥Ｏ，　Ｉ∈Ｒ　，ｄｊ＝～ｇｌ，　：＝１若　ｇ１＝０，则停．　步骤２：用强ｗｏｌｆｅ线搜索（５）（６），求出步长　ＯＱ，・　步骤３：　＋１＝　＋　ｄ　，ｇ　＋ｌ＝ｇ（　＋１），若ｆｆ　ｇ…ｌＩ≤　，则停．　步骤４：由公式（８）计算　＋　，由（３）式求ｄ…．　步骤５：ｋ：＝ｋ＋１．转步２．　

一类无约束优化的非单调共轭梯度法

一类无约束优化的非单调共轭梯度法

第３８卷　第１期　２０１０年１月　河南师范大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｅｎａｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｚ．３８　Ｎｏ．１　Ｊａｎ．２０１０　

文章编号：１０００—２３６７（２０１０）Ｏ１—００１２—０４　

无约束优化的非单调共轭梯度法　

孙中波，段复建　

（桂林电子科技大学数学与计算科学学院，广西桂林５４１００４）　

摘　要：针对无约束优化问题，提出一类新的非单调共轭梯度法，在新的非单调Ｗｏｌｆｅ条件下保证了算法的　

全局收敛性，并在每次迭代过程中，均可得到初始的自适应步长和充分下降方向．数值结果表明算法是可行和　

有效的．　

关键词：共轭梯度法；非单调线搜索；全局收敛　

中图分类号：０２２４．２　文献标志码：Ａ　

考虑无约束优化问题　

ｍｉｎｆ（ｘ），　（１）　ｚ∈Ｒ　其中厂：　一Ｒ　是一个二次连续可微函数．Ｒ”为欧几里得空问．对于问题（１），一般采用迭代方法近似求解，即　一ｚ　＋　

ａ　ｄ　，其中　为搜索步长，ｄ　为搜索方向．例如，线搜索方法、拟牛顿法、信赖域方法等等．近年来，许多学者提出不同的共轭　

梯度法求解问题（１）．例如，ＦＲ，ＰＲＰ，ＨＳ，ＣＤ，ＬＳ和ＤＹ方法　．文献［３—４］分别提出了校正的ＭＦＲ和ＭＰＲＰ方法，使得迭　

代次数和ＣＰＵ时问都比经典的ＦＲ和ＰＲＰ方法要好．文献［５—６］根据不同的情况的共轭梯度公式　提出了一个混合搜索方　

向ｄ　的共轭梯度法，并且得到了很好的数值试验结果．在强Ｗｏｌｆｅ条件和精确线搜索条件下，文献［７—８］证明了ＦＲ和ＣＤ方　

法的全局收敛性．　有许多经典的非单调线搜索技术，例如非单调Ａｒｍｉｊｉｏ，Ｇｏｌｄｓｔｅｉｎ，ｗｏｌｆｅ线搜索，只关心非单调ｗｏｌｆｅ搜索，即　

。厂‘ｚ　＋　＾ｄ　ｋ　。　ｍ　ａ　ｘ（　）＋　１　＋　＾ｇ　，　

１　ｇ（ｘ　＋ａ＾ｄ　）　ｄ　≥ａｇ　ｄ　，　

其中０＜　＜１，ａ　为搜索步长且ｄ　为搜索方向，ｇ　为目标函数厂（ｚ）在　的梯度，整数ｍ　

一类新的混合共轭梯度算法

一类新的混合共轭梯度算法

第１０卷第１９期２０１０年７月　１６７１—１８１５（２０１０）１９—４６０４—０４　科学技术与工程　Ｓｅｉｅ　ｎｅｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｏ１．１０　Ｎｏ．１９　Ｊｕｌｙ　２０１０　⑥２０１０　Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ．　一类新的混合共轭梯度算法　刘玉建黄炳家　（中国石油大学（华东）数学与计算科学学院，东营２５７０６１）　摘要共轭梯度算法在无约束最优化问题中有着广泛应用。现给出的一类新的共轭梯度算法，在迭代过程中保持了下降　性质；在一般Ｗｏｌｆｅ线搜索条件下，新算法是全局收敛的。　关键词无约束最优化共轭梯度法Ｗｏｌｆｅ线搜索　下降方向　全局收敛性　中图法分类号０２２４；　文献标志码Ａ　考虑无约束最优化问题　ｍｉｎ．厂（　），　∈Ｒ”　（１）　式（１）中　Ｒ一月　是是连续可微的函数。共轭梯度　算法是求解问题（１）的非常有效的算法，特别是对　于大规模的无约束优化问题。由于存储量小，算法　简便，共轭梯度算法的优势更加明显。　．　共轭梯度算法的一般迭代公式为　＋１＝　＋　ｄ　（２）　：ｆ　（３）　【一ｇ　＋　ｄ　１，Ｉｉ｝≥２　其中，ｇ　＝Ｖｆ（ｘ　）为函数Ｊｒ的梯度，ＯＬ　为搜索步长，　通过一维搜索得到，　为一标量，不同的　构成不　同的共轭梯度算法。著名的算法有　，　朋，　ＰＲＰ，　，　口ｙ等。这些算法的总体收敛性已经得　到了广泛的研究，这其中包括Ｚｏｕｔｅｎｄｉｊｋ…，Ａ１一　Ｂａａｌｉ　，Ｇｉｌｂｅｒｔ和Ｎｏｃｅｄａｌ　，戴或虹和袁亚湘　以　及Ｐｏｗｅｌｌ【５　等。为确定这些法的收敛性结果，一般　要求步长　满足强Ｗｏｌｆｅ线搜索条件，即　＋ＯＬ　ｄ　）≤　＾（　）＋Ｊ口　ｇ　ｄ　（４）　ｆｇ（ｘ　＋ｏｚｋｄ　）　ｄｋ　Ｉ≤一　Ｔ　（５）　这里０＜ｐ＜　＜１。有时甚至需要Ｏｔ　满足精确　线搜索条件，即　２０１０年４月９日收到　第一作者简介：刘玉建（Ｉ９８Ｏ一），男，山东滨州人，硕士研究生，研　究方向：最优化理论和方法。Ｅ—ｍａｉｌ：ｌｉｕｙｕｊｉａｎｑｕｆｕ＠１６３．ｃｏｒｎ。　＋Ｏｔ　ｄ　）＝ｍｉ　＋　ｄ　）　（６）　１９９５年戴或虹和袁亚湘　提出了ＤＹ方法，即　公式卢　＝　—　，证明了在一般Ｗ。Ｉｒｅ线　搜索条件即式（４）和　ｇ（　＋Ｏｔ　ｄ　）　ｄ　＞ｏｒｇ￣ｄ　（７）　下，ＤＹ方法每一步均产生一个下降方向，并证明了　算法的全局收敛性。　众所周知，共轭梯度算法的良好的收敛性与数　值表现之间并没有必然的联系，例如ＦＲ虽然有很　好的收敛性质，但数值表现往往较差。Ｐｏｗｅｌｌ『７　证　明了在某些情况下，即使采用精确步长搜索，ＦＲ也　会产生非常小的步长，除非采用重开始策略，否则　将很难摆脱这种困境；另一方面，例如ＰＲＰ和ＨＳ等　方法，虽然对一般函数不具备收敛性，但在实际计　算当中却往往有好的数值表现。这启发我们，对不　同的共轭梯度算法取长补短，采用混合策略结合研　究，或许能得到令人满意的结果，这也是近些年共　轭梯度领域的一个研究热点。Ｇｉｌｂｅｒｔ和Ｎｏｃｅｄａｌ＿３　Ｊ，　Ｔｏｕａｔｉ—ａｈｍｅｄ和Ｓｔｏｒｅｙ　以及Ｈｕ和Ｓｔｏｒｅｙ　在这方　面做出了突出贡献。郑希峰［】刚提出了一种新的共　轭梯度算法　老　。　并与ＤＹ方法结合，提出了一种混合的共轭梯度　

共轭梯度法matlab程序

共轭梯度法matlab程序

共轭梯度法matlab程序

共轭梯度法是一种用于求解无约束优化问题的迭代算法。以下是一个简单的 MATLAB

程序示例，用于实现共轭梯度法：

matlab复制代码

function [x, fval, iter] = conjugate_gradient(A, b, x0, tol,

max_iter)

% A: 矩阵

% b: 向量

% x0: 初始解

% tol: 容忍度

% max_iter: 最大迭代次数

r = b - A*x0;

p = r;

x = x0;

fval = A*x - b;

iter = 0;

while (norm(r) > tol) && (iter < max_iter)

Ap = A*p;

alpha = dot(p, r) / dot(p, Ap);

x = x + alpha*p;

r = r - alpha*Ap;

if iter == 0

fval_new = dot(r, r);

else

beta = dot(r, r) / dot(p, Ap);

p = r + beta*p;

fval_new = dot(r, r);

end

if fval_new < fval

fval = fval_new;

end

iter = iter + 1;

end

end 该程序接受一个矩阵 A、一个向量 b、一个初始解 x0、一个容忍度 tol 和一个最大迭代次数 max_iter 作为输入，并返回最终解 x、目标函数值 fval 和迭代次数 iter。

使用该函数时，您需要将要优化的目标函数转换为矩阵形式，并调用该函数来找到最优解。例如，假设您要最小化一个函数 f(x)，可以将该函数转换为矩阵形式 A*x - b，其中 A 是目标函数的雅可比矩阵，b 是目标函数的常数项向量。然后，您可以调用该函数来找到最优解，例如：