整体说明

• tee 命令是 Linux 中的一个常用工具，主要功能是将标准输入同时输出到两个地方 ：
  • 一个是标准输出（stdout，通常是终端屏幕）
  • 另一个是指定的文件
• tee 命令的作用类似于“三通管”，既让数据在屏幕上可见，又能保存到文件中，避免了“输出重定向（>）会隐藏屏幕显示”的问题
• TLDR：tee 的核心价值就是“一份输入，双重输出（屏幕 + 文件）”，在需要同时查看和保存命令结果时非常方便

基本用法示例：

• 查看系统信息并保存到文件：

  1	uname -a | tee system_info.txt

  • 屏幕上会显示 uname -a 的输出结果
  • 同时会创建 system_info.txt 文件，内容与屏幕输出一致

• 使用 -a 选项可以追加内容（默认是覆盖文件）：

  1	echo "新内容" | tee -a system_info.txt

  • 屏幕显示“新内容”
  • 同时将“新内容”追加到 system_info.txt 末尾，原有内容保留

技巧：配合 sudo 编辑无写入权限的文件

• 这是 tee 非常实用的场景

• 例如，普通用户想向 /etc 目录下的文件写入内容（需要 root 权限）：

  1	echo "配置内容" | sudo tee /etc/some_config.conf

• 避免了直接用 sudo echo "..." > /etc/... 因权限问题失败的情况

• 既能看到输出，又能正确写入有权限要求的文件

整体说明

• tmux（Terminal Multiplexer 的缩写）是 Linux/Unix 系统的一款优秀的终端复用工具 （一般 Linux 系统默认自带，无需封装），也是 GNU Screen 的升级版，功能更强大、设计更优雅
• tmux 的核心作用包括：
  • 1）借助 tmux，在远程连接服务器时，即使 断开 SSH 连接、终端关闭、网络中断 ，tmux 里运行的程序也不会停止，重新连接后可无缝恢复会话继续操作
  • 2）一个终端窗口中，创建 多个会话、多个窗口、多个分屏面板 ，无需开多个终端窗口，高效管理多个任务
  • 3）支持会话分离/接入、窗口切换、面板缩放、快捷键操作等，是后端开发/运维必备工具

安装 tmux

• 几乎所有 Linux 发行版都能通过包管理器一键安装，系统默认一般不带，执行对应命令即可

• CentOS / RHEL / Fedora (yum/dnf)

  1 2	yum install -y tmux # CentOS7 dnf install -y tmux # CentOS8+/Fedora

• Ubuntu / Debian / Deepin (apt)

  1	apt update && apt install -y tmux

• MacOS (brew)

  1	brew install tmux

• 安装完成后，终端输入 tmux -V 验证版本，显示版本号即安装成功

tmux 核心概念

• tmux 的结构是 会话 > 窗口 > 面板 三层嵌套，从大到小 包含关系

会话 (Session)

• 最顶层的独立运行环境，一个 tmux 可以创建多个相互独立的会话
• 每个会话有唯一的「会话名」或「会话ID」，可以随时分离（detach） 或接入（attach）
• 分离会话：会话在后台继续运行，当前终端退出 tmux 界面
• 接入会话：重新进入之前分离的会话，恢复所有操作界面，程序正常运行

窗口 (Window)

• 一个会话里可以创建多个 窗口 ，默认占满整个屏幕，窗口之间可以快速切换
• 类似浏览器的 标签页，比如：一个窗口跑项目日志、一个窗口执行代码部署、一个窗口做文件编辑

面板 (Pane)

• 一个窗口里可以分割成多个 面板（分屏），所有面板在同一个窗口中显示，共享当前会话环境
• 类似终端的「分屏功能」，比如：左边面板编辑代码、右边面板实时运行程序，上下面板分别查看日志和执行命令

tmux 通用操作规则

• tmux 所有的功能操作，都依赖 前缀键+ 功能键 的组合方式，这是 tmux 的核心操作逻辑：

前缀键 (Prefix Key)

• 默认的前缀键是： Ctrl + b （先按住 Ctrl 和 b 一起松开，再按后面的功能键）

tmux 命令两种执行方式

• 快捷键方式 ：前缀键 + 功能键，效率最高，日常使用99%的场景都用这个；
• 命令行方式 ：在 tmux 终端中输入 tmux 命令参数，适合会话管理（创建/接入/删除）等场景

基础核心操作

• 会话是 tmux 最核心的功能，所有操作都围绕会话展开，以下命令全部在系统原生终端执行（未进入 tmux 时）

• 创建新会话

  1 2	tmux # 创建无名称会话，默认会话ID从0开始 tmux new -s 会话名 # 推荐！创建指定名称的会话，比如 tmux new -s project

• 分离当前会话（核心！不会停止程序）

  • 方式一：进入 tmux 会话后，执行快捷键：Ctrl+b d（放开 CTRL+b 后再按 d）
  • 方式二：在 tmux 终端输入 tmux detach
  • 方式三：在其他外部终端输入 tmux detach -t 会话名/会话ID
  • 方式四：直接关闭窗口（SSH 或 网页窗口），不建议这种方式，可能存在问题？
  • 注：以上四种方式下，当前终端退出 tmux 界面，回到系统原生终端，tmux 会话在后台继续运行 ，里面的程序不会停止

• 彻底关闭当前会话：

  1 2	exit # 简单命令 tmux kill-session # 明确关闭当前 session

• 查看所有后台会话

  1	tmux ls # 列出所有会话，格式：会话名: 窗口数 (创建时间) [终端大小]

• 接入/恢复指定会话（核心）

  1 2	tmux a # 简写，接入最近的一个会话 tmux a -t 会话名/会话ID # 推荐！精准接入指定会话，比如 tmux a -t project

• 关闭/杀死指定会话

  1 2	tmux kill-session -t 会话名/会话ID # 比如 tmux kill-session -t project tmux kill-server # 慎用！杀死所有 tmux 会话，停止 tmux 服务

• 重命名当前会话

  • 进入 tmux 会话后，快捷键：Ctrl+b $，然后输入新的会话名即可

窗口管理（待测试）

