线性优化：从基础到高级方法

### 线性优化：从基础到高级方法 #### 1. 约束条件对优化问题的影响 在无约束问题中，例如函数 –x – y 的下确界为 –∞。但约束条件会带来巨大的改变。以二维多边形（多面体）为例，最优值往往出现在多边形的某个顶点上，这并非巧合。 我们可以画一条直线 –x – y = c，让直线的一部分落在可行集内。然后沿着梯度向量的负方向移动（梯度向量的负方向是函数下降最快的方向），这条直线会朝着向量 (1, 1) 的方向移动。只要直线还有部分在可行集内，我们就可以不断移动直线使 c 值变小，直到无法再移动，因为再移动就会超出可行集，导致问题变得不可行。当整条直线刚好超出可行集，仅与可行集内的点 (1, 1) 接触时，我们就找到了使 –x – y 最小的最优点。 #### 2. 凸函数与线性优化的转换 在很多情况下，即使目标函数是非线性的，我们也有可能将问题重新表述为线性问题，然后使用线性优化技术来获得精确解或近似解。当目标函数是凸函数时，就属于这种情况。在优化问题中，除了线性函数，凸函数是非常理想的，因为凸函数的局部最小值也是全局最小值，我们不用担心陷入局部最优。 我们可以用分段线性凸函数来近似凸（且可微）函数。之后，将具有分段线性目标函数的优化问题转化为具有线性目标函数的问题。不过，这个过程会使我们在第一步失去函数的可微性（函数不再平滑），在第二步增加问题的维度。 ##### 2.1 凸函数的定义和性质 - **定义**：函数 f: ℝⁿ → ℝ 是凸函数，当且仅当对于所有的 x, y ∈ ℝⁿ 和 0 ≤ λ ≤ 1，有 f(λx + (1 - λ)y) ≤ λf(x) + (1 - λ)f(y)。这意味着连接函数 f 图像上任意两点的线段位于函数 f 图像的上方。 - **性质**： - 凸函数不会有非全局的局部最小值。 - 如果函数 f₁, f₂, ..., fₘ: ℝⁿ → ℝ 是凸函数，那么函数 f(x) = maxᵢ fᵢ(x) 也是凸函数，但 f 可能会失去平滑性，优化方法可能无法使用导数。 - 函数 f(x) = max{m₁x + d₁, m₂x + d₂, ⋯, mₙx + dₙ} 是分段线性的，也是凸函数，因为每个 mᵢx + dᵢ 是凸函数（线性函数既是凸函数又是凹函数），凸函数的最大值也是凸函数。 ##### 2.2 优化问题的重新表述 我们可以将具有分段线性凸目标函数的优化问题重新表述为线性优化问题： 原问题：min {Ax ≥ b, maxᵢ mᵢ.x + dᵢ} 转化后：min {Ax ≥ b, z ≥ mᵢ.x + dᵢ, z} 例如，绝对值函数 f(x) = |x| = max{x, –x} 是分段线性且凸的。对于目标函数包含决策变量绝对值的优化问题，我们可以用两种方式将其重新表述为线性优化问题（目标函数中的 cᵢ 必须是非负的，否则目标函数可能是非凸的）： 方式一： 原问题：min {Ax ≥ b, ∑ᵢ₌₁ⁿ cᵢ|xᵢ|} 转化后：min {Ax ≥ b, zᵢ ≥ xᵢ, -zᵢ ≥ xᵢ, ∑ᵢ₌₁ⁿ cᵢzᵢ} 方式二： 原问题：min {Ax ≥ b, ∑ᵢ₌₁ⁿ cᵢ|xᵢ|} 转化后：min {Ax⁺ - Ax⁻ ≥ b, x⁺, x⁻ ≥ 0, ∑ᵢ₌₁ⁿ cᵢ(xᵢ⁺ + xᵢ⁻)} #### 3. 线性优化问题的几何意义 考虑标准形式的线性优化问题： min {Ax = b, x ≥ 0, c.x} 这个问题涉及线性代数方程。我们要理解这些方程以及最小化过程对应的几何图像。线性意味着“平坦”，当这些“平坦”的对象相互相交时，会形成超平面、直线和顶点。 线性约束条件定义了一个多面体。我们对这个多面体的顶点非常感兴趣。但如何确定多面体有顶点呢？如果它只是一个半空间怎么办？当我们从一般形式转换到标准形式时，问题的维度会增加，并且我们对决策变量施加了非负性约束。所以，即使一般形式的多面体没有顶点，在更高维的标准形式中它总会有顶点，因为标准形式的多面体位于第一卦限，不可能包含完整的直线。 对于线性优化问题，要么最优值为 –∞，要么存在一个有限的最优值，且该最优值在多面体的某个顶点处取得。因此，在寻找最优解时，我们必须关注这些顶点。由于与实际约束相关的多面体通常有数千个顶点，我们需要有效的方法来筛选它们。 ##### 3.1 代数与几何的相互作用 在讨论单纯形法之前，我们将约束条件的代数方程（或一般形式问题中的不等式）与几何图像联系起来： - **多面体**：约束条件整体构成一个多面体。代数上，多面体是满足线性系统 x ∈ ℝⁿ，使得 Ax ≥ b（对于某些 Aₘₓₙ 和 b ∈ ℝᵐ）的点的集合。 - **半空间的内部**：考虑约束条件中的一个不等式 ai.x > bi（一个不等式约束的严格不等式部分），它对应于多面体某一面一侧的所有点。由于是严格不等式，这些点位于半空间的内部，而不是边界上。 - **超平面**：考虑一个等式约束 ai.x = bi，或者一个不等式约束的等式部分。这是半空间 ai.x > bi 的边界，也是多面体的一个面。 - **有效约束**：当我们将点 x* 的坐标代入约束条件 ai.x ≥ bi 得到等式 ai.x* = bi 时，该约束在点 x* 处是有效的。几何上，这意味着 x* 位于半空间的边界上，而不是内部。 - **多面体的顶点**：几何上，需要适当数量的超平面相交才能形成一个顶点。代数上，在顶点处有适当数量的约束是有效的。这就是基本可行解，我们在讨论单纯形法时会详细介绍。 - **相邻基与相邻顶点**：矩阵 A 的两列子集，除了一列不同外其余都相同，我们用它们来计算相邻顶点的坐标。在单纯形法中，我们需要从一个顶点几何地移动到相邻顶点，相邻基可以帮助我们以系统的代数方式实现这一点。 - **退化情况**：在二维中，假设有两条直线相交形成一个顶点。如果第三条直线也恰好通过这个交点，即有超过两个约束在同一点有效，就会出现退化情况。在 n 维中，点 x* 有超过 n 个超平面通过，或者有超过 n 个有效约束。在优化算法中，退化可能导致我们选择另一组线性无关的列来求解另一个基本可行解（顶点）时，得到与之前相同的解，从而使算法陷入循环。 #### 4. 单纯形法 我们的目标是设计一种算法，用于找到标准形式线性优化问题的最优解： min {Ax = b, x ≥ 0, c.x} 其中 A 是 m × n 矩阵，有 m 个线性无关的行（所以 m ≤ n），b 是 m × 1 向量，c 和 x 是 n × 1 向量。我们假设 A 的 m 行是线性无关的，这意味着约束条件没有冗余，并且保证 A 至少有一组 m 个线性无关的列（rank(A) = m）。我们需要这些线性无关的列（即基）来启动在多面体某个顶点处的最优解搜索，并使用单纯形法从一个顶点移动到另一个顶点。 ##### 4.1 单纯形法的主要思想 我们从多面体的一个顶点（也称为基本可行解）开始，朝着保证能降低目标函数（或成本）的方向移动到另一个顶点，直到我们找到最优解或发现问题是无界的（最优成本为 –∞）。在退化问题中可能会出现循环，但