优化-第123章复习市公开课特等奖市赛课微课一等奖课件

要求：空集和单元素集也是凸集。三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸。等价定义（凸集）：设凸集与性质

定义（凸集）：若集合中任意两点连线都属于，则称为凸集。因为两点

连线上任一点能够表示为

凸集几何特征凸集代数特征称集合为凸集。恒有凸集、凸函数与凸规划

第1页

例1:证实集合S={x∣Ax=b}是凸集，其中A为m

n矩阵，b为m维向量。凸集与性质

证实:即所以即S是凸集。例2:集合是凸集,称为超平面，c为n维向量。例3：邻域是凸集。第2页定义：设那么称是

凸组合。

性质2：S是凸集

S中任意有限个点凸组合属于S。凸集与性质

性质1：设是凸集，则也是凸集。注：不一定是凸集。第3页定义（凸函数）:设集合D

Rn为凸集，函数f:D

R,若x,y

D,

(0,1)，都有

f(

x+(1-

)y

)≤f(x)+(1-

)f(y)

，则称f(x)为凸集D上凸函数。若深入有上面不等式以严格不等式成立，则称f(x)为凸集D上严格凸函数。当-f(x)为凸函数(严格凸函数)时，则称f(x)为凹函数(严格凹函数)。严格凸函数凸函数严格凹函数凸函数----推广到多元函数第4页定理(一阶条件):

设D

Rn为非空凸集，函数f:D

R在D上可微，则(1)f在D上为凸函数任意x，y

D，恒有

f(y)

≥f(x)+

fT(x)(y-x)

(1)(2)

f在D上为严格凸函数任意x≠y

D，恒有

f(y)>f(x)+

fT(x)(y-x).(2)

凸函数判定定理第5页定理（二阶条件）:设D

Rn为含有内点非空凸集，函数f:D

R在D上二次可微，则a)f在D上为凸函数

x

D，2f(x)

半正定；b)若

x

D，2f(x)

正定，则f在D上为严格凸函数。回想：一个矩阵半正定充要条件是全部主子式非负；一个矩阵正定充要条件是全部次序主子式非负。凸函数判定定理第6页例：设二次函数(1)：若为半定矩阵，在中为凸函数；(2)：若为正定矩阵，在中为严格凸函数。例：判断f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？次序主子式都是正，所以正定，所以f(x)在凸集D上是严格凸函数。凸函数判定定理第7页定义（凸规划）:考虑以下非线性规划当都是凸函数时,称规划为凸规划凸规划第8页性质1:

设(1)为凸规划，则

i)(1)可行集R是凸集；

ii)(1)最优解集是凸集；

iii)(1)任何局部极小点都是全局极小点。

性质2:

设(1)为凸规划，若f(x)在非空可行集R上是严格凸函

数，则(1)全局极小点是唯一。

证实：见书中(P24)定理3.11.注:非线性规划局部最优解不一定是全局最优解,其可行解和最优解集也不一定是凸集,甚至不是连通集.如果是凸规划,就有很多好性质。凸规划性质证实：见书中(P23)定理3.9、3.10.第9页普通情况下

,为正整数,分别表示约束条件个数和决议变量个数,为价值向量,

为决议向量,通常

为已知常数。称m为线性规划阶数,称n为线性规划维数。线性规划标准形第10页怎样化成标准形若要求目标函数是:maxz=cTx,只需将目标函数最大值变换为求目标函数最小值,即maxz=min

(-z)。令zˊ=-z,于是得到：min

zˊ=-cTx。

目标函数转换第11页若约束方程组为不等式约束条件为“”形式不等式,则在“”号左边加入非负松弛变量;把原“”形不等式变为等式;约束方程转换：由不等式转换为等式称为松弛变量对应松弛变量在目标函数中价值系数取值为0。怎样化成标准形第12页约束条件为“”形式不等式,则可在“”号左端减去一个非负剩下变量。约束方程转换：由不等式转换为等式称为剩下变量对应剩下变量在目标函数中价值系数取值为0。怎样化成标准形第13页

