求解约束最优化问题KKT系统的BFGS方法
“Jennylaugh”通过精心收集，向本站投稿了8篇求解约束最优化问题KKT系统的BFGS方法，下面小编为大家整理后的求解约束最优化问题KKT系统的BFGS方法，欢迎阅读与借鉴!
篇1：求解约束最优化问题KKT系统的BFGS方法
求解约束最优化问题KKT系统的BFGS方法
利用Fischer-Burmeister函数,将约束最优化问题KKT系统转化为等价的`非光滑方程组,利用广义导数,给出一个求解该非光滑方程组的BFGS方法.其子问题是一个系数阵为正定对称阵的线性方程组.为保证全局收敛性,我们引进了一个适当的线性搜索,它使得效益函数近似下降.在适当的条件下,我们证明了算法是适定的,并具有全局收敛性和超线性收敛性.
作 者：张继伟 王仙桃 作者单位：湖南大学,数学与计量经济学院,湖南,长沙,410082 刊 名：湖南大学学报(自然科学版) ISTIC EI PKU英文刊名：JOURNAL OF HUNAN UNIVERSITY(NATURAL SCIENCES) 年，卷(期)： 30(3) 分类号：O221.1 关键词：KKT系统 BFGS方法 全局收敛 超线性收敛 广义导数 半光滑篇2：求解等式约束最优化问题的Broyden算法的全局收敛性
求解等式约束最优化问题的Broyden算法的全局收敛性
将单边既约Hesse矩阵SQP方法和无导数线性搜索技术相结合,提出了一种求解等式约束最优化问题的拟牛顿算法.在适当的假设条件下,证明了算法全局收敛于优化问题的KKT点,而且收敛速度是局部超线性的..当迭代次数k充分大时,这种算法可以实现单位步长,因此不会出现Marotos效应.
作 者：蒋月评 王扉 作者单位：湖南大学,数学与计量经济学院,湖南,长沙,410082 刊 名：湖南大学学报(自然科学版) ISTIC EI PKU英文刊名：JOURNAL OF HUNAN UNIVERSITY(NATURAL SCIENCES) 年，卷(期)：2003 30(3) 分类号：O221.1 关键词：等式约束 线性搜索 Broyden算法 全局收敛 超线性收敛篇3：量子进化算法用于求解约束多目标优化问题的探析
量子进化算法用于求解约束多目标优化问题的探析
摘 要：本文提出了一种用于解决约束多目标优化问题的方法。本算法在进化算法的基础上加入了邻里竞争与邻里合作算子，并通过引入agent-based模型的设计理念，更加注重个体变化对整个群体的影响。本算法首先使用约束偏离值的方法将约束多目标优化问题简化为多目标优化问题;然后使用自我更新算子，当新产生的个体优于原先的个体时予以替换;之后通过邻里竞争与邻里合作加快种群内部的信息交流;最后加入量子加速算子，通过使用量子旋转门来扩大计算搜寻范围提高程序计算速度。本文最后与两种已有算法进行对比，实验结果表明，本算法完成了设计目标。在运行时间和输出结果精度方面都有不错的表现。
关键词：约束多目标优化 约束偏离值 邻里竞争 量子计算
一、引言
进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术。与传统的优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具有自组织、自适应、自学习的特性。尤其是在处理多目标优化问题时，进化算法表现出很好的效果。
近年来，出现了很多优秀的算法用于解决约束多目标优化问题，其中Deb提出的NSGA-II算法是最为经典的一个算法。NSGA-II成功的将进化算法应用在约束多目标优化问题上，在进化算法的基础上引入了约束偏离值。Hongguang Li提出了基于agent的进化算法用于求解约束多目标优化问题。算法利用agent概念认为每个个体与其种群内其他个体都有相互的作用和影响，虽然算法精度不是很高但是计算速度很快。本文受到基于agent概念的启发，希望设计出一个计算速度快，精度高的算法。
二、量子进化算法
2.1 邻里竞争与邻里合作
agent-based模型是一种从底层到高层的数学模型，模型更加注重的是每个个体对整个群体的影响，通过改变个体的某些特征和表现从而影响整个整体。本算法在此基础上，通过模仿自然界种群内部个体之间既有竞争又有合作的关系，设计出了邻里竞争与邻里合作算子。邻里竞争算子采用的是吞并算子，算子表示如下：
设对于一个种群共有k个个体X1，X2，…，Xi，每个个体的目标函数值分别为，则：
(1)
其中表示的是新产生的个体。公式表达的意义是：每个个体与其排名靠后一位的个体进行竞争，将两者目标函数值进行对比，目标函数值较小的个体成为这一位置上的新个体。
邻里合作算子如下：
(2)
(3)
其中，是个体i、j的第k个决策变量，且。r，u是分布在[0，1]之间的随机数。
2.2 量子计算
加入量子算子是为了加快计算速度，希望通过更少的进化代数进化出更加优秀的种群。本算法通过设计出一个对周围区域具有自适应调整搜索步长的量子旋转门，从而提升量子计算运行效率。量子计算首先需要将个体的基因编码从实数编码形式转换为量子编码形式，之后通过量子旋转门的计算快速搜索周围空间寻找更加优秀的个体进行输出。
个体在完成量子旋转门的计算后，个体的基因编码需要映射回实数域，完成其他计算过程。量子算子的本质也就是通过将个体基因编码转换为量子域，通过利用量子计算在量子域具有指数级加速和指数级存储的能力，快速的寻找最优解的过程。
2.3 算法的主要流程
图1为本算法流程图。算法采用顺序结构设计，结构简单， 在进化计算的基础上首先使用了约束偏离值的方法，将约束多目标问题进行简化。其次借鉴了基于agent模型里种群中个体之间又相互的影响和作用，设计了邻里竞争与邻里合作算子。又利用了量子计算的加速性能，提升了算法的运行速度。
若为第一代种群，本算法通过之前修正好的目标函数向量进行选择，首先在可行解里选取非支配解，形成种群FeaPop，并在全部种群中寻找非支配解，放入种群NonPop中;若不是第一代种群，则将上一代产生的父代FeaPop与当代的进化种群Pop合并形成NPop，在合并之后的种群里再去寻找可行非支配解形成当代的FeaPop种群，寻找非支配解形成当代的NonPop。变异算子对于防止种群陷入局部最优解起到了重要的作用，本算法采用文献中非一致性变异算子。
三、仿真实验与结果分析
本文的测试问题是Deb提出的.六个经典的约束多目标最小化问题， 算法参数设计为：初始种群大小为100，合作概率为0.9， 合作指数为10，变异概率为0.5，非一致系数为2，自我更新指数为20。最大的可行非支配解集FeaPop大小为100，非支配解集NonPop大小为100。对比算法初始种群大小为100， 交叉概率为0.9， 交叉分布指数为15， 变异概率为0.1， 变异分布指数为20。
文中所有测试问题均独立运行30次，我们采用的度量指标分别为GD和算法运行时间。世代距离指标(GD)，是度量算法所得Pareto前端与真实前端之间的距离。其数学表达式如下式所示：
(4)
其中，，n为个体数目，是中第个个体的目标函数向量与中最近个体间的欧氏距离。GD值越小，所求得的前端就越接近真实前端，解集的收敛性就越好。运行时间则是算法的跑完相同进化代数所需要的时间，时间越短说明算法运行速度越快，本文中涉及到的几种算法运行代数均为1000代。
表1给出本文算法与两种对比算法运行6测试问题的结果。
CTP2、CTP7是寻找离散的几个线段，CTP3、CTP4两个问题要寻找的Pareto前端都是离散的端点，CTP5是离散点和线段的组合，CTP6问题是寻找连续的直线。从表中我们可以看出几种算法对于处理CTP2问题都有不错的结果，都可以很好地找到几个离散端点。对于CTP3和CTP4问题由于测试函数难度的加大，算法[3]已不能很好地找出真实Pareto前端所在位置，而NSGA-II、本算法还能找到真实Pareto前端所在区域，不过已经无法做到很精准的定位Pareto前端的位置。对于CTP5，几种算法在找离散点的能力都很不错。对于CTP6问题几种算法都找到了Pareto前端，只是均匀性稍有差异。CTP7问题，除了算法[3]之外也都很好的找到了前端所在区域。
4 总结与展望
本文算法用于处理约束多目标优化问题，在设计上借鉴了agent-based模型，更加注意种群中个体对整个种群的影响，通过进行自我更新，邻里协作与邻里竞争等操作来改变个体的基因编码，从而改变了整个种群的进化方向进化速度，共同朝着真实的Pareto前端进行进化。并且本算法融入了量子计算，使得程序可以更高效更快捷更准确的去寻找最优解。在和现有的几种算法的对比上体现出了算法的优势，在保证精度值的基础上减少了大量的程序运行时间。不过提高算法的精度仍然是之后研究的重点。如何更好地处理种群中个体之间的关系是我们今后需要进一步做的工作。
篇4：一类求解非线性等式和不等式约束优化问题的区间算法
一类求解非线性等式和不等式约束优化问题的区间算法
在Moore二分法的基础上,通过构造的.区间列L中标志矢量R的分量取值来删除部分不满足约束条件的区域,将非线性约束优化问题转化为初始域子域上的无约束优化问题,该算法可利用极大熵方法求解多目标优化问题,理论分析和数值结果均表明,这种算法是稳定且可靠的.
作 者：黄时祥 梁晓斌 HUANG Shi-xiang LIANG Xiao-bin 作者单位：上饶师范学院,数学与计算机系,江西,上饶,334001 刊 名：大学数学 PKU英文刊名：COLLEGE MATHEMATICS 年，卷(期)： 25(2) 分类号：O242.29 O221.2 关键词：区间算法 全局约束优化 非线性函数 多目标规化篇5：一类新的求解约束优化问题的锥模型信赖域算法
一类新的求解约束优化问题的锥模型信赖域算法
本文提出了一类新的求解线性等式约束优化问题的锥模型信赖域算法.不同于以往的求解约束问题的锥模型信赖域算法,无论试探步是否被接受,我们在每步都采用Wolfe线搜索得到下一个迭代点,避免了重解子问题,并且保证了序列{Bk}满足拟牛顿方程及其正定性.在适当条件下,证明了算法的全局收敛性,数值试验表明该算法是有效的'.
作 者：张娜 焦宝聪 Zhang Na Jiao Baocong 作者单位：首都师范大学数学科学学院,北京,100048 刊 名：首都师范大学学报（自然科学版） ISTIC英文刊名：JOURNAL OF CAPITAL NORMAL UNIVERSITY(NATURAL SCIENCES EDITION) 年，卷(期)：2009 30(6) 分类号：O224 关键词：线性等式约束优化 锥模型信赖域 Wolfe线搜索 全局收敛性篇6：用伴随方法求解多个工业污染源优化布局问题
用伴随方法求解多个工业污染源优化布局问题
发展了一种伴随方法,引入罚函数来处理环境约束不等式,构造优化问题的Lagrange函数,从理论上推导了伴随方程和目标函数梯度公式.通过求解伴随方程得到目标函数的.梯度,利用梯度信息使得目标函数下降,用迭代的方法逼近最优解.用二维的简化模式进行了数值试验,结果验证了理论的正确性.该方法收敛速度快,效率高,与空气质量数值模式和计算机技术的飞速发展相适应,为工业规划和污染防治提供了有力的研究工具.
作 者：刘峰 胡非 朱江 作者单位：中国科学院大气物理研究所,LAPC,北京,100029 刊 名：中国科学D辑 ISTIC PKU英文刊名：SCIENCE IN CHINA (SERIES D) 年，卷(期)： 35(1) 分类号：X5 关键词：优化布局 工业污染源 伴随方程 罚函数 梯度篇7：约束最优化问题中一个全局误差界及其应用
约束最优化问题中一个全局误差界及其应用
本文利用信赖域方法中的几个特征量(由预测下降量给出的价值函数与信赖域半径等),在目标函数的梯度向量是强单调的条件下,为约束最优化问题的.可行解与最优解之间的距离提供了一个全局误差界.我们利用误差界得出了可行解点列收敛于最优解的充分条件和可行解点列收敛到KT点的必要条件.最后,还给出了可行解点列至KT点集的距离趋于零的必要条件.
作 者：赵文玲 王长钰 ZHAO Wen-ling WANG Chang-yu 作者单位：赵文玲,ZHAO Wen-ling(大连理工大学应用数学系,大连,116024;山东理工大学数学与信息科学学院,淄博,255049)王长钰,WANG Chang-yu(大连理工大学应用数学系,大连,116024;曲阜师范大学运筹所,曲阜,273165)
刊 名：工程数学学报 ISTIC PKU英文刊名：CHINESE JOURNAL OF ENGINEERING MATHEMATICS 年，卷(期)： 24(6) 分类号：O221.2 关键词：信赖域子问题 价值函数 全局误差界 收敛性 trust region subproblem value function global error bound convergence篇8：水文学中雨强公式参数求解的一种最优化方法
水文学中雨强公式参数求解的一种最优化方法
提出了一种客观的、最优化的暴雨强度公式参数估算方法:先将公式线性化,确定出未知参数b,C取值范围,给定一个b值(分公式)、b,C组合(总公式),再对雨强-历时-重现期(i-t-T)三联表数据进行最小二乘法拟合可得到参数A,n,以总误差最小为控制条件,理论上可得到最优的'一组参数估算值.并以深圳、武汉两市为例,进行暴雨强度公式参数估算,精度高于国家标准要求,且明显优于对比方法.该法已被编制成计算机软件,只要输入原始资料就可以很快输出结果,包括曲线型估计、参数估算、误差分析、图表,使用极其方便,可向全国各地推广应用.
作 者：陈正洪 王海军 张小丽 Chen Zhenghong Wang Haijun Zhang Xiaoli 作者单位：陈正洪,Chen Zhenghong(武汉区域气候中心,武汉430074;中国气象局武汉暴雨研究所,武汉430074)王海军,Wang Haijun(湖北省气象信息与技术保障中心,武汉430074)
张小丽,Zhang Xiaoli(深圳市气象台,深圳518008)
刊 名：应用气象学报 ISTIC PKU英文刊名：JOURNAL OF APPLIED METEOROLOGICAL SCIENCE 年，卷(期)：2007 18(2) 分类号：P4 关键词：暴雨强度公式 线性化 最优化 误差控制【求解约束最优化问题KKT系统的BFGS方法】相关文章：
10.职场新人优化生存的方法
文档为doc格式
