《最优化方法》课程复习考试.doc

《最优化方法》复习提要 最优化问题与数学预备知识 §1. 1 模型 无约束最优化问题 ． 约束最优化问题（） 即 其中称为目标函数，称为决策变量，称为可行域， 称为约束条件． §1. 2 多元函数的梯度、Hesse矩阵及Taylor公式 定义 设．如果维向量，，有 ． 则称在点处可微，并称为在点处的微分． 如果在点处对于的各分量的偏导数 都存在，则称在点处一阶可导，并称向量 为在点处一阶导数或梯度． 定理1 设．如果在点处可微，则在点处梯度 存在，并且有． 定义 设．是给定的维非零向量，．如果 存在，则称此极限为在点沿方向的方向导数，记作． 定理2 设．如果在点处可微，则在点处沿任何非零方向的方向导数存在，且，其中． 定义 设是上的连续函数，．是维非零向量．如果，使得，有（）．则称为在点处的下降（上升）方向． 定理3 设，且在点处可微，如果非零向量，使得（）0，则是在点处的下降（上升）方向． 定义 设．如果在点处对于自变量的各分量的二阶偏导数都存在，则称函数在点处二阶可导，并称矩阵 为在点处的二阶导数矩阵或Hesse矩阵． 定义 设，记，如果 在点处对于自变量的各分量的偏导数 都存在，则称向量函数在点处是一阶可导的，并且称矩阵 为在点处的一阶导数矩阵或Jacobi矩阵，简记为． 例2 设，求在任意点处的梯度和Hesse矩阵． 解 设，则， 因，故得． 又因，则． 例3 设是对称矩阵，，称为二次函数，求在任意点处的梯度和Hesse矩阵． 解 设，则 ， 从而． 再对求偏导得到，于是 ． 例4 设，其中二阶可导，，试求． 解 由多元复合函数微分法知 ． 定理4 设，且在点的某邻域内具有二阶连续偏导数，则在点处有Taylor展式 ． 证明 设，则．按一元函数Taylor公式在处展开，有 ． 从例4得知． 令，有． 根据定理1和定理4，我们有如下两个公式 ， ． §1. 3 最优化的基本术语 定义 设为目标函数，为可行域，． （1） 若，都有，则称为在上的全局（或整体）极小点，或者说，是约束最优化问题的全局（或整体）最优解，并称为其最优值． （2） 若，都有，则称为在上的严格全局（或整体）极小点． （3） 若的邻域使得，都有，则称为在上的局部极小点，或者说，是约束最优化问题的局部最优解． （4） 若的邻域使得，都有，则称为在上的严格局部极小点． 第二章 最优性条件 §2.1 无约束最优化问题的最优性条件 定理1 设在点处可微，若是问题的局部极小点，则． 定义 设在处可微，若，则称为的平稳点． 定理2 设在点处具有二阶连续偏导数，若是问题的局部极小点，则，且半正定． 定理3 设在点处具有二阶连续偏导数，若，且正定，则是问题的严格局部极小点． 注：定理2不是充分条件，定理3不是必要条件． 对于无约束最优化问题，其中，显然 ，令，得的平稳点，而且 ． 易见为半正定矩阵． 但是，在的任意邻域，总可以取到，使，即不是局部极小点． 对于无约束最优化问题，其中， 易知，从而得平稳点，并且 ． 显然不是正定矩阵．但是，在处取最小值，即为严格局部极小点． 求解下面无约束最优化问题， 其中， 解 因为 ， 所以令，有 解此方程组得到的平稳点． 从而 ， ． 由于和是不定的，因此和不是极值点．是负定的，故不是极值点，实际上它是极大点．是正定的，从而是严格局部极小点． 定理4 设是凸函数，且在点处可微，若，则为的全局极小点． 推论5 设是凸函数，且在点处可微．则为的全局极小点的充分必要条件是． 例4 试证正定二次函数有唯一的严格全局极小点，其中为阶正定矩阵． 证明 因为为正定矩阵，且，所以得的唯一平稳点．又由于是严格凸函数，因此由定理4知，是的严格全局极小点． §2.2 等式约束最优化问题的最优性条件 定理1 设在点处可微，在点处具有一阶连续偏导数，向量组线性无关．若是问题 的局部极小点，则，使得 ． 称为Lagrange函数，其中． 称为Lagrange乘子向量． 易见，这里． 定理2 设和在点处具有二阶连续偏导数，若，使得，并且，，只要，便有，则是问题 的严格局部极小点． 试用最优性条件求解 解 Lagrange函数为，则， 从而得的平稳点和，对应有 和． 由于． 因此 ． 并且，有． 利用定理2，所得的两个可行点和都是问题的严格局部极小点． §2.3 不等式约束最优化问题的最优性条件 定义 设，若，使得，， 则称为集合在点处的可行方向． 这里． 令 ， ． 定理1 设是非空集合，在点处可微．若是问题的局部极小点，则 ． 对于 （1） 其中． 令，其中是上述问题（1）的可行点． 定理2 设是问题（1）的可行点，和在点处