📁 最优化方法
期末速成：最优化方法考点总览
串起线性规划、凸分析、最优性条件和主要算法，整理高频公式、判断步骤与计算套路
往年题
0 folders, 3 posts
绪论：把现实问题写成优化模型
从决策变量、目标函数、约束和可行域出发，理解最优化问题的基本语言与建模步骤
线性规划：标准形、基本解与极点
理解线性规划标准形、基与基本可行解，并建立极点和最优解之间的联系
单纯形法（一）：换基、检验数与单纯形表
从一个基本可行解出发，掌握检验数、进出基规则和单纯形表的完整迭代
单纯形法（二）：初始基与特殊情形
掌握大 M 法、两阶段法，并识别不可行、无界、退化和多重最优等特殊情况
线性规划对偶：定理、互补松弛与影子价格
从资源定价理解 LP 对偶，掌握弱对偶、强对偶、互补松弛及经济解释
对偶单纯形法：保持对偶可行的换基过程
理解对偶单纯形法的适用场景、进出基规则及其与原始单纯形法的对称关系
灵敏度分析：最优基何时保持不变
分析目标系数、右端向量和技术系数变化对当前最优基与最优值的影响
单纯形法的复杂性、椭球法与内点法
理解单纯形法的指数最坏情形，以及椭球法和内点法为何具有多项式时间意义
凸集分离：投影、Farkas 与 Gordan 定理
从凸集与极点出发，理解分离超平面，并掌握 Farkas、Gordan 二择一定理的用法
凸函数与凸规划
掌握凸函数的一阶、二阶判据、保凸运算，以及凸规划中局部最优与全局最优的关系
无约束最优性条件
从方向导数到梯度和 Hessian，掌握无约束局部极值的一阶、二阶必要与充分条件
约束最优性条件：可行方向、Fritz John 与 KKT
从活动约束和可行方向推导 Fritz John、KKT 条件，并理解约束资格的作用
Lagrange 对偶与对偶间隙
从 Lagrange 函数构造对偶函数，理解弱对偶、强对偶、Slater 条件和鞍点
算法映射、收敛性与收敛速度
用算法映射、闭性、下降函数和极限点理解迭代算法为何收敛以及收敛有多快
一维搜索：黄金分割、Newton 与三次插值
理解精确与非精确一维搜索，掌握搜索区间、黄金分割和常见插值法的计算逻辑
最速下降法与 Newton 法
比较负梯度和 Newton 方向，推导二次函数步长，并理解条件数、阻尼与收敛速度
共轭方向法与共轭梯度法
理解 $Q$-共轭方向、有限步终止性质，并掌握共轭梯度法的迭代公式
拟 Newton 法与 DFP 更新
从割线方程构造逆 Hessian 近似，推导 DFP 更新并理解正定性条件
Powell 直接方法
理解无需导数的方向搜索、共轭方向生成及 Powell 方法的一轮更新
Zoutendijk 可行方向法
在线性约束下刻画可行下降方向，并把搜索方向子问题写成线性规划
投影与既约梯度法
通过投影、消元和既约梯度在约束流形内构造下降方向，并理解边界变量处理
第 2 周作业：凸集与凸函数
根据同学提交的作答整理凸集证明、凸函数 Hessian 判别和凸组合推广
第 3 周作业：图解法、基本解与单纯形法
根据同学提交的作答整理二维线性规划图解、基本可行解枚举和单纯形换基
第 6 周作业：对偶与互补松弛
整理多种符号约束下的 LP 对偶写法、互补松弛求解和对偶图解法
第 8 周作业：单纯形表与灵敏度分析
整理从最优表读解、目标系数与右端变化，以及对偶单纯形继续迭代的方法
第 9 周作业：KKT 与二阶条件
整理约束问题的 KKT 乘子求解，并在临界锥上用 Lagrange Hessian 判断局部最优
第 10 周作业：最速下降、Newton 与共轭方向
整理多道无约束迭代计算，比较最速下降、Newton 和共轭梯度的方向与步长
第 11 周作业：直接方法与可行方向法
整理 Powell 方向更新、线性约束可行方向和 Zoutendijk 子问题的手算过程
第 12 周作业：算法收敛与一维搜索
整理极限点与闭映射、收敛速度判断、黄金分割和一维 Newton 迭代