f(X*)=0
解无约束问题的算法: 解无约束问题的算法: 求f(X)的驻点X*,若是凸函数, f(X)的驻点 ,若是凸函数, 的驻点X* 得到最优解.否则,转下一步. 得到最优解.否则,转下一步. 在驻点X*处 计算H(x). 在驻点X*处,计算H(x). 根据H(x)来判断该驻点 是否是 根据H(x)来判断该驻点X*是否是 来判断该驻点X* 极值点. 极值点.
X ∈ E1
解:利用一阶必要条 件求出有可能成为最 优解的那些点: 优解的那些点: f(X) = 6x(x2-1)2 =0 得到: f(X 得到: x1=0,x2=1,x3= -1 进一步考虑二阶必要条件,缩小范围: 进一步考虑二阶必要条件,缩小范围: 二阶必要条件
H(X) =xxf(X) = 6(x2-1)2+24 x2(x2-1) = H(x1) =xxf(x1) = xxf(0) =6>0 = H(x2) =xxf(x2) = xxf(1) = 0 = H(x3) =xxf(x3) = xxf(-1) =0 = f(f(X)在 =0点正定 依二阶必要条件, f(X)在x1=0点正定,依二阶必要条件, 点正定, x1=0为(P1)的局部最优解.而x2=1, =0为 的局部最优解. =1, x3= -1满足二阶必要条件和一阶必要条 但它们显然都不是最优解. 件,但它们显然都不是最优解.
例6-3 Min f(X)= 2x12+5x22+x32+ 2x2x3 2x + 2x1x3 - 6x2+3 X ∈ E3 f(X 解:f(X) = (4x1+ 2x3, 10x2+ 2x3 – 6, 2x1+ 2x2 + 2x3 )=0 驻点x*=(1,1,驻点x*=(1,1,-2)
H(X) =xxf(X)= =
都是k 的非线性函数, 都是ki的非线性函数,构造非线性规划 模型如下: 模型如下: Max ∑ ∫Ei(ki,Q) dFi(Q) s.t.V1(k1)+ V2(k2)+…… + Vn(kn)=V V1(k1), V2(k2),……,Vn(kn) ≥ 0 利用一定的算法,可求出最优分配ki* 利用一定的算法,可求出最优分配k 和Vi *(i=1,2,….n).
电厂水库径流输入量分布为F (Q), 电厂水库径流输入量分布为Fi(Q),发 电量随库容与径流量而变化, 电量随库容与径流量而变化,以Ei(ki,Q) 表示.计划部门构造一个模型, 表示.计划部门构造一个模型,即在一 定条件下,使总发电量年平均值最大, 定条件下,使总发电量年平均值最大, 用数学语言来说,使其期望值最大. 用数学语言来说,使其期望值最大.对 每个电厂i 每个电厂i ,其年发电量的期望值为 ∫Ei(ki,Q) dFi(Q) 设V为总投资额,Vi为各水电厂的投资, 为总投资额, 为各水电厂的投资,
f(λx1+(1- λ)x2 ) f(λ +(1-
f(X1)
X1
+(1λx1+(1-
λ)x2
X2
X
f(X)
λf( x1 ) +(1- λ) f( x2) +(1-
f(X2)
f(λx1+(1- λ)x2 ) f(λ +(1-
f(X1)
X1
+(1λx1+(1-
λ)x2
X2
X
f(X) 任意两点的函数值的连线上的点都在曲线的上方
λf( x1 ) +(1- λ) f( x2) +(1-
f(X2)
f(λx1+(1- λ)x2 ) f(λ +(1-
f(X1)
X1
+(1λx1+(1-
λ)x2
X2
X
线性函数既是凸函数,又是凹函数, 线性函数既是凸函数,又是凹函数, 反之也然. 反之也然. 梯度向量 f(X)=grad f(X) =(f/x1 ,f/x2 ,…..,f/xn) =(f/ f/ ,…..,f/ 正定矩阵 如果对矩阵H(X),对任意 对任意X 如果对矩阵H(X),对任意X ∈ N(X* ,δ) Z∈ En 均有 ZT H(X)Z > 0( ≥ 0 ) 则称H(X)在 点正定(半正定). 则称H(X)在X* 点正定(半正定).
(P1) Min f(X)
X ∈ En
定理4 一阶充分条件) 定理4(一阶充分条件) 设f(X)为En上的凸函数,又设f(X) f(X)为 上的凸函数,又设f(X) 点可微,如果f(X 在X*点可微,如果f(X*) =0 ,则X*为 (P1) 的一个整体最优解. 的一个整体最优解.
例6-2 Min f(X)=(x2-1)3 f(X)=(
最优性条件的研究是非线性规划理论 研究的一个中心问题. 研究的一个中心问题. 为什么要研究最优性条件? 为什么要研究最优性条件? o本质上把可行解集合的范围缩小. 本质上把可行解集合的范围缩小. o它是许多算法设计的基础. 它是许多算法设计的基础.
无约束问题的最优性条件
(P1)
Min f(X)
X ∈ En
模型分类2 模型分类2 o若m=l=0 ,则称(P)为无约束问题. 则称( 为无约束问题. Min f(X) (P1)
X ∈ En
模型分类2 模型分类2 o若m≠0,l=0 ,则称(P)为带等式 则称( 约束问题. 约束问题. (P2) Min
f(X)
s.t. hi(X)=0 (i=1,2,….m)
凸函数的概念 定义:定义在凸集D 定义:定义在凸集DEn上的函数f(X) 如果对任意两点x 如果对任意两点x(1),x(2) ∈D,均有0<λ<1 均有0<λ 使得 f(λ x(1)+(1- λ)x(2)) ≤ λ f( x(1) ) +(1- λ) f( x(2)) f(λ +(1+(1则称函数f(X)为D上的凸函数. 上的凸函数.
Min f(X)
s.t. hi(X)=0 (i=1,2,….m) gj(X) ≥ 0 (j=1,2….l)
X ∈ En
凸函数的概念 凸集概念: 凸集概念: 设D是n维线性空间En的一个点集, 维线性空间E 的一个点集, 中的任意两点x 的连线上的 若D中的任意两点x(1),x(2)的连线上的 一切点x仍在D 则称D为凸集. 一切点x仍在D中,则称D为凸集. 中的任意两点x 即:若D中的任意两点x(1),x(2) ∈D, 存在0<α 存在0<α<1 使得 x= α x(1)+(1- α)x(2) ∈ D,则称D为凸集 +(1D,则称 则称D
凸函数的概念 若严格不等式成立, 若严格不等式成立,则称函数f(X)为D上 的严格凸函数. 的严格凸函数. 如果 - g(X)为D上的(严格)凸函数,则g(X) 上的(严格)凸函数, 上的(严格) 凹函数. 为D上的(严格) 凹函数.
f(X) f(X2)
f(X1)
X1
X2
X
f(X) f(X2)
定理3 二阶充分条件) 定理3(二阶充分条件) 设f(X)在X*点二阶可微,如果f(X*) f(X)在 点二阶可微,如果f(X =0 和 H(X*)为正定,则X*为(P1) 的一个 H(X 为正定, 局部最优解.( H(X 的邻域内为 局部最优解.( H(X)在X*的邻域内为 半正定. 半正定.
无约束问题的最优性条件
定理2 二阶必要条件) 定理2(二阶必要条件) 设f(X)在X*点二阶可微,如果X*为 f(X)在 点二阶可微,如果X (P1) 的一个局部最优解,则有 的一个局部最优解, f(X*) =0 和 H( X* )为半正定. f(X 为半正定.
无约束问题的最优性条件
(P1) Min f(X)
X ∈ En
第六章 非线性规划
1 引
言
非线性规划是运筹学中包含内容最多, 非线性规划是运筹学中包含内容最多, 应用最广泛的一个分支, 应用最广泛的一个分支,计算远比线性 规划复杂,由于时间的限制, 规划复杂,由于时间的限制,只能作简 单的介绍. 单的介绍. 例6-1 电厂投资分配问题 水电部门打算将一笔资金分配去建设n 水电部门打算将一笔资金分配去建设n 个水电厂,其库容量为k ,i=1,2….n,各 个水电厂,其库容量为ki,i=1,2….n,各
几个概念 定义2 定义2 X*称为(P)的一个(整体) 称为( 的一个(整体) 最优解,如果X 最优解,如果X* ∈D,满足 f(X) ≥ f(X*), X ∈D.
几个概念 定义3 定义3 X*称为(P)的一个(局部) 称为( 的一个(局部) 最优解,如果X 且存在一个X 最优解,如果X* ∈D,且存在一个X* 的邻域 N(X* ,δ)= X ∈ En X- X* < δ 满足 f(X) ≥ f(X*), X ∈D∩ N(X* ,δ) δ>0
几个概念 定义1 如果X满足( 定义1 如果X满足(P)的约束条件 hi(X)=0 (i=1,2,….m) gj(X) ≥ 0 (j=1,2….l) 则称X 则称X ∈ En 为(P)的一个可行解. 的一个可行解. 记(P)的所有可行解的集合为D, 的所有可行解的集合为D D称为(P)可行域. 称为( 可行域.
局部最优n f(X) s.t. hi(X)=0 (i=1,2,….m) gj(X) ≥ 0 (j=1,2….l) X ∈ En f(X) hi(X) gj(X) 为En上 的实函数. 的实函数. (P)
模型分类1 模型分类1 如果 f(X) hi(X) gj(X) 中至少有 一个函数不是线性(仿射)函数, 一个函数不是线性(仿射)函数,则 为非线性问题. 称(P)为非线性问题. 如果 f(X) hi(X) gj(X) 都是线性 仿射)函数,则称( (仿射)函数,则称(P)为线性问 题.
o若H(x)为正定,该驻点X*是严格局部 H(x)为正定 该驻点X*是严格局部 为正定, 极小值点; 极小值点; o若H(x)为负定,该驻点X*是严格局部 H(x)为负定 该驻点X*是严格局部 为负定, 极大值点; 极大值点; o若H(x)为半正定(半负定)则进一步 H(x)为半正定 半负定) 为半正定( 观察它在该点某邻域内的情况, 观察它在该点某邻域内的情况,如果保 持半正定(半负定), ),那它们是严格局 持半正定(半负定),那它们是严格局 部极小值点(极大值点); 部极小值点(极大值点); o如果H(x) 不定的,该驻点X*就不是f(X) 如果H(x) 不定的,该驻点X*就不是 就不是f(X) 极值点. 极值点.