若存在取值无约束变量，可令

其中：

变量转换若，可令，显然怎样化成标准形第14页例1:试将以下线性规划问题化成标准形任何形式线性规划问题都能够化成标准形。现举例以下：怎样化成标准形第15页解：令x3=x4-x5,x4,x50,

(1)式左端加上非负松弛变量x6

,(2)式左端减去非负剩下变量x7,则可将上述线性规划问题化成以下标准形:怎样化成标准形第16页可行解（或允许解）:满足约束条件解x=(x1,x2,···,xn)T

称为线性规划问题可行解;可行域：全部可行解集合称为可行解集或可行域。3.最优解:使得目标函数取到最小值可行解称为线性规划问题最优可行解，简称为最优解或者解。

线性规划问题标准形为：线性规划基本概念第17页基:假设A是约束方程组系数矩阵,其秩数为m,B是矩阵A中由m列组成非奇异子矩阵(B行列式值不为0），则称B是线性规划问题一个基。矩阵B是由m个线性无关列向量组成,不失普通性,可假设:称Pj(j=1,2,···,m)为基向量,与基向量Pj相对应变量xj(j=1,2,···,m)为基变量,不然称为非基变量。线性规划基本概念第18页5.基本解：

若令(2.1)式中非基变量xm+1=···=xn=0,求出一个解x=(x1,x2,···,xm,0,···,0)T,这个解非0分量数目小于方程个数m,称x为基本解。线性规划基本概念当基本解中有一个或者一个以上基变量是0时，称这个基本解是退化基本解。第19页基本可行解:满足非负约束条件基本解称为基本可行解.基本可行解非0分量数目小于m,都是非负。7.可行基:对应于基本可行解基称为可行基.约束方程组Ax=b基本解数目至多是Cnm个.普通地讲,基本可行解数目要小于基本解数目,至多相等.以上提到几个解概念,可用以下列图来表示:基解可行解基本可行解线性规划基本概念第20页1947年,美国学者GeorgeDantzig(丹茨格)提出了求解线性规划单纯形法,为线性规划推广奠定了基础。从可行域一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)迭代过程，转移条件是使目标函数值得到改进(逐步变优),当目标函数到达最优值时,问题也就得到了最优解。基本思想单纯形法第21页重复以上过程，能够深入改进基本可行解，直到全部时为止。单纯形法基本原理基变量基变量非基变量非基变量初始基本可行解改进基本可行解目标函数值减小了进基变量确实定离基变量确实定f0是最优值,当前基本可行解是最优解第22页以极小化问题为例每次迭代必出现以下三种情形之一(1).这时当前基本可行解就是最优解。(2).这种情形下，我们知道取任何正数，总能得到可行解。所以当无限增大时，目标函数趋于负无穷，所以解无界。(3)，大于零。这时求出新基本可行解，经迭代使目标函数下降。单纯形法收敛性第23页zk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1初始单纯形表……………………………………………………使用表格形式单纯形方法1.结构单纯形表

xk是进基变量，是离基变量；主元把xk

所对应列向量pk变成所对应列向量，即是单位向量。把xk和

位置对换，第24页对应新目标函数值即为：使用表格形式单纯形方法2.高斯主元消去法以yrk

为主元素进行Gauss消元:将第r行每个元素除以yrk

:将第r行每个元素乘以–yik/yrk

加到第i行(i=1,···,m,

i≠r)将第r行每个元素乘以–(zk–ck)

/yrk

加到检验数行第25页经过Gauss消元后，针对于新基B1基本可行解为：使用表格形式单纯形方法2.高斯主元消去法第26页minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7例3.利用单纯形算法求解以下线性规划问题。解：

x6，x7，x5对应是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。第27页xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002

-1101-11-10-1001010110-1x6x1x5112

02-1100-2cB1102131/2--2100x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7c

000001

1

第28页x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

全部判别数zj-cj≤0

