1最优化问题与数学预备知识

第一章 最优化问题与数学预备知识

本章主要内容：最优化的概念 经典最优化中两种类型的问题——无约束极值问

题、具有等式约束的极值问题的求解方法 最优化问题的模型及 分类 向量函数微分学的有关知识 最优化的基本术语

教学目的及要求：理解最优化的概念，掌握经典最优化中两种类型的问题——无

约束极值问题、具有等式约束的极值问题的求解方法，了解最 优化问题的模型及分类，掌握向量函数微分学的有关知识，了 解最优化的基本术语．

教学重点：向量函数微分学的有关知识． 教学难点：向量函数微分学的有关知识． 教学方法：启发式．

教学手段：多媒体演示、演讲与板书相结合． 教学时间：2学时． 教学内容：

§1.1 模型与实例

无约束最优化问题 minf(x),x?(x1,x2,?,xn)T?Rn．

约束最优化问题（S?{x|x?Rn,gi(x)?0,i?1,2,?,m;hj(x)?0,j?1,2,?,l}）

?minfx();?minf(x);?,2m, ,, 即 ?s.t.gi(x)?0i,?1???s.t.x?S.?h(x)?0j,?1?,2l,,.j?其中f(x)称为目标函数，x1,x2,?,xn称为决策变量，S称为可行域，

gi(x)?0(i?1,2,?,m),hj(x)?0(j?1,2,?,l)称为约束条件．

例1 （海洋运输问题）某航运公司承接了一项将客户停放在港口等待运输的N种货物运往目的地的业务．设航运公司运输单位货物i的收益为ci（元/吨），货船能够装载的货物的重量限制为W（吨），相应的容积限制为V（立方米），设ai是单位货物i所占的容积（立方米／吨），bi是货物i可提供的最大数量（吨），，q1为货船的日泊位费（元／日），q2为wi是货物i的日平均装船速度（吨／日）

货船在海上航行时的日费用（元／日），d为航行距离（公里），v为航行速度（公里／日）．问如何确定货船的装载方案，使航运公司获利最大？

解 设xi(i?1,2,?,N)是货船装载货物的数量（吨），则得到该问题的线性分式规划模型

NNq1xiq2d?cx????ii?vi?1wi?maxz?i?1;Nxd?i???wvi?1i??N ?s.t.x?W,?i?i?1?N?aixi?V,??i?1?0?xi?bi.??

§1.2 数学预备知识

1．向量的范数和矩阵的条件数

定义 如果Rn上的实值函数?满足以下三个条件：

（1）?x?Rn，有x?0，同时，当且仅当x?0时，x?0； （2）?x?Rn,??R，有?x???x； （3）?x,y?Rn，有x?y?x?y．

22???xn?(xTx)1/2． 则称x为x的范数．通常取x?x12?x2x的p范数：xp?(?|xi|p)1/p(p?1)．

i?1nx的最大范数：x??max{|xi|1?i?n}．

性质 设?A和?B是定义于Rn中的两种范数，则总存在正数c1和c2，使

?x?Rn，有c1xA?xB?c2xA．

1?i?n定义 设A是n阶方阵，?1,?2,?,?n是A的全部特征值．max|?i|称为A的谱半径，记作?(A)．

设A?Rm?n，称ATA的特征值的正平方根为A的奇异值．A的最大奇异值与

最小非零奇异值之商称为A的谱条件数，记为?(A)，即

?(A)??1(A)， ?t(A)其中?1(A)??2(A)????n(A)为A的所有奇异值，且t?R(A)．

性质 如果A为n阶正定矩阵，?1(A)??2(A)????n(A)?0和

?1(A)??2(A)????n(A)分别为A的特征值和奇异值，则

?i(A)??i(A),i?1,2,?,n，于是?(A)??1(A)． ?n(A)如果A为n阶满秩矩阵，则A的所有奇异值?1(A)??2(A)????n(A)?0，从而?(A)??1(A)． ?n(A)定义 一个n阶满秩矩阵A称为病态的，如果A的n个列向量之间存在着近似线性关系．

性质 条件数可以用来度量矩阵的病态程度． 2．多元函数的梯度、Hesse矩阵及Taylor公式

