最优化方法第一章.ppt

1、1,最优化方法,2,前言 什么是最优化 最优化是一门应用性相当广泛的学科, 它讨论决策问题的最佳选择之特性, 寻找最佳的计算方法, 研究这些计算方法的理论性质及其实际计算表现,研究内容: 在有限种或无限种可行方案中挑选最优方案, 构造寻求最优解的计算方法 研究目的: 主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题. 应用领域：科学工程、国防、交通、管理、经济、金融、计算机等,3,学习本课程所需的数学知识,向量、向量的模(范数)、向量的运算、 线性相关与无关、基. 矩阵的运算及性质、矩阵的秩、特征值、正定性. 向量函数、连续性、可微性、梯度、海森矩阵、向量函数(多元函数)的

2、Taylor定理,4,主要参考书目： 理论方面： (1)袁亚湘、孙文瑜著,最优化理论与方法, 科学出版社, 2005 (2) 何坚勇, 最优化方法, 清华大学出版社, 2007 计算方面： (3) 曹卫华, 郭正, 最优化技术方法及MATLAB的实现, 化学工业出版社，2005 (4) 朱德通, 最优化模型与实验, 同济大学出版社, 2003,5,其它参考书： (5)卢名高、刘庆吉编著, 最优化应用技术, 石油工业出版社,2002 (6)唐焕文, 秦学志,实用最优化方法, 大连理工大学出版社, 2004 (7)钱颂迪, 运筹学, 清华大学出版社, 1990 (8)解可新、韩健, 最优化方法,

3、天津大学出版社, 2004,6,目录,第1章 基本概念 第2章 线性规划 第3章 线性搜索与信赖域方法 第4章 无约束最优化方法 第5章 线性与非线性最小二乘问题 第6章 二次规划 第7章 约束最优化的理论与方法,7,第一章基本概念,8,1.1 最优化问题简介,9,第1章 基本概念,1.1 最优化问题简介 1.2 凸集和凸函数 1.3 最优性条件 1.4 最优化方法概述,10,举 例,例：对边长为a的正方形铁板, 在四个角处剪去相等的正方形以制成方形无盖水槽, 问如何剪法使水槽的容积最大？,解 设剪去的正方形边长为x, 由题意易知, 与此相应的水槽容积为 要使其最大, 则,令,得两个驻点：,因

4、此, 每个角剪去边长为,的正方形可使所制成的水槽容积最大,11,例:某制药厂生产甲、乙两种药品, 生产这两种药品要消耗某种维生素. 生产每吨药品所需要的维生素量, 所占用的设备时间, 以及该厂每周可提供的资源总量如下表所示:,已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元.但根据市场需求调查的结果, 甲药品每周的产量不应超过4吨. 问该厂应如何安排两种药品的产量才能使每周获得的利润最大？,12,定义: x1为生产甲种药品的计划产量数, x2为生产乙种药品的计划产量数. 目标：要使总利润最大化 max z=5x1+2x2 约束：每周资源总量的限制, 30 x1+20 x2160 5x1+

5、x2 15 甲种药品每周产量不应超过4吨的限制 x14 计划生产数不可能是负数, x10 x20,13,数学模型为,这是一个如何合理的使用有限的资源, 使生产经营的效益达到最大的数学规划问题. 在满足一组约束条件的限制下, 寻求决策变量x1, x2的决策值, 使目标函数达到最大值.,14,例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品. 已知甲、乙两种原料都含有A、B、C三种化学成分, 两种原料分别所含三种化学成分的百分比含量, 以及按合同规定的产品中三种化学成分的最低含量如下表所示： 已知甲、乙两种原料的成本分别是每公斤3元和2元, 厂方希望总成本达到最小,

