最优化方法第一章课件

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

3学习本课程所需的数学知识向量、向量的模(范数)、向量的运算、主要参考书目：理论方面：(1)袁亚湘、孙文瑜著,《最优化理论与方法》,科学出版社,2005(2)何坚勇,《最优化方法》,清华大学出版社,2007计算方面：(3)曹卫华,郭正,《最优化技术方法及MATLAB的实现》,化学工业出版社，2005(4)朱德通,《最优化模型与实验》,同济大学出版社,20034主要参考书目：4其它参考书：(5)卢名高、刘庆吉编著,《最优化应用技术》,石油工业出版社,2002(6)唐焕文,秦学志,《实用最优化方法》,大连理工大学出版社,2004(7)钱颂迪,《运筹学》,清华大学出版社,1990(8)解可新、韩健,《最优化方法》,天津大学出版社,20045其它参考书：5目录第1章基本概念第2章线性规划第3章线性搜索与信赖域方法第4章无约束最优化方法第5章线性与非线性最小二乘问题第6章二次规划第7章约束最优化的理论与方法6目录第1章基本概念6第一章

基本概念7第一章

基本概念7§1.1最优化问题简介8§1.1最优化问题简介8第1章基本概念1.1最优化问题简介1.2凸集和凸函数1.3最优性条件1.4最优化方法概述9第1章基本概念1.1最优化问题简介9举例例：对边长为a的正方形铁板,在四个角处剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大？解设剪去的正方形边长为x,由题意易知,与此相应的水槽容积为要使其最大,则令得两个驻点：因此,每个角剪去边长为的正方形可使所制成的水槽容积最大．

10举例例：对边长为a的正方形铁板,在四个角处剪去相等的正方例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素.生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:每吨产品的消耗每周资源总量甲乙维生素(公斤)

3020160设备(台)

5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元.但根据市场需求调查的结果,甲药品每周的产量不应超过4吨.问该厂应如何安排两种药品的产量才能使每周获得的利润最大？11例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维

定义:

x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数.

目标：要使总利润最大化maxz=5x1+2x2

约束：每周资源总量的限制,30x1+20x2≤1605x1+x2≤15甲种药品每周产量不应超过4吨的限制x1≤4计划生产数不可能是负数,x1≥0x2≥0每吨产品的消耗

每周资源总量甲乙维生素（公斤）3020160设备（台）

5115单位利润(万元)

5２12定义:x1为生产甲种药品的计划产量数

数学模型为每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)5２这是一个如何合理的使用有限的资源,使生产经营的效益达到最大的数学规划问题.在满足一组约束条件的限制下,寻求决策变量x1,x2的决策值,使目标函数达到最大值.13数学模型为每吨产品的消耗每周资源总量甲乙维生素（例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品.已知甲、乙两种原料都含有A、B、C三种化学成分,两种原料分别所含三种化学成分的百分比含量,以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元,厂方希望总成本达到最小,问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分14例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混定义

x1，x2分别为每公斤产品中甲,乙两种原料的数量,目标：使总成本最小化minz=3x1+2x2约束：配料平衡条件,x1+x2=1产品中A、B、C三种化学成分的最低含量12x1+3x2≥42x1+3x2≥23x1+15x2≥5非负性条件x1≥0,x2≥0原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分15定义x1，x2分别为每公斤产品中甲,乙两种原料的数量,数学模型：原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分这是一个原料配制问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题.满足一组约束条件的同时,寻求变量x1和x2的值使目标函数取得最小值.16数学模型：原料化学成分含量（%）产品中化学成分的例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,2.1米和1.5米的圆钢各一根.已知原料长为7.4米,问应如何下料,可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案：圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的余料总长为最短.17例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,

设表示用第j种下料方案下料的原料根数,j=1,2…,8,目标:使余料总长度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束：三种规格圆钢根数x1+2x2+x4+x6≥1002x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x5+x6+4x8≥100非负取整条件xj≥0(j=1,2…8)且取整数圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104余料（米）00.10.20.30.80.91.１1.418设表示用第j种下料方案下料的原料根数,j=

数学模型

s.t.

这是一个下料问题,是在生产任务确定的条件下,合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最小值.圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.11.4且为整数19数学模型圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002最优化的数学模型的一般形式:(1.1.1)其中为连续函数,通常还要求连续可微20最优化的数学模型的一般形式:20目标函数f(x)决策变量x