，所以到达最优解第29页两阶段法和大M法对于标准线性规划问题(简写为LP):这里A=(aij)m

n,b≥0,

秩(A)=m.使用单纯形方法，需要给定一个初始基本可行解，方便从这个基本可行解出发，求改进基本可行解。若A中包含m阶单位矩阵，则初始基本可行解轻易找到。若A中不包含m阶单位矩阵，初始基本可行解怎么找？初始基本可行解怎么找？

第30页设A中不包含m阶单位矩阵引入人工变量得到(5)一个基本可行解：显然(5)系数矩阵中包含一个m阶单位矩阵，取做基矩阵，人工变量人为引入变量个数变多了，线性规划维数变大了把每个等式增加一个非负变量，得到怎样排除人工变量，求出原线性规划最优解呢？惯用方法：两阶段法大M法第31页

两阶段法第一阶段是用单纯形法消去人工变量(可能话)，即把人工变量都变换成非基变量，求出原来问题一个基本可行解。消去人工变量其中一个方法是解以下一个问题：其中e是分量全为1m维列向量，两阶段法基本思想第32页

两阶段法基本思想设(6)最优基本可行解是实际上，假如(LP)存在可行解，则是(6)可行解，对应(6)目标函数值是矛盾！是(6)最优解这时，m个基变量都是原来变量，是(6)基本可行解，(i)若，则标准线性规划(LP)没有可行解；(ii)若，且xa

分量都是非基变量。是(LP)一个基本可行解。第33页

两阶段法基本思想设(6)最优基本可行解是此时最优值是0.这时，可用主元消去法，把原来变量中非基变量引进基，替换出基变量中人工变量，此时最优值一直都保持是0，从而就

得到(LP)一个基本可行解。第一阶段结束，得到原来线性规划一个基本可行解。(iii)若，且xa

一些分量是基变量。可化为第(ii)种情况，第34页两阶段法第二阶段，就是从得到基本可行解出发，用单纯形法求问题(*)最优解。第35页例1.利用两阶段法求解以下线性规划问题。

min-2x1-x2

s.t.x1+x2≥

2x1-x2≥1x1≤3x1,x2≥0min-2x1-x2

s.t.x1+x2-

x3=

2x1-x2-

x4=1x1+x5=3xj≥0,j=1,2,…,5解：

1.首先把问题化成标准形式：系数矩阵中不包含单位矩阵第36页minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7

2.

引进人工变量x6,x7结构单位矩阵，求解下面问题3.

x6，x7，x5对应是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。第37页xBx1x2x3x4x5x6

x7

11-100101-10-10011000100x6x7x5213

20-1-100002

-1101-11-10-1001010110-1x6x1x5112

02-1100-2cB1102131/2--2100x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000minx6+x7

s.t.x1+x2-

x3+x6=

2x1-x2-

x4+x7

=1x1+x5=3xj≥0,j=1,2,……,7c

000001

1

第38页x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

4.全部判别数zj-cj≤0

，所以到达最优解。从表中可看到：在一阶段问题最优解中，人工变量x6，x7都是非基变量。所以我们得到了原线性规划基本可行解

第39页xBx1x2x3x4x5

cB-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2min-2x1-x2

s.t.x1+x2-

x3=

2x1-x2-

x4=1x1+x5=3xj≥0,j=1,2,…,5

003/21/20c

-2-1000

5.第二阶段，修改最终单纯形表。x2x1x501-1/21/201/2-1/210-1/2-1/201/21/2001/21/21-1/2-1/21/23/23/2

00000-1-1000xBx1x2x3x4x5x6

x7

cBc

000001

1

修改检验数和目标函数，去掉人工变量对应列，其它不变。第40页xBx1x2x3x4x5

x2x1x3233

000-1-3cB-1-20----3-1-2001-1/21/2010-1/2-1/20001/2-1/21x2x1x51/23/23/2

003/21/2001001100-11001-12c

-2-1000

6.这时，检验数全部小于等于0，得到最优解：

