无约束多目标优化的记忆梯度法

《无约束多目标优化的记忆梯度法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２３卷第３期运筹与管理Ｖｏｌ．２３，Ｎｏ．３２０１４年６月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＪｕｎ．２０１４无约束多目标优化的记忆梯度法范开林，徐尔（北京科技大学数理学院，北京１０００８３）摘要：基于无约束单目标记忆梯度法，本文提出了一种无约束多目标优化问题的记忆梯度法，并证明了算法在Ａｒｍｉｊｏ线性搜索下的收敛性。数据试验结果验证了该算法的有效性。关键词：多目标优化；记忆梯度法；Ａｒｍｉｊｏ线性搜索；Ｐａｒｅｔｏ-临界点中图分类号：Ｏ２２１．６文章标识码：Ａ文章编号：１００７-３２２１（２０１４）０３-

2、００４５-０４MemoryGradientMethodforMultiobjectiveProgrammingwithoutConstraintsＦＡＮＫａｉ-ｌｉｎ，ＸＵＥｒ（Dept．ofMathematics＆Mechanics，BeijingUniversityofScience＆Techonlogy，Beijing１０００８３，China）Abstract：Ｂａｓｅｄｏｎｔｈｅｍｅｍｏｒｙｇｒａｄｉｅｎｔｍｅｔｈｏｄｓｆｏｒｕｎｃｏｎｓｔｒａｉｎｅｄｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ，ｗｅｐｒｅｓｅｎｔａｍｅｍｏｒｙｇｒａｄｉｅｎｔ

3、ｍｅｔｈｏｄｆｏｒｍｕｌｔｉｏｂｊｅｃｔｉｖｅｐｒｏｇｒａｍｍｉｎｇｗｉｔｈｏｕｔｃｏｎｓｔｒａｉｎｔｓ，ａｎｄｐｒｏｖｅｉｔｓｃｏｎｖｅｒｇｅｎｃｅｕｎｄｅｒＡｒｍｉｊｏｌｉｎｅｓｅａｒｃｈ．Ｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｓｅｆｆｉｃｉｅｎｔ．Keywords：ｍｕｌｔｉｏｂｊｅｃｔｉｖｅｐｒｏｇｒａｍｍｉｎｇ；ｍｅｍｏｒｙｇｒａｄｉｅｎｔｍｅｔｈｏｄ；ａｒｍｉｊｏｌｉｎｅｓｅａｒｃｈ；ｐａｒｅｔｏｃｒｉｔｉｃａｌ０引言本文考虑下列无约束多目标优化问题：n（ＭＯＰ）ｍｉｎF（x）＝（f１（x）

4、，f２（x），⋯，fp（x）），x∈Rnpp×nT其中F（x）：R硳R为连续可微函数。设F（x）在x点的Ｊａｃｏｂｉ矩阵JF（x）∈R，其JF（x）＝（磹f１，磹f２，⋯，磹fp）。在多目标规划问题中，不再使用单目标问题中最优解的概念，而是使用有效解（即Ｐａｒｅｔｏ最优解）的概念。文献［１］给出了Ｐａｒｅｔｏ-临界点的定义。基于此定义，文献［２］给出了多目标优化的最速下降方向。np定义1点x∈R称为问题（ＭＯＰ）的Ｐａｒｅｔｏ-临界点，是指满足ｒａｎｇｅ（JF（x））∩（－R＋＋）＝矱。nnp定义2对于给定的点x∈R，设A＝JF（x），定义函数f：

5、R硳R，fx（v）＝ｍａｘ｛（Av）l｜l＝１，２，⋯，p｝。考虑下面的无约束最小值问题（P）１２ｍｉｎfx（v）＋‖v‖２nｓ．ｔ．v∈R根据文献［２］，可求得其最优解v（x）和最优值α（x）。文献［３］提出了一种单目标优化记忆梯度法，在每步迭代中，除利用当前的迭代信息外，还用到前面若干迭代信息，这种算法无需计算二阶导数，又因增加了参数选择的自由度，具有较好的收敛性质。本文［２］在文献［３］的基础上，结合多目标优化最速下降算法给出了多目标的记忆梯度法，并证明了算法的收敛性。收稿日期：２０１２-１１-１７作者简介：范开林（１９８７-），男，山东临沂

6、人，硕士研究生，主要研究方向：运筹理论及应用；徐尔（１９６１-），女，北京人，副教授，主要研究方向：运筹理论及应用。４６运筹与管理２０１４年第２３卷１算法及其性质n１取常数σ∈（０，１），初始点x０∈R和参数m∈R＋＋，n∈R＋＋．置k＝０，定义J＝｛n｜n＝０，１，⋯｝．２（１）若α（xk）＝０，停止迭代。否则转第２步。vkk＝０（２）按下列公式计算dk；dk＝１m。vk＋∑βkidk－ik≥１mi＝１记vk＝v（xk），dk＝d（xk）．T其中取βki＝－fx（vk）／ψki，ψki＝ｍａｘ｛磹fj（xk）dk－i＋‖磹fj（xk）‖‖dk－i

7、‖＋n｝。k１≤j≤p１（３）计算搜索步长tk，其中tk∈J＝｛n｜n＝０，１，⋯｝中满足下式的最大者，F（xk＋tkdk）≤F（xk）＋２σtkJF（xk）dk。（４）置xk＋１＝xk＋tkdk，k＝k＋１，转至第１步。下面证明算法的两个性质：nn引理1（１）点xk是Ｐａｒｅｔｏ-临界点，则v（xk）＝０∈R，α（xk）＝０，d（xk）＝０∈R。（２）点xk不是Ｐａｒｅｔｏ-临界点，则α（xk）＜０并且当k≥１时，有T１T磹fj（xk）dk≤磹fj（xk）vk＜０，（j＝１，２，⋯，p）（１）２证明由文献［２］的引理１和dk的迭代公式易证，此略。

8、引理2若xk是非临界点，则对橙k≥１，有１T‖dk‖≤‖vk‖－·（磹fj（xk）dk），（j＝１，２，⋯，p）‖磹fj（