• 窗口 = tmux 的 标签页，一个会话可以创建多个窗口，所有操作均在 tmux 会话内执行（快捷键为主）
• 核心快捷键（均需先按 Ctrl+b 松开，再按对应键）：
  • 1）c → 创建一个新的窗口（默认名称为当前路径）
  • 2）w → 弹出窗口列表，按上下键选择，回车切换
  • 3）n → 切换到下一个窗口（按创建顺序）
  • 4）p → 切换到上一个窗口（按创建顺序）
  • 5）数字键 0~9 → 快速切换到指定序号的窗口（窗口默认从0开始编号）
  • 6）, → 重命名当前窗口（比如给窗口命名为 log、deploy、edit）
  • 7）& → 关闭当前窗口（会有确认提示，按 y 确认）
• 注：这里有个 小技巧，tmux 底部状态栏会显示当前会话的所有窗口，* 标记的是当前激活的窗口

面板管理（待测试）

• 面板 = tmux 的 分屏，一个窗口可以分割成多个面板，所有操作均在 tmux 会话内执行 ，这是 tmux 提升效率的核心功能
• 核心快捷键（均需先按 Ctrl+b 松开，再按对应键）：
• 面板分割（创建面板）
  • %：垂直分割 ，将当前面板分成左右两个面板（最常用）
  • "：水平分割 ，将当前面板分成上下两个面板
• 面板切换（重点）
  • 方向键 ↑ ↓ ← →，切换到对应方向的面板（最直观，推荐）
  • o，按顺序循环切换所有面板
  • ;， 切换到上一次操作的面板
• 面板调整/操作
  • Ctrl + 方向键 ， 调整当前面板的边框大小（按住 Ctrl+b 不放，再按方向键，持续调整）
  • x ， 关闭当前面板（光标所在面板，会有确认提示，按 y 确认）
  • z ， 面板最大化/还原 ：当前面板占满整个窗口，再按一次恢复原大小（看日志/长代码必备）
  • ! ， 将当前面板独立成新窗口 ：适合需要单独放大某个面板的场景

本文介绍共轭梯度法和最速下降法

• 最速下降法（Steepest Descent Method）和共轭梯度法（Conjugate Gradient Method, CG）也是求解无约束最优化问题的优化方法，其他无约束优化方法见：ML——求解无约束最优化问题的优化方法
• 共轭梯度法是以共轭方向为搜索方向的一类算法，最早用于求解线性方程组，后来用于求解无约束最优化问题
• 最速下降法和共轭梯度法都仅限于求解正定矩阵对应的方程或正定二次型对应的无约束最优化问题

优化问题定义

• 在满足一定要求的情况下，求解线性方程组的解和求解最优化问题有一定的等价性
• 当 \(A\) 为对称正定矩阵时，有下面的两个问题等价：
  • 问题一：求解线性方程组
    $$ Ax = b $$
  • 问题二：求解最优化问题的解
    $$ \min_x \frac{1}{2}(x - x^*)^TA(x - x^*) $$
    • 其中 \(x^*\) 为线性方程组的解
  • 等价原因：正定矩阵 \(A\) 使得二次型 \((x - x^*)^TA(x - x^*) \) 一定大于等于0，当二次型 \((x - x^*)^TA(x - x^*) = 0 \) 时，一定有 \(x=x^*\)
• 对以上最优化问题进一步化简有：
  • 上图中用到了以下性质：
    • 对称正定矩阵的性质： \(A = A^T\)
    • \(x^*\) 为线性方程组的解： \(Ax^* = b\)
  • 上图中 \((Ax,x)\) 表示内积
• 思考：对于参数数量为2的问题，实际上原始优化问题 \((x - x^*)^TA(x - x^*)\) 的等值线可以理解为是一个椭圆，原始问题的最优解在多个椭圆的圆心
  • 为什么是一个椭圆，因为正定矩阵可以被对角化为一个对角线上元素都是正数的对角矩阵 ，即正定二次型一定可以化简为系数全为正的标准型
  • 假设 \(A\) 已经是一个对角矩阵，对角线上的数字为 \(d_1, d_2\)，那么原始二次型对应的 \(c\) 等值线为： \((x - x^*)^TA(x - x^*) = d_1x_1^2+d_2x_2^2 = c\)

最速下降法

• 最速下降法推导

  
  • 上面的式子中，最后一步的推导是直接展开以后得到
    $$
    \begin{align}
    &=\frac{1}{2} (A(x+\alpha r, x+\alpha r)) - (b, (x+\alpha r)) \\
    &= \frac{1}{2} (x^TA^Tx + \alpha r^TA^Tx + \alpha x^TA^Tr + \alpha^2r^TA^Tr) - (b^Tx+\alpha b^T r) \\
    &= \frac{1}{2}( 2\alpha r^TA^Tx) + \frac{1}{2}\alpha^2r^TA^Tr - \alpha b^T r + \frac{1}{2}x^TA^Tx - b^Tx\\
    &= \alpha r^TA^Tx + \frac{1}{2}\alpha^2r^TA^Tr - \alpha (Ax + r)^T r + \frac{1}{2}x^TA^Tx - b^Tx\\
    &= \alpha r^TA^Tx + \frac{1}{2}\alpha^2r^TA^Tr - \alpha x^TA^Tr + \alpha r^Tr + \frac{1}{2}x^TA^Tx - b^Tx\\
    &= \alpha r^TA^Tx - \alpha x^TA^Tr + \frac{1}{2}\alpha^2r^TA^Tr + \alpha r^Tr + \frac{1}{2}x^TA^Tx - b^Tx\\
    &= 0 + \frac{1}{2}\alpha^2r^TA^Tr + \alpha r^Tr + \frac{1}{2}x^TA^Tx - b^Tx\\
    &= \frac{1}{2}\alpha^2r^TA^Tr + \alpha r^Tr + \frac{1}{2}x^TA^Tx - b^Tx\\
    \end{align}
    $$
  • 上面的推导中使用到了 \(b = Ax + r\)，和 \(x^TA^Tr = x^TAr = (x, Ar) = (Ar, x) = r^TA^Tx \)
  • 其中 \( \frac{1}{2}x^TA^Tx - b^Tx\) 与 \(\alpha\) 无关

• 最速下降法的流程及收敛性分析

  
  • 收敛速度与特征值有关，当特征值之间的差距过大时，收敛可能会比较慢

