研究生最优化课程部分笔记

  |  

摘要: 最优化最优化课程笔记:仅含基本概念、线性规划、单纯形、对偶原理四部分

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


这是当年研究生上最优化时的教材,定理的证明和算法的推导主要以数学分析和线性代数为基础。

现在看的话有更好的书,并且本书有点老了,没有新算法。本书其实没必要看了,这里是一部分当时的笔记,是基于这本书的。

  • 书名: 最优化理论与算法
  • 作者: 陈宝林
  • 豆瓣链接

书中包括以下内容,其中加粗的是笔记上有的内容,笔记共 56 页。其它内容其它更好的书里一般会有,如果没有但是又需要了解的话,翻回来看也不迟。

  • 基础概念
    • 线性与非线性规划问题
    • 几个数学概念
    • 凸集和凸函数
  • 线性规划的基本性质
    • 标准形式及图解法
    • 基本性质
  • 单纯形方法
    • 单纯形方法原理
    • 两阶段法与大M法
    • 退化情形
    • 修正单纯形法
    • 变量有界的情形
    • 分解算法
  • 对偶原理及灵敏度分析
    • 线性规划中的对偶理论
    • 对偶单纯形法
    • 原始-对偶算法
    • 灵敏度分析
    • 含参数线性规划
  • 运输问题
    • 运输问题的数学模型与基本性质
    • 表上作业法
    • 产销不平衡运输问题
  • 线性规划的内点算法
    • Karmarkar算法
    • 内点法
    • 路径跟踪法
  • 最优性条件
    • 无约束问题的极值条件
    • 约束极值问题的最优性条件
    • 对偶及鞍点问题
  • 优化算法
    • 算法概念
    • 算法收敛问题
  • 一维搜索
    • 一维搜索概念
    • 试探法
    • 函数逼近法
  • 使用导数的最优化方法
    • 最速下降法
    • 牛顿法
    • 共轭梯度法
    • 拟牛顿法
    • 信赖域方法
    • 最小二乘法
  • 无约束最优化的直接方法
    • 模式搜索法
    • Rosenbrock方法
    • 单纯形搜索法
    • Powell方法
  • 可行方向法
    • Zoutendijk可行方向法
    • Rosen梯度投影法
    • 既约梯度法
    • Frank Wolfe方法
  • 惩罚函数法
    • 外点罚函数法
    • 内点罚函数法
    • 乘子法
  • 二次规划
    • Lagrange方法
    • 起作用集方法
    • Lemke方法
    • 路径跟踪法
  • 整数规划简介
    • 分支定界法
    • 割平面法
    • 0-1规划的隐数法
    • 指派问题
  • 动态规划简介
    • 动态规划的一些基本概念
    • 动态规划的基本定理和基本方程
    • 逆推解法和顺推解法
    • 动态规划与静态规划的关系
    • 函数迭代法

基础概念

线性与非线性规划问题

最优化的各种分类

最优化的三要素: 变量、约束条件、目标函数

最优化的方法: 解析法、直接法、数值法

几个数学概念

向量范数、矩阵范数(代数基础)

向量序列的解析(分析基础)

向量函数的梯度、Hesse矩阵、Taylor展开式

向量值函数的 Jacobi矩阵、连式法则、隐函数存在定理




凸集和凸函数

凸集

极点、极方向

表示定理

凸集分离定理

凸函数

凸规划





线性规划的基本性质

标准形式及图解法

基本性质

一般线性规划的标准形式

松弛变量

最优基本可行解




单纯形方法

单纯形方法原理

从一基可行解出发找最优基可行解

单纯形法计算步骤



两阶段法与大M法

找基可行解:两阶段法的第一阶段
单纯形法:两阶段法的第二阶段

其中

若 A 中含有 m 阶单位阵,则初始基可行解立刻可以得到

如果 A 中不含 m 阶单位阵,则进行两阶段法的第一阶段:**首先增加人工变量,然后用单纯形法消人工变量。




大M法: 初始基可行解未知时的另一解法


单纯性表








退化情形

摄动法




怎样找摄动问题的基可行解


修正单纯形法

修正单纯形步骤


变量有界的情形

推广基可行解






分解算法

主规划、子规划

对偶原理及灵敏度分析

线性规划中的对偶理论

对偶定理

互补松弛性质




对偶单纯形法

对偶基可行解

对偶单纯形法计算步骤



原始-对偶算法

原始-对偶算法的计算步骤




Share