x=(3,2,3,0,0)T目标函数最小值为：f=-2*3-1*2=-8第41页大M法基本思想在约束中添加人工变量，M>0,e为全1m维列向量。(7）是可行,基本可行解因为大M是充分大正数，在极小化目标函数过程中，就会迫使人工变量离基。同时修改目标函数，加上处罚项经过求解（7）而取得(*)最优解第42页用单纯形法求解(7)，假如(7)存在有限最优解，设为(ii)当时，(7)无可行解。(i)当时,x*是问题(*)最优解。实际上，假如(*)存在可行解，则是(7)可行解，对应(7)目标函数值是M是充分大正数是(7)最优解矛盾！第43页在单纯形表中假如(7)不存在有限最优解(i)当时，问题(LP)无界;(ii)当时，即，问题(LP)无可行解.第44页例3.利用大M法求解以下线性规划问题。

minx1+x2-3x3

s.t.x1-2x2+x3≤112x1+x2-4x3≥3x1-2x3=1x1,x2,x3≥0解：

1.将问题化成标准形式，引进松弛变量x4,x5minx1+x2-3x3

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5=3x1-2x3=1xj,≥0,j=1,2,…,5系数矩阵中不包含单位矩阵第45页2.引进人工变量x6,x7

结构单位矩阵，用单纯形法求解以下问题minx1+x2-3x3+M(x6+x7)

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5+

x6=3x1-2x3+

x7=1xj,≥0,j=1,2,…,73.

x4，x6，x7对应是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。第46页xBx1x2x3x4x5x6

x7

x4x6x711313M-1M-1-6M+30-M00x4x6x11011

0M-110-M01-3McB0MM113/21--1--0M1x4x2x11211011c

11-300M

M1-21100021-40-11010-20001minx1+x2-3x3+M(x6+x7)

s.t.x1-2x2+x3+

x4=112x1+x2-4x3-x5+

x6=3x1-2x3+

x7=1xj,≥0,j=1,2,…,70-23100-10100-11-210-200010031-22-50100-11-210-20001

0010-11-M-1-M4----第47页

000-1/3-1/31/3-M2/3-M419xBx1x2x3x4x5x6

x7

cBx4x2x11211011c

11-300M

M0031-22-50100-11-210-20001

0010-11-M-1-M4----x3x2x1-3110011/3-2/32/3-5/30100-11-21002/3-4/34/3-7/34.检验数全部小于等于0，而且人工变量全取0，

于是得到最优解：最优值为：f=9+1-3*4=-2

x=(9,1,4)T第48页(1)对称形式 特点：目标函数求极小值，约束条件“≥”，变量非负;目标函数求极大值，约束条件“≤”，变量非负;对偶定义互为对偶第49页普通称不含有对称形式一对线性规划为非对称形式对偶规划。

方法一：对于非对称形式线性规划，能够先化成对称形式线性规划，写出其对偶规划。(2)非对称形式对偶问题对偶定义第50页例1：写出以下线性规划问题对偶问题第51页第52页原问题对偶问题第53页例2：标准形式对偶问题对偶定义对偶问题第54页变量数：n个第j个变量≤0第j个变量≥0第j个变量是自由变量约束条件：m个第i个约束类型为“≥”第i个约束类型为“≤”第i个约束类型为“＝”目标函数max对偶问题（原问题）约束条件：n个第j个约束类型为“≤”第j个约束类型为“≥”第j个约束类型为“＝”变量数：m个第i个变量≤0第i个变量≥0第i个变量是自由变量目标函数min原问题（对偶问题）方法二：按照下面对应关系直接给出其对偶规划:(2)非对称形式对偶问题第55页变量数：n个第j个变量≤0第j个变量≥0第j个变量是自由变量约束条件：m个第i个约束类型为“≥”第i个约束类型为“≤”第i个约束类型为“＝”目标函数max对偶问题（原问题）约束条件：n个第j个约束类型为“≤”第j个约束类型为“≥”第j个约束类型为“＝”变量数：m个第i个变量≤0第i个变量≥0第i个变量是自由变量目标函数min原问题（对偶问题）第56页定理1(对称性)对偶问题对偶是原问题对偶问题基本定理第57页定理2(弱对偶定理)设

分别是原问题

和对偶问题可行解,

则

原问题任一可行解对应目标函数值大于其对偶问题任一可行解对应目标函数值。对偶问题基本定理第58页定理3(最优性定理)设

分别是原问题

和对偶问题可行解,

若

则分别是它们最优解。对偶问题基本定理定理4(强对偶定理)若原问题

有最优解，则其对偶问题一定有最优解,

且它们目标函数值相等。第59页n=1时，是一维无约束优化问题---------第三章第1部分内容n>1时，是多维无约束优化问题---------第三章第2部分内容n元函数求解无约束优化问题第60页找初始点判断当前点是否满足终止条件下一个迭代点最优解(a)找初始点(b)终止条件(c)迭代格式找步长和下降方向，确定下一个迭代点不一样对应不一样算法是否循环线搜索迭代法框架分析不一样对应不一样算法第61页求目标函数f(x)极小：因为这项工作是求以

为变量一元函数极小点，故常称这一过程为（准确）一维搜索或线搜索迭代法框架分析----一维搜索（准确）线搜索或一维最优化，确定步长为最正确步长。第62页在搜索方向上所得最优点处梯度和该搜索方向正交。定理设目标函数含有一阶连续偏导数，规则产生则有（准确）一维搜索一个主要性质按下述证实：结构函数，则得即是函数极小点，所以第63页“成功—失败”法（进退法）基本思想：一个试探法：从一点出发，按一定步长搜索新点，若搜索成功，加大步长继续搜索；若搜索失败，缩小步长小步后退。第64页“成功—失败”法（进退法）步骤1：选取初始点x∈R,初始步长h>0及精度ε>0，步骤2：计算步骤3：若搜索成功,转步骤4；不然，搜索失败，转步骤5。步骤4：令x:=x+h,转步骤2。步骤5：判断若停顿迭代，；不然令转步骤2。缺点：效率低。优点：能够求搜索区间。注意：初始步长不能选得太小第65页例1：设给定初始点为a及初始步长为h,求搜索区间[c,d]1)前进运算首先计算f(a),f(a+h),假如f(a)>f(a+h),则步长加倍,计算f(a+3h).若f(a+h)<=f(a+3h),则c=a,d=a+3h;不然将步长再加倍，并重复上面运算.2)后退运算假如f(a)<f(a+h),则将步长缩为原来1/4并改变符号，即将步长改为-h/4,假如f(a)<f(a-h/4),则c=a-h/4,d=a+h;不然将步长加倍，并继续后退。注意:1.h选择要适当.(太大含多个单峰区间,太小迭代次数多)；2.f(x)单调时无结果,(加迭代次数限制)；