• 最速下降法的收敛性图示分析

  
  • 如果运气好，也可能一步到位，如果运气不好则可能要很久才收敛

共轭梯度法

• 共轭梯度法的引入
  • \(p_{k-1}\) 是上次迭代的方向， \(p_{k}\) 是本次迭代的方向，初始该值设置为 \(p_{-1} = 0\)，或第一步按照 \(p_0 = r_0\) 迭代
  • 步长推导和最速下降法推导一致
• 共轭梯度法的方向
  • 共轭的含义为：
  • 共轭梯度法名字的由来 ：
    • 共轭来自于： \( \forall i, \quad (Ap_{i},p_{k}) = 0\)，每一步迭代的方向与之前的所有步都是共轭相对于矩阵 \(A\) 共轭的
    • 梯度则来自于下降的方向 \(r\) 是原始目标函数 \(\frac{1}{2}(x - x^*)^TA(x - x^*) = \frac{1}{2}(Ax, x)- (b, x)\) 的梯度，由于 \(r\) 同时也是方程 \(Ax = b\) 的残差 \(r = b-Ax\)，所以也会称 \(r\) 为残差
• 共轭梯度法的性质
• 共轭梯度法的流程
  % asset_img Conjugate-Gradient-Method-5.png %}
  • 注意：第0步使用 \(p_0 = r_0\)
• 共轭梯度法收敛性

Jensen不等式定义

• 詹森不等式（Jensen’s Inequality）是数学中，特别是概率论和凸分析中的一个重要结果。它描述了凸函数或凹函数在期望值上的性质
• 对于一个实值的凸函数 \(f\) 和任意一组非负权重 \(\lambda_i\) （满足 \(\sum_{i=1}^{n} \lambda_i = 1\) ），以及对应的随机变量 \(X_i\) 的取值，詹森不等式可以表述为：
  • 如果 \(f\) 是一个凸函数，则有：
    $$ f\left( \sum_{i=1}^{n} \lambda_i X_i \right) \leq \sum_{i=1}^{n} \lambda_i f(X_i) $$
  • 如果 \(f\) 是一个凹函数，则不等号方向相反：
    $$ f\left( \sum_{i=1}^{n} \lambda_i X_i \right) \geq \sum_{i=1}^{n} \lambda_i f(X_i) $$
  • 特别注意：和中文字面意思相反，凸函数是个碗状，凹函数是个伞状

概率论中的Jenson不等式

• 在概率论的上下文中，这可以被解释为：对于一个凸函数 \(f\) 和一个随机变量 \(X\)，我们有：
  $$ f(E[X]) \leq E[f(X)] $$
• 这里 \(E[\cdot]\) 表示期望值。同样地，对于凹函数，不等号的方向会反过来

Jenson不等式的简单推导

推导詹森不等式的简单方法：

• 考虑最简单的情况，即当 \(n = 2\) 时，并且 \(\lambda_1 + \lambda_2 = 1\)，不失一般性，假设 \(f\) 是一个凸函数。根据凸函数的定义，对于所有 \(0 \leq \lambda \leq 1\) 和任意两个点 \(x_1, x_2\)，我们有：
  $$ f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) $$
• 这个不等式就是詹森不等式在 \(n = 2\) 情况下的形式。为了推广到任意正整数 \(n\) 和任何权重 \(\lambda_i\)，我们可以使用归纳法，或者利用凸组合的概念来证明
• 对于更一般的随机变量 \(X\)，通过积分的形式，也可以得到相同的结果。具体来说，设 \(P\) 是 \(X\) 的概率分布，那么对任意凸函数 \(f\)，我们有：
  $$ f\left(\int X dP\right) \leq \int f(X) dP $$
• 这是连续版本的詹森不等式，其中左边是对 \(X\) 的期望应用函数 \(f\)，而右边是先对 \(X\) 应用 \(f\) 再求期望

Jenson不等式的使用

• 经常在推导时，可以使用Jenson不等式来实现求和计算和函数的交换，比如在VAE变分下界推导时就是用到了Jenson不等式

整体说明

• 增广拉格朗日方法（Augmented Lagrangian Method, ALM）是一种用于求解约束优化问题的数值优化算法。它结合了拉格朗日乘子法和罚函数法的优点，能够在保证收敛性的同时避免传统罚函数法中罚参数过大导致的数值不稳定问题

问题描述

• 考虑一个约束优化问题：
  $$
  \begin{align}
  &\min_{x \in \mathbb{R}^n} , f(x) \\
  \text{s.t.} \quad &g_i(x) = 0, \quad i = 1, \dots, m, \\
  &h_j(x) \leq 0, \quad j = 1, \dots, p.
  \end{align}
  $$
• 其中：
  • \(f(x)\) 是目标函数；
  • \(g_i(x)\) 是等式约束；
  • \(h_j(x)\) 是不等式约束

增广拉格朗日函数

• 为了处理上述约束优化问题，引入拉格朗日乘子 \(\lambda \in \mathbb{R}^m\) 和 \(\mu \in \mathbb{R}^p\)，并定义增广拉格朗日函数为：
  $$
  L_A(x, \lambda, \mu; \rho) = f(x) + \sum_{i=1}^m \left[ \lambda_i g_i(x) + \frac{\rho}{2} g_i(x)^2 \right] + \sum_{j=1}^p \left[ \mu_j h_j(x) + \frac{\rho}{2} \max(0, h_j(x))^2 \right],
  $$
• 其中：
  • \(\lambda_i\) 是等式约束 \(g_i(x) = 0\) 的拉格朗日乘子；
  • \(\mu_j\) 是不等式约束 \(h_j(x) \leq 0\) 的拉格朗日乘子；
  • \(\rho > 0\) 是罚参数，用于平衡约束违反的程度

算法步骤

• 增广拉格朗日方法通过迭代更新变量 \(x\)、拉格朗日乘子 \(\lambda\) 和 \(\mu\)，以及罚参数 \(\rho\) 来求解优化问题。具体步骤如下：

初始化

• 初始化 \(x^{(0)}\)，\(\lambda^{(0)}\)，\(\mu^{(0)}\)，以及初始罚参数 \(\rho^{(0)} > 0\)
• 设置收敛容差 \(\epsilon > 0\) 和最大迭代次数 \(k_{\text{max}}\)

