3不等式约束最优化问题的最优性条件.ppt

《3不等式约束最优化问题的最优性条件.ppt》由会员分享，可在线阅读，更多相关《3不等式约束最优化问题的最优性条件.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件不等式约束最优化问题不等式约束最优化问题 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件定定义义闭包闭包：Closure Closure 可行方向可行方向：可行方向锥可行方向锥：S S在点在点 处的可行方向锥处的可行方向锥Feasible direction cone注注:当当 时时,S在在 处的可行方向锥是全空间处的可行方向锥是全空间Rn.不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件定定义义下降方向下降方向(descent direction)：下降方向锥下降方向锥：f f在点在点 处的下降

2、方向锥处的下降方向锥 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件可行方向锥与下降方向锥的几何解释可行方向锥与下降方向锥的几何解释在极小点处，任何在极小点处，任何在极小点处，任何在极小点处，任何下降方向都不是可下降方向都不是可下降方向都不是可下降方向都不是可行方向，而任何可行方向，而任何可行方向，而任何可行方向，而任何可行方向也不是下降行方向也不是下降行方向也不是下降行方向也不是下降方向，即，不存在方向，即，不存在方向，即，不存在方向，即，不存在可行下降方向可行下降方向可行下降方向可行下降方向.SF F0 0D D有效约束有效约束：非有效约束非有效约束：有效集有效集：不等式

3、约束最优化问题的最优性条件不等式约束最优化问题的最优性条件定义定义设设(3.3.1)(3.3.1)中的一个可行点中的一个可行点满足满足为在为在处的有效约束或紧约束处的有效约束或紧约束则称约束则称约束 Active Active Constraint Constraint 若有若有则则为为在在处的非有效约束或松约束处的非有效约束或松约束称称 inactive inactive ConstraintConstraint 在可行点在可行点在可行点在可行点 处的有效约束的指标集：处的有效约束的指标集：处的有效约束的指标集：处的有效约束的指标集：有效约束与非有效约束有效约束与非有效约束-几何解释几何解释

4、不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Sg g2 2(x)=0(x)=0g g1 1(x)=0(x)=0g g3 3(x)=0(x)=0(1)(1)在点在点 处处,g g1 1(x)0(x)0 和和 g g2 2(x)0(x)0是有效约束；是有效约束；g g3 3(x)0(x)0是非有效约束是非有效约束.(2)(2)的非有效约束的非有效约束g g3 3(x)0(x)0对对 处的可行方向没有影响，处的可行方向没有影响，故非有效约束也称为故非有效约束也称为不起作用的约束不起作用的约束.定理定理3.3.1:3.3.1:考虑约束最优化问题考虑约束最优化问题几何最优性条件几何最

5、优性条件一阶必要条件一阶必要条件 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件定理定理3.3.2:3.3.2:在问题在问题(3.3.1)(3.3.1)中，假设：中，假设：(1)(1)为局部最优解且为局部最优解且(2)(2)与在在点可微；点可微；(3)(3)在在点连续；点连续；则则几何最优性条件几何最优性条件一阶必要条件一阶必要条件 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件仅考虑在某点起作用的约束仅考虑在某点起作用的约束例例1 1：确定确定：在点在点处的可行下降方向处的可行下降方向.解解：不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件

6、几何最优性条件几何最优性条件一阶必要条件一阶必要条件设设 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件几何最优性条件几何最优性条件一阶必要条件一阶必要条件 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件l 几何最优性条件直观几何最优性条件直观,但难以在实际但难以在实际 计算中应用计算中应用.l将几何最优性条件转化为代数将几何最优性条件转化为代数 最优性条件最优性条件.?几何最优性条件几何最优性条件一阶必要条件一阶必要条件(1)Fritz John 条件条件(2)Kuhn-Tucker 条件条件(1948)(1948)不等式约束最优化问题的最优性条件不等式约