“成功—失败”法（进退法）第66页0.618法（黄金分割法）0.618法是求单峰函数极值一个试探法，有书上也称为区间收缩法。在搜索区间[a,b]上插入两个点，将分为三个子区间，经过比较2个插入点函数值大小，可删去左边或者右边区间，使搜索区间缩短。重复上述过程，使搜索区间不停缩短，当区间缩短到一定程度时，区间上各点都能够作为极小点近似。仅适合用于求解单峰函数第67页例：利用“成功-失败”法求函数搜索区间，取初始点，步长解：取初始点，步长“成功—失败”法----算例得到搜索区间为第68页0.618法（黄金分割法）

定义(单峰函数)：设f(x)是定义在[a,b]上函数，若1）

x*∈[a,b]是φ在[a,b]上最小点，2）若对任意x1,x2,a≤x1<x2

≤b,满足：1º若x2

≤x*，则f(x1)>f(x2);

2º若x1

≥x*，则f(x1)<f(x2).则称f(x)为[a,b]上单峰函数。

第69页定理：设f：R→R在[a,b]上是单峰函数，a≤x1<x2

≤b。那么1°若f(x1)≥f(x2)，则x*

∈[x1

,b],如左下列图2°若f(x1)<f(x2)，则x*

∈[a,x2

],如右下列图

