数学软件MATLAB课件第六章-非线性规划

第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 非线性规划非线性规划Non-linear Programming第第2页页第六章第六章 非线性规划非线性规划v基本概念基本概念v凸函数和凸规划凸函数和凸规划v一维搜索方法一维搜索方法v无约束最优化方法无约束最优化方法v约束最优化方法约束最优化方法第第3页页第一节第一节 基本概念基本概念v非线性规划问题非线性规划问题v非线性规划方法概述非线性规划方法概述第第4页页一、非线性规划问题引例一、非线性规划问题引例例例1 曲线的最优拟合问题曲线的最优拟合问题第第5页页例例2 构件容积问题构件容积问题设计一个右图所示的由圆锥和圆柱设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积面围成的构件，要求构件的表面积为为S，圆锥部分的高，圆锥部分的高h和圆柱部分的和圆柱部分的高高x2之比为之比为a。确定构件尺寸，使其。确定构件尺寸，使其容积大。容积大。h第第6页页二、二、数数 学学 模模 型型约束集约束集或或可行域可行域其中其中x=(x1,x2,.,xn)TRn，D中的点称为中的点称为可行解可行解或或可行点可行点第第7页页三、三、分分 类类（1）线性规划：目标函数和约束条件皆为）线性规划：目标函数和约束条件皆为x的线的线性函数。性函数。（2）非线性规划：目标函数和约束条件中至少）非线性规划：目标函数和约束条件中至少有一个是有一个是x的非线性函数。的非线性函数。本章讨论非线性规划。本章讨论非线性规划。（1）当）当p=0,q=0,即可行域即可行域D=Rn 时，时，(P)可可 写成写成称为无约束非线性规划或无约束最优化问题。称为无约束非线性规划或无约束最优化问题。（2）若可行域）若可行域DRn，(P)(P)称为约束非线性规划称为约束非线性规划或约束最优化问题。或约束最优化问题。第第8页页定义定义 1 对于非线性规划对于非线性规划(P)，若，若 并且存在并且存在x*的一个领域的一个领域 则则x*称为称为局部最优解局部最优解或或局部极小点局部极小点，称称f(x*)为为局部最优值局部最优值或或局部极小值局部极小值。则称则称x*为为严格局部最优解严格局部最优解或或严格局部极小点严格局部极小点,称称f(x*)为为严格局部最优值严格局部最优值或或严格局部极小值严格局部极小值。若使得若使得使得使得四、最优解和最优值四、最优解和最优值第第9页页四、最优解和最优值四、最优解和最优值第第10页页全局最优解为全局最优解为x*=(1/2,1/2)T,全局最优值为全局最优值为f(x*)=1/2。1 x1x21x*若目标函数改为：若目标函数改为：其最优解和最优值如何？其最优解和最优值如何？第第11页页五、非线性规划方法概述五、非线性规划方法概述迭代法迭代法:按某种方法给出目标函数极小点的一个初始估计，按某种方法给出目标函数极小点的一个初始估计，称为初始点。然后按某种特定的迭代规则产生一称为初始点。然后按某种特定的迭代规则产生一点列点列xk，使得，使得xk 为有穷点列时，其最后一个为有穷点列时，其最后一个点是最优解；当点是最优解；当 xk 是无穷点列时，其极限点是无穷点列时，其极限点是最优解是最优解(此时称该方法是收敛的此时称该方法是收敛的)。第第12页页定义定义3则称向量则称向量p是函数是函数f(x)在点在点 处的下降方向。处的下降方向。定义定义4则称向量则称向量 p是函数是函数 f(x)在点在点 处的可行方向。处的可行方向。图例说明。图例说明。第第13页页基本迭代格式基本迭代格式第第1步步 选取初始点选取初始点 ,k:=0;第第2步步 构造搜索方向构造搜索方向第第3步步 根据根据，确定步长，确定步长第第4步步 若若x k+1已满足某种终止条件，停止迭代，输出已满足某种终止条件，停止迭代，输出近似解近似解.否则令否则令k:=k+1，转回第，转回第2步。步。第第14页页随机性方法随机性方法是按照某种规则随机产生迭代点是按照某种规则随机产生迭代点,迭代迭代点列依概率收敛到最优解，包括遗传算法点列依概率收敛到最优解，包括遗传算法,模拟退模拟退火算法火算法,神经网络算法等神经网络算法等,这类方法具有对函数性质这类方法具有对函数性质要求低、容易实现等优点要求低、容易实现等优点,但效率低、可靠性差、但效率低、可靠性差、不能保证产生优化问题的最优解不能保证产生优化问题的最优解.全局优化算法概述全局优化算法概述全局优化方法可分为随机性方法和确定性方法全局优化方法可分为随机性方法和确定性方法.第第15页页全局优化算法概述全局优化算法概述确定性方法确定性方法充分利用了问题的解析性质充分利用了问题的解析性质,如函数的如函数的凸性、单调性、稠密性等凸性、单调性、稠密性等,产生一个确定性的有限产生一个确定性的有限或无限点序列或无限点序列,使得该点序列收敛于全局最优解使得该点序列收敛于全局最优解.包包括分枝定界算法、区间算法、填充函数法、割平面括分枝定界算法、区间算法、填充函数法、割平面法、顶点枚举法等法、顶点枚举法等,这类算法在理论上有较强的可行这类算法在理论上有较强的可行性性,但对较为复杂的大型优化问题却难于应用但对较为复杂的大型优化问题却难于应用.全局优化方法可分为随机性方法和确定性方法全局优化方法可分为随机性方法和确定性方法.第第16页页第二节第二节 凸函数和凸规划凸函数和凸规划q凸函数及其性质凸函数及其性质q凸规划及其性质凸规划及其性质第第17页页一、凸函数及其性质一、凸函数及其性质定义定义 5 设设是非空凸集是非空凸集，如果对任意的如果对任意的有有则称则称 f 是是S上的上的凸函数凸函数，或，或 f 在在S上是上是凸凸的。的。有有则称则称 f 是是S上的上的严格凸函数，严格凸函数，或或 f 在在S上是上是严格凸的。严格凸的。如果对于任意的如果对于任意的若若 f 是是S上的（严格）凸函数，则称上的（严格）凸函数，则称 f 是是S上的上的（严格）（严格）凹函数凹函数或或 f 在在S上是上是（严格）凹的（严格）凹的第第18页页例例1 线性函数线性函数在在Rn上既是凸函数又是凹函数。上既是凸函数又是凹函数。例例2 函数函数证证证证第第19页页证证:(1)定理定理 1 (1)若若f(x)是是S上的凸函数，上的凸函数，都是都是S上的凸函数上的凸函数,是是S上的凸函数。上的凸函数。是非空凸集。是非空凸集。(2)则则也是也是S上的凸函数。上的凸函数。凸函数的性质凸函数的性质第第20页页定理定理 1 (1)若若f(x)是是S上的凸函数，上的凸函数，是是S上的凸函数。上的凸函数。是非空凸集。是非空凸集。凸函数的性质凸函数的性质都是都是S上的凸函数上的凸函数,(2)则则也是也是S上的凸函数。上的凸函数。证证:(2)第第21页页定理定理 2 设设是非空凸集，是非空凸集，是凸函数，是凸函数，则集合，则集合是凸集。是凸集。证：证：水平集水平集又因又因 f 是是S上的凸函数，所以上的凸函数，所以凸函数的性质凸函数的性质第第22页页定理定理 3 设设是非空开凸集，是非空开凸集，是函数是函数f在点在点处的梯度处的梯度（1）f是是S上的凸函数的充要条件是上的凸函数的充要条件是（2）f是是S上的严格凸函数的充要条件是上的严格凸函数的充要条件是可微可微，则则凸函数的判定凸函数的判定第第23页页证证(1)必要性必要性.设设f是是S上的凸函数，则对上的凸函数，则对代入得代入得由泰勒公式得由泰勒公式得第第24页页证证 （1）（2）对对和和 充分性充分性.设设第第25页页定理定理 4 设设是非空开凸集，是非空开凸集，则则f 是是S上的凸函数的充要条件是上的凸函数的充要条件是f 的的Hesse矩阵矩阵在在S上是半正定的上是半正定的.注意注意：该逆命题不成立。该逆命题不成立。f在在S上二阶连续可导上二阶连续可导,在在S上正定时，上正定时，f是是S上的严格凸函数上的严格凸函数.凸函数的判定凸函数的判定第第26页页二二 次次 型型二次型函数二次型函数其中其中xR n,A是一个是一个n阶对称矩阵，阶对称矩阵，所以当且仅当所以当且仅当A为半正定矩阵时，为半正定矩阵时，f(x)是凸函数。是凸函数。A为正定矩阵时，为正定矩阵时，f(x)是严格凸函数。是严格凸函数。例例第第27页页二、二、凸规划及其性质凸规划及其性质约束集约束集如果如果(P)的约束集的约束集D是凸集，目标函数是凸集，目标函数f是是D上的凸函上的凸函数，则数，则(P)叫做叫做非线性凸规划非线性凸规划，或简称为，或简称为凸规划凸规划。非线性规划非线性规划第第28页页定理定理 5 对于非线性规划对于非线性规划(P)，若，若并且并且f 是是D上的凸函数，则上的凸函数，则(P)是凸规划。是凸规划。皆为皆为Rn上的凸函数，上的凸函数，皆为线性函数皆为线性函数证：证：又因又因f 是是D上的凸函数，上的凸函数，(P)是凸规划是凸规划第第29页页定理定理 6 6 凸规划的任一局部最优解都是它的全局凸规划的任一局部最优解都是它的全局最优解。最优解。证：证：又因又因f 是凸函数，所以是凸函数，所以矛盾矛盾第第30页页例：例：验证下列规划为凸规划验证下列规划为凸规划 第第31页页第三节第三节 一维搜索方法一维搜索方法 非精确一维搜索方法非精确一维搜索方法 Goldstein法法 Armijo法法精确一维搜索方法精确一维搜索方法 0.618法法 Newton法法第第32页页目标函数为单变量的非线性规划问题称为一维搜索目标函数为单变量的非线性规划问题称为一维搜索问题问题数学模型数学模型由定义知，由定义知，t*是是 在在a,b上的唯一极小点。上的唯一极小点。一、基本原理一、基本原理定义定义1 如果存在一个如果存在一个 ，使得，使得 在在 区间区间 上严格递减，且在区间上严格递减，且在区间 上严格上严格递增，则称递增，则称函数函数 在区间在区间a,b上是上是单谷的，单谷的，区间区间 a,b 称为称为 的的单谷区间单谷区间。第第33页页使得使得，称，称a,b为搜索区间。为搜索区间。不断缩短搜索区间的长度，当区间足够小时不断缩短搜索区间的长度，当区间足够小时,得到得到所求问题的近似最优解。所求问题的近似最优解。在区间在区间a,b上任取两点上任取两点t1,t2，设，设t1 t2，然后，然后，图图第第34页页让下一次迭代中区间缩短相同的比例让下一次迭代中区间缩短相同的比例，并且，并且已有一个计算过的点在缩短后的区间内。已有一个计算过的点在缩短后的区间内。二、二、0.618法（近似黄金分割法）法（近似黄金分割法）abt1t2第第35页页设新的探索区间为设新的探索区间为a,t2,其上的两个探索点其上的两个探索点为为0.618法（近似黄金分割法）法（近似黄金分割法）第第36页页由以上分析得迭代公式：由以上分析得迭代公式：0.618法（近似黄金分割法）法（近似黄金分割法）第第37页页算法步骤：算法步骤：第第38页页例例1：试用黄金分割法求解：试用黄金分割法求解解解 (1)第第39页页 (2)(3)(4)得最优解得最优解：第第40页页三、斐波那契（三、斐波那契（Fibonacci）法）法定义定义2 设数列设数列Fn满足：满足：数列数列Fk 称为斐波那契（称为斐波那契（Fibonacci）数列）数列。k0 1 2 3 4 5 6 7 8 Fk1 1 2 3 5 8 13 21 34第第41页页一、斐波那契（一、斐波那契（Fibonacci）法）法计算计算n次函数值所得最大缩短率为次函数值所得最大缩短率为1/Fn要把区间缩短为原区间的要把区间缩短为原区间的(0，有，有第第55页页定理定理2 若若x*是是(UP)的的定理定理3 则则x*是是(UP)的严格局部最优解。的严格局部最优解。局部最优解，则局部最优解，则一、无约束问题的最优性条件一、无约束问题的最优性条件第第56页页定理定理4 则则x*是是(UP)的全局最优解。的全局最优解。x*是是(UP)的全局最优解。的全局最优解。一、无约束问题的最优性条件一、无约束问题的最优性条件第第57页页例例1解解目标函数的目标函数的Hesse矩阵为矩阵为一、无约束问题的最优性条件一、无约束问题的最优性条件第第58页页一、无约束问题的最优性条件一、无约束问题的最优性条件第第59页页二、最速下降法二、最速下降法基本思想：基本思想：从当前点从当前点xk出发，取函数出发，取函数 f(x)在点在点 x k处处下降最快的方向为搜索方向下降最快的方向为搜索方向 pk，即负梯度方向。，即负梯度方向。设目标函数设目标函数f(x)一阶连续可微一阶连续可微.第第60页页二、最速下降法二、最速下降法算法步骤：算法步骤：第第1步步 选取初始点选取初始点x0,给定终止误差给定终止误差 0,令令k:=0；第第2步步 计算计算第第4步步 进行一维搜索，求进行一维搜索，求 t k使得使得第第3步步 用最速下降法求得最优解是目标函数的一个驻点。用最速下降法求得最优解是目标函数的一个驻点。第第61页页例例2 用最速下降法求解用最速下降法求解解：解：经经10轮迭代得最优解。轮迭代得最优解。第第62页页三、共轭方向法三、共轭方向法定义定义 设设A是是n阶是对称矩阵，若阶是对称矩阵，若则称则称p和和q是相互是相互A共轭的。共轭的。对于非零向量组对于非零向量组则称则称p0,p1,.,pn-1是是A共轭方向组，或称共轭方向组，或称一组一组 A共轭方向。共轭方向。共轭概念是正交概念的推广。共轭概念是正交概念的推广。第第63页页证证线性无关线性无关第第64页页共轭方向组中最多含共轭方向组中最多含n个向量，且线性无关个向量，且线性无关反之，反之，n维空间的一组基可以构造一组维空间的一组基可以构造一组A共轭方向共轭方向共轭方向组的构造共轭方向组的构造由定理知：由定理知：第第65页页二次严格凸函数的无约束最优化问题二次严格凸函数的无约束最优化问题定理定理 6 对于问题对于问题(QP)，若，若组组A共轭方向，则由任意初始点共轭方向，则由任意初始点出发，依次沿出发，依次沿 则最多经则最多经n次迭代可次迭代可得得(QP)的整体最优解。的整体最优解。为任意一为任意一进行精确一维搜索，进行精确一维搜索，由任意初始点出发，依此沿某共轭方向组进行一维搜由任意初始点出发，依此沿某共轭方向组进行一维搜索求解无优化约束的方法叫索求解无优化约束的方法叫共轭方向法。共轭方向法。利用迭代点处的负梯度向量为基础产生一组共轭方向，利用迭代点处的负梯度向量为基础产生一组共轭方向，这种方法叫这种方法叫共轭梯度法。共轭梯度法。第第66页页共轭梯度法共轭梯度法首先，取定初始点首先，取定初始点 x0，从从x0点沿方向点沿方向p0进行，精确一维搜索求得进行，精确一维搜索求得t0，则，则否则，取否则，取（1）依此进行下去，依此进行下去，（2）第第67页页共轭梯度法共轭梯度法否则，取否则，取和沿这些方向的迭代点，和沿这些方向的迭代点，（4）（3）从而有从而有第第68页页共轭梯度法共轭梯度法（5）（3）可以写成）可以写成公式（公式（5）是由）是由Fletcher和和Reeves于于1964年提出的，称为年提出的，称为F-R公式，用公式（公式，用公式（5）求解无约束最优化问题最优解的）求解无约束最优化问题最优解的方法简称为方法简称为F-R法。法。第第69页页第第1步步 选取初始点选取初始点x0,给定终止误差给定终止误差 0；第第2步步 计算计算第第4步步 进行一维搜索，求进行一维搜索，求 t k使得使得第第3步步 F-R法步骤法步骤第第70页页第第5步步 计算计算第第6步步 第第7步步 用用F-R公式取公式取第第71页页例例2 用用F-R法求解法求解解：解：利用利用F-R公式得：公式得：第第72页页若用某种方法求解若用某种方法求解(QP)问题，经有限轮迭代可以达到最问题，经有限轮迭代可以达到最优解，称此方法具有二次终止性。优解，称此方法具有二次终止性。F-R法具有二次终止性。法具有二次终止性。第第73页页第五节第五节 约束最优化方法约束最优化方法v约束最优化问题约束最优化问题的最的最 优优 化条件化条件v简简 约约 梯梯 度度 法法v惩惩 罚罚 函函 数数 法法第第74页页第第75页页一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件定理定理 1 处可微，处可微，在点在点 x*处连续，处连续，在点在点 x*划划(P)的局部最优解，则存在两组实数的局部最优解，则存在两组实数若若x*是非线性规是非线性规称约束规范条件称约束规范条件Kuhn-Tucker条件，简称条件，简称K-T条件条件第第76页页特殊地，对于只有不等式约束的非线性规划问题特殊地，对于只有不等式约束的非线性规划问题若若x*是局部最优解，则存在实数是局部最优解，则存在实数对于只有等式约束的非线性规划问题对于只有等式约束的非线性规划问题一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件第第77页页现引进现引进Lagrange函数如下：函数如下：一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件第第78页页定理定理 2 对于问题对于问题(P)，若，若在点在点x*处连续可微，若可行点处连续可微，若可行点x*满足满足(P)的的K-T条件，且条件，且是凸函数是凸函数,是线性函数，则是线性函数，则 x*是是(P)的全局最优解。的全局最优解。一、约束最优化问题的最优化条件一、约束最优化问题的最优化条件第第79页页二、简约梯度法二、简约梯度法假设（假设（1）每个可行点至少有）每个可行点至少有m个大于个大于0的分量的分量（2）A的任意的任意m列线性无关列线性无关简约梯度法的基本思想是简约梯度法的基本思想是Wolfe于于1962年提出年提出第第80页页二、简约梯度法二、简约梯度法基本思想：基本思想：类似于单纯性法，将当前点类似于单纯性法，将当前点xk的的m个个最大正分量定为基变量，其余的最大正分量定为基变量，其余的m-n个分量作为个分量作为非基变量，那么目标函数作为非基变量的函数求非基变量，那么目标函数作为非基变量的函数求负梯度方向，并依据这一方向构造从负梯度方向，并依据这一方向构造从xk到到xk+1的的可行下降方向。可行下降方向。第第81页页二、简约梯度法二、简约梯度法称称rN为为f 在点在点x处对应于基矩阵处对应于基矩阵B的的简约梯度简约梯度。首先，求首先，求f 对非基变量的梯度对非基变量的梯度第第82页页二、简约梯度法二、简约梯度法其次，在迭代点其次，在迭代点xk处依据简约梯度构造可行下降方向处依据简约梯度构造可行下降方向第第83页页二、简约梯度法二、简约梯度法这是因为，这是因为，第第84页页二、简约梯度法二、简约梯度法综上所述，利用简约梯度综上所述，利用简约梯度 （*）第第85页页定理定理 3 设设f 是可微函数，是可微函数，二、简约梯度法二、简约梯度法第第86页页二、简约梯度法二、简约梯度法最后，考察如何从点最后，考察如何从点 xk Dl 沿上面构造的可行下降方向沿上面构造的可行下降方向pk进行有效一维搜索。进行有效一维搜索。因而取因而取t的上界为的上界为为使为使第第87页页Wolfe法步骤法步骤第第88页页Wolfe法步骤法步骤第第89页页例例 用用Wolfe法求解极小化问题法求解极小化问题解解 上面问题可化为下列问题上面问题可化为下列问题第第90页页三、惩罚函数法三、惩罚函数法罚函数法罚函数法障碍函数法障碍函数法基本思想基本思想：利用问题中的约束函数做出适当的：利用问题中的约束函数做出适当的带有参数的惩罚函数，然后在原来的目标函数带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数，构造出带参数的增广目标函上加上惩罚函数，构造出带参数的增广目标函数，把问题的求解转换为求解一系列无约束非数，把问题的求解转换为求解一系列无约束非线性规划问题。线性规划问题。第第91页页罚函数法罚函数法考虑问题：考虑问题：设法适当地加大不可行点处对应的目标函数值，使不设法适当地加大不可行点处对应的目标函数值，使不可行点不能成为相应无约束极小化问题的最优解。可行点不能成为相应无约束极小化问题的最优解。可行域为可行域为D构造罚函数：构造罚函数：c称为罚参数或罚因子称为罚参数或罚因子第第92页页实际应用中，选取一个递增且趋于无穷的正罚实际应用中，选取一个递增且趋于无穷的正罚函数参数列函数参数列ck于是于是第第93页页罚函数法计算步骤罚函数法计算步骤第第94页页例例 用罚函数法求解用罚函数法求解解解 罚函数为罚函数为增广目标函数为增广目标函数为第第95页页原问题转化为求解一系列无约束最优化问题：原问题转化为求解一系列无约束最优化问题：用解析法求解上述问题：用解析法求解上述问题：因此，罚函数法也称为因此，罚函数法也称为外点法外点法O x1 x2 1 x 1第第96页页障碍函数法障碍函数法基本思想：基本思想：在可行区域的边界上筑起一道在可行区域的边界上筑起一道“墙墙”，当迭代点靠近边界时，所构造的增广目标函数值陡当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被然增大，于是最优点就被“挡挡”在可行区域内部了。在可行区域内部了。仅考虑带不等式约束的问题仅考虑带不等式约束的问题当点当点x从可行域内部趋于可行域边界时，至少有一个从可行域内部趋于可行域边界时，至少有一个gi(x)趋于趋于0。因此下列函数会无限增大。因此下列函数会无限增大第第97页页构造障碍函数：构造障碍函数：取一个递减且趋于取一个递减且趋于0的正罚函数参数列的正罚函数参数列dk(k=1,2,.)第第98页页障碍函数法步骤障碍函数法步骤第第99页页例例 用障碍函数法求解极小化问题用障碍函数法求解极小化问题解解 取取增广目标函数为：增广目标函数为：用解析法求用解析法求得无约束优化问题得无约束优化问题的最优解为：的最优解为：因此，罚函数法也称为因此，罚函数法也称为内点法内点法第第100页页v罚函数法适用于一般的规划问题，障碍函数法罚函数法适用于一般的规划问题，障碍函数法仅适用于带等式约束的规划问题。仅适用于带等式约束的规划问题。v罚函数法的优点是方法结构简单，对初始点的罚函数法的优点是方法结构简单，对初始点的选取没有要求，障碍函数法的优点也是方法结构选取没有要求，障碍函数法的优点也是方法结构简单，但初始点必须是内点。简单，但初始点必须是内点。v缺点：收敛速度慢；工作量大；方法本身造成缺点：收敛速度慢；工作量大；方法本身造成数值困难。数值困难。两种方法优缺点比较：两种方法优缺点比较：