第4章最优性条件

45 第4 章 最优性条件 §4 .1 最优性条件的预备知识 1．极小点的定义 无约束问题： 1 (1) 定义1（全局极小点）若存在nRx使得 nRxxfxf ),()( 则称x 为问题(1)的全局极小点。如果有 xxRxxfxfn, ),()( 则称x 为问题(1)的严格全局极小点。 定义2 （局部极小点）设nRx，如果存在0使得 )( ),()(xNxxfxf 则称x 为问题(1)的局部极小点。如果有 }/{)( ),()(xxNxxfxf 则称x 为问题(1)的严格局部极小点。 约束问题： )(minxf (2) s.t. mixgi,,1,0)( ljxhj,,1,0)( 其中)( ),( ),(xhxgxfji都是定义在nR 上的实值连续函数，且至少有一个是非线性的。 称)(xf为目标函数，)(xgi为不等式约束函数,)( xhj为等式约束函数。 (i) 如果0m，称(2)为等式约束优化问题； (ii) 如果0l，称(2)为不等式约束优化问题； (iii) 如果),,1)(( ),,,1)((ljxhmixgji都为线性函数，)(xf是二次函数，则称(2)为二次规划问题。 若nRx满足(2)的所有约束条件，称x为(2)的可行点(或可行解)。 可行集（可行域）：.,,1,0)(,,,1,0)( ljxhmixgxSji。 定义3 (全局极小点)设Sx 使得 Sxxfxf ),()( 成立，则称x 为问题(2)的全局极小点。如果有 xxSxxfxf, ),()( 46 成立，则称x为问题(2)的严格全局极小点。 定义4 (局部极小点)设Sx，如果存在0使得 SxNxxfxf)( ),()( 成立，则称x为问题(2)的局部极小点。如果有 xxSxNxxfxf,)( ),()( 成立，则称x为问题(2)的严格局部极小点。 2. 内容安排 ■ 求全局极小点一般来说相当困难。实际上可行的只是求一个局部(或严格局部)极小点。故本课程后面所指极小点，通常指求局部极小点。 ■ 仅当问题为凸规划(即目标函数)(xf为凸函数，不等式约束函数mixgi,,1 ),(为凸函数，等式约束函数ljxhj,,1 ),(为线性函数)时，局部极小点才是全局极小点。 ■ 按定义验证最优解是不可能的。因此有必要给出只依赖于在x处目标函数和约束函数信息的、且与定义等价的条件。 这样的条件称其为最优性条件，它们是各种基于梯度算法的理论基础。 §4 .2 无约束问题的最优性条件 考虑无约束问题(1)，回忆当Rx时，即单变量函数极值问题的最优性条件： 必要条件：若Rx且)(xf在x处取到极值，如果)(xf在x可微，则x为)(xf的驻点，即满足0)...