7、束最优化问题的最优性条件Fritz John 最优性条件最优性条件一阶必要条件一阶必要条件 定理定理3.3.3:3.3.3:设设为问题为问题(3.3.1)(3.3.1)的局部最优解且的局部最优解且在在点可微，点可微，则存在非零则存在非零使得：使得：则存在则存在非非零的向量零的向量例例2 2：验证验证处处Fritz-John条件是否成立？条件是否成立？解解：取有Fritz John 最优性条件最优性条件一阶必要条件一阶必要条件 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件即该问题在即该问题在x*处处Fritz-John条件成立条件成立.Fritz John 最优性条件最优性条

8、件一阶必要条件一阶必要条件 不等式约束最优化不等式约束最优化问题的最优性条件问题的最优性条件注注:(1)上例说明在上例说明在Fritz John条件中有可能条件中有可能0=0.此时，目此时，目 标标 函数的梯度就会从函数的梯度就会从Fritz John中消失中消失,即即Fritz John 条件实际上不包含目标函数的任何信息，仅仅表明条件实际上不包含目标函数的任何信息，仅仅表明 起作用约束函数的梯度线性相关，而这对表述最优起作用约束函数的梯度线性相关，而这对表述最优 点没有什么实际价值点没有什么实际价值.(2)为了保证为了保证0 0,还需要对约束再加上一些限制条件这种限还需要对约束再加上一些限

9、制条件这种限 制条件通常称为制条件通常称为约束规格约束规格(Constraint Qualification)一个一个 自然的想法是附加自然的想法是附加 线性无关的约束规格线性无关的约束规格 (当然还有许多其他的约束规格当然还有许多其他的约束规格)，这样就得到了著名的，这样就得到了著名的 KuhnTuker条件条件.(1951)(1951)定理定理3.3.43.3.4设设为为 (3.3.1)(3.3.1)局部最优解局部最优解,在在点可微，点可微，对于对于的的线性无关，线性无关，则存在非零向量则存在非零向量使得：使得：不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tu

10、cker 最优性条件最优性条件一阶必要条件一阶必要条件 K-TK-T条条件件互补互补松弛松弛条件条件 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tucker 最优性条件最优性条件一阶必要条件一阶必要条件 式式(a)(a)的几何意义的几何意义:在局部在局部极小点极小点 x xk k 处处,目标函数的梯度目标函数的梯度能表示成有效约束梯度的能表示成有效约束梯度的非负组合非负组合,即目标函数的即目标函数的梯度属于有效约束的梯度梯度属于有效约束的梯度所生成的凸锥内所生成的凸锥内.例例3 3：验证验证处处kuhnkuhn-Tucker-Tucker条件是否成立？条件是否成

11、立？解解：对对所以所以不是不是K-T点点原因是原因是线性相关线性相关 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tucker 最优性条件最优性条件一阶必要条件一阶必要条件 定理定理3.3.53.3.5 不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tucker 最优性条件最优性条件一阶充分条件一阶充分条件 设设在问题在问题(3.3.1)(3.3.1)中中是凸函数是凸函数,是可行点，是可行点，且在在 处可微处可微.若若 是是(3.3.1)(3.3.1)的的K-TK-T点点,则则是是(3.3.1)(3.3.1)的全局极小点的全局极小点.K

12、-T条件对于约束问题的重要性在于：条件对于约束问题的重要性在于：1）检验某点是否为约束最优点；）检验某点是否为约束最优点；2）检验一种搜索方法是否可行。）检验一种搜索方法是否可行。例例4 4：判断判断x x(k(k)=1 0=1 0T T是否为下列约束优化问题最优点：是否为下列约束优化问题最优点：不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tucker 最优性条件最优性条件一阶充分条件一阶充分条件 解：解：1）判断）判断该点起作用约束该点起作用约束：2）计算目标函数及计算目标函数及有效约束在有效约束在 该点梯度：该点梯度：不等式约束最优化问题的最优性条件不等式约束最优化问题的最优性条件Kuhn-Tucker 最优性条件最优性条件一阶充分条件一阶充分条件 5-1 5-1 约束最优解及其必要条件约束最优解及其必要条件3）代入）代入K-T条件，求乘子条件，求乘子：解得解得：因此该点是最优点因此该点是最优点.又该问题为凸规划又该问题为凸规划,即该点是即该点是K-T点点.