《运筹学课件第六章 非线性规划》由会员分享，可在线阅读，更多相关《运筹学课件第六章 非线性规划（100页珍藏版）》请在金锄头文库上搜索。
1、运 筹 学,Non-linear Programming,第六章 非线性规划,基本概念 凸函数和凸规划 一维搜索方法 无约束最优化方法 约束最优化方法,第一节 基本概念,非线性规划问题 非线性规划方法概述,一、非线性规划问题引例,例1 曲线的最优拟合问题,例2 构件容积问题,设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为S，圆锥部分的高h和圆柱部分的高x2之比为a。确定构件尺寸，使其容积大。,h,二、 数 学 模 型,其中x=(x1,x2,.,xn )TRn ，,D中的点称为可行解或可行点,三、 分 类,（1）线性规划：目标函数和约束条件皆为x的线性函数。,（2）非线性规划：目
2、标函数和约束条件中至少有一个是x的非线性函数。,本章讨论非线性规划。,（1）当p=0,q=0 ,即可行域D=Rn 时， (P)可 写成,称为无约束非线性规划或无约束最优化问题。,（2）若可行域DRn ，(P)称为约束非线性规划或约束最优化问题。,定义 1 对于非线性规划(P)，若 并且存在x*的一个领域,则x*称为局部最优解或局部极小点， 称f(x*)为局部最优值或局部极小值。,则称x*为严格局部最优解或严格局部极小点,称f(x*)为严格局部最优值或严格局部极小值。,若使得,使得,四、最优解和最优值,四、最优解和最优值,全局最优解为x*=(1/2,1/2)T , 全局最优值为f(x*)=1/2
3、。,1 x1,x2,1,x*,若目标函数改为：,其最优解和最优值如何？,五、非线性规划方法概述,迭代法:,按某种方法给出目标函数极小点的一个初始估计，称为初始点。然后按某种特定的迭代规则产生一点列xk，使得xk 为有穷点列时，其最后一个点是最优解；当 xk 是无穷点列时，其极限点是最优解(此时称该方法是收敛的)。,定义3,则称向量p是函数f(x)在点 处的下降方向。,定义4,则称向量 p是函数 f (x)在点 处的可行方向。,图例说明。,基本迭代格式,第1步 选取初始点 ,k:=0;,第2步 构造搜索方向,第3步 根据,，确定步长,第4步,若x k+1已满足某种终止条件，停止迭代，输出 近似解
4、.,否则令k:=k+1，转回第2步。,随机性方法是按照某种规则随机产生迭代点, 迭代点列依概率收敛到最优解，包括遗传算法,模拟退火算法,神经网络算法等,这类方法具有对函数性质要求低、容易实现等优点, 但效率低、可靠性差、不能保证产生优化问题的最优解.,全局优化算法概述,全局优化方法可分为随机性方法和确定性方法.,全局优化算法概述,确定性方法充分利用了问题的解析性质, 如函数的凸性、单调性、稠密性等, 产生一个确定性的有限或无限点序列, 使得该点序列收敛于全局最优解. 包括分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等,这类算法在理论上有较强的可行性, 但对较为复杂的大型优化问题却难
5、于应用.,全局优化方法可分为随机性方法和确定性方法.,第二节 凸函数和凸规划,凸函数及其性质 凸规划及其性质,一、凸函数及其性质,定义 5 设,是非空凸集，,如果对任意的,有,则称 f 是S上的凸函数，或 f 在S上是凸的。,有,则称 f 是S上的严格凸函数，或 f 在S上是严格凸的。,如果对于任意的,若 f 是S上的（严格）凸函数，则称 f 是S上的（严格）凹函数或 f 在S上是（严格）凹的,例1 线性函数,在Rn上既是凸函数又是凹函数。,例2 函数,证,证,证: (1),定理 1,(1)若f(x)是S上的凸函数，,都是S上的凸函数,是S上的凸函数。,是非空凸集。,(2),则,也是S上的凸函
6、数。,凸函数的性质,定理 1,(1)若f(x)是S上的凸函数，,是S上的凸函数。,是非空凸集。,凸函数的性质,都是S上的凸函数,(2),则,也是S上的凸函数。,证: (2),定理 2 设,是非空凸集，,是凸函数，,，则集合,是凸集。,证：,水平集,又因 f 是S上的凸函数，所以,凸函数的性质,定理 3 设,是非空开凸集，,，,是函数f在点,处的梯度,（1）f是S上的凸函数的充要条件是,（2）f是S上的严格凸函数的充要条件是,可微，则,凸函数的判定,证 (1) 必要性.设f是S上的凸函数，则对,代入得,由泰勒公式得,证,（1）,（2）,对,和,充分性.设,定理 4 设,是非空开凸集，,则f 是S
7、上的凸函数的充要条件是f 的Hesse矩阵,在S上是半正定的.,注意：该逆命题不成立。,f在S上二阶连续可导,在S上正定时，f是S上的严格凸函数.,凸函数的判定,二 次 型,二次型函数,其中xR n ,A是一个n阶对称矩阵，,所以当且仅当A为半正定矩阵时，f(x)是凸函数。,A为正定矩阵时，f(x)是严格凸函数。,例,二、 凸规划及其性质,约束集,如果(P)的约束集D是凸集，目标函数f是D上的凸函数，则(P)叫做非线性凸规划，或简称为凸规划。,非线性规划,定理 5 对于非线性规划(P)，若,并且f 是D上的凸函数，则(P)是凸规划。,皆为Rn上的凸函数，,皆为线性函数,证：,又因f 是D上的凸
8、函数，,(P)是凸规划,定理 6 凸规划的任一局部最优解都是它的全局最优解。,证：,又因f 是凸函数，所以,矛盾,例： 验证下列规划为凸规划,第三节 一维搜索方法,非精确一维搜索方法Goldstein法Armijo法,精确一维搜索方法0.618法Newton法,目标函数为单变量的非线性规划问题称为一维搜索问题,数学模型,由定义知，t*是 在a,b上的唯一极小点。,一、基本原理,定义1 如果存在一个 ，使得 在 区间 上严格递减，且在区间 上严格递增，则称函数 在区间a,b上是单谷的，区间 a,b 称为 的单谷区间。,使得,，称a, b为搜索区间。,不断缩短搜索区间的长度，当区间足够小时,得到所
9、求问题的近似最优解。,在区间a,b上任取两点t1, t2，设t1 t2，,然后，,图,让下一次迭代中区间缩短相同的比例，并且已有一个计算过的点在缩短后的区间内。,二、0.618法（近似黄金分割法）,a,b,t1,t2,设新的探索区间为a ,t2,其上的两个探索点为,0.618法（近似黄金分割法）,由以上分析得迭代公式：,0.618法（近似黄金分割法）,算法步骤：,例1：试用黄金分割法求解,解 (1),(2),(3),(4),得最优解 ：,三、斐波那契（Fibonacci）法,定义2 设数列Fn满足：,数列Fk 称为斐波那契（Fibonacci）数列 。,一、斐波那契（Fibonacci）法,计
10、算n次函数值所得最大缩短率为1/Fn,要把区间缩短为原区间的(0，有,定理2,若x*是(UP)的,定理3,则x*是(UP)的严格局部最优解。,局部最优解，则,一、无约束问题的最优性条件,定理4,则x*是(UP)的全局最优解。,x*是(UP)的全局最优解。,一、无约束问题的最优性条件,例1,解,目标函数的Hesse矩阵为,一、无约束问题的最优性条件,一、无约束问题的最优性条件,二、最速下降法,基本思想：从当前点xk出发，取函数 f(x)在点 x k处下降最快的方向为搜索方向 pk，即负梯度方向。,设目标函数f(x)一阶连续可微.,二、最速下降法,算法步骤：,第1步 选取初始点x0,给定终止误差
11、0,令k:= 0；,第2步 计算,第4步 进行一维搜索，求 t k使得,第3步,用最速下降法求得最优解是目标函数的一个驻点。,例2 用最速下降法求解,解：,经10轮迭代得最优解。,三、共轭方向法,定义 设A是n阶是对称矩阵，若,则称p和q是相互A共轭的。,对于非零向量组,则称p0, p1,., pn-1是A共轭方向组，或称一组 A共轭方向。,共轭概念是正交概念的推广。,证,线性无关,共轭方向组中最多含n个向量，且线性无关,反之，n维空间的一组基可以构造一组A共轭方向,共轭方向组的构造,由定理知：,二次严格凸函数的无约束最优化问题,定理 6 对于问题(QP)，若,组A共轭方向，则由任意初始点,出
12、发，依次沿,则最多经n次迭代可 得(QP)的整体最优解。,为任意一,进行精确一维搜索，,由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无优化约束的方法叫共轭方向法。,利用迭代点处的负梯度向量为基础产生一组共轭方向，这种方法叫共轭梯度法。,共轭梯度法,首先，取定初始点 x0，,从x0点沿方向p0进行，精确一维搜索求得t0，则,否则，取,（1）,依此进行下去，,（2）,共轭梯度法,否则，取,和沿这些方向的迭代点，,（4）,（3）,从而有,共轭梯度法,（5）,（3）可以写成,公式（5）是由Fletcher和Reeves于1964年提出的，称为F-R公式，用公式（5）求解无约束最优化问题最优解的
13、方法简称为F-R法。,第1步 选取初始点x0,给定终止误差 0；,第2步 计算,第4步 进行一维搜索，求 t k使得,第3步,F-R法步骤,第5步 计算,第6步,第7步 用F-R公式取,例2 用F-R法求解,解：,利用F-R公式得：,若用某种方法求解(QP)问题，经有限轮迭代可以达到最优解，称此方法具有二次终止性。,F-R法具有二次终止性。,第五节 约束最优化方法,约束最优化问题 的最 优 化条件 简 约 梯 度 法 惩 罚 函 数 法,一、约束最优化问题的最优化条件,定理 1,处可微，,在点 x* 处连续，,在点 x*,划(P)的局部最优解，则存在两组实数,若x*是非线性规,称约束规范条件,Kuhn-Tucker条件，简称K-T条件,特殊地，对于只有不等式约束的非线性规划问题,若x*是局部最优解，则存在实数,对于只有等式约束的非线性规划问题,一、约束最优化问题的最优化条件,现引进Lagrange函数如下：,一、约束最优化问题的最优化条件,定理 2 对于问题(P)，若,在点,x*处连续可微，若可行点x* 满足(P)的K-T条件，且,是凸函数,是线性函数，则 x*,是(P)的全局最优解。,一、约束最优化问题的最优化条件,二、简约梯度法,假设（1）每个可行点至少有m个大于0的分量 （2）A的任意m列线性无关,简约梯度法的基本思想是Wolfe于1962年提出,二、简约梯度法,
