最优化方法第一章课件

最优化方法最优化方法1最优化方法1前言什么是最优化最优化是一门应用性相当广泛的学科,它讨论决策问题的最佳选择之特性,寻找最佳的计算方法,研究这些计算方法的理论性质及其实际计算表现研究内容:在有限种或无限种可行方案中挑选最优方案,构造寻求最优解的计算方法研究目的:主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题.应用领域：科学工程、国防、交通、管理、经济、金融、计算机等2前言研究内容:在有限种或无限种可行方案中挑选最优方案,构学习本课程所需的数学知识向量、向量的模(范数)、向量的运算、线性相关与无关、基.矩阵的运算及性质、矩阵的秩、特征值、正定性.向量函数、连续性、可微性、梯度、海森矩阵、向量函数(多元函数)的Taylor定理 3学习本课程所需的数学知识向量、向量的模(范数)、向量的运算、主要参考书目：理论方面：(1)袁亚湘、孙文瑜著,最优化理论与方法,科学出版社,2005(2)何坚勇,最优化方法,清华大学出版社,2007计算方面：(3)曹卫华,郭正,最优化技术方法及MATLAB的实现,化学工业出版社，2005(4)朱德通,最优化模型与实验,同济大学出版社,20034主要参考书目：4v其它参考书：v(5)卢名高、刘庆吉编著,最优化应用技术,石油工业出版社,2002v(6)唐焕文,秦学志,实用最优化方法,大连理工大学出版社,2004v(7)钱颂迪,运筹学,清华大学出版社,1990 v(8)解可新、韩健,最优化方法,天津大学出版社,20045其它参考书：5目录v第1章 基本概念v第2章 线性规划v第3章 线性搜索与信赖域方法v第4章 无约束最优化方法v第5章 线性与非线性最小二乘问题v第6章 二次规划v第7章 约束最优化的理论与方法6目录第1章 基本概念6第一章第一章基本概念基本概念7第一章基本概念71.1 最优化问题简介81.1 最优化问题简介8第1章 基本概念v1.1 最优化问题简介v1.2 凸集和凸函数v1.3 最优性条件v1.4 最优化方法概述9第1章 基本概念1.1 最优化问题简介9举 例例：对边长为a的正方形铁板,在四个角处剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大？解 设剪去的正方形边长为x,由题意易知,与此相应的水槽容积为要使其最大,则令得两个驻点：因此,每个角剪去边长为的正方形可使所制成的水槽容积最大 10举 例例：对边长为a的正方形铁板,在四个角处剪去相等的正方例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素.生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:每吨产品的消耗 每周资源总量 甲乙维生素(公斤)3020160设备(台)5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元.但根据市场需求调查的结果,甲药品每周的产量不应超过4吨.问该厂应如何安排两种药品的产量才能使每周获得的利润最大？11例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维 定义定义:x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数.目标：要使总利润最大化 max z=5x1+2x2约束：每周资源总量的限制,30 x1+20 x2160 5x1+x2 15甲种药品每周产量不应超过4吨的限制 x14计划生产数不可能是负数,x10 x20每吨产品的消耗 每周资源总量甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)512 定义:x1为生产甲种药品的计划产量数 数学模型为每吨产品的消耗 每周资源总量 甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)5这是一个如何合理的使用有限的资源,使生产经营的效益达到最大的数学规划问题.在满足一组约束条件的限制下,寻求决策变量x1,x2的决策值,使目标函数达到最大值.13 数学模型为每吨产品的消耗 每周资源总量 甲乙维生素（例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品.已知甲、乙两种原料都含有A、B、C三种化学成分,两种原料分别所含三种化学成分的百分比含量,以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元,厂方希望总成本达到最小,问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分化学成分14例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混定义 x1，x2分别为每公斤产品中甲,乙两种原料的数量,目标：使总成本最小化 min z=3x1+2x2约束：配料平衡条件,x1+x2=1产品中A、B、C三种化学成分的最低含量 12x1+3x24 2x1+3x22 3x1+15x25非负性条件 x10,x20 原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）化学成分15定义 x1，x2分别为每公斤产品中甲,乙两种原料的数量,数学模型：原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）化学成分化学成分这是一个原料配制问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题.满足一组约束条件的同时,寻求变量x1和x2的值使目标函数取得最小值.16数学模型：原料化学成分含量（%）产品中化学成分的例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,2.1米和1.5米的圆钢各一根.已知原料长为7.4米,问应如何下料,可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案：圆钢（米）291201010021002211301531203104料头（米）00.10.20.30.80.91.1.4问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的余料总长为最短.17例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,设 表示用第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+3x5+x6+4x8 100非负取整条件 xj0(j=1,28)且取整数圆钢（米）291201010021002211301531203104余料（米）00.10.20.30.80.91.1.418 设 表示用第j 种下料方案下料的原料根数,j=数学模型 s.t.这是一个下料问题,是在生产任务确定的条件下,合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最 小值.圆钢（米）291201010021002211301531203104料头（米）00.10.20.30.80.91.11.4且为整数19 数学模型圆钢（米）29120101002最优化的数学模型的一般形式:(1.1.1)其中为连续函数,通常还要求连续可微20最优化的数学模型的一般形式:20v目标函数 f(x)v决策变量 x v约束函数 ci(x)v等式约束 ci(x)=0 (i=1,2,.,m)v不等式约束 ci(x)0 (i=m+1,m+2,.,p)vmin 极小化vs.t.受约束21目标函数 f(x)21v根据实际问题的不同要求,最优化模型有不同的形式,但经过适当的变换都可以转换成上述一般的形式v例如,对于求目标函数f(x)极大的问题 max f(x)可转换成求-f(x)极小的问题 其中 22根据实际问题的不同要求,最优化模型有不同的形式,但经过适 又如对于形如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的不等式约束形式23 又如对于形如ci(x)0的不等式约束,可同样转换 问题(1.1.1)是最优化问题的一般数学表现形式.只要在问题中存在任何约束条件,就称为约束最优化问题.只有等式约束 称为等式约束最优化问题 24 问题(1.1.1)是最优化问题的一般数学表现形式.2 只有不等式约束 称为不等式约束最优化问题.如果既有等式约束,又有不等式约束,则称为混合约束问题.25 只有不等式约束 25 如果问题中无任何约束条件,则称为无约束最优化问题.无约束最优化问题的数学模型为 min f(x),xRn,(1.1.2)一般简记为 min f(x)26 如果问题中无任何约束条件,则称为无约束最优化问题.2 无约束最优化问题是最优化的基础v一则很多实际的最优化问题本身就是无约束最优化问题v二则许多约束最优化方法都是通过变换把约束最优化问题转换成无约束最优化问题后,用适当的无约束优化方法求解.27 无约束最优化问题是最优化的基础27 根据模型(1.1.1)中函数的具体性质和复杂程度,最优化问题又有许多不同的类型.根据决策变量的取值是离散的还是连续的分为离散最优化和连续最优化 离散最优化通常又称组合最优化,如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子 离散最优化问题的求解较之连续最优化问题的求解难度更大,本书只介绍连续最优化的理论与方法.28 根据模型(1.1.1)中函数的具体性质和复杂程度,最 根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光滑最优化 如果模型(1.1.1)中的所有函数都连续可微,则称为光滑最优化 只要有一个函数非光滑,则相应的优化问题就是非光滑优化问题.本书只研究光滑最优化问题的求解方法29 根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光v如果所有函数都是变量x=(x1,x2,xn)T的线性函数,则称(1.1.1)为线性规划问题.线性规划问题的一般形式为30如果所有函数都是变量x=(x1,x2,xn)T的线v上述线性规划模型的矩阵向量表示为 其中c=(c1,c2,cn)T,b1=(b1,b2,bm)T,b2=(bm+1,bp)T31上述线性规划模型的矩阵向量表示为31v当模型(1.1.1)中的目标函数f(x)是变量x 的二次函数,而所有约束都是x 的线性函数时称为二次规划问题.二次规划问题的一般形式为 其中A1,A2的表示同线性规划模型类似,c=(c1,c2,cn)T,d 为纯量,G为nn阶对称矩阵32当模型(1.1.1)中的目标函数f(x)是变量x 的二次函v只要模型(1.1.1)的函数中有一个关于x是非线性的,就称为非线性最优化问题.v非线性最优化问题是最一般的最优化问题,而线性规划和二次规划问题却是相当重要的特殊的最优化问题33只要模型(1.1.1)的函数中有一个关于x是非线性的,就称v如果点xRn 满足最优化模型(1.1.1)中的所有约束条件,就称其为可行点(feasible point)v所有可行点的全体称为可行域(feasible region)vF表示可行域,即vF=x|ci(x)=0,i=1,2,m,ci(x)0,i=m+1,p34如果点xRn 满足最优化模型(1.1.1)中的所有约束条件v对于一个可行点 ,考虑不等式约束ci(x)0v如果有ci(x)=0,就称约束ci(x)0在点 是有效约束或起作用约束(active constraint),并称可行点 位于约束ci(x)0的边界.v如果有ci(x)0,就称不等式约束ci(x)0 在点 是无效约束或不起作用约束(inactive constraint),并称 是约束ci(x)0 的内点v在任意可行点,所有的等式约束都被认为是有效约束35对于一个可行点 ,考虑不等式约束ci(x)035v在一个可行点,所有有效约束的全体被称为该可行点的有效集,并记为 v对于一可行点,如果没有一个不等式约束是有效的,就称 是可行域的内点36在一个可行点,所有有效约束的全体被称为该可行点的有效集,v例图1.1 给出了由下述约束条件给出的可行域F:c1(x)=2x1+3x2+x3-6=0,x10,x20,x30 可行点x1 可行点x2 可行点x337例图1.1 给出了由下述约束条件给出的可行域F:37v一个可行点x*F称为问题(1.1.1)的(全局或总体)最优解,如果有v如果上述不等式对所有不同于x*的可行点x严格成立,即 则称x*为严格(全局或总体)最优解.38一个可行点x*F称为问题(1.1.1)的(全局或总体)最优v对于可行点x*,如果存在一个邻域 使得成立 则称x*为优化问题(1.1.1)的局部最优解,其中0是一个小的正整,范数可以是任意向量范数,但一般常用l2范数39对于可行点x*,如果存在一个邻域39v如果上述不等式对所有xN(x*)F,xx*严格成立,则称x*为严格局部极小点40如果上述不等式对所有xN(x*)F,xx*严格成立,凸规划v如果最优化问题的目标函数是凸的,可行域是凸集,则问题的任何最优解(不一定唯一)必是全局最优解,这样的最优化问题称为凸规划41凸规划如果最优化问题的目标函数是凸的,可行域是凸集,则问1.2 凸集和凸函数凸集和凸函数v凸集的定义 定义1.2.1 集合 称为凸的,如果对于任意x,yD有 换句话说,如果x,yD,则连接x与y的直线段上的所有点都在D内线性约束条件线性约束条件421.2 凸集和凸函数凸集的定义42凸集定义的几何解释凸集定义的几何解释43凸集定义的几何解释43X X(1)(1)X X(3)(3)X X(2)(2)XXX=X=XX +(1-+(1-)X)X(2)(2)，(0 (0 1)1)x x1 1x x2 2OOX=X=X X(1)(1)+(1-+(1-)X)X(3)(3)，(0 (0 1)1)44X(1)X(3)X(2)XX=X+(1-)X(X X(1)(1)X X(3)(3)X X(2)(2)XXX=uX=u1 1X X(1)(1)+u+u2 2X X(2)(2)+u+u3 3X X(3)(3)x x1 1x x2 2OOX=X=X X(1)(1)+(1-+(1-)X)X(3)(3)，(0 (0 1)0使成立 则称s为f(x)在 处的一个下降方向.在点 处的所有下降方向的全体记为 下面的定理给出了在f(x)连续可微时下降方向同函数f(x)的梯度f(x)之间的关系.54定义1.3.1 设f(x)为定义在空间Rn上的连续函数,点 定理1.3.2 设函数f(x)在点 处连续可微,如存在非零向量sRn使成立 则s是f(x)在点 处的一个下降方向 证明 对于充分小的0,将 在点 处展开有 由于0以及 ,那么存在 使得对任意 有55 定理1.3.2 设函数f(x)在点 处连续可微结合这两式有这就证明了s是f(x)在点 处的下降方向56结合这两式有565757可行方向 定义1.3.3 设 为一可行点,sRn,若存在非零方向序列S(k),k=1,2,和正数序列 ,k=1,2,使成立 且有 ,则称s是在 处的一个可行方向 在点 的所有可行方向的全体记为58可行方向 定义1.3.3 设 为一可行v有了可行方向和下降方向的概念,我们就很容易直观的理解最优化问题最优解所满足的最优性条件.v显然在一个最优解处,不可能有任何一个既是可行的又是下降的方向.v因为根据可行方向和下降方向的定义,如果存在任何可行的下降方向,我们就能沿着这个方向找到使函数值更小的可行点,这与最优解的定义相矛盾.v这就是由下述定理给出的一个最优解所必须满足的条件.59有了可行方向和下降方向的概念,我们就很容易直观的理解最优化问 定理1.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 由泰勒展开式有60 定理1.3.4 考虑最优化问题(1.1.1),设x 由于x*是局部最优解,对充分大的k有f(x(k)f(x*)由此得 在上式两端除以k,再令k取极限得 这样就证明了61 由于x*是局部最优解,对充分大的k有f(x(k)fv最优化问题的可行域一般是由于等式或不等式表示的约束条件确定的,v然而由定义1.3.3 所给出的可行方向同具体的约束条件无任何直接的联系,v而由定理1.3.4 给出的最优性的条件对确定最优解没有任何直接的帮助.v为此,有必要给出由确定可行域的约束条件表示的可行方向62最优化问题的可行域一般是由于等式或不等式表示的约束条件确定的 定义1.3.5 设 为一可行点,可行域F由问题(1.1.1)中的约束条件定.设向量sRn非零,且有 则称s是可行域F在可行点 的约束线性化后的可行方向,其中 表示在可行点 处的有效不等式约束集合.记这样的可行方向的全体为63 定义1.3.5 设 为一可行点,可行 对于这样定义的可行方向,如果在最优解x*处有 成立,那么定理1.3.4 就可以表示成 由于集合L(x*)是用问题的约束函数表示,而集合D(x*)用问题的目标函数表示,我们就可用问题中的函数来表达最优解的最优性条件 下面的定理给出了在某一可行点 处 成立的条件64 对于这样定义的可行方向,如果在最优解x*处有64 定理1.3.6 设所有约束函数ci(x),i=1,2,p在可行点 处连续可微,则有 (2)如果或者所有ci(x),i=1,2,m,i()是x的线性函数 或者 ,i=1,2,m,iL()线性无关,则 成立.65 定理1.3.6 设所有约束函数ci(x),i=1,2v证明 任取一个非零的可行方向 ,则存在可行点序列 ,其中k0,k0 和s(k)0,s(k)s 由x(k)的可行性以及有效集的定义有66证明 任取一个非零的可行方向 ,在上述两式的两端都同除以k后再对k取极限,由函数的连续可微性得 这就证明了 ,由 的任意性证明了6767 定理1.3.6 的(2)中关于约束函数的条件称为约束规范 有许多不同的约束规范条件和表现形式,但最常见也是最方便使用的还是由上述定理的(2)所给出的约束规范条件.有了上面的准备,我们现在就可以给出最优解的一阶必要条件,又称Kuhn-Tucker条件68 定理1.3.6 的(2)中关于约束函数的条件称为约 定理1.3.7 设x*F是最优化问题(1.1.1)的一个局部最优解,f(x),ci(x),i=1,2,p 在x*的一个邻域内连续可微.如果对所有的等式约束和在x*的有效约束,或者都是x的线性函数,或者他们在点x*的梯度向量线性无关,则存在向量 使成立 (1.3.2)69 定理1.3.7 设x*F是最优化问题(1.1.1)证明 根据定理的条件,由定理1.3.6在点x*成立有F(x*)=L(x*).再据定理1.3.4有 .根据集合D(x*)与L(x*)的定义,这以表示成下述不等式组无解 将上述不等式组改写成70 证明 根据定理的条件,由定理1.3.6在点x*成立有或矩阵向量的表示其中由不等式组(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*)|.将上式展开得71或矩阵向量的表示71令并对非有效约束指标i置 ,则有对于不等式约束还有又因对有效的不等式约束有对非有效的不等式约束有所以有 72令72 在大部分最优化研究的文献中,称最优解x*所满足的一阶必要条件(1.3.2)为Kuhn-Tucker条件或K-K-T条件 满足Kuhn-Tucker条件的点为Kuhn-Tucker点或K-K-T点 称式(1.3.2)中的第三个等式为互补松弛条件 如果对于任意i=m+1,p,ci(x*)和 中有且仅有一个取零值,则称严格互补松弛条件成立73 在大部分最优化研究的文献中,称最优解x*所满足的一阶 由于无约束最优化问题中无任何约束条件,由定理1.3.7立即可以得到无约束最优化问题最优解的一阶必要条件是 (1.3.4)即在无约束最优化问题的最优解处,任何方向都不是目标函数的下降方向 习惯上把满足条件(1.3.4)的点称为平稳点或驻点74 由于无约束最优化问题中无任何约束条件,由定理1.3.这是因为无约束问题的最优点一定满足条件(1.3.4)但满足(1.3.4)的点不一定是无约束问题的局部最优解 单变量函数f(x)=x3就提供了这样的一个例子.在点x*=0,有f(x*)=0,但x*=0却不是其最优解.这种情况同样适用于约束最优化问题,即约束最优化问题的最优解在约束规范条件满足时必定是Kuhn-Tucker点,但满足Kuhn-Tucker条件的可行点未必是最优解 下面的定理表明对于凸规划问题Kuhn-Tucker条件却是最优解的充分条件.75 这是因为无约束问题的最优点一定满足条件(1.3.4)但 定理1.3.8 设凸规划问题的目标函数与约束函数都连续可微,如果在可行点x*处约束规范条件和Kuhn-Tucker条件成立,则x*是问题的全局最优解 证明设x*是Kuhn-Tucker点,*是相应的向量.根据凸规划对函数的要求,我们知,f(x)是凸函数,ci(x),i=1,m(如果m0)是线性函数,ci(x),i=m+1,p(如果pm)是凹函数.因此对任意xF有76 定理1.3.8 设凸规划问题的目标函数与约束函数都连续 由于 ,i=m+1,p,对任意xF有 .因此对任意xF得这就证明了x*是凸规划问题的全局最优解77 由于 ,i=m+1,p Kuhn-Tucker条件中的向量*称为最优Lagrange乘子.事实上,引入问题(1.1.1)的Lagrange函数 那么我们可以看到条件(1.3.2)中的第一个方程可以写成 即Lagrange 函数L(x,)关于x的一阶偏导数在(x*,*)处取零值78 Kuhn-Tucker条件中的向量*称为最优Lagr 如果不考虑在点x*的无效约束,则在点x*的可行性条件ci(x*)=0,i=1,2,m,iI(x*),又可表示成 即Lagrange 函数关于的一阶偏导数在(x*,*)处也取零值 因而(x*,*)是Lagrange函数的一个平稳点79 如果不考虑在点x*的无效约束,则在点x*的可行性条件v下面我们讨论最优解的二阶最优性条件,为简化讨论,假定在点x*处严格互补松弛条件成立,并定义在点x*处的有效约束的零可行方向集80下面我们讨论最优解的二阶最优性条件,为简化讨论,假定在点 定义1.3.9 设在可行点x*处严格互补松弛条件成立,如果存在非零向量序列s(k)和正数序列k0使有 且有s(k)s,k0,则称s为可行域在点x*处的零可行方向 所有这些方向的集合称为零可行方向集,记为Z(x*)81 定义1.3.9 设在可行点x*处严格互补松弛条件成立,称满足 的非零向量s为约束线性化后的零可行方向 所有这些方向的集合称为约束线性化后的零可行方向集,记为Lz(x*)集合Z(x*)是集合F(x*)的子集 集合Lz(x*)是集合L(x*)的子集 下面的定理给出了最优解的二阶必要条件82称满足82 定理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的二阶偏导数矩阵83 定理1.3.10 考虑最优化问题(1.1.1),设x 证明 任取非零可行方向sZ(x*),则存在可行点序列x(k)=x*+ks(k)使得ci(x(k)=0,i=1,2,m,iI(x*),其中k0,s(k)s.由于对于无效不行约束有*i=0,因而对这样的序列有 由各函数的二阶连续可微性,并利用Kuhn-Tucker 条件有84 证明 任取非零可行方向sZ(x*),则存在可行点序 由于x*是局部最优解,对充分大的k有f(x(k)f(x*)成立,由此得8585在上式两边同除以 后再令k取极限得8686 由于定理1.3.6 的约束规范条件成立时有Z(x*)=Lz(x*)成立,上述定理二阶必要条件可以用下述更直接的方式给出87 由于定理1.3.6 的约束规范条件成立时有Z(x*)定理1.3.11 设x*F是问题(1.1.1)的最优解且函数f(x)与ci(x),i=1,2,p 二阶连续可微.又设定理1.3.6 的约束规范条件在点x*成立,从而存Lagrange乘子向量*使Kuhn-Tucker条件成立.如果严格互补松弛条件在x*成立,则 对一切满足 的方向s均成立 下面的定理则给出了最优解的二阶充分条件88 定理1.3.11 设x*F是问题(1.1.1)的最 定理1.3.12 考虑最优化问题(1.1.1),函数f(x)与ci(x),i=1,2,p均二阶连续可微.设对于可行点x*存在Lagrange乘子向量*使Kuhn-Tucker条件成立.若成立有 则x*是问题(1.1.1)的严格局部最优解89 定理1.3.12 考虑最优化问题(1.1.1),函 证明 定理的证明采用反证法.设x*不是问题的严格局部最优解,则存在收敛于x*的可行点序列x(k),x(k)x*,k=1,2,使成立 f(x(k)f(x*),k=1,2,不失一般性,设并令 ，则且k0,因此s F(x*)=L(x*)90 证明 定理的证明采用反证法.90由函数f(x)的连续可微性有由此得在上式两端除以k后再令k取极限得 (1.3.5)由于sL(x*)而 ,有两种可能性91由函数f(x)的连续可微性有91(a),即存在有指标i0I(x*)使得sTci(x*)0,这时由Kuhn-Tucker条件有 这与式(1.3.5)相矛盾,这一矛盾表明 不成立,因而有sZ(x*)92(a),即存在有指标i0I(2)由x(k)的可行性和*,i 0,i=m+1,p,有93(2)由x(k)的可行性和*,i 0,i=m+注意到f(x(k)f(x*),由上式得两边除以 ,并令k取极限得 这与定理的条件相矛盾,由此证明了x*是问题的严格局部最优解94注意到f(x(k)f(x*),由上式得94 当定理1.3.6 的约束规范条件在x*处成立时,有Z(x*)=Lz(x*)成立,这上述二阶充分条件可用下述更直接的方式给出.95 当定理1.3.6 的约束规范条件在x*处成立时,有Z 定理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)的一个严格局部最优解.96 定理1.3.13 设最优化问题(1.1.1)的函数f(由于无约束最优化问题无任何约束,由上述几个最优解的二阶条件(必要的和充分的),直接可以得到无约束最优化问题最优解的下列二阶必要条件和二阶充分条件97 由于无约束最优化问题无任何约束,由上述几个最优解的二 定理1.3.14(二阶必要条件)设x*是无约束最优化问题的一个最优解,f(x)在x*的一个邻域内二阶连续可微,则有f(x*)=0,且f(x)在x*的二阶Hesse阵正半定,即成立98 定理1.3.14(二阶必要条件)设x*是无约束最 定理1.3.15(二阶充分条件)设f(x)在x*的一个邻域内二阶连续可微,且有f(x*)=0,2f(x*)正定,即成立 则x*是f(x)的无约束优化问题的一个严格局部最优解99 定理1.3.15(二阶充分条件)设f(x)在x1.4 最优化方法概述 以下述简单的无约束最优化问题为例根据最优性的一阶必要条件,最优解必定是方程 的解1001.4 最优化方法概述 以下述简单的无约束最优化问题为例 由f(x)的连续性,当x-有f(x)-和x有f(x),上述方程的解存在 但我们却无法得出解的任何解析表达式 因此求最优化问题的解,一般用迭代的方法,其基本思想为,给定最优解的一个初始估计,记为x(0),方法产生一个逐步改善的有限或无限的迭代序列x(k)在x(k)是有限点列时,它的最后一个点是Kuhn-T ucker点;在 x(k)是无限点列时,其任意一个聚点是Kuhn-Tucker 点,并在对最优解的估计满足指定的精度要求时停止迭代101 由f(x)的连续性,当x-有f(x)-根据最优性的一阶必要条件,最优解一定是Kuhn-Tucker点 因此理论上由迭代法所确定的解一般是Kuhn-Tucker点 再由方法的其他一些特性,如下降性可以确保所得的Kuhn-Tucker点是所论问题的最优解或最优解的近似102 根据最优性的一阶必要条件,最优解一定是Kuhn-Tu基本的迭代格式算法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后转步2103基本的迭代格式算法1.4.1(最优化方法的基本迭代格式)1迭代法涉及问题 基本格式中涉及初始点的选取;迭代点好坏的判定;迭代的终止条件;以及最重要也是最关键的修正量(k)的确定104迭代法涉及问题 基本格式中涉及初始点的选取;104初始点的选取 初始点的选取依赖于方法的收敛性能 一个算法称为收敛的,如果算法产生的序列x(k)满足 其中x*是问题的Kuhn-Tucker点105初始点的选取 初始点的选取依赖于方法的收敛性能105全局收敛和局部收敛 一个算法如果对于任意给定的初始点都能够收敛,就说这个方法全局收敛或整体收敛 有些算法只有当初始点接近或充分接近最优解时才有收敛性,称这样的算法为局部收敛的方法 因此对于全局收敛的算法,初始点的选取可以没有任何的限制 对于局部收敛的算法,则要求初始点应尽可能接近最优解106全局收敛和局部收敛 一个算法如果对于任意给定的初始点都能 然而由于最优解是未知的,选取一个好的初始点也是一个困难的问题.对于大量实际的最优化问题一般可以从以前的实践经验确定合适的最优解的初始估计107 然而由于最优解是未知的,选取一个好的初始点也是一个困评价函数 在最优化方法中,一般要选用一个评价函数(Merit Function)来评价一个迭代点的好坏.对于无约束最优化问题,由于没有约束条件,通常就用目标函数f(x)作为评价函数 以无约束极小化问题 min f(x)为例,如果有f(x(k+1)0是给定的精度要求 准则(1.4.1)一般适用于收敛速度比较慢的算法110迭代的终止条件 迭代的终止条件在不同的最优化方法中也是收敛速度 收敛速度是迭代方法的又一重要性质.对于一个不可能在有限步内找到最优解的最优化方法,我们不仅要求它收敛,还要求它有较快的收敛速度 111收敛速度 收敛速度是迭代方法的又一重要性质.111设向量序列 收敛于x*,定义误差序列如果存在常数C和r使成立就说序列 x(k)以C为因子r阶收敛于x*(1)当r=1,C=0时,称序列x(k)超线性收敛于x*,超线性收敛是一种比线性收敛快的收敛(2)称r=2时的收敛为二次收敛,二次收敛是一种更快的收敛112设向量序列 收敛于x*,定终止准则 一个理想的算法终止准则为 然而由于x*是未知的,这样的准则并不具有任何实用价值113终止准则 一个理想的算法终止准则为113 在序列x(k)超线性收敛于x*时,我们可以得到114114上式表明,对于一个超线性收敛的算法，是 估计.因此对于具有超线性收敛速度的方法是一个比较合适的终止准则115上式表明,对于一个超线性收敛的算法，115 同样也可以用评价函数值序列来确定终止准则,还是以无约束优化问题为例,由于x*未知 不可能直接用作收敛准则,但当f(x)二次连续可微时可以推得 因此对于快速收敛的算法 也是一个相当有效的收敛准则116 同样也可以用评价函数值序列来确定终止准则,还是以无约修正量 如果最优解的一个近似不能满足要求的精度,方法需要计算一个修正量s(k)来得到最优解的一个更好的近似 s(k)的计算是最优化方法最关键和最主要的计算工作117修正量 如果最优解的一个近似不能满足要求的精度,方法需 对于大多数的最优化方法来说,s(k)是通过求解一个相对简单易于求解的最优化问题(通常称为子问题)确定的.由于最优化要求确定使目标函数值取最优(最小)的可行点,修正量s(k)的确定要求在新点x(k+1)处的评价函数值小于在点x(k)处的评价函数值,称这样每次迭代都使评价函数值下降的算法为单调下降算法,本书介绍的都是这类单调下降算法118 对于大多数的最优化方法来说,s(k)是通过求解一个相