6、 问如何配置该产品？,化学成分,15,定义 x1，x2分别为每公斤产品中甲, 乙两种原料的数量, 目标：使总成本最小化 min z=3x1+2x2 约束：配料平衡条件, x1+x2=1 产品中A、B、C三种化学成分的最低含量 12x1+3x24 2x1+3x22 3x1+15x25 非负性条件 x10, x20,化学成分,16,数学模型：,化学成分,这是一个原料配制问题, 是在生产任务确定的条件下, 合理的组织生产, 使所消耗的资源数最少的数学规划问题. 满足一组约束条件的同时, 寻求变量x1和x2的值使目标函数取得最小值.,17,例:某铁器加工厂要制作100套钢架, 每套要用长为2.9米,

7、2.1米和1.5米的圆钢各一根. 已知原料长为7.4米, 问应如何下料, 可使材料最省？ 分析：在长度确定的原料上截取三种不同规格的圆钢, 可以归纳出8种不同的下料方案：,问题归纳为如何混合使用这8种不同的下料方案, 来制造100套钢架, 且要使剩余的余料总长为最短.,18,设 表示用第j 种下料方案下料的原料根数, j=1,2,8, 目标: 使余料总长度最小化 min z=0 x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8 约束：三种规格圆钢根数 x1+2x2+ x4+ x6 100 2x3+2x4+x5+ x6+3x7 100 3x1+x2+2x3

8、+3x5+x6+4x8 100 非负取整条件 xj0 (j=1,28)且取整数,19,数学模型 s.t. 这是一个下料问题, 是在生产任务确定的条件下, 合理的组织生产， 使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时, 寻求变量x1至x8的值,使目标函数取得最 小值.,且为整数,20,最优化的数学模型的一般形式: (1.1.1) 其中 为连续函数, 通常还要求连续可微,21,目标函数 f(x) 决策变量 x 约束函数 ci(x) 等式约束 ci(x)=0 (i=1, 2, .,m) 不等式约束 ci(x)0 (i=m+1, m+2, .,p) min 极小化 s.t. 受约束,

9、22,根据实际问题的不同要求, 最优化模型有不同的形式, 但经过适当的变换都可以转换成上述一般的形式 例如, 对于求目标函数f(x)极大的问题 max f ( x) 可转换成求- f ( x) 极小的问题 其中,23,又如对于形如ci(x)0的不等式约束, 可同样转换成上述形式的不等式约束 hi (x)0 , 其中hi(x) =-ci(x) 还有像a(x)b(x)+c的不等式约束, 可通过令 h(x)=b(x)-a(x)+c 转换成h(x)0的不等式约束形式,24,问题(1.1.1)是最优化问题的一般数学表现形式. 只要在问题中存在任何约束条件, 就称为约束最优化问题. 只有等式约束 称为等式

10、约束最优化问题,25,只有不等式约束 称为不等式约束最优化问题. 如果既有等式约束, 又有不等式约束, 则称为混合约束问题.,26,如果问题中无任何约束条件, 则称为无约束最优化问题. 无约束最优化问题的数学模型为 min f(x) , xRn , (1.1.2) 一般简记为 min f (x),27,无约束最优化问题是最优化的基础 一则很多实际的最优化问题本身就是无约束最优化问题 二则许多约束最优化方法都是通过变换把约束最优化问题转换成无约束最优化问题后, 用适当的无约束优化方法求解.,28,根据模型(1.1.1)中函数的具体性质和复杂程度, 最优化问题又有许多不同的类型. 根据决策变量的取

11、值是离散的还是连续的分为离散最优化和连续最优化 离散最优化通常又称组合最优化, 如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子 离散最优化问题的求解较之连续最优化问题的求解难度更大, 本书只介绍连续最优化的理论与方法.,29,根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光滑最优化 如果模型(1.1.1)中的所有函数都连续可微, 则称为光滑最优化 只要有一个函数非光滑, 则相应的优化问题就是非光滑优化问题. 本书只研究光滑最优化问题的求解方法,30,如果所有函数都是变量x=(x1, x2, , xn)T的线性函数, 则称(1.1.1) 为线性规划问题.线性规