α

x1

x2

b

αx1

x2

b0.618法（黄金分割法）缩短区间第一个标准---去坏留好标准选二点x1

<x2

,比较f(x1

)与f(x2

),可去掉[a,x1

]或者[x2,b].第70页考虑条件：

2°对称标准：x1–a=b-x2……①

（使“坏”情况去掉，区间长度大于“好”情况）

3°保持缩减比标准t=(保留区间长度／原区间长度)不变。

（使每次保留下来节点，x1或x2，在下一次比较中成为一个对应百分比位置节点）。推导缩减比t:如图设第一次保留[a,x2](去掉[x2,b]),第二次保留长度为[α,x1],则αx1

x2b0.618法（黄金分割法）第71页整理②：

x2=a+t(b-α)

x1=a+t(

x2-α)结合①式：t2+t–1=0

故

t≈0.618注意:上式有

t2=1-t,故有

x1=a+(1-t)(b-a)=a+0.328(b-a)x2=a+t(b-a)=a+0.618(b-a)0.618法（黄金分割法）第72页

优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小，程序简单缺点：收敛速度慢。黄金分割法（0.618法）优缺点0.618法（黄金分割法）第73页例：试用0.618法求目标函数最优解。给定初始区间[0,2]，收敛精度解：第一次区间缩短计算过程：计算两点及对应函数值：作数值比较，可见,再做置换：0.618法----算例第74页第二次区间缩短计算过程：作数值比较，,再做置换：第三次区间缩短计算过程：作数值比较，,再做置换：第75页各次迭代结果以下：迭代次数x1x2f

(x1)f

(x2)[a,b]|b-a|第1次0.7641.236-0.08210.4126[0,1.236]1.236第2次0.4720.7640.1612-0.0821[0.472,1.236]0.788第3次0.7640.944-0.0821-0.0468[0.472,0.944]0.472第4次0.6520.764-0.0268-0.0821[0.652,0.944]0.292第5次0.7640.832-0.0821-0.0881[0.764,0.944]0.230第6次0.8320.906-0.0881-0.0683[0.764,0.906]0.124缺点：收敛速度慢优点：不要求函数可微，且每次迭代只需计算一个函数值，计算量小第76页

设f(x)在

[a,b]上可微，求函数f在[a,b]极小点，就是求函数导数为零点。假如，则在(a,b)内一定存在一点x，使得。为求极小点，可取，若

,x为最小点,x=x*;,x0

在上升段,x*<x0，去掉[x0

,b];

,x0

在下降段,x*>x0，去掉[a,x0].二分法---基本思想第77页用或者作新区间[a,b]，继续这个过程，逐步将区间[a,b]缩小，当区间[a,b]长度充分小时，可将[a,b]中点取做极小点近似点。二分法---基本思想第78页优点：计算量较少，而且总能收敛到一个局部极小点。缺点：收敛速度较慢二分法---计算步骤步骤1：计算步骤2：若，令，转步骤3；若，令，转步骤3；若，停顿，。步骤3：若，则，停顿，不然，转步骤1.第79页例：试用二分法求目标函数最优解。给定初始区间[0,2]，收敛精度解：在[0,2]内有极小点。二分法----算例第一次区间缩短计算过程：因为所以函数第80页第二次区间缩短计算过程：第三次区间缩短计算过程：第81页各次迭代结果以下：迭代9次后，|b-a|=0.00391<0.004,故迭代次数x0=(a+b)/2f’(x0)[a,b]|b-a|第1次x0=11[0,1]1第2次x0=1/2-5/4[1/2,1]1/2第3次x0=3/4-5/16[3/4,1]1/4第4次x0=7/819/64[3/4,7/8]1/8第5次x0=13/16-0.0195[13/16,7/8]1/16第6次x0=27/320.0136[13/16,27/32]1/32第7次x0=53/640.0574[13/16,53/64]1/64第8次x0=105/1280.0184[13/16,105/128]1/128第9次x0=209/256-0.0004[209/256,105/128]1/256第82页牛顿法（Newton）---基本思想对f(x)在xk点二阶泰勒展开：略去高阶项得两边对x求导，令，得到牛顿法是一个函数迫近法，基本思想是：在极小点附近用函数二阶泰勒多项式近似代替目标函数，从而求得目标函数极小点近似值。第83页牛顿法（Newton）---基本思想取作为新迭代点，继续迭代，直到抵达精度，这么就得到了函数f一个驻点。第84页牛顿法（Newton）---计算步骤步骤1：给定初始点令。步骤2：计算。步骤3：若，停顿，，不然转步骤4。步骤4：计算令，转步骤2。特点：收敛速度快，局部二阶收敛。缺点：须计算二次导数，工作量大；对初始点要求高，要求初始点离极小点不太远，不然有可能使极小化发散或收敛到非极小点；局部收敛。第85页例：试用Newton法求函数最优解。解：Newton法----算例第86页Newton法----算例Newton法收敛速度快得到近似解第87页用