定义 设f:Rn?R,x?Rn．如果?n维向量p，使得??x?Rn，有

f(x??x)?f(x)?pT?x?o(?x)．

则称f(x)在点x处可微，并称df(x)?pT?x为f(x)在点x处的微分．

如果f(x)在点x处对于x?(x1,x2,?,xn)T的各分量的偏导数

?f(x),i?1,2,?,n都存在，则称f(x)在点x处一阶可导，并称向量 ?xi?f(x)?(?f(x)?f(x)?f(x)T,,?,) ?x1?x2?xn为f(x)在点x处一阶导数或梯度．

定理1 设f:Rn?R,x?Rn．如果f(x)在点x处可微，则f(x)在点x处梯度?f(x)存在，并且有df(x)??f(x)T?x．

定义 设f:Rn?R,x?Rn．d是给定的n维非零向量，e?lim??0d．如果 df(x??e)?f(x)?(??R)

存在，则称此极限为f(x)在点x沿方向d的方向导数，记作

?f(x)． ?d定理2 设f:Rn?R,x?Rn．如果f(x)在点x处可微，则f(x)在点x处沿任何非零方向d的方向导数存在，且

d?f(x)． ??f(x)Te，其中e??ddd是n维非零向量．定义 设f(x)是Rn上的连续函数，x?Rn．如果???0，

使得???(0,?)，有f(x??d)?（>）f(x)．则称d为f(x)在点x处的下降（上升）方向．

定理3 设f:Rn?R,x?Rn，且f(x)在点x处可微，如果?非零向量

d?Rn，使得?f(x)Td?（>）0，则d是f(x)在点x处的下降（上升）方向．

定义 设f:Rn?R,x?Rn．如果f(x)在点x处对于自变量

?2f(x)x?(x1,x2,?,xn)的各分量的二阶偏导数(i,j?1,2,?,n)都存在，则称函

?xi?xjT数f(x)在点x处二阶可导，并称矩阵

??2f(x)?2??x1??2f(x)?2?f(x)???x2?x1?????2f(x)???xn?x1?2f(x)?2f(x)????x1?x2?x1?xn??2f(x)?2f(x)???2?x2?x2?xn?

?????22?f(x)?f(x)????xn?x2?2xn?为f(x)在点x处的二阶导数矩阵或Hesse矩阵．

定义 设h:Rn?Rm,x?Rn，记h(x)?(h1(x),h2(x),?,hm(x))T，如果

hi(x)(i?1,2,?,m)在点x处对于自变量x?(x1,x2,?,xn)T的各分量的偏导数

?hi(x)(i?1,2,?,m;j?1,2,?,n) ?xj都存在，则称向量函数h(x)在点x处是一阶可导的，并且称矩阵

??h1(x)??x1???h2(x)??m?nh(x)???x1?????hm(x)??x1??h1(x)??xn???h2(x)?h2(x)???x2?xn??

??????hm(x)?hm(x)???x2?xn????h1(x)?x2为h(x)在点x处的一阶导数矩阵或Jacobi矩阵，简记为?h(x)．

例2 设a?Rn,x?Rn,b?R，求f(x)?aTx?b在任意点x处的梯度和Hesse矩阵．

解 设a?(a1,a2,?,an),x?(x1,x2,?,xn)，则f(x)??akxk?b，

TTk?1n因

?f(x)?ak(k?1,2,?,n)，故得?f(x)?a． ?xk?2f(x)又因?0(i,j?1,2,?,n)，则?2f(x)?O．

?xi?xj例3 设Q?Rn?n是对称矩阵，b?Rn,c?R，称f(x)?次函数，求f(x)在任意点x处的梯度和Hesse矩阵．

解 设Q?(qij)n?n,x?(x1,x2,?,xn)T,b?(b1,b2,?,bn)T，则

n1nnf(x1,x2,?,xn)???qijxixj??bkxk?c，

2i?1j?1k?11TxQx?bTx?c为二2由于f(x1,x2,?,xn)中所有含xi的项为

1qi1xix1???qi,i?1xixi?1?qiixi2?qi,i?1xixi?1???qinxixn?bixi，

2?f(x)n所以??qijxj?bi，

?xij?1

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库1最优化问题与数学预备知识在线全文阅读。