n元函数局部极值存在的一阶充分条件*

黄正刚

(重庆理工大学 理学院, 重庆 400054)

摘要: 提出了n(n≥1)维欧氏空间中,相对经典无约束最优化问题更一般情况下,局部极值存在的统一的一阶充分条件,解决了最优化领域至今没有这一结论的困难,证明了一元函数局部极值存在的一阶充分条件是它的特殊情况通过具体例子说明了该文结论可以消除经典的多元函数局部极值存在的二阶充分条件的缺点,最后在拟凸、拟凹假设下证明了该结论还是 n元函数局部极值存在的充分且必要条件

关 键 词: 局部极值; 一阶充分条件; 二阶充分条件; 拟凸; 拟凹

引 言

基于n-维欧氏空间的无约束最优化问题是最优化领域中一个基本而又十分重要的内容,其形式为

min(max) f(x), xRn,

(1)

其中,函数f:RnR,Rn表示n维欧氏空间,1≤nN,N表示自然数集,当n=1时,R1简记为R(实数集)这里假设f在点x0Rn的某去心邻域内可微

对问题(1),fRn上的极值、极值点定义如下:

定义1[1-2]f:RnR,点x0Rn如果存在x0的某一邻域U使得

f(x)≥(>)f(x0), ∀xU, xx0,

则称x0fRn上的局部(严格局部)极小点, f(x0)是fRn上的局部(严格局部)极小值; 若以上不等号改为“≤(<)” 时成立,则称x0fRn上的局部(严格局部)极大点, f(x0)是fRn上的局部(严格局部)极大值fRn上的局部(严格局部)极大点、极小点统称为fRn上的局部(严格局部)极值点,简称极值点; fRn上的局部(严格局部)极大值、极小值统称为fRn上的局部(严格局部)极值,简称极值

显然,fRn上的严格局部极值点是fRn上的局部极值点, fRn上的严格局部极值是fRn上相应的局部极值

众所周知,计算(或判断)问题(1)中函数的极值主要是利用f在一点的导数(梯度)、二阶导数(Hesse矩阵)[1-3],或f或约束函数(可行集)局限于一定的条件,如文献[3-10]f在所讨论点可微时,部分不存在极值的具体问题可以由极值存在的必要条件解决,而计算(或判断)问题(1)中极值的统一的非方向导数形式的充分条件除了一元函数(即n=1)有一阶和二阶充分条件外,多元函数只有二阶充分条件(见定理2),没有一阶充分条件,所以当f在所讨论点不可导或Hesse矩阵不存在,或f在这一点的AC-B2=0时就不能解决了(见定理3); 当f非可微时,研究问题(1)的另一个方法是利用方向导数[6,11-23]Ginchev等[6]利用下一、二阶和高阶Ginchev方向导数得到了严格局部极小点存在的二阶和高阶充分条件,Huang等[11]用一阶下Dini方向导数和下二阶Chaney方向导数获得了严格局部极小点存在的二阶充分条件,Bednarik等[12]基于一、二阶B-P方向导数给出了驻点是严格局部极小点的二阶充分条件以方向导数为工具得到函数极值存在的充分或必要条件很多,使用方向导数研究问题(1)的其他已有结果不再一一详述但如果f在所讨论点可微时,则f在这一点的这些方向导数很多等价于这一点的同阶导数,如下二阶Dini方向导数fD(x0,u)=2f(x0)u(2f(x0)表示fx0的Hesse矩阵),于是又面临上面同样的困难其他方向导数如下二阶Hadmard、Ginchev方向导数fH(x0,u), fG(x0,u)虽然不等于2f(x0)u,但这些方向导数的计算都是不容易的, f的维数较高(≥3)时尤其如此,如文献[13,19]

因此,我们有必要研究一种既不需任何方向导数,又无需函数在所讨论点二次可微的统一方法,这就是本文的工作背景和中心任务

f是一元函数时,问题(1)的极值点是否存在的一阶充分条件如下:

定理1 设函数f(x)在点x0连续,且在x0的某去心邻域N0(x0,δ)内可导,又f′(x0)=0或f′(x0)不存在

(a) 如果当x∈(x0-δ,x0)时, f′(x)<0,而当x∈(x0,x0+δ)时, f′(x)>0,则f(x)在x0取得极小值;

(b) 如果当x∈(x0-δ,x0)时, f′(x)>0,而当x∈(x0,x0+δ)时, f′(x)<0,则f(x)在x0取得极大值;

