数值最优化方法罚函数方法.pptVIP

* * * 内外罚函数的比较 罚函数： 可行性： 收敛性： 特殊性质： * 外罚 内罚 单调增加 单调减少 单调减少 单调增加 单调增加 单调减少 增广函数 惩罚项 目标函数 惩罚因子 * * 外罚函数 想！。。。。。 * 一个“罚”的例子 怎么办？ 再想！～～～ * * * * 对于不等式约束 怎么办？ 想一想 有没有其他形式的惩罚项。 * * * * 理由充分吗？ * 小结 * Previously 外罚 SUMT技术 * 外罚函数法的计算步骤 那么这类方法是否能收敛呢？？ 有道理吗？ 又是一个 伏笔！！ * 解释一下这三个式子，告诉我们什么信息呢？？ * * * * * * * * * 如何克服上述的可行性的缺点 内罚的原因 保持可行性 方法： 筑墙 防止 越界 特点：只适用于不等式约束 * * 如何可行？ * 内罚函数法计算举例 * SUMT内点法的特点 * 第(2)问作为课堂练习！(课本上没有，请补充) * * * 一般约束优化问题 s.t. 已经有的工具，无约束优化的方法 怎么样利用？？ s.t. 考虑如下理想的罚函数 能算不？？？ 计算机是否认识无穷大？ 其中的表示很大的正数。 这种形式唯一吗？？ 它的解是多少。 s.t. s.t. 其中的表示很大的正数。 当时， 即无约束优化问题最优解的极限为原问题的解。 将此问题更一般化，对于等式约束问题。 s.t. 其中的为参数，成为惩罚因子。定义惩罚项 仔细想想惩罚项的应该具有的性质。 类似的构造 其中 惩罚项所具有的性质应该怎么样呢？怎么取呢？ 一般约束优化问题 s.t. 怎么构造罚函数？ 通常取 为什么？ 具体实施的时候，真的取一个很大的吗？ 求解一系列的无约束极小问题 ，这样和取有什么区别。 举例 s.t. 伏笔：这里发生了一件很重要的事情！！！！~~ 有没有发现“伏笔” 故 令 ， 当时可得最优解 我们容易发现，时，的最优解趋向于，即趋向于原来问题的最优解。但是，我们也能发现，往往是不可行的。 例如上面的例子中 所以这类方法都是从可行域的外部趋向于最优解的，因此我们陈这类方法为外罚函数法。 通过求解一系列的无约束优化问题，来求解约束优化问题的方法，又称之为序列无约束极小化技术(Sequential Unconstrained Minimization Technique)，简称SUMT。所以外罚函数方法又称为SUMT外罚函数法。 一般约束优化问题 s.t. 怎么构造罚函数？ Step 1 初始点 和 初始罚因子 。 Step 2 以为初始点，求无约束问题 得到。 Step 3 若（为什么这个是收敛准则），则以为近似最优解，停止。否则，令，转Step 2。 引理：用外罚函数法求解约束的最优化问题，设迭代产生的点列为，证明如下不等式： （1）， （2）， （3）。 证明 (1)因为是的极小点，且，故 （2）因为是的极小点，将带入中得 又因为是的极小点，将带入中得 将上述两个式子移项可得 ① ② 将① 和②联立可得 即 ③ 因为，所以由③式可得。 （3），又由第（2）问得结果和②式可得 即 收敛定理：设为约束极值问题的整体最优解，为的整体最优解。对于正的序列,,，则，由SUMT外点法产生的任何聚点，必定是原来约束优化问题的整体最优解。 s.t. 证明：不妨设：，由题意，从而有 看出问题了吗 由上面的引理，单调上升，并且根据上面的式子有上界，所以， 。 根据引理，我们还知道单调增加，并且 （4.1.3） 故也收敛，设，于是 定理证明的过程中还有什么信息告诉我们。 由于，并且连续，所以 所以为可行解，根据的定义 由4.1.3式和以及的连续性可知 所以 证明完毕。 说明： ，故。 （4.1.3） 优点：好用！ 缺点： 不可行， 很大时，条件很坏。 不等式约束优化问题 s.t. 罚函数 特点？ 高墙！ ，或 障碍函数（内罚函数） 为惩罚因子(很小的正数)。 应用SUMT技术，求解一系列的无约束优化问题 可行域内部逼近最优解，也称为内罚函数法，或SUMT内点法。 内罚函数法的计算步骤（可行域的内点集非空） Step 1 初始点可行点 和 初始罚因子 。 Step 2 以为初始点，求无约束优化问题 得到。 Step 3 若（为什么这个是收敛准则）， 则以为近似最优解，停止。 否则，令，转Step 2。 s.t. 解： 令： ， ，当时，， 用内罚函数法求解只含不等式约束的最优化问题，设迭代产生的点列为，证