12、划问题的一般形式为,31,上述线性规划模型的矩阵向量表示为 其中c= (c1, c2, , cn)T , b1=(b1, b2, , bm)T , b2=(bm+1, , bp)T,32,当模型(1.1.1)中的目标函数f (x)是变量x 的二次函数, 而所有约束都是x 的线性函数时称为二次规划问题.二次规划问题的一般形式为 其中A1, A2的表示同线性规划模型类似, c=(c1, c2, , cn)T , d 为纯量, G为nn阶对称矩阵,33,只要模型(1.1.1)的函数中有一个关于x是非线性的, 就称为非线性最优化问题. 非线性最优化问题是最一般的最优化问题, 而线性规划和二次规划问题却

13、是相当重要的特殊的最优化问题,34,如果点xRn 满足最优化模型(1.1.1)中的所有约束条件, 就称其为可行点(feasible point) 所有可行点的全体称为可行域 (feasible region) F表示可行域, 即 F= x | ci(x)=0, i= 1, 2 , , m, ci(x)0, i= m+1, , p,35,对于一个可行点 , 考虑不等式约束ci(x)0 如果有ci(x)=0, 就称约束ci(x)0在点 是有效约束或起作用约束(active constraint) , 并称可行点 位于约束ci(x)0的边界. 如果有ci(x)0, 就称不等式约束ci(x)0 在点

14、是无效约束或不起作用约束(inactive constraint), 并称 是约束ci(x)0 的内点 在任意可行点, 所有的等式约束都被认为是有效约束,36,在一个可行点, 所有有效约束的全体被称为该可行点的有效集, 并记为 对于一可行点 ,如果没有一个不等式约束是有效的, 就称 是可行域的内点,37,例图1. 1 给出了由下述约束条件给出的可行域F: c1(x)=2x1+3x2+x3-6=0, x10, x20, x30 可行点x1 可行点x2 可行点x3,38,一个可行点x*F称为问题(1.1.1)的(全局或总体)最优解, 如果有 如果上述不等式对所有不同于x*的可行点x严格成立, 即

15、则称x*为严格(全局或总体)最优解.,39,对于可行点x*, 如果存在一个邻域 使得成立 则称x* 为优化问题(1.1.1) 的局部最优解, 其中0是一个小的正整, 范数可以是任意向量范数, 但一般常用l2范数,40,如果上述不等式对所有xN(x*)F, xx*严格成立, 则称x*为严格局部极小点,41,凸规划,如果最优化问题的目标函数是凸的, 可行域是凸集, 则问题的任何最优解(不一定唯一)必是全局最优解, 这样的最优化问题称为凸规划,42,1.2 凸集和凸函数,凸集的定义 定义1.2.1 集合 称为凸的, 如果对于任意x, yD有 换句话说, 如果x, yD, 则连接x与y的直线段上的所有

16、点都在D内,线性约束条件,43,凸集定义的几何解释,44,X,X =X +(1- )X(2)， (0 1),X= X(1) +(1- )X(3)， (0 1),45,X,X =u1X(1) +u2X(2) +u3X(3),X= X(1) +(1- )X(3)， (0 1),46,凸集的性质,两个凸集的交,和以及差仍然是凸集 对于任意非零实数a, 集合aD1=ax|xD1 也是凸集,47,定理1.2.2 设 是凸集, 则任意m 个点x(i)D( i= 1 , 2 , , m)的凸组合仍属于D, 即有 其中 证明定理的结论可以用归纳法证明.根据凸集的定义, 定理的结论在m= 2时显然成立. 设结论