迭代过程

对于第 \(k\) 次迭代依次执行下面的流程：

• 优化子问题（更新原始变量） ：固定 \(\lambda^{(k)}\)、\(\mu^{(k)}\) 和 \(\rho^{(k)}\)，求解以下无约束优化问题：
  $$
  x^{(k+1)} = \arg\min_x L_A(x, \lambda^{(k)}, \mu^{(k)}; \rho^{(k)}).
  $$

• 更新拉格朗日乘子 ：

  • 对于等式约束 ：
    $$
    \lambda_i^{(k+1)} = \lambda_i^{(k)} + \rho^{(k)} g_i(x^{(k+1)}), \quad i = 1, \dots, m.
    $$
    • 问题：为什么拉格朗日乘子的更新公式是这样的？理论上，这等价于梯度上升法
    • 直观理解：目标是让 \(g_i(x^{(k+1)}) \rightarrow 0\)?
      • 当 \(g_i(x^{(k+1)}) < 0\) 时，缩小 \(\lambda\)，表示可适当放开约束，使得下次优化子问题时 \(g_i(x^{(k+1)})\) 变大？
      • 当 \(g_i(x^{(k+1)}) > 0\) 时，增大 \(\lambda\)，表示可适当收紧约束，使得下次优化子问题时 \(g_i(x^{(k+1)})\) 变小？
  • 对于不等式约束 ：
    $$
    \mu_j^{(k+1)} = \max\left(0, \mu_j^{(k)} + \rho^{(k)} h_j(x^{(k+1)})\right), \quad j = 1, \dots, p.
    $$

• 检查收敛条件 ：如果满足下面条件，则停止迭代，输出 \(x^{(k+1)}\) 作为解，否则继续迭代
  $$
  |g(x^{(k+1)})|_\infty \leq \epsilon \quad \text{ And } \quad |\max(0, h(x^{(k+1)}))|_\infty \leq \epsilon,
  $$

• 更新罚参数 ：通常选择逐步增大罚参数，例如按下面的方法更新
  $$
  \rho^{(k+1)} = \beta \rho^{(k)},
  $$

  • 其中 \(\beta > 1\) 是一个预设的增长因子

终止条件

• 当达到最大迭代次数或满足收敛条件时，算法终止

特点与优势

• 稳定性 ：相比于传统罚函数法，增广拉格朗日方法对罚参数 \(\rho\) 的依赖较小，能够避免数值不稳定问题
• 灵活性 ：可以处理等式和不等式约束，适用范围广泛
• 全局收敛性 ：在适当的条件下，增广拉格朗日方法具有全局收敛性

附录：对偶上升法与增广拉格朗日乘子法

• 对偶上升法（Dual Ascent）和增广拉格朗日乘子法（Augmented Lagrangian Method，ALM）都是用于解决约束优化问题的迭代算法。它们在更新变量的方式上有显著的不同
• 特别说明 ：两者的区别不仅仅是对偶变量更新的公式不同，最小化求解原始变量时，分别在最小化拉格朗日函数和增广拉格朗日函数 ，这里区别也很大
• 以下对照均已等式约束为例

对偶上升法

• 对偶上升法是一种基于拉格朗日对偶理论的优化方法。它的基本思想是通过交替更新原始变量和对偶变量来逼近最优解。具体步骤如下：
  • 初始化 ：选择初始值 \(x^{(0)}\) 和对偶变量 \(\lambda^{(0)}\)
  • 构建增广拉格朗日函数 ：构造带拉格朗日函数 \(L(x, \lambda) = f(x) + \lambda^T h(x) \)
  • 最小化拉格朗日函数 ：对于固定的 \(\lambda^{(k)}\)，求解无约束优化问题（拉格朗日函数）以找到 \(x^{(k+1)}\)
  • 更新对偶变量 ：更新对偶变量 \(\lambda^{(k+1)} = \lambda^{(k)} + \alpha_k \nabla_\lambda L(x^{(k+1)}, \lambda^{(k)})\)，其中 \(\alpha_k\) 是步长参数
    • 说明：这是根据梯度上升法来更新参数（使用梯度上升是因为更新对偶变量时，目标是最大化原始拉格朗日函数 \(L(x^{(k+1)}, \lambda^{(k)})\)）,其中有\(\nabla_\lambda L(x^{(k+1)}, \lambda^{(k)}) = h(x^{(k+1)})\)
• 这种方法要求目标函数和约束条件满足一定的凸性条件，并且通常需要较小的步长 \(\alpha_k\) 来保证收敛性

增广拉格朗日乘子法

• 增广拉格朗日乘子法是在拉格朗日乘子法的基础上添加了一个二次惩罚项 ，从而增强了原问题的凸性和稳定性。其主要特点如下：
  • 初始化 ：同样选择初始值 \(x^{(0)}\) 和 \(\lambda^{(0)}\)
  • 构建增广拉格朗日函数 ：构造带有惩罚项的拉格朗日函数 \(L_{\rho}(x, \lambda) = f(x) + \lambda^T h(x) + \frac{\rho}{2} |h(x)|^2\)，其中 \(\rho > 0\) 是惩罚参数
  • 最小化增广拉格朗日函数 ：对于固定的 \(\lambda^{(k)}\) 和 \(\rho\)，求解无约束优化问题（增广拉格朗日函数）以找到 \(x^{(k+1)}\)
  • 更新对偶变量 ：更新 \(\lambda^{(k+1)} = \lambda^{(k)} + \rho h(x^{(k+1)})\)
    • 说明：这等价于固定学习率为 \(\rho\) 的梯度上升法更新 \(\lambda\)，其中有\(\nabla_\lambda L_{\rho}(x^{(k+1)}, \lambda^{(k)}) = h(x^{(k+1)})\)
• 与对偶上升法相比，增广拉格朗日乘子法不需要特别小的步长（固定为 \(\rho\) 了），并且由于惩罚项的存在，它能够更好地处理非凸问题，并且通常具有更好的数值稳定性和收敛速度

比较总结