在2个或3个点函数值或导数值，结构2次或3次多项式作为

近似值，以这多项式极小点作为新迭代点。包含3点2次，2点2次，4点3次，3点3次，2点3次等插值法.下面以3点2次插值法（二次插值法）为例：利用在区间函数值作出以下二次插值多项式它应满足条件（1）插值法（2）（3）第88页从极值必要条件求得求出系数和，就可得到极小点表示式。插值法---求二次插值多项式极小点第89页1.寻找满足以下条件点（成功失败法寻找），成为两头大中间小点：x1<

x

2<x3，f(x1)>f(x2),f(x2)<f(x3

)2.两头大中间小，可得a2>0

,则为g(x)极小值点，且3.若，则迭代结束，取，不然在点

中，选取使f(x)最小点作为新x2，并使新x1，x3各是新x2近旁左右两点，继续进行迭代，直到满足终止准则。插值法---算法思绪：第90页2）用二次插值法迫近极小点(1)相邻三点及其函数值:x1=0,x2=1,x3=2;

f1=2,f2=1,f3=18.例用二次插值法求函数f(x)=3x3-4x+2极小点，

给定x0=0,h=1,ε=0.2。解：1）确定初始搜索区间初始区间[a,b]=[0,2],另有一中间点x2=1。依据公式计算差值多项式极小点第91页(2)在新区间，相邻三点及其函数值:

x1=0,x2=0.555,x3=1;

f1=2,f2=0.292,f3=1.故新区间[a,b]=[a,x2]=[0,1]，应继续迭代。x1=0,x2=1,x3=2;f1=2,f2=1,f3=18因为依据公式计算差值多项式极小点第92页故新区间[a,b]=[x2,b]=[0.555,1]，迭代终止。x1=0,x2=0.555,x3=1;f1=2,f2=0.292,f3=1因为故第93页目标是找中一点，使对，都有，称为此无约束最优化问题全局极小点。

无约束最优化问题：求解无约束最优化问题计算方法称为无约束最优化方法。多维无约束最优化方法第94页无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中基本方法---无约束优化方法：利用函数一阶或二阶导数方法收敛速度快，需要计算梯度或者Hesse矩阵：仅利用函数值信息，寻找最优解不包括导数，适用性强，但收敛速度慢可求得目标函数梯度时使用解析法在不可能求得目标函数梯度或偏导数时使用直接法我们介绍解析法第95页最优性条件(OptimalityConditions)所谓最优性条件，是指最优化问题最优解所要满足必要条件或充分条件。解析法要用到目标函数梯度或者Hesse矩阵，轻易想到利用一阶必要条件将无约束优化问题转化成一个梯度为0确定方程组。这里用到一阶必要条件就是最优性条件。第96页定理(一阶必要条件)

设，若为