1. 最优性条件 (Optimality Condition) 1.1. 优化问题 任何一个优化问题，无论是在机器学习、金融、还是工程领域，我们都可以用三个核心组件来描述它： * 目标函数 (Objective Function) $f:\mathbb{R}^n\mapsto\mathbb{R}$ 这是我们希望最小化（或最大化）的那个函数。在机器学习中，这通常是损失函数 (Loss Function)，比如衡量模型预测值与真实值差距的均方误差。 * 优化变量 (Optimization Variable) $x\in\mathbb{R}^n$ 这是我们可以调整和控制的变量，以期改变目标函数的值。在机器学习中，$x$ 通常是模型的参数或权重 (weights)。我们训练模型的过程，就是在寻找一组最优的权重 $x$ 来让损失函数 $f(x)…
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(…