• 收敛性 ：增广拉格朗日乘子法通常比对偶上升法有更强的收敛性，特别是在非凸问题上
• 鲁棒性 ：由于加入了惩罚项，增广拉格朗日乘子法通常更稳健，不易受到数值不稳定的影响
• 计算复杂度 ：每一步中，增广拉格朗日乘子法可能需要解决一个更加复杂的优化问题 ，因为它包含了额外的惩罚项
• 适用场景 ：如果问题是严格凸的，对偶上升法可能是足够的；但如果存在非凸性或需要更高的鲁棒性 ，则增广拉格朗日乘子法通常是更好的选择

附录：其他相关方法之拉格朗日乘子法

• 拉格朗日乘子法一般用于求解一个原始问题的最优形式（最优形式一般包含着拉格朗日乘子），部分时候根据KKT条件可以直接求得最优解

具体示例

• 拉格朗日乘子法 ：通过引入拉格朗日乘子将约束条件与目标函数结合成一个新的函数，即拉格朗日函数。其基本思想是将原约束优化问题转化为无约束的拉格朗日函数的极值问题
  • 对于具有等式约束的优化问题：
    $$
    \begin{align}
    &\min f(x) ， \\
    \text{s.t.} \ &h_i(x)=0 ， i = 1,2,\cdots,m
    \end{align}
    $$
  • 拉格朗日函数定义为：
    $$ L(x,\lambda)=f(x)+\sum_{i = 1}^{m}\lambda_ih_i(x)$$
  • 通过求解 \(\nabla L = 0\) 来得到原问题的最优解

求解方式

• 拉格朗日乘子法 ：直接对拉格朗日函数求偏导数并令其为零，得到一组方程组，然后求解方程组得到最优解。这种方法在理论上很优美，但在实际求解中，当约束条件较多或问题较为复杂时，求解方程组可能会变得非常困难

• 参考文献
  • 【强化学习】个人总结03——动态规划寻找最优策略
  • 手把手教你强化学习 (四)动态规划与策略迭代、值迭代
  • 第四章 动态规划（DP）、蒙特卡罗（MC）、时间差分（TD） - 臭皮匠的文章 - 知乎
  • David Silver强化学习之动态规划寻找最优策略理论与实战(三) - CristianoC的文章 - 知乎

动态规划方法

• 动态规划（Dynamic Programming, DP） 是一种将复杂问题分解为若干子问题，并通过求解这些子问题来获得原问题解的方法。它适用于满足以下两个性质的问题：
  • 最优子结构（optimal substructure） ：原问题可以分解为多个子问题，通过解决这些子问题并将其解组合起来，可以得到原问题的最优解
  • 重叠子问题（overlapping subproblems） ：子问题在求解过程中会多次出现，且这些子问题的解可以被存储并重复利用
• 马尔可夫决策过程 (MDP) 恰好满足动态规划的这两个条件：贝尔曼方程将问题分解为递归结构的子问题，而价值函数能够存储并复用其最优解。因此，我们可以使用动态规划来解决马尔可夫决策过程的核心问题：预测和控制
  • 预测（prediction） ：给定一个马尔可夫决策过程 MDP 和一个策略 \(\pi\)，或者给定一个马尔可夫奖励过程 MRP，求解基于该策略的价值函数 \(v_\pi\)。（评估给定策略的效果）
  • 控制（control） ：给定一个马尔可夫决策过程 MDP，求解最优价值函数 \(v_\∗\) 和最优策略 \(\pi_\∗\)。（即寻找最佳策略）
• 预测问题和控制问题的主要区别在于，预测问题是在策略已知的情况下求解其价值函数，而控制问题则是在没有给定策略的情况下寻找最优价值函数及其对应的策略。两者之间存在递进关系：在强化学习中，我们通常先解决预测问题，再进一步解决控制问题

同步动态规划（Synchronous Dynamic Programming）

• 同步动态规划算法中，每一次迭代都更新所有状态的价值
• 参考链接：策略迭代与值迭代的区别

策略迭代（policy iteration）

• Step1：初始化所有状态的价值 (\(v(s)\)) 和策略 (\(\pi(s)\))
• Step2：策略评估（policy evaluation）：按照贝尔曼方程迭代，直到收敛（求解当前策略下的不动点）
• Step3：策略迭代（policy improvement）：寻找一个新的策略，在任意状态下都有 \(Q^\pi(s,\pi’(s)) \ge V^\pi(s)\)，可以证明此时有 \(V^{\pi’}(s) \ge V^\pi(s)\)
• 循环Step2和Step3直到收敛

值迭代（value iteration）

• Step1：初始化所有状态的价值 (\(v(s)\))
• Step2：迭代找到最优策略（常常隐含直接使用 argmax 作为最优策略决策），直到收敛
• Step3：最优策略提取
• 这种方法仅进行价值函数迭代，不考虑策略，最终迭代到最优价值函数后，即可反向求解得到最优的策略

异步动态规划（Asynchronous Dynamic Programming，非重点）

• 异步动态规划算法中，在每一次迭代时，根据特定规则选择性地更新部分状态的价值（并不更新所有状态的价值）
  • 注：这种方法可以显著节省计算资源，并且只要所有状态能够持续被访问和更新，算法最终仍能收敛到最优解
  • 目标：解决经典DP需遍历全部状态的问题，通过异步更新提高效率
• 以下是几种常见的异步动态规划方法：
  • 就地动态规划（In-place DP） ：直接覆盖旧价值函数，而非保留新旧两份
  • 优先扫描（Prioritized Sweeping） ：根据优先级对状态进行排序，优先更新优先级较高的状态的价值（优先更新贝尔曼误差较大的状态）
  • 实时动态规划（Real-time DP） ：仅更新当前交互中访问的状态

动态规划的其他说明

• 动态规划算法的缺点 ：采用全宽度（full-width）的回溯机制来更新状态价值，算力需求大且容易导致维度灾难
  • 无论是同步还是异步动态规划，每次回溯更新某个状态的价值时，都需要追溯到该状态的所有可能后续状态，并结合已知的马尔可夫决策过程的状态转换矩阵和奖励来更新该状态的价值
  • 解决方案：可以使用采样回溯方法来近似估计价值，从而减少算力的消耗
• 动态规划算法是model-based算法，因为需要回溯当前状态的所有后续状态（full-width回溯机制）

