最优化方法及其Matlab程序设计

最优化方法的matlab实现，从理论到仿真实现前运筹学的理论与方法广泛应用于工业与农业、交通与运输、国防与建筑以及通信与管珄等各个部门各个领域;它主要解决最优计划、最优分配、最优决策以及最佳设计和最佳管理等最优化问题.本书所介绍的最优化方法又称为数学规划,是运筹学的一个重要分支,也是计算数学和应用数学的一个重要组成部分木书系统地介绍了非线性优化的理论与方法及其 Matlab程序设计,其主要阅读对象是数学与应用数学和信息与计算科学专业的本科生,应用数学、讣算数学和运筹学与控制论专业的研究生,珥工科有关专业的研究生,对最优化理论与算法感兴趣的教师及科技工作人员.读者只需具备微积分、线性代数和 Matlab程序设计方面的初步知识木书的主要内容包括:最优化理论基础:(精确或非精确)线搜索技术;最速下降法与(修正)牛顿法;共轭梯庋法;拟牛顿法;信赖域方法;非线性最小二乘问题的解法;(约束优化问题的)最优性条件:罚数法;可行方向法;二次规划问题的解法;序列二次规划法以及附录等.设计的 Matlab程序有精确线搜索的0.616法和抛物线法,非精确线搜索的 Armijo准则,最速下降法,牛顿法,再开始共轭梯度法,对称秩1算沁,BFGS算法,DFP算法, Broyden族方法,信赖域方法,求解非线性最小二乘问题的LM算法,解约束优化问题的乘了法,求解二次规划的有效集法,牛顿-拉格朗口算法,SQP了问题的光滑牛顿法以及求解约束优化问题的SQP方法等.此外,书中型有丰富的例题和习题,同时,作为附录介绍了Matlab优化工具箱的使用方法.本书既注重计算方法的实用性.又注意保持理论分析的严谨性,强调数值方法的思想和原理在计算机上的实现木书具有如下特点1.介绍非线性优化中最重要最基础的理论与方法,它们是研究各种复杂的最优化问题的基础和工具2.最优化方法与 Matlab程序设计相结合,采用当前最流行的数学软件Matlab编制了主要优化算法的 Matlab程序.所有程序都在计算机上经过调试和运行,简洁而不乏准确.3.本书所给的每一程序之后都给出了相应的计算实例.这不仅能帮助学生理解程序里所包含的最优化理论知识,而且对培养学生处理数值最优化问题的能力也大有裨益.4.全书每章都配备了一定数量的习题,习题包括理论分析题和编程实验题,以加强学生对所学知识的理解和巩固本书的编写和出版待到了国家自然科学基金项日(编号:10661005)褊建省自然科学基金项日(编号:2009.J01002)的部分资助,在此作者表示由衷的感谢.作者还要感谢福建师范大学教务处及数学与计算机科学学院给予的帮助和支持.此外,木书之所以能够顺利付梓,在很大程度上要归功于大人刘菊庄女士给予的理解秈支持,深表感谢由于作者水平有限,加之时间仓促,书中的缺点和错误在所难免,敬请专家和读者批评指止作者2009年12月于福建师范大学目录第一章最优化理论基础卫1最优化回题的数学模型112L2向量和知阵范数3函数的可微性与展开14凸集与凸函数L5无约束问题的最优性条10L6无约束优化问题的算法框架12第二章线搜索技术162.]精确线搜索及其 Matlab实现1822非精确线搜索及其 Matlab实现2423线搜索泅的收敛性27俤第三章最速下降法和牛顿法323]最速下降方法及其 Matlab实现3232牛顿法及其Mata实现B3修正牛顿法及其 Matlab实现第四章共轭梯度法474.1共轭方向法47.2共轭梯度洇4.3共轭梯度法的Mtab程55第五章拟牛顿法595,1拟牛顿法及其性质592BFGS算法及其 Matlab实现5.3DFP算法及其 Matlab实现6754 broyden族算法及其 Matlab实现7055我牛顿泓的收敛性第六章信赖域方法836信赖域方法的基本结构6.2信赖域方法的收敛性563信赖域子问题的求解64信赖域方法的 Matlab程93第七章非线性最小三乘问题9871 Gauss-Newton法987.2 Levenberg-Marquardt方洇10273T-M算法的Mata程同第八章最优性条仼l148,等式约束间题的最优性条佣1148.2不等式约束问题的最优性条俐117S.3—般约束问题的最优性条件1218.4鞍点和对偶问题124第九章罚函数法1329外罚函数泅1329.2内点法136乘子洇94莱子法的 Matlab实现149第十章可行方向法155⊥ Zoutendijk可行方向泅15510,1线性约束下的可行方向洇15510.2非线性约束下的可行方向洇,161102梯度投影1661021梯度投影法的理论基础16710.22梯度投影法的计算步骤17110.3简约梯度·看,17510.31Wofe简约梯度洇17510.32广义間约梯度洇183萬十一章二次规划1901等式约束凸二次规划的解洇11.1.1零空间方法1901112拉格朗日方法及其 Matlab程,192112一般凸二次规划的有效集方法19511.2.1有效集方法的理论推导196山22有效集方泅的算泓步骡Qc1123有效集方法的 Matlab程序204第十二章序列二次规划法211121牛顿拉格朗日法211121.1牛顿-拉格朗法的基本理论21112.1.2牛顿-拉朗目法的 Matlab程扇...213122SQP方法的算法模型21612.2.1某于拉格朗日函数Hese阵的SQP方涸21612.2棊于修正Hese阵的SQP方洇22423SQP方法的相关间题227123.1二次规划子问题的 Hesse阵22712.32价值函数与搜索方向的下降性22912.4SQP方泅的 Matlab程2362.4SQP了问题的 Matlab实现12.2SQP方法的Mtab实现244附录 A Matlab优化工具箱简介252A1线性规划252A.2二次规划254A.3无约束非线性优化255A.4非线性最小二乘间题257A.5约東条件的非线性优化命交258A6最小最大值的优化间题..261第一章最优化理论基础1.1最优化问题的数学模型通俗地说,所谓最优化问题,就是求一个多元函数在某个给定集合上的极值.几乎所有类型的最优化问题都可以用下面的数学模型来描述:min (a(1.1)t.x∈K,这里,K是某个给定的集合(称为可行集或可行域),f(x)是定义在集合K上的实值函数,此外,在模型小中,x通常称为决策变量,st.是 subject to受限于)的缩写人们通常按照可行集的性质对最优化问题(进行一个大致的分类:·线性规划和非线性规划.可行集是有限维空间中的一个子集;组合优化或网络规划.一可行集中的元素是有限的:动态规划.一可行集是个依赖时间的决策序列;●最优控制.可行集是无穷维空间中的一个连续子集本书主要考虑在工程设计中有着重要应用的非线性规划,其数学模型为minh;(x)=0,其中,f(x),h(x)(=1,……,l)及g:(x)(-1,…,m)都是定义在R上连续可微的多元实值函数,且至少有一个是非线性的.记E={:h(x)=0},I={:91(x)≥0}第一章最优化理论基础回目录§12向量和矩阵范数若指标集E∪Ⅰ=⑩,称之为无约束优化问题,否则称为约束优化问题.特别地,把E≠且I=0的优化问题称为等式约束优化问题;而把I≠0且E=0的优化问题称为不等式约束优化问题f(x)称为目标函数,h:(x),9(x(=1,…,;j-1,…,m)称为约束函数.此外,通常把目标函数为二次函数而约束函数都是线性函数的优化问题称为二次规划:而目标函数和约束函数都是线性函数的优化问题称为线性规划.12向量和矩阵范数在算法的收敛性分析中,需要用到向量和矩阵范数的概念及其有关理论设R”表示实维向量空间,RX表示实阶矩阼全体所组成的线性空间.在这炳个空间中,我们分别定义向量和矩阵的范数向量x∈Rn的范数|;是一个非负数,它必须满足以下条件(1)‖cl≥0,‖c‖l=0÷→x=0;)Axll=|入|x‖,入∈R;(3)‖x+y|<‖l‖+lyl向量x=(x1,……,xn)7的p=范数定义为lp=(∑|rP)(1.6常用的向量范数有范数:‖x|1=∑|:范数:|x|2=(∑;2)∞0-范数:|x|=max|ax1矩阵A∈RXn的范数是一个非负实数,它除了满足跟向量范数相似的三条性质之外,还必须具备乘法性质:(4)‖AB<‖A‖B|,A,B∈R2×n如果“矩阵范数‖·相对于某向量氾数‖·‖满足下面的不等式(5)‖Acll≤‖Alrl,x∈Rn,则称矩阵范数‖·‖和向量范数‖·‖是相容的.进一步,若存在m≠0使成立Aamnax‖Axl,A∈]R(1.7)lx‖-1第一章最优化理论基础回目录81.2向量和矩阵范数则称矩阵范数|·‖μ是由向量范数·‖诱导出来的算子范数,简称算子范数,有时也称为从属于向量范数‖·‖的矩阵范数.此时向量范数和算子范数通常采用相同的符号·|.不难验证,从属于向量范数‖x‖lx,‖x‖1.‖|xl2的矩阵范数分别为max1<<∑Inax∑|ay小2=A|2=max{y|A∈X(A7A)}它们分别称作行和范数、列和范数和谱范数.木书在讨论各种迭代算法的收敛性时,通常采用谱范数和按下述方式定义的F-范数:4=-(∑∑)1/2vtr(ATA现在我们来讨论向量序列和矩阵序列的收敛性.我们知道,若{x()}则lim cx<÷limxk→∞0k类似地,若{A(}x1 C Rnxn,则limA()=A←→lmm a=为了利用范数来描述上述极限,必须建立向量范数的等价定理以及矩阵范数的等价定理定理1(1)设‖·|和‖·‖'是定义在B上的两个向量范数,则存在两个正数C1,C2,对所有汇∈R"均成立1c≤‖(2)设‖·|和‖·‖是定义在RⅫn上的两个矩阵范数,则存在两个正数m1,m2,对所有A∈Rx均成立