文档介绍：无约束最优化和非线性规划

如图1,有一条河,两个工厂P 和Q位于河岸L(直线)的同一侧,工厂 P 和 Q 距离河岸L分别为8千米和10千米,两个工厂的距离为14千米,现要在河的工厂一侧选一点R,在R处建一个水泵站,向两工厂P、Q 输水,请你给出一个经济合理的设计方案。
8
l
10
Q
14
P
河
图1
R
即找一点 R ,使 R 到P、Q及直线 l 的距离之和为最小。
P
Q
R
Q'
这里建立的是关于x、y的二元函数,可以归结为如下模型:
建立如图3的坐标系,则易得P(0,10)、
Q( 8 ,8)设点R(x , y ) ,
则S(R)=|PR| + |RQ| + |RM|
=

1、梯度
关于梯度:
1)梯度方向是函数在点 X 处增长变化率最大的方向,负梯度方向是下降最快的方向。
设是定义在 n 维欧氏空间上的可微函数,则:
为函数在点X处的梯度,记为
2)梯度的模:
是函数
沿这一方向的变化率。
3)满足的点称为驻点,在区域内部,极值点必为驻点,而驻点不一定为极值点.
2、海赛矩阵
为函数的二阶偏导数矩阵.
特别若为二次函数时,其
海赛矩阵,与点X的位置无关.
3、多元函数Taylor展开
一次展开
二次展开
其中:
3、正定矩阵、负定矩阵、半正定矩阵、半负定矩阵
名称
定义
充要条件
正定矩阵
特征值都大于零的实对称矩阵
半正定矩阵
特征值都大不小于零的实对称矩阵
负定矩阵
特征值都小于零的实对称矩阵
半负定矩阵
特征值都大不大于零的实对称矩阵
不定矩阵
特征值既有大于零又有小于零的实对称矩阵
有两个奇数阶主子式,其中一个为正,另一个为负
其中为各阶主子式。

考虑无约束最优化问题:
1)有海赛矩阵判断驻点性质
已知函数的驻点:
A)若是正定的,则驻点是极小值;
B)若是负定的,则驻点是极大值;
C)若是不定的,则驻点不是极值点;
D)若是半定的,则驻点可能是极值点,可能不是极值点,需视高阶导数的性质而定。
2)极值点的必要条件和充分条件
定义1
对于
问题,设是任意
给定点,P为非零向量,若存在一个数,使得对于
任意,都有
,则称P是
在处的下降方向.
定理1
,则P为在X处的下降方向。
设在可微,如果存在向量,使得
定理2
(一阶必要条件)设 f 在点
可微,如果
是局部
最优解,则必有
定理3
(二阶必要条件)设 f 在点
二阶可微,如果
局部最优解,则必有
是
且Hessian矩阵
是半正定的.
定理4
(二阶充分条件)设 f 在点
二阶可微,如果
最优解。
是问题的严格局部
且Hessian矩阵
是正定的,则
定理5
(充要条件)设 f 是
上的凸函数,
极值点的充要条件是
。若 f 是严格凸函数,
则全局极值点是唯一的。
则
为全局
解法

希望点列,且极限是 f(x)的一个极小值点。
搜索方向序列,对应的搜索方向。
步长序列。
在给定初始点后,使得每次迭代使目标函数值有所下降。
使得