真正的火羽白

# 不等式约束最小化问题 问题层次结构 假设所有问题都是凸的，可以按照以下层次结构来理解： 二次问题：最简单，有闭式解 等式约束的二次问题：仍然容易，使用 KKT 条件推导闭式解 等式约束的光滑问题：使用牛顿方法将其转化为一系列等式约束的二次问题 不等式约束（以及等式约束）的光滑问题：使用内点法将其转化为一系列等式约束问题 含不等式约束的凸优化问题 标准形式 minimizef0(x)subject tofi(x)≤0,i=1,…,mAx=b\begin{align*} \text{minimize} \quad & f_0(x) \\ \text{su

# 等式约束 问题形式 等式约束（凸）优化问题： min⁡f(x)s.t.Ax=b\begin{align*} \min \quad & f(x) \\ \text{s.t.} \quad & Ax = b \end{align*} mins.t.​f(x)Ax=b​ 其中： f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}f:Rn→R，定义域为 dom f\text{dom}\ fdom f A∈Rp×nA \in \mathbb{R}^{p \times n}A∈Rp×n，rank(A)=p<n\t

# 概述 拟牛顿方法（Quasi-Newton Methods）是一类重要的优化算法，它们通过近似 Hessian 矩阵来避免牛顿方法中计算和存储完整 Hessian 矩阵的高昂成本，同时保持较快的收敛速度。 # 拟牛顿方法的动机 牛顿方法的优势与劣势 考虑光滑凸优化问题： min⁡xf(x)\min_x f(x) xmin​f(x) 其中 fff 是凸函数，二次可微，且 dom(f)=Rn\text{dom}(f) = \mathbb{R}^ndom(f)=Rn。 梯度下降更新： x+=x−t∇f(x)x^+ = x - t \nabla

# Vanilla Gradient Descent（基本梯度下降） 基本思想 基本梯度下降算法遵循的思想是：梯度的相反方向指向较低的区域。所以它在梯度的相反方向迭代。 更新公式 对于每个参数 θ\thetaθ，更新公式为： θ←θ−η⋅∇J(θ)\theta \leftarrow \theta - \eta \cdot \nabla J(\theta) θ←θ−η⋅∇J(θ) 其中： η\etaη 是学习率（learning rate） ∇J(θ)\nabla J(\theta)∇J(θ) 是目标函数 JJJ 关于参数 θ\thetaθ 的梯度 特点： 算法简单直观 每次迭代只考虑

# 概述 无约束可微优化问题可以直接利用梯度信息求解。主要关注两个问题： 如何计算搜索方向 如何计算前进步长 # 下降算法与直线搜索 （梯度）下降算法通用框架 对于无约束优化问题 min⁡xf(x)\min_x f(x)minx​f(x)，下降算法的通用框架如下： Step 1：确定初始点 x0∈dom fx^0 \in \text{dom}\ fx0∈dom f，令 k=0k = 0k=0 Step 2：判断是否停止：如果 ∥∇f(xk)∥≤ε\|\nabla f(x^k)\| \leq \varepsilon∥∇f(xk)∥≤ε，停止 Step 3：计

# 概述 迭代算法 优化算法通常是迭代过程。从给定点 x0x_0x0​ 开始，生成迭代序列 {x(k)}\{x^{(k)}\}{x(k)}，收敛到"解"——或者至少设计为如此。 收敛性定义 标量序列 {x(k)}\{x^{(k)}\}{x(k)} 收敛到 0，当且仅当对于所有实数 ε>0\varepsilon > 0ε>0，存在正整数 KKK，使得： ∣x(k)∣<ε对所有 k≥K|x^{(k)}| < \varepsilon \quad \text{对所有 } k \geq K ∣x(k)∣<ε对所有 k≥K 序列 {x(k)}\{

# 几何问题 # 凸集的投影与距离 投影的定义 点 xxx 在集合 CCC 上的投影定义为： PC(x)=arg⁡min⁡z∈C∥x−z∥P_C(x) = \arg\min_{z \in C} \|x - z\| PC​(x)=argz∈Cmin​∥x−z∥ 即 CCC 中与 xxx 距离最近的点。 凸优化形式 假设 CCC 具有形式： C={x∣Ax=b, fi(x)≤0, i=1,…,m}C = \{x \mid Ax = b, \ f_i(x) \leq 0, \ i = 1, \ldots,

# 卡尔曼滤波 卡尔曼滤波（Kalman Filtering）由 Rudolf E. Kalman 在 1960 年提出，是一种高效的递归估计器，用于估计带噪声的线性离散时间动态系统的状态。它是状态估计和信号处理中的经典方法。 系统模型与观测模型 动态系统模型 线性离散时间动态系统可以表示为： x(k+1)=Ax(k)+Bu(k)+w(k)x(k+1) = A x(k) + B u(k) + w(k) x(k+1)=Ax(k)+Bu(k)+w(k) 其中： x∈Rnx \in \mathbb{R}^nx∈Rn 是需要估计的状态向量 u∈Rmu \in \ma

# 最大切问题 最大切问题（Max-Cut Problem）是图论中的一个经典组合优化问题，属于 NP 难问题。通过半正定松弛（Semidefinite Relaxation），可以将这一非凸问题转化为可求解的凸优化问题。 半正定松弛 (Semidefinite Relaxation) 非凸优化问题的例子 考虑以下非凸优化问题： min⁡x1−2x2s.t.x1≥0,x2≥0(x1−1)2+x22≤1(x1−1)2+(x2−1)2≥1\begin{align*} \min \quad & x_1 - 2x_2 \\ \text{s.t.} \quad & x_1 \geq

# 范数逼近 范数逼近问题旨在找到向量 xxx，使得 AxAxAx 在某种范数意义下最接近 bbb。不同的范数选择会导致不同的逼近性质和求解方法。 线性范数逼近 (Linear Norm Approximation) 问题形式 考虑线性范数逼近问题： min⁡∥Ax−b∥\min \quad \|Ax - b\| min∥Ax−b∥ 其中 A∈Rm×nA \in \mathbb{R}^{m \times n}A∈Rm×n，m≥nm \geq nm≥n，∥⋅∥\|\cdot\|∥⋅∥ 是 Rm\mathbb{R}^mRm 上的范数。 解的几何解释 解 x∗=arg⁡min⁡x∥Ax