约束函数ci(x)等式约束ci(x)=0(i=1,2,…..,m)不等式约束ci(x)≥0(i=m+1,m+2,…..,p)min极小化s.t.受约束21目标函数f(x)21根据实际问题的不同要求,最优化模型有不同的形式,但经过适当的变换都可以转换成上述一般的形式例如,对于求目标函数f(x)极大的问题

maxf(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

如果问题中无任何约束条件,则称为无约束最优化问题.

无约束最优化问题的数学模型为

minf(x),x∈Rn

,(1.1.2)

一般简记为

minf(x)

26如果问题中无任何约束条件,则称为无约束最优化问题.2

无约束最优化问题是最优化的基础一则很多实际的最优化问题本身就是无约束最优化问题二则许多约束最优化方法都是通过变换把约束最优化问题转换成无约束最优化问题后,用适当的无约束优化方法求解.27无约束最优化问题是最优化的基础27

根据模型(1.1.1)中函数的具体性质和复杂程度,最优化问题又有许多不同的类型.根据决策变量的取值是离散的还是连续的分为离散最优化和连续最优化

离散最优化通常又称组合最优化,如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子

离散最优化问题的求解较之连续最优化问题的求解难度更大,本书只介绍连续最优化的理论与方法.28根据模型(1.1.1)中函数的具体性质和复杂程度,最根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光滑最优化

如果模型(1.1.1)中的所有函数都连续可微,则称为光滑最优化

只要有一个函数非光滑,则相应的优化问题就是非光滑优化问题.本书只研究光滑最优化问题的求解方法29根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光如果所有函数都是变量x=(x1,x2,⋯,xn)T的线性函数,则称(1.1.1)为线性规划问题.线性规划问题的一般形式为30如果所有函数都是变量x=(x1,x2,⋯,xn)T的线上述线性规划模型的矩阵向量表示为其中c=(c1,c2,⋯,cn)T,b1=(b1,b2,⋯,bm)T,b2=(bm+1,⋯,bp)T31上述线性规划模型的矩阵向量表示为31当模型(1.1.1)中的目标函数f(x)是变量x的二次函数,而所有约束都是x的线性函数时称为二次规划问题.二次规划问题的一般形式为

其中A1,A2的表示同线性规划模型类似,c=(c1,c2,⋯,cn)T,d为纯量,G为n×n阶对称矩阵32当模型(1.1.1)中的目标函数f(x)是变量x的二次函只要模型(1.1.1)的函数中有一个关于x是非线性的,就称为非线性最优化问题.非线性最优化问题是最一般的最优化问题,而线性规划和二次规划问题却是相当重要的特殊的最优化问题33只要模型(1.1.1)的函数中有一个关于x是非线性的,就称如果点x∈Rn

满足最优化模型(1.1.1)中的所有约束条件,就称其为可行点(feasiblepoint)所有可行点的全体称为可行域(feasibleregion)F表示可行域,即F={x|ci(x)=0,i=1,2,⋯,m,ci(x)≥0,i=m+1,⋯,p}34如果点x∈Rn满足最优化模型(1.1.1)中的所有约束条件对于一个可行点,考虑不等式约束ci(x)≥0如果有ci(x)=0,就称约束ci(x)≥0在点是有效约束或起作用约束(activeconstraint),并称可行点位于约束ci(x)≥0的边界.如果有ci(x)>0,就称不等式约束ci(x)≥0在点是无效约束或不起作用约束(inactiveconstraint),并称是约束ci(x)≥0的内点在任意可行点,所有的等式约束都被认为是有效约束35对于一个可行点,考虑不等式约束ci(x)≥035在一个可行点,所有有效约束的全体被称为该可行点的有效集,并记为

对于一可行点,如果没有一个不等式约束是有效的,就称是可行域的内点36在一个可行点,所有有效约束的全体被称为该可行点的有效集,例图1.1给出了由下述约束条件给出的可行域F:c1(x)=2x1+3x2+x3-6=0,x1≥0,x2≥0,x3≥0可行点x1可行点x2可行点x337例图1.1给出了由下述约束条件给出的可行域F:37一个可行点x*∈F称为问题(1.1.1)的(全局或总体)最优解,如果有如果上述不等式对所有不同于x*的可行点x严格成立,即

则称x*为严格(全局或总体)最优解.38一个可行点x*∈F称为问题(1.1.1)的(全局或总体)最优对于可行点x*,如果存在一个邻域

使得成立

则称x*为优化问题(1.1.1)的局部最优解,其中δ>0是一个小的正整,范数‖·‖可以是任意向量范数,但一般常用l2范数39对于可行点x*,如果存在一个邻域39如果上述不等式对所有x∈N(x*)∩F,x≠x*严格成立,则称x*为严格局部极小点40如果上述不等式对所有x∈N(x*)∩F,x≠x*严格成立,凸规划如果最优化问题的目标函数是凸的,可行域是凸集,则问题的任何最优解(不一定唯一)必是全局最优解,这样的最优化问题称为凸规划41凸规划如果最优化问题的目标函数是凸的,可行域是凸集,则问1.2凸集和凸函数凸集的定义

定义1.2.1

集合称为凸的,如果对于任意x,y∈D有

换句话说,如果x,y∈D,则连接x与y的直线段上的所有点都在D内线性约束条件421.2凸集和凸函数凸集的定义42凸集定义的几何解释43凸集定义的几何解释43X(1)X(3)X(2)X’X=X’

+(1-)X(2)，(0<<1)x1x2OX’=X(1)+(1-)X(3)，(0<<1)44X(1)X(3)X(2)X’X=X’+(1-)X(X(1)X(3)X(2)X’X=u1X(1)+u2X(2)+u3X(3)x1x2OX’=X(1)+(1-)X(3)，(0<<1)45X(1)X(3)X(2)X’X=u1X(1)+u2X(2凸集的性质两个凸集的交,和以及差仍然是凸集

对于任意非零实数a,集合aD1={ax|x∈D1}也是凸集46凸集的性质两个凸集的交,和以及差仍然是凸集46定理1.2.2

设是凸集,则任意m个点x(i)∈D(i=1,2,⋯,m)的凸组合仍属于D,即有其中证明定理的结论可以用归纳法证明.根据凸集的定义,定理的结论在m=2时显然成立.设结论在m=k时成立,我们证明结论在m=k+1时也成立.47定理1.2.2设是凸集,则任意m个设

考虑任意一组实数

48设48由于,我们有由归纳假设有再由凸集的定义得49由于,我们有4定义1.2.3

设为两非空凸集,若存在非零向量a∈Rn

和实数β,使得

则称超平面

分离了集合D1和D250定义1.2.3设为两如果更有则称超平面H严格分离D1和D251如果更有51

定理1.2.4

设是非空闭凸集,但,则(1)存在唯一的点,使得集合D到点y的距离最小,即(2)是点y到集合D的最短距离点的充分必要条件为52定理1.2.4设是非空闭凸集,§1.3最优性条件最优性条件是指最优化问题(1.1.1)的最优解(局部的或全局的)所必须满足的条件常见并常用的有一阶必要条件和二阶必要条件

先引入两个同最优解相关的基本概念—可行方向和下降方向53§1.3最优性条件最优性条件是指最优化问题(1.1.1)的定义1.3.1

设f(x)为定义在空间Rn上的连续函数,点,若对于方向s∈Rn存在数δ>0使成立

则称s为f(x)在处的一个下降方向.在点处的所有下降方向的全体记为

下面的定理给出了在f(x)连续可微时下降方向同函数f(x)的梯度▽f(x)之间的关系.54定义1.3.1设f(x)为定义在空间Rn上的连续函数,点

定理1.3.2

设函数f(x)在点处连续可微,如存在非零向量s∈Rn使成立

则s是f(x)在点处的一个下降方向

证明对于充分小的α>0,将在点处展开有由于α>0以及,那么存在使得对任意有55定理1.3.2设函数f(x)在点处连续可微结合这两式有这就证明了s是f(x)在点处的下降方向56结合这两式有565757可行方向

定义1.3.3

设为一可行点,s∈Rn,若存在非零方向序列S(k),k=1,2,⋯和正数序列,k=1,2,⋯使成立

且有,则称s是在处的一个可行方向

在点的所有可行方向的全体记为58可行方向定义1.3.3设为一可行有了可行方向和下降方向的概念,我们就很容易直观的理解最优化问题最优解所满足的最优性条件.显然在一个最优解处,不可能有任何一个既是可行的又是下降的方向.因为根据可行方向和下降方向的定义,如果存在任何可行的下降方向,我们就能沿着这个方向找到使函数值更小的可行点,这与最优解的定义相矛盾.这就是由下述定理给出的一个最优解所必须满足的条件.59有了可行方向和下降方向的概念,我们就很容易直观的理解最优化问

定理1.3.4

考虑最优化问题(1.1.1),设x*是问题的一个局部最优解,函数f(x)连续可微,则成立有

证明对于任意的可行方向s∈F(x*),我们证明对可行方向s∈F(x*),存在可行点序列x(k)=x*+αks(k)收敛于x*其中s(k)≠0,αk>0,且s(k)→s,αk→0由泰勒展开式有60定理1.3.4考虑最优化问题(1.1.1),设x

由于x*是局部最优解,对充分大的k有f(x(k))≥f(x*)由此得在上式两端除以αk,再令k→∞取极限得这样就证明了61由于x*是局部最优解,对充分大的k有f(x(k))≥f最优化问题的可行域一般是由于等式或不等式表示的约束条件确定的,然而由定义1.3.3所给出的可行方向同具体的约束条件无任何直接的联系,而由定理1.3.4给出的最优性的条件对确定最优解没有任何直接的帮助.为此,有必要给出由确定可行域的约束条件表示的可行方向62最优化问题的可行域一般是由于等式或不等式表示的约束条件确定的

定义1.3.5

设为一可行点,可行域F由问题(1.1.1)中的约束条件定.设向量s∈Rn非零,且有

则称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,i∈L()线性无关,则成立.65定理1.3.6设所有约束函数ci(x),i=1,2证明任取一个非零的可行方向,则存在可行点序列,其中αk>0,αk→0和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(如果m≠0)是线性函数,ci(x),i=m+1,⋯,p(如果p>m)是凹函数.因此对任意x∈F有76定理1.3.8设凸规划问题的目标函数与约束函数都连续

由于,i=m+1,⋯,p,对任意x∈F有.因此对任意x∈F得这就证明了x*是凸规划问题的全局最优解77由于,i=m+1,⋯,p

Kuhn-Tucker条件中的向量λ*称为最优Lagrange乘子.事实上,引入问题(1.1.1)的Lagrange函数

那么我们可以看到条件(1.3.2)中的第一个方程可以写成

即Lagrange函数L(x,λ)关于x的一阶偏导数在(x*,λ*)处取零值78Kuhn-Tucker条件中的向量λ*称为最优Lagr

如果不考虑在点x*的无效约束,则在点x*的可行性条件ci(x*)=0,i=1,2,⋯,m,i∈I(x*),又可表示成

即Lagrange函数关于λ的一阶偏导数在(x*,λ*)处也取零值因而(x*,λ*)是Lagrange函数的一个平稳点79如果不考虑在点x*的无效约束,则在点x*的可行性条件下面我们讨论最优解的二阶最优性条件,为简化讨论,假定在点x*处严格互补松弛条件成立,并定义在点x*处的有效约束的零可行方向集80下面我们讨论最优解的二阶最优性条件,为简化讨论,假定在点

定义1.3.9

设在可行点x*处严格互补松弛条件成立,如果存在非零向量序列s(k)和正数序列αk>0使有

且有s(k)→s,αk→0,则称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

证明任取非零可行方向s∈Z(x*),则存在可行点序列x(k)=x*+αks(k)使得ci(x(k))=0,i=1,2,⋯,m,i∈I(x*),其中αk→0,s(k)→s.由于对于无效不行约束有λ*i=0,因而对这样的序列有

由各函数的二阶连续可微性,并利用Kuhn-Tucker条件有84证明任取非零可行方向s∈Z(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,⋯

不失一般性,设并令，则且αk→0,因此s∈F(x*)=L(x*)90证明定理的证明采用反证法.90由函数f(x)的连续可微性有由此得在上式两端除以αk后再令k→∞取极限得(1.3.5)由于s∈L(x*)而,有两种可能性91由函数f(x)的连续可微性有91(a),即存在有指标i0∈I(x*)使得sT▽ci(x*)>0,这时由Kuhn-Tucker条件有

这与式(1.3.5)相矛盾,这一矛盾表明不成立,因而有s∈Z(x*)92(a),即存在有指标i0∈I(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)在x§1.4最优化方法概述

以下述简单的无约束最优化问题为例根据最优性的一阶必要条件,最优解必定是方程

的解100§1.4最优化方法概述以下述简单的无约束最优化问题为例

由▽f(x)的连续性,当x→-∞有▽f(x)→-∞和x→∞有▽f(x)→∞,上述方程的解存在但我们却无法得出解的任何解析表达式

因此求最优化问题的解,一般用迭代的方法,

其基本思想为,给定最优解的一个初始估计,记为x(0),方法产生一个逐步改善的有限或无限的迭代序列{x(k)}在{x(k)}是有限点列时,它的最后一个点是Kuhn-Tucker点;在{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然而由于最优解是未知的,选取一个好的初始点也是一个困评价函数

在最优化方法中,一般要选用一个评价函数(MeritFunction)来评价一个迭代点的好坏.对于无约束最优化问题,由于没有约束条件,通常就用目标函数f(x)作为评价函数以无约束极小化问题minf(x)为例,如果有f(x(k+1))<f(x(k)),就说点x(k+1)要好于点x(k),即要求产生的迭代序列{x(k)}使评价函数值单调下降108评价函数在最优化方法中,一般要选用一个评价函数(Me

对于约束最优化问题,则要复杂一些.如果迭代点都是可行点,当然可以直接用目标函数作评价函数,这适用于迭代点都是可行点的方法对于那些迭代点不是可行点的方法,判定一个点的好坏既要考虑目标函数值的大小,还要考虑这个点的可行程度(离可行域的距离)因此这类方法采用的评价函数中一般既包含目标函数又包含约束函数109对于约束最优化问题,则要复杂一些.109迭代的终止条件迭代的终止条件在不同的最优化方法中也是不同的.理论上,根据最优性的一阶必要条件,以及算法的设计思想,Kuhn-Tucker条件是最合适的迭代终止条件

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

121学习本课程所需的数学知识向量、向量的模(范数)、向量的运算、主要参考书目：理论方面：(1)袁亚湘、孙文瑜著,《最优化理论与方法》,科学出版社,2005(2)何坚勇,《最优化方法》,清华大学出版社,2007计算方面：(3)曹卫华,郭正,《最优化技术方法及MATLAB的实现》,化学工业出版社，2005(4)朱德通,《最优化模型与实验》,同济大学出版社,2003122主要参考书目：4其它参考书：(5)卢名高、刘庆吉编著,《最优化应用技术》,石油工业出版社,2002(6)唐焕文,秦学志,《实用最优化方法》,大连理工大学出版社,2004(7)钱颂迪,《运筹学》,清华大学出版社,1990(8)解可新、韩健,《最优化方法》,天津大学出版社,2004123其它参考书：5目录第1章基本概念第2章线性规划第3章线性搜索与信赖域方法第4章无约束最优化方法第5章线性与非线性最小二乘问题第6章二次规划第7章约束最优化的理论与方法124目录第1章基本概念6第一章

基本概念125第一章

基本概念7§1.1最优化问题简介126§1.1最优化问题简介8第1章基本概念1.1最优化问题简介1.2凸集和凸函数1.3最优性条件1.4最优化方法概述127第1章基本概念1.1最优化问题简介9举例例：对边长为a的正方形铁板,在四个角处剪去相等的正方形以制成方形无盖水槽,问如何剪法使水槽的容积最大？解设剪去的正方形边长为x,由题意易知,与此相应的水槽容积为要使其最大,则令得两个驻点：因此,每个角剪去边长为的正方形可使所制成的水槽容积最大．

128举例例：对边长为a的正方形铁板,在四个角处剪去相等的正方例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素.生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:每吨产品的消耗每周资源总量甲乙维生素(公斤)

3020160设备(台)

5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元.但根据市场需求调查的结果,甲药品每周的产量不应超过4吨.问该厂应如何安排两种药品的产量才能使每周获得的利润最大？129例:某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维

定义:

x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数.

目标：要使总利润最大化maxz=5x1+2x2

约束：每周资源总量的限制,30x1+20x2≤1605x1+x2≤15甲种药品每周产量不应超过4吨的限制x1≤4计划生产数不可能是负数,x1≥0x2≥0每吨产品的消耗

每周资源总量甲乙维生素（公斤）3020160设备（台）

5115单位利润(万元)

5２130定义:x1为生产甲种药品的计划产量数

数学模型为每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)5２这是一个如何合理的使用有限的资源,使生产经营的效益达到最大的数学规划问题.在满足一组约束条件的限制下,寻求决策变量x1,x2的决策值,使目标函数达到最大值.131数学模型为每吨产品的消耗每周资源总量甲乙维生素（例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品.已知甲、乙两种原料都含有A、B、C三种化学成分,两种原料分别所含三种化学成分的百分比含量,以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元,厂方希望总成本达到最小,问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分132例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混定义

x1，x2分别为每公斤产品中甲,乙两种原料的数量,目标：使总成本最小化minz=3x1+2x2约束：配料平衡条件,x1+x2=1产品中A、B、C三种化学成分的最低含量12x1+3x2≥42x1+3x2≥23x1+15x2≥5非负性条件x1≥0,x2≥0原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分133定义x1，x2分别为每公斤产品中甲,乙两种原料的数量,数学模型：原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分这是一个原料配制问题,是在生产任务确定的条件下,合理的组织生产,使所消耗的资源数最少的数学规划问题.满足一组约束条件的同时,寻求变量x1和x2的值使目标函数取得最小值.134数学模型：原料化学成分含量（%）产品中化学成分的例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,2.1米和1.5米的圆钢各一根.已知原料长为7.4米,问应如何下料,可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢,可以归纳出8种不同的下料方案：圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4问题归纳为如何混合使用这8种不同的下料方案,来制造100套钢架,且要使剩余的余料总长为最短.135例:某铁器加工厂要制作100套钢架,每套要用长为2.9米,

设表示用第j种下料方案下料的原料根数,j=1,2…,8,目标:使余料总长度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束：三种规格圆钢根数x1+2x2+x4+x6≥1002x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x5+x6+4x8≥100非负取整条件xj≥0(j=1,2…8)且取整数圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104余料（米）00.10.20.30.80.91.１1.4136设表示用第j种下料方案下料的原料根数,j=

数学模型

s.t.

这是一个下料问题,是在生产任务确定的条件下,合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时,寻求变量x1至x8的值,使目标函数取得最小值.圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.11.4且为整数137数学模型圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002最优化的数学模型的一般形式:(1.1.1)其中为连续函数,通常还要求连续可微138最优化的数学模型的一般形式:20目标函数f(x)决策变量x

约束函数ci(x)等式约束ci(x)=0(i=1,2,…..,m)不等式约束ci(x)≥0(i=m+1,m+2,…..,p)min极小化s.t.受约束139目标函数f(x)21根据实际问题的不同要求,最优化模型有不同的形式,但经过适当的变换都可以转换成上述一般的形式例如,对于求目标函数f(x)极大的问题

maxf(x)可转换成求-f(x)极小的问题其中

140根据实际问题的不同要求,最优化模型有不同的形式,但经过适又如对于形如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的不等式约束形式141又如对于形如ci(x)≤0的不等式约束,可同样转换

问题(1.1.1)是最优化问题的一般数学表现形式.

只要在问题中存在任何约束条件,就称为约束最优化问题.只有等式约束

称为等式约束最优化问题

142问题(1.1.1)是最优化问题的一般数学表现形式.2只有不等式约束

称为不等式约束最优化问题.如果既有等式约束,又有不等式约束,则称为混合约束问题.143只有不等式约束25

如果问题中无任何约束条件,则称为无约束最优化问题.

无约束最优化问题的数学模型为

minf(x),x∈Rn

,(1.1.2)

一般简记为

minf(x)

144如果问题中无任何约束条件,则称为无约束最优化问题.2

无约束最优化问题是最优化的基础一则很多实际的最优化问题本身就是无约束最优化问题二则许多约束最优化方法都是通过变换把约束最优化问题转换成无约束最优化问题后,用适当的无约束优化方法求解.145无约束最优化问题是最优化的基础27

根据模型(1.1.1)中函数的具体性质和复杂程度,最优化问题又有许多不同的类型.根据决策变量的取值是离散的还是连续的分为离散最优化和连续最优化

离散最优化通常又称组合最优化,如整数规划、资源配置、邮路问题、生产安排等问题都是离散最优化问题的典型例子

离散最优化问题的求解较之连续最优化问题的求解难度更大,本书只介绍连续最优化的理论与方法.146根据模型(1.1.1)中函数的具体性质和复杂程度,最根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光滑最优化

如果模型(1.1.1)中的所有函数都连续可微,则称为光滑最优化

只要有一个函数非光滑,则相应的优化问题就是非光滑优化问题.本书只研究光滑最优化问题的求解方法147根据连续最优化模型中函数的光滑与否又分为光滑最优化与非光如果所有函数都是变量x=(x1,x2,⋯,xn)T的线性函数,则称(1.1.1)为线性规划问题.线性规划问题的一般形式为148如果所有函数都是变量x=(x1,x2,⋯,xn)T的线上述线性规划模型的矩阵向量表示为其中c=(c1,c2,⋯,cn)T,b1=(b1,b2,⋯,bm)T,b2=(bm+1,⋯,bp)T149上述线性规划模型的矩阵向量表示为31当模型(1.1.1)中的目标函数f(x)是变量x的二次函数,而所有约束都是x的线性函数时称为二次规划问题.二次规划问题的一般形式为