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

不等式约束最优化问题 定义 定义 可行方向锥与下降方向锥的几何解释 定义 * * 不等式约束最优化问题的最优性条件　 不等式约束最优化问题的最优性条件　 闭包： Closure 可行方向： 可行方向锥： S在点 处的可行方向锥 Feasible direction cone 注:当 时, S在 处的可行方向锥是全空间Rn . 不等式约束最优化问题的最优性条件　 下降方向(descent direction)： 下降方向锥： f在点 处的下降方向锥 不等式约束最优化问题的最优性条件　 在极小点处，任何下降方向都不是可行方向，而任何可行方向也不是下降方向，即，不存在可行下降方向. S F0 D 有效约束： 非有效约束： 有效集： 不等式约束最优化问题的最优性条件　 设(3.3.1)中的一个可行点 满足 为在 处的有效约束或紧约束． 则称约束 Active Constraint 若有 则 为 在 处的非有效约束或松约束． 称 inactive Constraint 在可行点 处的有效约束的指标集： 有效约束与非有效约束---几何解释 不等式约束最优化问题的最优性条件　 S g2(x)=0 g1(x)=0 g3(x)=0 (1) 在点 处, g1(x)≥0 和 g2 (x)≥0是有效约束； g3(x)≥0是非有效约束. (2) 的非有效约束g3(x)≥0对 处的可行方向没有影响， 故非有效约束也称为不起作用的约束. 定理3.3.1: 考虑约束最优化问题 几何最优性条件—一阶必要条件 不等式约束最优化问题的最优性条件　 定理3.3.2: 在问题(3.3.1)中，假设： (1) 为局部最优解且 (2) 与 在 点可微； (3) 在 点连续； 则 几何最优性条件—一阶必要条件 不等式约束最优化问题的最优性条件　 仅考虑在某点起作用的约束 例1： 确定： 在点 处的可行下降方向. 解： 不等式约束最优化问题的最优性条件　 几何最优性条件—一阶必要条件 设 不等式约束最优化问题的最优性条件　 几何最优性条件—一阶必要条件 不等式约束最优化问题的最优性条件　 几何最优性条件直观,但难以在实际 计算中应用. 将几何最优性条件转化为代数 最优性条件. ??? 几何最优性条件—一阶必要条件 (1) Fritz John 条件 (2) Kuhn-Tucker 条件 (1948) 不等式约束最优化问题的最优性条件　 Fritz John 最优性条件—一阶必要条件 定理3.3.3: 设 为问题(3.3.1)的局部最优解且 在 点可微， 则存在非零 使得： 则存在非零的向量 例2： 验证 处Fritz-John条件是否成立？ 解： 取 有 Fritz John 最优性条件—一阶必要条件 不等式约束最优化问题的最优性条件　 即该问题在x*处Fritz-John条件成立. Fritz John 最优性条件—一阶必要条件 不等式约束最优化问题的最优性条件　 注: (1)上例说明在Fritz John条件中有可能λ0=0. 此时，目 标 函数的梯度就会从Fritz John中消失, 即Fritz John 条件实际上不包含目标函数的任何信息，仅仅表明 起作用约束函数的梯度线性相关，而这对表述最优 点没有什么实际价值. (2) 为了保证λ0 0, 还需要对约束再加上一些限制条件．这种限 制条件通常称为约束规格(Constraint Qualification)． 一个 自然的想法是附加 线性无关的约束规格 (当然还有许多其他的约束规格)，这样就得到了著名的 Kuhn—Tuker条件. (1951) 定理3.3.4 设 为 (3.3.1)局部最优解, 在 点可微， 对于 的 线性无关， 则存在非零向量 使得： 不等式约束最优化问题的最优性条件　 Kuhn-Tucker 最优性条件—一阶必要条件 K-T 条件 互补 松弛 条件 不等式约束最优化问题的最优性条件　 Kuhn-Tucker 最优性条件—一阶必要条件 式(a)的几何意义:在局部 极小点 xk 处,目标函数的梯度能表示成有效约束梯度的 非负组合,即目标函数的 梯度属于有效约束的梯度 所生成的凸锥内. 例3： 验证 处kuhn-Tucker条件是否成立？ 解： 对 所以 不是K-T点． 原因是 线性相关． 不等式约束最优化问题的最优性条件　 Kuhn-Tucker