(c) 如果当x∈N0(x0,δ)时f′(x)的符号不变,则fx0不取得极值,其中f′(x)表示fx0的导数

f是多元函数时,问题(1)的极值是否存在的二阶充分条件如下:

定理2 假定函数f在点x0Rn(n≥2)二次可微如果f(x0)=0,Hesse矩阵H(x0)正(负)定,则x0f的极小点(极大点),H(x0)不定时x0不是f的极值点

n=2时,该定理退化为二元函数极值是否存在的二阶充分条件

定理3 设函数z=f(x1,x2)在点x0R2的某邻域内连续且有一阶及二阶偏导数, fx0 的一阶偏导数fx1(x0)=0, fx2(x0)=0,令fx0的二阶偏导数fx1x1(x0)=A, fx1x2(x0)=B, fx2x2(x0)=Cf(x1,x2)在x0是否取得极值的充分条件如下:

(a) AC-B2>0时有极值,且当A<0时有极大值,当A>0时有极小值;

(b) AC-B2<0时无极值;

(c) AC-B2=0时可能有极值,可能无极值,还需另做讨论

现在我们用定理3来解决以下典型问题:

例1 求函数的极值

分析: 不可导点为(0,0)由于f在点(0,0)的导数(梯度)f(0,0)不存在,定理3无法解决然而从函数表达式明显可知,(0,0)是f的极大点,极大值=0

例2 求函数的极值,其中x2∈(-1,1)

分析: 驻点(0,0),又A=0,B=0,C=0,AC-B2=0,所以用定理3无法解决但根据函数表达式,(0,0)是f的极小点,极小值=1

例3 讨论点(0,0)是否是函数的极值点

分析: f(0,0)=(0,0)T,A=B=C=0,不能用定理3解决事实上,当∀(x1,x2)属于折线x2=|x1|时,有所以f在(0,0)不取得极值

例4 求函数f(x1,x2)=C(C是某一常数)的极值

分析:A=B=C=0,定理3无法解决但由定义1, f在任何点(x1,x2)∈R2处取得极大、极小值C

限于篇幅,这里不再一一举例

实际上,以上各极值问题之所以无法用定理3解决,主要是因为当目标函数f为多元时,非方向导数形式的充分条件只有二阶充分条件(定理2或定理3),该充分条件只考虑所求点的导数信息,不考虑该点附近(某去心邻域)的导数信息,所以当以上各极值问题的函数不满足定理3对该点的导数要求时,就无法用该定理解决了

本文考虑比问题(1)更一般的最优化问题,首先利用目标函数f在不可导点(或驻点)的某去心邻域内的导数信息导出了极值是否存在的非方向导数形式的一阶充分条件,证明了它是定理1的推广;然后直接用此条件解决了定理3不能解决的所有典型问题,并用具体例子说明了n元函数极值存在的充分条件是充分而不必要条件;最后在函数拟凸、拟凹的假设下,证明了它还是极值存在的充分且必要条件

1 预 备 知 识

定义2 设非空集合ORn若对于∀x,yO,∀λ∈[0,1],有λx+(1-λ)yO,则称O是凸集

定义3ORn既是凸集又是开集,则称O是开凸集

实际上,当n=1时,数轴与任何开区间都是开凸集; 当n=2时,任何开圆域、开椭圆域都是开凸集; 当n=3时,任何开球都是开凸集; 当n≥1时,Rn中的任何邻域都是开凸集,RnRn中的最大开凸集

定义4[2]ORn是非空凸集, f:OR.若对于∀x,yO,有

f[λx+(1-λ)y]≤(≥)max(min){f(x), f(y)},

则称fO上的拟凸(拟凹)函数

由定义可知,凸(凹)函数一定是拟凸(拟凹)函数

引理1 有限个开凸集的交集是开凸集

引理2[24](广义Lagrange中值定理) 设ORn是非空开集, fO上可微则对任一片段[a,b]⊆O,∃c∈(a,b),使得f(b)-f(a)=(f(c))T(b-a)其中,点a,bO,片段[a,b]{λa +(1-λ)b: λ∈[0,1]}

引理3[2]ORn是非空开凸集, f: OR可微f 拟凸(凹)当且仅当对∀x,yO, f(x)≤(≥)f(y),有(f(y))T(y-x)≥(≤)0

2 一阶充分条件

考虑比问题(1)更一般的最优化问题:

min(max) f(x), xS,

(2)

其中,SRn是非空开凸集,n,N,Rn表示的意义与式(1)相同,点x0S,函数f:RnRx0的某去心邻域内可微