Model-free方法辨析

• Model-free 不知道环境动力学（Dynamics），无法精确计算精确的目标值，所以通常使用 TD 和 MC 这两种方案来近似估计目标值
  • 时序差分（Temporal Difference, TD）：Q-learning 和 SARSA 都使用这种方法估计目标值
  • 蒙特卡罗方法（Monte-Carlo，MC）：REINFORCE方法就使用了MC方法估计目标值
  • n-step方法是 TD 和 MC 的结合
• TD 其实同时是结合了 MC 和 DP 的思想，更详细的比较见附录
  • 需要模拟交互序列（和MC方法一样）；但不需要积累很多交互数据求均值（不同于 MC）
  • 使用当前回报和下一时刻的价值预估来更新当前时刻的价值（和DP方法一样）；不需要知道状态转移矩阵，也不需要full-width回溯（不同于DP方法）
• Q-learning 和 SARSA 为什么不是DP方法？
  • Q-learning 并不基于模型计算期望（不需要依赖状态转移矩阵），是直接使用贪心策略
  • SARSA 依赖采样，并不是精确计算期望

附录：Planning、Decision、Prediction和Control的区别

• 在自动化和智能系统中，Planning、Decision、Prediction 和 Control 是四个关键的概念：
  • Planning（规划） ：制定未来行动步骤，生成一系列行动步骤或策略
  • Decision（决策） ：在当前时刻选择最佳行动，即在已知状态下决策动作
  • Prediction（预测） ：推断未来状态或事件，预估环境相关的变化等
  • Control（控制） ：实时调节系统行为以实现目标，常常涉及到反馈机制，以应对环境变化
• 实际例子举例：自动驾驶中，Prediction用于预测其他车辆行为，Decision用于选择最佳驾驶策略，Planning用于规划路径，Control用于执行驾驶操作

附录：MC、TD和DP 详细比较

• 蒙特卡罗方法（MC） ：通过完整回合的采样回报估计值函数，依赖实际经验，无需环境模型
• 时序差分（TD） ：结合MC和DP思想，结合当前奖励和后续状态的价值估计来更新当前状态
• 动态规划（DP） ：基于模型的全宽度回溯更新，利用贝尔曼方程迭代求解值函数，需已知环境动力学

动态规划（DP）

• 核心思想 ：利用贝尔曼方程全宽度回溯更新值函数，需已知状态转移 \( P \) 和奖励函数 \( R \)
• 策略评估（Policy Evaluation） ：
  $$
  V_{k+1}(s) = \sum_a \pi(a|s) \sum_{s’, r} P(s’, r|s, a) \left[ r + \gamma V_k(s’) \right]
  $$
  • 迭代至收敛得到精确值函数
• 策略改进（Policy Improvement） ：
  $$
  \pi’(s) = \arg\max_a \sum_{s’, r} P(s’, r|s, a) \left[ r + \gamma V^\pi(s’) \right]
  $$

蒙特卡罗方法（MC）

• 核心思想 ：用完整回合的回报均值估计值函数，仅适用于回合制任务
• 值函数更新 ：
  $$
  V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]
  $$
  • 其中 \( G_t = \sum_{k=t}^T \gamma^{k-t} R_{k+1} \) 是实际回报，\( \alpha \) 为学习率，\( T \) 为回合终止时刻

时序差分（TD）

• 核心思想 ：用当前奖励与下一状态估计值（自举）更新值函数，可在线学习
• TD(0) 更新 ：
  $$
  V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]
  $$
  • 其中 \( R_{t+1} + \gamma V(S_{t+1}) \) 称为 TD目标 ，\( \delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \) 为 TD误差

三者方差偏差比较

• MC ：高方差、无偏估计，需完整回合
• TD ：低方差、有偏估计，可在线学习
• DP ：精确但计算量大，需模型支持。

整体说明

• 在强化学习中，探索（Exploration）与利用（Exploitation）的平衡是核心挑战之一
• 探索（Exploration） ：探索旨在发现环境中未知的信息
• 利用（Exploitation） ：根据已有知识选择最优动作以最大化收益

基于随机性的策略

\(\epsilon\)-贪心（\(\epsilon\)-Greedy）

• 核心思路是以概率 \(\epsilon\) 随机选择动作（探索），否则选择当前最优动作（利用）
• \(\epsilon\)-Greedy简单易实现，但探索效率低（可能重复探索次优动作）
• 升级版 ：\(\epsilon\) 可随时间衰减（如 \(\epsilon = \frac{1}{\sqrt{t}}\) ）

Boltzmann探索（Softmax）

• 核心思路 ：根据动作的Q值按概率分布选择动作（玻尔兹曼分布），使用温度参数 \(\tau\) 控制探索强度：
  $$
  P(a) = \frac{e^{Q(a)/\tau} }{\sum_{b} e^{Q(b)/\tau} }
  $$
  • 玻尔兹曼分布 ，英文名是Boltzman Distribution ，又称吉布斯分布或Softmax分布
  • \(\tau\) 是温度系数，\(\tau\)高时偏向探索，\(\tau\) 低时偏向利用

基于不确定性的策略

Upper Confidence Bound (UCB)

• 基本思路 ：为每个动作的Q值添加置信区间上界，选择上界最大的动作：
  $$
  A_t = \arg\max_a \left[ Q(a) + c \sqrt{\frac{\ln t}{N_t(a)} } \right]
  $$
  • \(N_t(a)\) 是动作 \(a\) 被选择的次数，\(c\) 是探索系数
  • 特点 ：适用于多臂赌博机（Multi-Armed Bandit, MAB） ，但需维护动作计数（注：Bandit 本意为 “匪徒/强盗”，之前的老虎机又称为 “单臂强盗”）
• MCTS 中的UCT（Upper Confidence Bound applied to Trees）和PUCT（Polynomial Upper Confidence Trees）都是 UCB 的变体
• UCT（Upper Confidence Bound applied to Trees）算法：
  $$
  \textit{UCT}(s, a) = Q(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)} }
  $$
  • \(Q(s, a)\)：动作\(a\)的平均回报
  • \(N(s)\)：状态\(s\)的访问次数，\(N(s, a)\)：动作\(a\)的访问次数（注：如果分母不会为0，此时所有节点都是完整探索过的，不存在为0的情况）
  • \(c\)：探索系数（通常设为\(\sqrt{2}\)），当\(c=\sqrt{2}\)时，UCT的累计遗憾（Regret）有对数上界
  • 探索时选择动作为： \(a^* = \arg\max_a \textit{UCT}(s, a)\)
