张京-最优化第一章幻灯片.ppt

(1)必要性 已知 是凸函数，所以对任意 上式实际上仅要求对任意 成立即可。 右边按Taylor展开取一阶项有（在 处） * 充分性 （2）充分性与（1）中类似，必要性如下。 严格凸函数必是凸函数，所以对任意 * 由于 ，所以 矛盾。 定理： 为非空开凸集。 是二次 可微函数，则 （1） 上凸函数的充要条件是 的Hesse 阵在C上处处正半定； （2）当 在C上处处正定时，则 为严格 凸函数。 * 证（1）必要性 已知 上是凸函数，需要 证明，对任意 因为C是开集，所以存在 由Taylor公式 再由 凸性定理知 * 充分性 已知 对任意 所以 是凸函数。 （2）证明与（1）中充分性证明类似。 注：（2）不是充要条件，即当 是严格凸函 数时， 不一定处处正定。 例如，一元函数 不是处处 正定，但它是严格凸函数。因为对任意 * * 我们要证明 即证 当 时， 即证 即证 即证 即证 即证 即证 即证 当 时，必有 上式成立。当 时，必有上式成立。 * 所以 是严格凸函数。当 时，可类似 得到结论。由上述定理，可以验证： 是严格凹函数。因为 是处处正定的。 即不是凸函数，也不是凹函数。因为 非正半定， 非正半定。 三、 凸规划 设 是定义在非空凸集 上的凸函数， 则形式为 的最优化问题称为凸规划问题，简称凸规划。换言之， 定义在凸集上的凸函数的极小化问题是凸规划问题。 若 都是 上的凹函数， 都是 上的线性函数，容易验证集合 是凸集。在这种情况下，凸规划可以表示成如下形式 * 定理 设 是凸规划的局部极小点。则 （1）当 必是全局极小点； （2）当 是严格凸函数时， 必是唯一极小点； * 是凸函数时， 是凸函数）。 是凸集。而 是凸集。 （3）全局极小点集合仍是凸集。 * 证（1）如果 不是全局极小点，因为 是凸集，所以对任意 当 充分接近1时，上式也成立，且 充分接近 ，所以在 附近，有 这与 是局部极小点矛盾。 （2）即要证明严格凸函数的极小点必唯一。 假设 都是极小点，且 由（1）， 它们都是全局极小点，所以 矛盾。 四、 二次函数 函数 称为 元二次函数，其中 是对称矩阵， * 为常数。由于 * 显然， 当Q是正半定时，f是凸函数； 当Q是正定时，f是严格凸函数。 * 开始 最优化方法（最优化课件研制组） 退出 主讲：张 京 * 最优化方法 　 为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。最优化方法是在第二次世界大战前后，在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。 最优化方法解决问题一般步骤： （1）提出需要进行最优化的问题，开始收集有关资料和数据； （2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件； （3）分析模型，选择合适的最优化方法； （4）求解方程。一般通过编制程序在电子计算机上求得最优解； （5）最优解的验证和实施。 随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军事和社会研究的各个领域。 * 第1章 预备知识 §1.2 最优化问题实例 上述4个例子都是最优化问题，其中例3与例4是NP问题，例1与例2是LP问题，例3是无约束问题，例4是有约束问题，将在第三章、第四章中讨论它们的基本理论与算法。 通过求解方程组（求驻点） 问题（2） 问题（1） * 通过求 的无约束极值即可（也求L的驻点）。通过求驻点求极值问题的解的方法称为经典极值。它们的求解都归结为非线性方程组的解。 优化模型分类： （1）按函数类型分，有线性和非线性模型； （2）按有无约束分，有无约束和有约束模型； （3）按变量类型分，变量取整数值和取连续值； （4）按目标个数分，有单目标和多目标模型； （5）按涉及的阶段分，有静态和动态模型； （6）按参数类型分，有确定性和非确定性优化。 * 优化方法的的解题步骤：1、建模；2、求解；3、回代。 §1.3 最优化问题的基本概念 （1） 的实值函数，f为目标函数，其余为约束条件。以上问题还可用向量形式写出：