顶点

顶点 (Vertex)

顶点是几何体、图结构以及优化可行域中处于"极端位置"的点。在数学的不同分支中，顶点的精确定义各有侧重，但共享一个核心直觉：顶点是无法由集合内其他点的凸组合表示的点——它是形状的"角"，是结构的最远端，是算法搜索的终点。

几何中的顶点

在多边形、多面体及更一般的凸多胞形中，顶点是最基本的构成元素。一个 $n$ 维凸多胞形由顶点、边、面等不同维度的面构成，其中零维面即为顶点。顶点的代数刻画是：点 $v$ 是多胞形 $P$ 的顶点当且仅当存在某个线性函数在 $v$ 处取得唯一最大值。

对于二维的圆锥曲线，抛物线的顶点是其对称轴与曲线的交点，也是函数最值所在之处。二次函数 $f(x) = ax^2 + bx + c$ 经配方法化为顶点式 $f(x) = a(x-h)^2 + k$，其中顶点 $(h, k) = (-\frac{b}{2a}, f(-\frac{b}{2a}))$ 直接给出函数的全局最大值（$a < 0$）或最小值（$a > 0$）。

优化理论中的顶点

在线性规划中，顶点的地位由线性规划基本定理确立：若线性规划存在最优解，则至少有一个最优解位于可行域的某个顶点上。这一事实是单纯形法的理论基石。

可行域是由一组线性约束定义的凸多胞形。其顶点在代数上对应基本可行解（Basic Feasible Solution, BFS）——对于具有 $m$ 个等式约束和 $n$ 个变量（含松弛变量）的标准形式，令 $n-m$ 个变量取零（非基变量），解出剩余 $m$ 个变量（基变量）即得一个基本解；若所有基变量非负，则构成一个基本可行解，几何上即对应可行域的一个顶点。

单纯形法的迭代过程在几何上极为直观：从当前顶点出发，沿可行域的边（棱）移动到使目标函数值改善的相邻顶点，重复至无法改善。每次迭代通过旋转操作（Pivoting）实现基变量与非基变量的交换——代数学上对应从一个 BFS 切换到相邻 BFS，几何上对应从一个顶点沿边走向另一个顶点。

值得注意的是，线性规划也可能出现退化（Degeneracy）：多个基变量同时取零时，多个 BFS 对应同一顶点，可能导致单纯形法在顶点间循环。布兰德规则（Bland's Rule）等反循环策略可确保算法终止。

在非线性规划中，最优解不一定位于顶点——它可能位于可行域内部（内点解）或边界非顶点处。但当目标函数或约束条件具有特殊结构时，角点解（Corner Solution）——一种经济学中常见的顶点现象——仍会出现。例如，拟线性偏好下的效用最大化可能产生仅消费一种商品的角点解；LASSO回归利用 $\ell_1$ 约束域的顶点结构（菱形在高维中的推广），使最优解倾向于落在坐标子空间上，从而自动实现变量选择与系数稀疏化。

图论中的顶点

在图论中，顶点（Vertex，又称节点 Node）与边（Edge）共同构成图 $G = (V, E)$ 的基本元素。顶点表示对象，边表示对象间的关系。顶点的度数（与之相连的边数）、邻域（与之相邻的顶点集合）是刻画图结构的核心指标。

在最大割问题（MAX-CUT）中，目标是将图的顶点集划分为两个子集，使跨越子集的边权和最大化——这是 Karp 的 21 个 NP-完全问题之一，在投资组合优化和市场分割中有直接应用。在网络流问题中，源点（Source）和汇点（Sink）是两个特殊的顶点，最大流-最小割定理围绕它们展开。

经济学中的顶点

顶点在经济学中频繁出现，从微观分析到宏观政策均有其身影。

角点解（Corner Solution）：在消费者理论中，当边际替代率与价格比在可行域内部无法相等时，最优消费束落在坐标轴上——某些商品消费量为零，此为角点解。这与内点解形成对照。完美互补品的 L 形无差异曲线在顶点处达到最优，该顶点位于从原点出发的固定比例射线上，MRS 在顶点处不定义（尖点）。

拉弗曲线：税率与税收收入呈倒 U 形关系，其顶点将曲线分为两个区间——税率低于顶点时，提高税率增加税收；税率高于顶点时，再提高税率反而减少税收。顶点的精确位置是实证争议的焦点。

有效前沿：在马科维茨均值-方差分析中，有效前沿是一条双曲线（或抛物线，取决于参数化方式），其最左端的顶点是最小方差组合（MVP）——所有可行组合中风险最低者。MVP 上方的前沿才是真正"有效"的部分。

价格单纯形：$n$ 种商品的价格向量经归一化后落在 $\Delta^{n-1}$ 上，其 $n$ 个顶点分别对应仅一种商品具有正价格的极端情形。Arrow-Debreu 一般均衡模型中，均衡价格是单纯形内部的点还是边界点，取决于经济的禀赋结构和偏好。

顶点与极点的关系

在凸分析中，极点（Extreme Point）是凸集中不能表示为集合内其他两点凸组合的点。对于凸多胞形，顶点与极点完全等价。但对于一般凸集（如圆盘），边界上所有点都是极点，而其中没有任何一个点是"顶点"意义上的角点——这揭示了"顶点"一词通常隐含了多面体结构（即由平坦面围成）。

一个经典结果是Krein-Milman定理：任何紧凸集等于其极点集的闭凸包。这意味着在无限维空间中，极点的概念比顶点更具一般性。此外，Brouwer不动点定理的 Sperner 引理证明中，单纯形剖分的全标子单纯形本质上是一个组合版本的顶点存在性定理——它保证了在适当着色下，细剖分中必存在一个