• PUCT（Predictor UCT）算法：
  $$
  \textit{PUCT}(s, a) = Q(s, a) + c_\textit{puct}\cdot P(s,a)\cdot \frac{\sqrt{N(s)}}{1+N(s, a)}
  $$
  • \(P(s,a)\)：即 \(\pi(a|s)\)，是先验策略网络（Policy Network）给出的先验概率（表示动作 \(a\) 的初始偏好）
  • \(c_\text{puct}\)：探索系数（控制先验权重，AlphaZero中常设为1~2）
  • \(1+N(s,a)\)：（不用为了避免除0操作而增加1吧，毕竟此时所有节点都是完整探索过的，不存在为0的情况）
  • 探索时选择动作为：探索时选择 \(a^* = \arg\max_a \textit{PUCT}(s, a)\)
  • 基本思想：采样次数 \(N(s, a)\) 少时，按照策略 \(\pi(a|s)\) 为主探索；采样次数 \(N(s, a)\) 多时，按照价值 \(Q(s, a)\) 为主探索

Thompson Sampling

• 汤普森采样（Thompson Sampling, TS）的核心思想是通过概率分布建模不确定性，并基于后验分布采样
• 汤普森采样也称为后验采样（Posterior Sampling） ，是一种基于贝叶斯思想的探索与利用（Exploration-Exploitation）策略
• 广泛应用于多臂赌博机、推荐系统、在线广告投放和强化学习等领域
• 以点击率预估中伯努利奖励为例：
  • 初始化 ：
    • 假设每个动作 \( a \) 的奖励服从伯努利分布（Bernoulli Distribution） \( \text{Bern}(\theta_a) \)，即两点分布或0-1分布 ，\(\theta_a\) 是动作 \(a\) 真实的奖励期望
    • 设先验分布为 Beta 分布 ：\( \theta_a \sim \text{Beta}(\alpha_a, \beta_a) \)（初始 \( \alpha_a = \beta_a = 1 \)）
      • 注：Beta 分布的概率密度函数为\(f_\text{Beta}(x;\alpha, \beta) = \frac{1}{B(\alpha,\beta)}x^{\alpha-1}(1-x)^{\beta-1}\)，其中 \(B(\alpha,\beta) = \frac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)}\) 是 Beta 函数 ，（\(\Gamma(\alpha)\)为 伽马函数）
  • 迭代过程 ：
    • 采样 ：对每个动作 \( a \)，从其后验分布 \( \text{Beta}(\alpha_a, \beta_a) \) 中采样动作 \(a\) 的奖励值 \( \hat{\theta}_a \)（当采样次数足够多以后有\( \hat{\theta}_a = \theta_a\)）
      • 注意：每个动作都有一个自己的 Beta分布，都有自己的后验数据 \(\alpha_a, \beta_a\)
    • 选择动作 ：执行 \( a^* = \arg\max_a \hat{\theta}_a \)
    • 观测奖励 ：获得二元反馈 \( r \in {0, 1} \)
    • 更新后验 ：
      • 若 \( r = 1 \)，则 \( \alpha_{a^*} \leftarrow \alpha_{a^*} + 1 \)
      • 若 \( r = 0 \)，则 \( \beta_{a^*} \leftarrow \beta_{a^*} + 1 \)

基于内在激励的策略

好奇心驱动（Intrinsic Curiosity）

• 基本思想 ：通过预测环境动态模型（如状态转移）的误差作为内在奖励，鼓励探索新状态
• ICM（Intrinsic Curiosity Module）是一种好奇心驱动策略，通过预测下一状态和动作的误差生成奖励

计数基方法（Count-Based）

• 基本思想 ：对访问过的状态或动作计数，给予未频繁访问的状态更高探索奖励：
  $$
  R_{intrinsic} = \frac{1}{\sqrt{N(s)} }
  $$

神经网络中的探索策略

对输出动作加噪

• 动作空间加噪 ：直接在输出动作上添加噪声（如高斯噪声），思路和离散动作中的 \(\epsilon\)-Greedy 思想相似

对输入观测加噪

• 观测空间加噪 ：直接在观测上添加噪声（如高斯噪声）

对参数加噪（Parameter Noise）

• 参数空间加噪 ：直接在策略网络的参数上添加噪声（如高斯噪声）

熵正则化（Entropy Regularization）

• 在策略梯度目标函数中增加策略熵项，鼓励动作多样性：
  $$
  \nabla J(\theta) = \mathbb{E} \left[ \nabla \log \pi(a|s) Q(s,a) + \beta H(\pi(\cdot|s)) \right]
  $$
  • \(H\) 是熵，\(\beta\) 是权重系数

一些实践技巧

• 离散动作使用\(\epsilon\)-Greedy；连续动作使用参数噪声或动作噪声
• Thompson采样成本太高，一般选择 \(\epsilon\)-Greedy这种简单的即可

Gym 安装问题记录

• 一般来说使用 pip install gym 安装即可
• 但从经验来看往往会出现一些使用上的异常：由于经过多版迭代，导致很多接口不兼容，此时需要查看版本是否和目标项目是否一致
• 经验1：如果安装后使用 env.render() 无法显示可视化图像，可考虑安装 0.21.0 版本（亲测可用）

  1	pip install gym==0.21.0

Summary

• CE 方法逐步更新采样分布 \(Q\)，使其更接近目标分布 \(P^*\)，从而最小化两者之间的交叉熵
• 这一过程不仅有助于找到最优解，还能够在高维和复杂问题中有效地进行优化
• 注：在工业实践中，CEM 方法很容易使用

交叉熵基础定义

• Cross Entropy 方法中的 “Cross Entropy” 这个名字来源于信息论中的一个概念
  • 在信息论中，交叉熵（Cross Entropy）是用来衡量两个概率分布之间的差异的一个指标，通常用于评估一个概率模型对真实数据分布的拟合程度