17、在m= k 时成立, 我们证明结论在m=k+1时也成立.,48,设 考虑任意一组实数,49,由于 , 我们有 由归纳假设有 再由凸集的定义得,50,定义1.2.3 设 为两非空凸集, 若存在非零向量aRn 和实数, 使得 则称超平面 分离了集合D1和D2,51,如果更有 则称超平面H 严格分离D1和D2,52,定理1.2.4 设 是非空闭凸集, 但 , 则 (1)存在唯一的点 , 使得集合D到点y的距离最小, 即 (2) 是点y到集合D的最短距离点的充分必要条件为,53,1.3 最优性条件,最优性条件是指最优化问题(1.1.1)的最优解(局部的或全局的)所必须满足的条件 常见并常用的有一阶必要

18、条件和二阶必要条件 先引入两个同最优解相关的基本概念可行方向和下降方向,54,定义1.3.1 设f(x)为定义在空间Rn上的连续函数, 点 , 若对于方向sRn存在数0使成立 则称s为f(x)在 处的一个下降方向. 在点 处的所有下降方向的全体记为 下面的定理给出了在f(x)连续可微时下降方向同函数f(x) 的梯度f(x)之间的关系.,55,定理1.3.2 设函数f (x)在点 处连续可微, 如存在非零向量sRn使成立 则s是f(x)在点 处的一个下降方向 证明 对于充分小的0 , 将 在点 处展开有 由于0以及 , 那么存在 使得对任意 有,56,结合这两式有 这就证明了s是f(x)在点 处

19、的下降方向,57,58,可行方向,定义1.3.3 设 为一可行点, sRn, 若存在非零方向序列S(k), k= 1 ,2 , 和正数序列 , k= 1, 2, 使成立 且有 ,则称s是在 处的一个可行方向 在点 的所有可行方向的全体记为,59,有了可行方向和下降方向的概念,我们就很容易直观的理解最优化问题最优解所满足的最优性条件. 显然在一个最优解处,不可能有任何一个既是可行的又是下降的方向. 因为根据可行方向和下降方向的定义,如果存在任何可行的下降方向,我们就能沿着这个方向找到使函数值更小的可行点,这与最优解的定义相矛盾. 这就是由下述定理给出的一个最优解所必须满足的条件.,60,定理1.

