1. 引言 想象在三维空间中有一个光滑的曲面 S，比如一个完美的球面或者一个平缓的山坡。我们在这个曲面上选取一个点 a。这个点所在的区域必须是“光滑”的，不能有任何“褶皱 (fold)”、“尖点 (cusp)”或者“自我相交 (self-crossing)”的地方。比如，一个圆锥体的顶点就不是光滑的。 * 我们怎么定义在 a 点的切平面呢？PPT给出的方法是： * 想象有一张无限大的、平坦的纸（我们称之为平面 $Π$），一开始它在曲面 S 的外部。 * 现在，我们慢慢地把这张纸向曲面 S 移动，直到它刚刚好在 a 点附近“接触”到曲面。 * 关键在于，这个接触是“相切”的，意味着平面只在 a 这一个点上碰到了曲面，而没有“切入”…
实向量空间 集合 $\mathbb{R}^n$ 是一个向量空间。这里的 $\mathbb{R}$ 代表所有实数的集合，而上标 $n$ 代表维度。$\mathbb{R}^n$ 中的元素是像 $(a1 ,a2 ,…,an )$ 这样的有序元组。这里的每一个 $a_i $ 都是一个实数。 * 我们看待这些元素有两种视角： * 点 (Points) - 几何视角：当我们把 $(a1 ,a2 ,…,an )$ 看作是 $n$ 维空间中的一个位置或坐标时，我们把它称作一个“点”。为了强调它的几何属性，我们通常用大写字母来表示，比如 $A,B,C$。你可以想象在地图上标记一个位置，那就是一个点。 * 向量 (Vectors) -…
1. Integer Linear Programming 1.1. 整数规划 整数规划 (IP) 本质上就是一个带有额外整数约束的线性规划 (LP) 。 我们知道，标准的线性规划处理的是连续变量，比如生产5.25吨的产品，或者投资3.7万元。但在现实世界中，很多决策是不能被分割的，比如你不能雇佣3.5个员工，也不能建造0.7座工厂。整数规划就是为了解决这类问题而生的。 它的通用数学形式如下： $$\begin{array}{rl}\min_{x}&c^\top x\\mathrm{s.t.}&Ax=b,x\geq0\&x_i\in\mathbb{Z},\forall i\…
1.对偶理论 (Duality) 1.1 拉格朗日对偶 (Lagrangian Duality) 为了理解对偶理论，我们先引入拉格朗日函数 (Lagrangian)，它是解决带约束优化问题的一个强大工具。 我们的出发点是一个标准形式的线性规划（LP）问题 。 * 目标: 最小化成本函数 $c^Tx$ 。 * 约束: 解决方案 $x$ 必须满足等式约束 $Ax=b$ 和不等式约束 $x≥0$ 。 为了处理这些约束，我们定义了一个新的函数，即拉格朗日函数 $L(x,y,z)$ ，表达式是 $$L(x,y,z)=c^\top x-y^\top(Ax-b)-z^\top x$$ 这个函数是通过将约束条件融入到原始的目标函数中来构造的 。 在构造过程中，…
1.单纯形算法 (Simplex Algorithm) 1.1 引言：朴素解法的局限性 在线形规划问题中，我们有如下推论： * 可行域 (Feasible Region, Ω): 在几何上，满足约束条件 Ax = b 和 x ≥ 0 的所有解 x 构成的空间是一个凸多面体 (Convex Polyhedron)。你可以把它想象成一个高维度的、由平坦表面围成的几何体。 * 顶点 (Vertex): 就是这个凸多面体的“角点”。 * 为何最优解在顶点上? * 目标函数 c^T x 是线性的。在一个凸多面体内，如果你从一个顶点沿着一条边移动到另一个顶点，目标函数的值要么是线性增加，要么是线性减少，要么保持不变。 * 因此，目标函数的最大值或最小值（最优值）不可能出现在多面体的“内部”或“边”…
机器学习概览 (Machine Learning) 基本概念 机器学习的过程被概括为一个循环流程，包含三个关键环节 ： 1. 数据 (Data)：这是机器学习的基础 。我们假设数据集中隐藏着某种未知的模式或规律。在量化上，它被认为由输入特征和标签 $(s_i,y_i)$ 组成。 2. 模型 (Model)：模型是对数据中隐藏模式的一种简化或数学抽象。它可以是线性的，也可以是非线性的，由一个参数化函数 $h_{x}(s)$ 表示。 3. 优化 (Optimization)：寻找最佳模型的过程，通常被构建为一个优化问题，其被表示成损失函数 + 正则化项 $\min_x\frac{1}{m}\sum_{i=1}^m\ell(y_i,h_x(…