资源描述：
《构造辅助函数巧解题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、构造辅助函数巧解题1、相关定义1.1、一些定义和算法考虑如下非线性整数规划问题:(P)???s.mit.nxf(∈x)Ω,.(2-1)这里Ω={x∈In:a≤x≤b}是一个有界且封闭的箱子集合,In是Rn中的整数点集合。假设f(x)满足强制性条件,即当x→+∞时,有f(x)→+∞。定义2.2.1[30]整数集合N(x)?In称为整数点x的一个邻域,如果N(x)={x,x+ei,x?ei,i=1,2,,n},其中ei为第i个分量为1,其余分量为0的n维单位向量。整点x的一个空心邻域记为N0(x)=N(x){x}。定义2.2.2[30]整数点x0称为关于非线性整数规划问题(P
2、)的一个局部极小点,如果存在一个邻域N(x0),使得对所有x∈N(x0)∩Ω,均有f(x)≥f(x0)成立;整数点x0称为关于非线性整数规划问题(P)的一个全局极小点,如果对所有x∈Ω,均有f(x)≥f(x0)成立。另外,如果对所有x∈N0(x)∩Ω(x∈Ω{x0})均有f(x)>f(x0),则x0称为非线性整数规划问题(P)的一个严格局部(全局)极小点。显然,函数f(x)关于问题(P)的一个全局极小点一定是它的一个局部极小点。11函数f(x)关于非线性整数规划问题(P)的局部极小点由以下算法得到:算法1[30]步1.任取整数点x0∈Ω;步2.如果x0是问题(P)的一个局
3、部极小点,则算法终止;否则,在邻域N(x0)中搜索,得到一个点x∈N(x0)∩Ω满足f(x)0满足以下条件:01.2、一些定义考虑如下无约束全局优化问题:???s.mti.nxf∈(xR),n.本文一直假设以下情况成立:1.f(x)在Rn上连续可微;2.f(x)满足强制性条件,即当x→+∞时,f(x)→+∞。由假设2知,存在一个闭的箱子集合X?Rn,在X中含有f(x)的所有全局极小点,因此最初的问题又等价于以下问题:(P)???s.mti.nxf∈(xX).,3.f(x)在X中仅有有限个局部极小值,但可以有无限个局部极小点。下面我们给出填充函数定义如下:定义4.2.1[34
4、]设x*是f(x)的一个当前局部极小点,函数p(x,x*)称为f(x)在x*的一个填充函数,如果p(x,x*)具有以下性质:(1)x*是p(x,x*)的一个局部极大点,且f(x)在x*的盆谷成为p(x,x*)的山丘的一部分;(2)满足f(x)≥f(x*),x≠x*的点x均不是p(x,x*)的平稳点;(3)如果f(x)在另一个局部极小点x1*的盆谷B1*低于B*,那么p(x,x*)在x*和x2的连线上有极小点x’∈B1*,其中x2是x1*的某一邻域中的任意一点。291.3、一些基本定义对于全局最优化问题???sm.ti.nxf∈(xX).,(1-1)有如下基本定义:定义1.3
5、.1至少有一个x*G∈X使得对?x∈X有f(x)≥f(x*G),或证明这种点不存在,这样的问题称为极小化问题。定义1.3.2设x*∈X,如果对于?x∈X有f(x)≥f(x*)成立,则称x*是问题(1-1)的全局极小点;如果对于?x∈X且x≠x*均有f(x)≥f(x*)成立,则称x*是问题(1-1)的严格全局极小点。定义1.3.3设x*∈X,若对于x*的邻域Ο(x*,δ),δ>0中的任意点x有f(x)≥f(x*)成立,则称是问题(1-1)的局部极小点;如果对于?x∈Ο(x*,δ)且x≠x*均有f(x)>f(x*)成立,则称x*是问题(1-1)的严格局部极小点。定义1.3.4f
6、(x)在局部极小点x1*的盆谷B1*是一个连通域,x1*∈B1*,而且从B1*中任意一点出发的f(x)的最速下降轨迹趋向于x1*,但从B1*外面的点出发的最速下降轨迹均不趋向于x1*.若x?1*是f(x)的极大点,则f(x)在?x1*处的山丘是?f(x)在其极小点x?1*处的盆谷。为方便起见,称f(x)的一个极小点x2*小于(大于)x1*,当且仅当f(x2*)≤(>)f(x1*),(1-4)称f(x)在x*2的盆谷B2*低于(高于)B1*,当且仅当(1-4)成立。显然,若B1*是f(x)在局部极小点x1*的盆谷,则对所有的x∈B1*,x≠x1*,成立f(x)>f(x1*)。
7、可以证明,假设x1*是f(x)的局部极小点,若?2f(x1*)正定的,则S1*的最小半径*1*1Dminxx=x∈S?(1-5)不等于零,其中{()()}S1*=x∈B1*x?x1*T?fx>0是包含于B1*的一个连通域,B1*是4f(x)在局部极小点x1*的盆谷。称S1*为f(x)在局部极小点x1*的简单盆谷。1.4、”多思少算”的概念界定考的一种命题理念,也是《考试大纲》中明确指出的,应”多一点想的,少一点算的”.”多思少算”,顾名思义,即要求学生在解题时注重”多思”而非见着数字即”计算”,”多思”可达到减少思