20、3.4 考虑最优化问题(1.1.1) , 设x*是问题的一个局部最优解, 函数f(x)连续可微, 则成立有 证明 对于任意的可行方向sF(x*), 我们证明 对可行方向sF(x*), 存在可行点序列x(k)=x*+ks(k) 收敛于x* 其中s(k)0, k0 , 且s(k)s, k0 由泰勒展开式有,61,由于x*是局部最优解, 对充分大的k有f(x(k)f(x*) 由此得 在上式两端除以k , 再令k取极限得 这样就证明了,62,最优化问题的可行域一般是由于等式或不等式表示的约束条件确定的, 然而由定义1.3.3 所给出的可行方向同具体的约束条件无任何直接的联系, 而由定理1.3.4 给出

21、的最优性的条件对确定最优解没有任何直接的帮助. 为此, 有必要给出由确定可行域的约束条件表示的可行方向,63,定义1.3.5 设 为一可行点, 可行域F由问题(1.1.1) 中的约束条件定. 设向量sRn非零, 且有 则称s是可行域F在可行点 的约束线性化后的可行方向, 其中 表示在可行点 处的有效不等式约束集合. 记这样的可行方向的全体为,64,对于这样定义的可行方向, 如果在最优解x*处有 成立, 那么定理1.3.4 就可以表示成 由于集合L(x*)是用问题的约束函数表示, 而集合D(x*)用问题的目标函数表示, 我们就可用问题中的函数来表达最优解的最优性条件 下面的定理给出了在某一可行点

22、 处 成立的条件,65,定理1.3.6 设所有约束函数ci(x), i=1, 2, , p在可行点 处连续可微, 则有 (2)如果或者所有ci(x), i =1, 2, , m, i( ) 是x的线性函数 或者 , i=1, 2, , m, iL( )线性无关, 则 成立.,66,证明 任取一个非零的可行方向 , 则存在可行点序列 , 其中k0,k0 和s(k) 0, s(k)s 由x(k)的可行性以及有效集的定义有,67,在上述两式的两端都同除以k后再对k取极限, 由函数的连续可微性得 这就证明了 ,由 的任意性证明了,68,定理1. 3. 6 的(2)中关于约束函数的条件称为约束规范 有许

23、多不同的约束规范条件和表现形式, 但最常见也是最方便使用的还是由上述定理的(2)所给出的约束规范条件. 有了上面的准备, 我们现在就可以给出最优解的一阶必要条件, 又称Kuhn-Tucker条件,69,定理1.3.7 设x*F是最优化问题(1.1.1) 的一个局部最优解, f(x), ci(x), i= 1, 2, , p 在x*的一个邻域内连续可微. 如果对所有的等式约束和在x*的有效约束, 或者都是x的线性函数, 或者他们在点x*的梯度向量线性无关, 则存在向量 使成立 (1.3.2),70,证明 根据定理的条件, 由定理1.3.6在点x*成立有F(x*)=L(x*). 再据定理1.3.4

24、有 .根据集合D(x*)与L(x*) 的定义, 这以表示成下述不等式组无解 将上述不等式组改写成,71,或矩阵向量的表示 其中 由不等式组(1.3.3)无解, 根据引理1.2.6 存在非负向量 y=(y(1), y(2), y(3)T使得 其中y(1)Rm, y(2)Rm, y(3)R|I(x*)|. 将上式展开得,72,令 并对非有效约束指标i置 , 则有 对于不等式约束还有 又因对有效的不等式约束有 对非有效的不等式约束有 所以有,73,在大部分最优化研究的文献中, 称最优解x*所满足的一阶必要条件(1.3.2)为Kuhn-Tucker条件或K-K-T条件 满足Kuhn-Tucker条件的

25、点为Kuhn-Tucker点或K-K-T点 称式(1.3.2)中的第三个等式为互补松弛条件 如果对于任意i=m+1, , p, ci(x*)和 中有且仅有一个取零值, 则称严格互补松弛条件成立,74,由于无约束最优化问题中无任何约束条件, 由定理1.3.7立即可以得到无约束最优化问题最优解的一阶必要条件是 (1.3.4) 即在无约束最优化问题的最优解处, 任何方向都不是目标函数的下降方向 习惯上把满足条件(1.3.4)的点称为平稳点或驻点,75,这是因为无约束问题的最优点一定满足条件(1.3.4)但满足(1.3.4)的点不一定是无约束问题的局部最优解 单变量函数f(x)=x3就提供了这样的一个

26、例子. 在点x*=0, 有f(x*)=0, 但x*=0却不是其最优解. 这种情况同样适用于约束最优化问题, 即约束最优化问题的最优解在约束规范条件满足时必定是Kuhn-Tucker点, 但满足Kuhn-Tucker条件的可行点未必是最优解 下面的定理表明对于凸规划问题Kuhn-Tucker条件却是最优解的充分条件.,76,定理1.3.8 设凸规划问题的目标函数与约束函数都连续可微, 如果在可行点x*处约束规范条件和Kuhn-Tucker条件成立, 则x*是问题的全局最优解 证明设x*是Kuhn-Tucker点,*是相应的向量.根据凸规划对函数的要求, 我们知, f(x)是凸函数, ci(x)

27、, i=1, , m(如果m0)是线性函数, ci(x),i=m+1, , p(如果pm)是凹函数.因此对任意xF有,77,由于 , i= m+ 1, , p , 对任意xF有 . 因此对任意xF得 这就证明了x*是凸规划问题的全局最优解,78,Kuhn-Tucker条件中的向量*称为最优Lagrange乘子. 事实上, 引入问题(1.1.1)的Lagrange函数 那么我们可以看到条件(1.3.2)中的第一个方程可以写成 即Lagrange 函数L(x,)关于x的一阶偏导数在(x *,*)处取零值,79,如果不考虑在点x*的无效约束, 则在点x*的可行性条件ci(x*)=0, i= 1, 2

28、, , m, iI(x*), 又可表示成 即Lagrange 函数关于的一阶偏导数在(x*,*)处也取零值 因而(x*,*) 是Lagrange函数的一个平稳点,80,下面我们讨论最优解的二阶最优性条件, 为简化讨论, 假定在点x*处严格互补松弛条件成立, 并定义在点x* 处的有效约束的零可行方向集,81,定义1.3.9 设在可行点x*处严格互补松弛条件成立, 如果存在非零向量序列s(k)和正数序列k0使有 且有s(k)s,k0 , 则称s为可行域在点x*处的零可行方向 所有这些方向的集合称为零可行方向集, 记为Z(x*),82,称满足 的非零向量s为约束线性化后的零可行方向 所有这些方向的集

29、合称为约束线性化后的零可行方向集, 记为Lz(x*) 集合Z(x*)是集合F(x*)的子集 集合Lz(x*)是集合L(x*)的子集 下面的定理给出了最优解的二阶必要条件,83,定理1.3.10 考虑最优化问题(1.1.1), 设x*F是其最优解, 且函数f(x)与ci(x), i=1, 2, , p 二阶连续可微.又设定理1.3.6 的约束规范条件在x*成立, 从而存在Lagrange乘子向量*使Kuhn-Tucker 条件成立.设严格补松弛条件成立, 则有 其中 是Lagrange函数在(x*,*)处关于x的二阶偏导数矩阵,84,证明 任取非零可行方向sZ(x*), 则存在可行点序列x(k)

30、 =x*+ks(k)使得ci(x(k)=0, i= 1, 2, , m, iI(x*), 其中k0 , s(k)s.由于对于无效不行约束有*i=0 , 因而对这样的序列有 由各函数的二阶连续可微性, 并利用Kuhn-Tucker 条件有,85,由于x*是局部最优解, 对充分大的k有f (x(k) f(x*)成立, 由此得,86,在上式两边同除以 后再令k取极限得,87,由于定理1.3.6 的约束规范条件成立时有Z(x*) =Lz(x*)成立, 上述定理二阶必要条件可以用下述更直接的方式给出,88,定理1.3.11 设x*F是问题(1.1.1) 的最优解且函数f (x)与ci(x), i=1 ,

31、 2 , , p 二阶连续可微.又设定理1.3.6 的约束规范条件在点x*成立, 从而存Lagrange乘子向量*使Kuhn-Tucker条件成立.如果严格互补松弛条件在x*成立, 则 对一切满足 的方向s均成立 下面的定理则给出了最优解的二阶充分条件,89,定理1.3.12 考虑最优化问题(1.1.1) , 函数f (x)与ci(x) , i=1, 2, , p均二阶连续可微.设对于可行点x*存在Lagrange乘子向量* 使Kuhn-Tucker条件成立.若成立有 则x*是问题(1.1.1)的严格局部最优解,90,证明 定理的证明采用反证法. 设x*不是问题的严格局部最优解, 则存在收敛于

32、x*的可行点序列x(k), x(k)x*, k=1, 2, , 使成立 f(x(k)f(x*), k=1, 2, 不失一般性, 设 并令 ，则 且k0, 因此s F(x*)=L(x*),91,由函数f(x)的连续可微性有 由此得 在上式两端除以k后再令k取极限得 (1.3.5) 由于sL(x*)而 , 有两种可能性,92,(a) ,即存在有指标i0I(x*)使得sTci(x*)0, 这时由Kuhn-Tucker条件有 这与式(1.3.5)相矛盾, 这一矛盾表明 不成立, 因而有sZ(x*),93,(2)由x(k)的可行性和*, i 0 , i= m+ 1 , , p , 有,94,注意到f(x

33、(k)f(x*) , 由上式得 两边除以 , 并令k取极限得 这与定理的条件相矛盾, 由此证明了x*是问题的严格局部最优解,95,当定理1.3.6 的约束规范条件在x*处成立时, 有Z(x*)=Lz(x*)成立, 这上述二阶充分条件可用下述更直接的方式给出.,96,定理1.3.13 设最优化问题(1.1.1)的函数f(x) 与ci(x), i= 1, 2, , p 均二阶连续可微, 在可行点x*处定理1.3.6 的约束规范条件成立.若存在Lagrange乘子向量* 使Kuhn-Tucker条件和严格松弛互补条件成立, 且对所有满足 的非零向量s有 则x*是问题(1.1.1)的一个严格局部最优解

34、.,97,由于无约束最优化问题无任何约束, 由上述几个最优解的二阶条件(必要的和充分的) , 直接可以得到无约束最优化问题最优解的下列二阶必要条件和二阶充分条件,98,定理1.3.14 ( 二阶必要条件) 设x*是无约束最优化问题的一个最优解, f(x)在x*的一个邻域内二阶连续可微, 则有f(x*)=0, 且f(x)在x*的二阶Hesse阵正半定, 即成立,99,定理1.3.15 (二阶充分条件)设f ( x) 在x* 的一个邻域内二阶连续可微,且有f(x*)=0, 2f (x*)正定, 即成立 则x*是f(x)的无约束优化问题的一个严格局部最优解,100,1.4 最优化方法概述,以下述简单

35、的无约束最优化问题为例 根据最优性的一阶必要条件, 最优解必定是方程 的解,101,由f( x)的连续性, 当x-有f(x)-和x有f(x), 上述方程的解存在 但我们却无法得出解的任何解析表达式 因此求最优化问题的解, 一般用迭代的方法, 其基本思想为, 给定最优解的一个初始估计, 记为x(0),方法产生一个逐步改善的有限或无限的迭代序列x(k) 在x(k)是有限点列时,它的最后一个点是Kuhn-T ucker点; 在 x( k) 是无限点列时, 其任意一个聚点是Kuhn-Tucker 点, 并在对最优解的估计满足指定的精度要求时停止迭代,102,根据最优性的一阶必要条件, 最优解一定是Ku

36、hn-Tucker点 因此理论上由迭代法所确定的解一般是Kuhn-Tucker点 再由方法的其他一些特性, 如下降性可以确保所得的Kuhn-Tucker点是所论问题的最优解或最优解的近似,103,基本的迭代格式,算法1.4.1 (最优化方法的基本迭代格式) 1. 给定最优解的一个初始估计x(0), 置k = 0; 2. 如果x(k)满足对最优解估计的终止条件, 停止迭代; 3. 确定一个改善x(k)的修正量(k) ; 4. 得到最优解的一个更好的估计x(k+1)=x(k)+(k), 置k= k+1后转步2,104,迭代法涉及问题,基本格式中涉及初始点的选取; 迭代点好坏的判定; 迭代的终止条件

37、; 以及最重要也是最关键的修正量(k)的确定,105,初始点的选取,初始点的选取依赖于方法的收敛性能 一个算法称为收敛的, 如果算法产生的序列x(k)满足 其中x*是问题的Kuhn-Tucker点,106,全局收敛和局部收敛,一个算法如果对于任意给定的初始点都能够收敛, 就说这个方法全局收敛或整体收敛 有些算法只有当初始点接近或充分接近最优解时才有收敛性, 称这样的算法为局部收敛的方法 因此对于全局收敛的算法, 初始点的选取可以没有任何的限制 对于局部收敛的算法, 则要求初始点应尽可能接近最优解,107,然而由于最优解是未知的, 选取一个好的初始点也是一个困难的问题.对于大量实际的最优化问题一般可以从以前的实践经验确定合适的最优解的初始估计,1