• 给定两个概率分布 \(P\) 和 \(Q\)，其中 \(P\) 代表真实的概率分布，而 \(Q\) 代表模型预测的概率分布，那么 \(P\) 和 \(Q\) 之间的交叉熵定义为：
  $$ H(P, Q) = -\sum_x P(x) \log Q(x) $$
• 这里的 \(H(P, Q)\) 就是 \(P\) 相对于 \(Q\) 的交叉熵。当 \(Q\) 完美地匹配 \(P\) 时，即 \(P=Q\)，交叉熵达到最小值，此时等于 \(P\) 的熵 \(H(P)\)
  • 如果 \(Q\) 与 \(P\) 不同，那么交叉熵会比 \(P\) 的熵大，表示了额外的信息损失或误差

交叉熵损失函数

• 在优化和机器学习领域，交叉熵经常被用作损失函数，特别是在分类任务中，比如使用神经网络进行图像分类
• 在这种情况下， \(P\) 通常是样本的真实标签分布（例如，对于二分类问题，正类可以表示为 [1, 0]，负类为 [0, 1]），而 \(Q\) 是模型预测的概率分布
• 通过最小化交叉熵损失函数，可以训练模型更好地拟合训练数据

交叉熵方法名字的来源

• Cross Entropy 方法本身是一种用于优化和采样的算法，它最初是从稀有事件模拟中发展出来的
  • 该方法通过迭代地从候选解集中采样，并根据这些样本计算出一个精英集的概率分布，然后利用这个分布来指导下一步的采样过程
• 在这个过程中，算法实际上是在尝试最小化目标分布（最优解的分布）和当前采样分布之间的交叉熵，因此得名“Cross Entropy 方法”
  • 这种方法能够有效地解决一些复杂的优化问题，尤其是在高维空间中寻找最优解的问题

交叉熵方法的核心思想

• 在 Cross Entropy (CE) 方法中，最小化目标分布 \(P^*\) （最优解的分布）和当前采样分布 \(Q\) 之间的交叉熵是一个核心思想
• 这个过程可以通过以下步骤来理解：

定义目标

• 首先定义目标是找到一个分布 \(Q\)，使得 \(Q\) 尽可能接近目标分布 \(P^*\)
  • 这里 \(P^*\) 通常是一个难以直接求解的分布，因为它对应于所有可能解中的最优解

交叉熵作为度量

• 使用交叉熵 \(H(P^*, Q)\) 作为度量 \(P^*\) 和 \(Q\) 之间差异的标准，交叉熵定义为：
  $$ H(P^*, Q) = -\sum_x P^*(x) \log Q(x) $$
• 这里 \(x\) 表示解空间中的一个点， \(P^*(x)\) 是 \(x\) 属于最优解的概率，而 \(Q(x)\) 是 \(x\) 被当前采样分布选中的概率

精英集的选择

• 在 CE 方法中，我们并不直接计算 \(P^*\)，而是通过迭代过程逐步逼近 \(P^*\)
• 每一步，我们从当前的分布 \(Q\) 中随机采样一组解，然后选择表现最好的一部分解（称为精英集）
• 假设我们采样了 \(N\) 个解，并选择了其中表现最好的 \(N_e\) 个解作为精英集

更新分布

• 接下来，基于精英集来更新分布 \(Q\)
• 目标：希望新的 \(Q\) 更好地拟合精英集中的解
  • 这可以通过计算精英集的统计特性（如均值和协方差）来实现
• 如果 \(Q\) 是一个高斯分布，我们可以计算精英集的均值 \(\mu_e\) 和协方差矩阵 \(\Sigma_e\)，并用它们来更新 \(Q\) 的参数：
  $$ \mu_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} x_i \\
  \Sigma_{\text{new}} = \frac{1}{N_e} \sum_{i=1}^{N_e} (x_i - \mu_{\text{new}})(x_i - \mu_{\text{new}})^T $$

重复迭代

• 上述过程构成了 CE 方法的一个迭代步骤。我们重复执行采样、选择精英集和更新分布的过程，直到 \(Q\) 收敛到一个接近 \(P^*\) 的分布，或者满足某个停止条件（如达到最大迭代次数或分布变化小于某个阈值）

最小化交叉熵的直观解释

• 通过选择精英集并更新分布，CE 方法实际上是在逐步减少 \(P^*\) 和 \(Q\) 之间的交叉熵
• 这是因为每次迭代后，新的分布 \(Q\) 更加集中在那些表现好的解上，从而更接近 \(P^*\)
• 从数学上看，选择精英集并更新分布的过程可以看作是在最小化 \(P^*\) 和 \(Q\) 之间的 KL 散度（Kullback-Leibler divergence），而 KL 散度与交叉熵密切相关：
  $$ D_{\text{KL}}(P^* | Q) = H(P^*, Q) - H(P^*) $$
• 由于 \(H(P^*)\) 是常数，最小化 \(D_{\text{KL}}(P^* | Q)\) 等价于最小化 \(H(P^*, Q)\)

主动学习(Active Learning), 半监督学习(Semi-Supervised Learning)与直推学习(Transductive Learning)
半监督学习又称为归纳学习(Inductive Learning)

补充知识

“开放世界”假设

• 学得的模型能适用于训练过程中从未观察到的数据
• 也就是说:测试集未知

“封闭世界”假设

• 学得的模型仅仅能适用于训练过程中观察到的未标记样本
• 也就是说:测试集就是训练时观察到的未标记数据

相同点

• 都是用于解决有少量标注数据和海量未标注数据的问题的算法
• 都是迭代扩充标记数据集的算法:
  • 每次迭代时添加如一部分新的标记数据(由未标记数据标记产生的)

不同点

主动学习

• 主动学习添加了专家知识(人工确认或者打标签),每次迭代时加入的新的标记数据都是由专家打出来的标签
• 半监督学习和直推学习都是全自动的(无需人工干预),主动学习是半自动的

半监督学习与直推学习

• 直推学习将当前的为标签数据看成是最终的测试数据
• 半监督学习和主动学习的测试集都是未知数据
• 半监督学习是基于”开放世界”假设的
• 直推学习是基于”封闭世界”假设的

总结

总体概览

表格概览