最优化方法教案(1)Word文件下载.doc
《最优化方法教案(1)Word文件下载.doc》由会员分享，可在线阅读，更多相关《最优化方法教案(1)Word文件下载.doc（34页珍藏版）》请在冰点文库上搜索。
其中，是待定的参数，通过实验测得和的15组数据列表如下，如何确定参数？
i
1
2
3
4
5
6
7
8
50
55
60
65
70
75
80
85
34.78
28.61
23.65
19.63
16.37
13.72
11.54
9.744
9
10
11
12
13
14
15
90
95
100
105
110
115
120
8.261
7.03
6.005
5.147
4.427
3.82
3.307
建立数学模型：
测量点与曲线对应的点产生“偏差”，即
得如下无约束最优化问题：
通常采用最小二乘法。
1.2最优化问题的数学模型
一、最优化问题的数学模型
1.定义1：
设向量.
若，则记或；
若，则记或。
2．一般模型：
，
（1）
其中，；
，，是关于变量的实值连续函数，一般可假定它们具有二阶连续偏导数。
3．向量模型：
其中，称为目标函数；
，称为约束函数；
满足约束条件
（2），（3）的点称为容许解或容许点（或可行解）；
可行解的全体称为容许域（或可行域），记为R；
满足
（1）的容许点称为最优点或最优解（或极小（大）点），记为；
称为最优值；
不带约束的问题称为无约束问题，带约束的问题称为约束问题；
若目标函数，约束函数，都是线性函数，则称为线性规划；
若其中存在非线性函数，则称为非线性规划；
若变量只取整数，称为整数规划；
若变量只取0，1，称为0—1规划。
注：
因，，则最优化问题一般可
写成
二、最优化问题的分类
1.3二维问题的图解法
例1.
解：
1.由全部约束条件作图，求出可行域R：
凸多边形OABC
2.作出一条目标函数的等值线：
设，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方向平移可使值增大。
3.平移目标函数等值线，做图求解最优点，再算出最优值。
顶点是最优点，即最优解，最优值。
分析：
线性规划问题解的几种情况
（1）有唯一最优解（上例）；
（2）有无穷多组最优解：
目标函数改为
（3）无可行解：
增加约束，则。
（4）无有限最优解（无界解）：
例
结论：
（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。
（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。
例2.
目标函数等值线：
C为最优点，得
定义2：
在三维及三维以上的空间中，使目标函数取同一常数的点集称为等值面。
1.4预备知识
（一）线性代数
一、n维向量空间
1.向量的内积：
设，则
内积为
2.向量的范数（或长度或模）：
设，若实数具有以下
性质：
（1）当且仅当时；
（2）；
（3）.
则称为上的向量的范数，简记为。
规定了向量范数的线性空间称为线性赋范空间,记为.
3.常见的向量范数
向量的范数：
，
三个重要的向量范数：
，，
若无特殊说明，本书中的指的是。
4.间的距离：
5.与正交：
若非零向量组，…，的向量两两正交，称它们是正交向量组。
6.标准正交基：
，…，是n个正交的单位向量，即
二、特征值和特征向量
定义：
设为n阶方阵，存在数和非零向量，使
则称为矩阵的特征值，非零向量为矩阵属于特征值的特征向量。
三、正定矩阵
设为n阶实对称方阵，若对任意非零向量，均有，则称为正定二次型，为正定矩阵，记>
0。
；
若，半正定二次型，为半正定矩阵。
类似有负定（半负定）二次型，负定（半负定）矩阵的概念。
实对称方阵为正定矩阵（负）的特征值均为正（负）
的各阶顺序主子式均为正（奇数阶为负，偶数阶为正）
实对称方阵为半正定矩阵的特征值均非负
的各阶顺序主子式均为非负
（二）数学分析
一、梯度和海色（Hesse）矩阵
1.多元函数的可微性
可微定义：
设，，若存在维向
量，对，总有
（1）
则称函数在点处可微。
式
（1）等价于
（2）
其中，是的高阶无穷小。
定理1：
（可微的必要条件）若函数在点处可微，则在该点关于各个变量的偏导数存在，且
2.梯度
（1）概念
梯度：
令
则称为n元函数在处的梯度（或记为）。
又称为关于的一阶导数。
式
（2）等价于
（3）
等值面：
在三维和三维以上的空间中，使目标函数取同一
数值的点集称为等值面（曲面）。
方向导数：
设在点处可微，向量，是方向上的单位向量，则极限
称为函数在点处沿方向的方向导数，记作。
方向导数的几何解释：
方向导数表示函数在点处沿方向的的变化率。
函数的下降（上升）方向：
设是连续函数，点，为一方向，若存在，对于，都有
（）
则称方向是函数在点处的下降（上升）方向；
结论1：
若方向导数，则方向是在点处的下降方向；
若方向导数，则方向是在点处的上升方向；
（2）性质
【性质1】：
梯度为等值面在点处的
切平面的法矢（向）量。
【性质2】：
梯度方向是函数具有最大变化率的方向。
定理2：
设在点处可微，则方向导数
其中，是方向上的单位向量，为梯度与的夹角。
结论2：
1）与梯度方向成锐角的方向是上升方向；
与梯度方向成钝角的方向是下降方向；
2）梯度方向是函数值上升最快的方向，称为最速上升方向；
负梯度方向是函数值下降最快的方向，称为最速下降方向。
（3）几种特殊函数的梯度公式
（1），为常数；
（2），其中；
（3）；
（4）若是对称方阵，则.
例
3.泰勒（Taylor）公式与Hesse矩阵
性质1：
设具有一阶连续偏导数，则
（*）
其中，，即介于与之间。
性质2：
设具有二阶连续偏导数，则
（*‘
）
其中
为函数关于的二阶导数，称为的海色（Hesse）矩阵。
当时，（即海色矩阵对称）。
注1：
1）设向量函数时，
称为向量函数在点处的导数（梯度）。
2）向量函数在点处可微是指所有分量都在点处可微。
关于向量函数常见的梯度：
（1），；
（2），；
（3）
（4）设，其中，，则
例：
（三）极小点的判定条件（求）
一、基本概念
1.点的邻域：
2.局部极小点：
设.若存在点和数，对都有，则称为在上的（非严格）局部极小点；
若（），则称为在上的严格局部极小点。
3.全局极小点：
设.若存在点，对于
都有，则称为在上的（非严格）全局极小点；
若（），则称为在上的严格全局极小点。
性质：
全局极小点必是局部极小点；
但局部极小点不一定是全局极小点。
类似有极大点的概念。
因，本书主要给出极小问题。
4.驻点：
设可微，，若，
则称点为的驻点或临界点。
二、极值的条件
定理1（一阶必要条件）设具有一阶连续偏导数，是的内点，若是的局部极小点，则
定理2（二阶必要条件）设具有二阶连续偏导数，若是的内点且为的局部极小点，则是半正定的，即对恒有
定理3（二阶充分条件）设具有二阶连续偏导数，为的内点，且，若正定，则为的严格局部极小点。
（四）凸函数与凸规划
一、凸集
1.凸集的定义：
一个n维向量空间的点集中任意两点的连线仍属于这个集合，即对，有
则称该点集为凸集。
2.凸集的性质：
（1）凸集的交集仍是凸集；
（2）数乘凸集仍是凸集；
（3）凸集的和集仍是凸集
特别规定，空集是凸集。
3.超平面：
设且，则集合
称为中的超平面，称为该超平面的法向量，即；
（是凸集）
半空间：
集合称为中的一个半空间。
超球：
。
4.凸组合：
设为中的个点，若存在且，使得
则称为的凸组合。
若均为正，则称为严格凸组合。
5.顶点（或极点）：
设是凸集，，若不能用内不同两点和的凸组合表示，即，则称为的顶点。
二、凸函数
1.凸函数：
设，是凸集，若对
及，都有
则称为凸集上的凸函数；
若
则称为凸集上的严格凸函数。
类似有凹函数的定义。
2.几何意义：
函数图形上连接任意两点的线段处处都在函数图形的上方。
3.性质
为凸集上的凸函数，，则也为上
的凸函数。
两个凸函数的和仍是凸函数。
推论1：
凸集上有限个凸函数的非负线性组合
仍为上的凸函数。
性质3：
若为凸集上的凸函数，则对，的
水平集是凸集。
性质4：
为凸集上的凹函数为凸集上的凸函数。
4.凸函数的充分必要条件
定理1（一阶条件）设可微，是凸集，则
（1）为凸函数对，恒有
（2）为严格凸函数对，恒有
定理2（二阶条件）设具有二阶连续偏导数，为开凸集，则
（1）在内为凸函数对，是半正定的；
（2）若正定，则在内为严格凸函数。
特殊地，元二次函数为（为对称矩阵）；
若正定，则称为正定二次函数。
正定二次函数是严格凸函数。
（因为）
5.凸函数的极值
定理3设为凸集上的凸函数，则
（1）的任一局部极小点为全局极小点；
（2）若具有二阶连续偏导数，且存在，使，则为在上的全局极小点；
（3）若为严格凸函数，且全局极小点存在，则必唯一。
特殊：
对于正定二次函数，有
，得唯一驻点为唯一的全局极小点。
6.凸规划问题：
非空凸集上的凸函数的极小化问题。
考虑凸规划问题：
，
（1）
s.t.
其中，为上的凹函数，为上的线性函数，
为凸集，
为上的凸函数。
线性函数既可视为凸函数，又可视为凹函数。
二次规划：
其中，，，，半正定或正定。
（五）下降迭代算法
1.下降迭代算法的步骤
（1）选择一个初始点，令k：
=0
（2）检验是否最优？
若是，则停止迭代；
若不是，则
（3）确定一个下降方向：
存在，对，使得
（4）从点出发，沿方向进行直线搜索（一维搜索），即求步长使
（5）计算，令k：
=k+1，转
（2）
2.直线搜索及其性质
（1）简记
：
表示从点出发，沿方向进行直线搜索，得到极小点。
（2）定理：
设目标函数具有一阶连续偏导数，若，则
证明：
（反正法）设，则
1），此时是点的下降方向；
2），此时是点的下降方向；
与矛盾。
3.收敛速度
定义1：
设序列是线性赋范空间中的点列，，若
则称序列收敛于，记为。
设向量函数，，若当时，总有，则称在点连续；
若在内每一点都连续，则称在内连续。
特别地，m=1时，为数量函数，则
定义3：
设序列收敛于，若存在与无关的数和，使得当从某个开始，都有
则称序列收敛的阶为，或为阶收敛。
当，且时，称线性收敛或一阶收敛；
当时，称二阶收敛；
当时，称超线性收敛。
4.计算终止准则
计算终止准则根据相继两次迭代的结果
a.根据相继两次迭代的绝对误差（不常用）
b.根据相继两次迭代的相对误差
c.根据目标函数梯度的模足够小
为给定的足够小的正数。
以上准则统称为Himmelblau计算终止准则，简称H终止准则。
第二章线性规划
2.1数学模型
一、线性规划的标准型
1.繁写形式：
s.t.
其中，（否则，等式两端同乘以“-1”）。
2.缩写形式：
3.向量形式：
其中，，，，。
4.矩阵形式：
其中，
约束条件的系数矩阵，，，一般地，；
限定向量，一般地，；
价值向量；
决策向量，；
通常，，为已知，未知。
二、任一模型化为标准型
1.极大化目标函数：
令，则问题转化为
2.约束条件为不等式
若约束为“”型，则“左端+松弛变量=右端”（松弛变量0）
如：
，引入松弛变量，化为
若约束为“”型，则“左端-剩余变量=右端”（剩余变量0）
，引入剩余弛变量，化为
3.若存在无非负要求的变量（称为自由变量）
令，其中，，代入目标函数及约束条
件即可。
4.某变量有上、下界
若，即，令，有。
用代替即可。
2.2线性规划解的性质
一、基本概念
标准型（LP）：
可行解（容许解）：
满足约束
（2）、（3）的解。
最优解：
满足
（1）的容许解。
基：
设的秩为，若是中的阶可逆矩阵，称是线性规划问题（LP）的一个基。
基向量：
基中的一列（）即为一个基向量。
（共个）
非基向量：
基之外的一列（）即为一个非基向量。
基变量：
与基向量相应的变量。
非基变量：
与非基向量相应的变量。
基本解：
令所有非基变量为0，求出的满足约束
（2）的解。
基本容许解：
满足约束（3）的基本解。
最优基本容许解：
满足约束
（1）的基本容许解。
退化的基本解：
若基本解中有基变量为0的基本解。
退化的基本容许解：
退化的最优基本容许解：
二、线性规划问题的基本定理
定理1若线性规划问题存在容许域，则其容许域是凸集。
定理2线性规划问题的基本容许解对应于容许域的顶点。
定理3若线性规划问题存在有限最优解，则其目标函数最优值
一定可以在容许域的顶点达到。
2.3单纯形法
一、单纯形法原理
单纯形法的基本思路：
根据问题的标准型，从容许域的一个基本
容许解（一个顶点）开始，转移到另一个基本容许解（顶点），并且使目标函数值逐步下降；
当目标函数达到最小值时，问题就得到了最优解。
二、单纯形法的步骤（以“大M法”为例）数学描述
例（大M法）：
1.构造初始容许基
初始容许基是一个单位矩阵，它相应的基本解是容许的。
1º
引入附加变量，把数学模型化为标准型。
2º
若约束条件中附加变量系数为“-1”，或原约束即为等式，则一般须引入人工变量。
3º
目标函数中，附加变量系数为0，而人工变量系数为M（很大的正数）。
人工变量系数为大M：
只要人工变量>
0，使前后约束条件不等价，但由于目标函数的修改，同时也使所求的目标函数最小值是一个很大的数，也是对“篡改”约束条件的一种惩罚，因此，M叫做罚因子，大M法也叫做罚函数法。
若对极大化问题，目标函数中人工变量系数为（-M）。
得到如下标准型：
其中，表示基变量；
表示非基变量。
2.求出一个基本容许解
用非基变量表示基变量和目标函数。
用非基变量表示基变量，即有
用非基变量表示目标函数，即
其中，，而称为非基变量的检验数。
上式中，规定各基变量的检验数为0。
其中，是基变量的价值系数，随基的改变而改变。
求出一个基本容许解及相应的目标函数值。
令非基变量=0即得初始基本容许解：
初始目标函数值：
3.最优性检验
检验数：
目标函数式中，各非基变量的系数，即称为各非基变量的检验数。
最优解判别定理：
若在极小化问题中，对于某个基本容许解，
所有检验数，且人工变量为0，则该基本容许解是最优解。
无穷多最优解判别定理：
若在极小化问题中，对于某个基本容许解，所有检验数，又存在某个非基变量的检验数为0，且人工变量为0，则该线性规划问题有无穷多最优解。
4º
无容许解判别定理：
若在极小化问题中，对于某个基本容许解，所有检验数，但人工变量不为0，则该线性规划问题无容许解。
4.基变换
基本容许解的改进定理：
已知一个非退化的基本容许解具有目标函数值，设某一个非基变量，其，则存在一个可行解具有目标函数值；
如果用代替原基中的某一列向量而产生一个新的基本容许解，则该新的解将有。
换入变量的确定
为换入变量，使。
换出变量的确定——最小非负比值规则
为换出变量，使
无有限最优解判别定理：
若在极小化问题中，对于某个基本容许解，有一个非基变量的检验数，但列中没有正元素，且人工变量为0，则该线性规划问题无有限最优解。
三、单纯形法的表格形式
1．构造初始可行基，并计算检验数
2．从表中找出基本可行解和相应的目标函数值
3．最优性检验
4．基变换
换出变量的确定
主元素的确定
单纯形表中，换入变量所在的列和换出变量所在的行交叉处的元素为主元素（即），标“*”号。
取主变换（基变换）
即单纯形法的一次迭代。
在表中以主元素进行旋转变换（高斯消去法），把所对应的列向量
于是得到新一轮的单纯形表。
四、单纯形法解极大化和极小化问题的区别
原模型目标函数
标准型
最优性检验
目标函数中人工变量系数为大M
所有，且人工变量为0
目标函数中人工变量系数为“-M”
五、两阶段法
1.第一阶段：
判断原线性规划问题是否有容许解。
先求解以下线性规划
（人工变量之和）
用单纯形法对上述问题求解。
若，则原问题有容许解；
若，则原问题无容许解，停止计算。
2.第二阶段：
求原线性规划问题的最优解。
以第一阶段的最终单纯形表为基础，去掉其中的人工变量列，把目标函数换成原问题的目标函数，于是得到第二阶段的初始单纯形表，继续迭代下去，得最优解。
34
升级会员 