类似于问题(1), 可定义问题(2)中的fS上的极值、 极值点(只需将定义1中的U换成US)

现在我们给出问题(2)的极值是否存在的统一(n≥1)的一阶充分条件

定理4f: SRS\{x0}上可微,f(x0)不存在或f(x0)=0Rn

(a) 若存在x0的一个邻域U使得

(f(x))T(x-x0)≥0, ∀xUS\{x0},

fx0取得极小值;

(b) 若存在x0的一个邻域U使得

(f(x))T(x-x0)≤0, ∀xUS\{x0},

fx0取得极大值;

(c) 若存在两个不同的方向uRn, vRn, u0,v0,使得对任意充分小的t>0,(f(x0+tu))Tu>0(<0)且(f(x0+tv))Tv<0(>0),则fx0不取得极值

(a) 对假设的U,任取点xUS\{x0}由引理2,存在点y=λx+(1-λ)x0,某λ∈(0,1),使得

f(x)-f(x0)=(f(y))T(x-x0)

(3)

U是开凸集,由引理1,US是开凸集所以yUS

从而注意到假设,则有

(f(y))T(y-x0)≥0,

λ(f(y))T(x-x0)≥0,

(f(y))T(x-x0)≥0

由式(3), f(x)≥f(x0)

(b) 类似可证

(c) 不妨假定对任意充分小的t>0,(f(x0+tu))Tu>0,(f(x0+tv))Tv<0任取某一充分小的t>0,由引理2,存在0<t′<t使得

f(x0+tu)=f(x0)+t(f(x0+tu))Tu

注意到假设,则有

f(x0+tu)>f(x0)

(4)

同理可得

f(x0+tv)<f(x0)

(5)

所以由式(4)、(5),对任一充分小的t>0,

f(x0+tv)<f(x0)<f(x0+tu)

由充分小的t>0的任意性可知, fx0不取得极值

注1 根据定理4和极值存在的必要条件可知,函数的极值点(如果存在)只能来自不可导点或驻点

定理4的证明并不难,但目前最优化领域确实还未获得该结论这一结论的一个直接作用就是可以解决定理3不能解决的像上述例1~4那样的极值问题

例5 解:S=R2当(x1,x2)≠(0,0)时,

任取(0,0)的某一邻域U,有

(

∀(x1,x2)∈US\(0,0)

由定理4,(0,0)是f的极大点,极大值=0

例6 解:S=R×(-1,1),驻点(0,0)任取该驻点的某一邻域U,对∀(x1,x2)∈US,(x1,x2)≠(0,0),有

(f(x1,x2))T[(x1,x2)T-(0,0)T]=(

由定理4,(0,0)是f的极小点,极小值=1

例7 解:S=R2,u=(1,1)T,v=(-1,-1)T则对任一充分小的t>0,

(f(x0+tu))Tu=6t5>0, (f(x0+tv))Tv=-6t5<0

根据定理4, fx0没有极值

例8 解:S=R2,(f(x1,x2))T=(0,0),驻点(0,0)对(0,0)的任一邻域U,有

(f(x1,x2))T[(x1,x2)T-(0,0)T]=0,

∀(x1,x2)∈US,(x1,x2)≠(0,0)

由定理4,(0,0)是f的极大(小)点,极大(小)值=C

定理4只需函数在所求极值点附近可微,不需在该点导数与二阶导数存在,在以上例子中避免了定理4所需的条件另外,定理4对n(n≥1)元函数都适用,所以是一个统一的充分条件,举以下简单例子说明:

例9 求函数的极值

解:S=R3,驻点(0,0,0)T对驻点的任一邻域U,

(f(x1,x2,x3))T[(x1,x2,x3)T-(0,0,0)T]=

由定理4,(0,0,0)是f的极小点,极小值=0

接下来讨论: 特别地,当定理4中n=1,S=Rn,且≥(≤)为>(<)时,其结论退化为什么?

命题1n=1,S=Rn,且≥(≤)为>(<)时,定理4就是定理1

因为当n=1时,(f(x))T(x-x0)=f′(x)(x-x0),

(a) 若存在x0的某一邻域U,使得f′(x)(x-x0)>0,∀xSU,xx0,也就是当x<x0 时, f′(x)<0,当x>x0 时, f′(x)>0,所以得定理1(a);

(b) 同理这是定理1中的(b);

(c) 由于xUS, x<x0xUS, x>x0时, f′(x)的符号相同, 所以得定理1(c)

这里,有一个值得注意的问题是: 极值存在的充分条件——定理4(a)∪(b)是否还是充分且必要条件呢?

回答是否定的,举如下例子说明:

例10[20] 设函数

根据文献[20],x=0是f的极小点,且

现取点列pk=e-(2kπ-π/2),k=0,1,2,…,则limk→+∞pk=0,且当kN时均有

f′(pk)(pk-0)=f′(pk)pk>0

取点列qk=e-(2kπ+π/2),k=0,1,2,…,则limk→+∞qk=0,且当kN时均有

f′(qk)(qk-0)=f′(qk)qk<0

所以fx=0不满足定理4(a)∪ (b)的充分条件

例10说明定理4(a)∪(b)是n元函数极值存在的充分而不必要条件

最后,我们证明当定理4中的f满足广义凸(凹)-拟凸(拟凹)条件时,其结论(a)∪(b)还是充分且必要条件

定理5SRn是非空开凸集,点x0S, f:SR是可微函数x0fS上的极值点的充分且必要条件如下:

(a) 设fS上拟凸,则fx0取得极小值当且仅当存在x0的一个邻域U使得

(f(x))T(x-x0)≥0, ∀xUS\{x0};

(b) 设fS上拟凹,则fx0取得极大值当且仅当存在x0的一个邻域U使得

(f(x))T(x-x0)≤0, ∀xUS\{x0}

充分性见定理4的证明,下证必要性

(a) 设x0fS上的极小点,则存在x0 的某一邻域U,使得

f(x)≥f(x0), ∀xUS, xx0

由引理3,(f(x))T(x-x0)≥0

(b) 同理可证

3 结 论

给出了n(n≥1)维欧氏空间中最优化问题极值存在的非方向导数形式的统一的一阶充分条件,解决了最优化理论一直没有该结果的难点,证明了已有的一元函数局部极值存在的一阶充分条件是它的特殊情况通过具体例子说明本文结论可以消除经典的多元函数局部极值存在的二阶充分条件的缺点,并且从大量例子来看还没发现定理3(定理3的条件下)无法解决、定理4仍无法解决的极值问题,最后在f拟凸(凹)的假设下,证明了定理4(a)∪(b)还是问题(1)极值存在的充分且必要条件本文结论一定程度上填补了最优化理论在极值研究的空白,对工程技术、经济生产和预测等方面的优化设计有一定的理论指导作用,特别是当实际问题本身不存在最优方案时,可以在已设计的求解算法中,计算其中有无两个不同的非零方向(可用点列代替)满足定理4(c),若有,则断定原问题无解,停止迭代相信随着优化理论及应用的不断发展以及计算机水平的提高,在未来本文结论会引出其他更好的结果

参考文献References):

[1] 华东师范大学数学系. 数学分析(下册)[M]. 第4版. 北京: 高等教育出版社, 2010.(Department of Mathematics, East China Normal University. Mathematical Analysis(Vol 2)[M]. 4th ed. Beijing: Higher Education Press, 2010.(in Chinese))

[2] BAZARRA M S. 非线性规划: 理论与算法[M]. 张春柏, 王化存, 译. 贵阳: 贵州人民出版社, 1986.(BAZARRA M S. Nonlinear Programming Theory and Algorithm[M]. ZHANG Chunbai, WANG Huacun, transl. Guiyang: Guizhou People’s Publishing Press, 1986.(in Chinese))

[3] HIRIART-URRUTY J B, STRODIOT J J, NGUEN H V. Generalized Hessian matrix and second order optimality conditions for problems with C1,1 data[J]. Applied Mathematics and Optimization, 1984, 11: 43-56.

[4] BEDNARIK D, PASTOR K. l-stable functions are continuous[J]. Nonlinear Analysis: Theory, Methods & Applications, 2009, 70: 2317-2324.

[5] BEN-TAL A, ZOW J. Directional derivatives in nonsmooth optimization[J]. Journal of Optimization Theory and Applications, 1985, 47: 483-490.

[6] GINCHEV I, GUERRAGGIO A, ROCCA M. From scalar to vector optimization[J]. Applications of Mathematics, 2006, 51: 5-36.

[7] PAN L, XIU N, ZHOU S. On solutions of sparsity constrained optimization[J]. Journal of the Operations Research Society of China, 2015, 3: 421-439.

[8] YAMAMOTO S, KUROIWA D. Constraint qualifications for KKT optimality condition in convex optimization with locally Lipschitz inequalty constraints[J]. Nonlinear Analysis, 2016, 2: 101-116.

[9] MOVAHEDIAN N, NOBAKHTIAN S, SARABADAN M. Nonsmooth sparsity constrained optimization problems: optimality conditions[J]. Optimization Letters, 2019, 13(5): 1027-1038.

[10] MOVAHEDIAN N. Scaled constraint qualifications for generalized equation constrained problems and application to nonsmooth mathematical programs with equilibrium constraints[J]. Positivity, 2019, 24: 253-285.

[11] HUANG L R, NG K F. On some relations between Chaney’s generalized second-order directional derivative and that of Ben-Tal and Zow[J]. SIAM Journal on Control and Optimization, 1996, 34(4): 1220-1234.

[12] BEDNARIK D, PASTOR K. Elimination of strict convergence in optimization[J]. SIAM Journal on Control and Optimization, 2004, 4(3): 1063-1077.

[13] GINCHEV I. Higher order optimality conditions in nonsmooth optimization[J]. Optimization, 2002, 51(1): 47-72.

[14] HUANG L R, NG K F. Second-order necessary and sufficient conditions in nonsmooth optimization[J]. Mathematical Programming, 1994, 66: 379-402.

[15] HUANG L R. Separate necessary and sufficient conditions for the local minimum of a function[J]. Journal of Optimization Theory and Applications, 2005, 125: 241-246.

[16] COMINETTI R, CORREA R. A generalized second-order derivative in nonsmooth optimization[J]. SIAM Journal on Control and Optimization, 1990, 28: 789-809.

[17] CHAN W L, HUANG L R, NG K F. On generalized directional derivatives and Taylor expansions in nonsmooth optimization[J]. SIAM Journal on Control and Optimization, 1994, 32(3): 591-611.

[18] ROCKFELLA R T. First- and second-order epi-differentiability in nonlinear programming[J]. Transactions of the American Mathematical Society, 1998, 307: 75-108.

[19] JIMENEZ B, NOVO V. Higher-order optimality conditions for strict local minima[J]. Annals of Operations Research, 2008, 157: 183-192.

[20] BEDNARIK D, PASTOR K. On second-order conditions in unconstrained optimization[J]. Mathematical Programming, 2008, 113: 283-289.

[21] BAIER R, FARKHI E, ROSHCHINA V. Directed subdifferentiable functions and the directed subdifferential without delta-convex structure[J]. Journal of Optimization Theory and Applications, 2014, 160(2): 391-414.

[22] BAIER R, FARKHI E, ROSHCHINA V. From quasidifferentiable to directed subdifferentiable functions: exact calculus rules[J]. Journal of Optimization Theory and Applications Volume, 2016, 171: 384-401.

[23] SISARAT N, WANGKEEREE R. Characterizing the solution set of convex optimization problems without convexity of constraints[J]. Optimization Letters, 2019, 2: 1-18.

[24] HUBBARD J H, HUBBARD B B. Vector Calculus, Linear Algebra, and Differential Forms: a Unified Approach[M]. 3rd ed. New York: Matrix Editions, 2013.

First-Order Sufficient Conditions for Existence of Local Extremums of Multivariate Functions

HUANG Zhenggang

(College of Science, Chongqing University of Technology, Chongqing 400054, P.R.China)

Abstract: The unified 1st-order sufficient condition was proposed for existence of the local extremums of n-variable functions, in a case more general than classical unconstrained optimization ones. The difficulty of no such 1st-order sufficient condition in optimization theories was solved. Moreover, the 1st-order sufficient condition for 1-variable functions was proved to be a special case of the results. The work can eliminate the shortages of the 2nd-order sufficient conditions for existence of local extremums of classical multivariate functions, and the result is both necessary and sufficient under the assumption of quasiconvexity or quasiconcavity.

Key words: local extremum; 1st-order sufficient condition; 2nd-order sufficient condition; quasiconvexity; quasiconcavity

*收稿日期: 2019-08-09; 修订日期:2020-04-21

基金项目: 国家自然科学基金(50573095)

作者简介: 黄正刚(1972—),男,讲师,硕士(E-mail: hzg@cqut.edu.cn).

引用格式: 黄正刚. n元函数局部极值存在的一阶充分条件[J]. 应用数学和力学, 2020, 41(6): 687-694.

中图分类号: O224

文献标志码:A

DOI: 10.21656/1000-0887.400237

Foundation item: The National Natural Science Foundation of China(50573095)