线性优化导论

线性优化是优化领域中处理目标函数和约束均为线性的问题的分支。研究利用优化问题线性特性的算法与技术的领域被称为线性规划。

线性优化

什么是“线性”？一个线性函数 $f$ 具有如下形式：

$$f(x_1, x_2, ..., x_n) = a_1x_1 + a_2x_2 + ... + a_nx_n + b$$

线性函数是次数为零或一的多项式函数。这意味着每个变量的指数只能是零或一。当函数仅包含一个变量时，其图像是一条直线。在一般情况下（如上例中的 $n$ 个变量），该函数的图像在数学中被称为超平面。

在上述例子中，$a_1, a_2, ..., a_n$ 以及 $b$ 都是标量（即数值）。这意味着线性函数只允许变量与标量相乘以及加法运算。因此，一个线性优化问题的形式如下：

$$\min_{x_1, x_2, ..., x_n} a_1x_1 + a_2x_2 + ... + a_nx_n + b \\ \text{s.t.: } p_{i1}x_1 + p_{i2}x_2 + ... + p_{in}x_n < p_i \\ i = 1, 2, ..., m$$

在此例中，共有 $m$ 个不等式约束和 $k$ 个等式约束（$q_{j1}x_1 + ... + q_{jn}x_n = q_j$，$j=1,...,k$）。所有约束也必须是线性的。所有的 $p_{ij}, p_i, q_{ij}, q_i$ 都是标量。我们使用 $p$ 和 $q$ 来区分不等式约束和等式约束。

注意：约束的左侧仅包含标量乘法和加法，右侧仅为一个标量。这正是我们称这些约束为线性的原因。

矩阵形式

这种表示线性问题的方式有助于初学者更好地理解，尤其是对矩阵符号不太熟悉的人。然而，从现在起我们将使用向量和矩阵。一般来说，一个线性优化问题可以定义如下：

$$\min_{\mathbf{x}} \mathbf{a}\mathbf{x}^\top \\ \text{s.t.: } P\mathbf{x}^\top < \mathbf{p} \\ Q\mathbf{x}^\top = \mathbf{q}$$

这两种定义是等价的。其中，$\mathbf{x} = (x_1, x_2, ..., x_n)$，$\mathbf{a} = (a_1, a_2, ..., a_n)$，$\mathbf{p} = (p_1, p_2, ..., p_m)$，$\mathbf{q} = (q_1, q_2, ..., q_k)$。不等式约束的数量不必等于变量数量，也不必等于等式约束的数量。矩阵 $P$ 的维度为 $m \times n$，且 $P_{ij} = p_{ij}$；矩阵 $Q$ 的维度为 $k \times n$，且 $Q_{ij} = q_{ij}$。

现在我们可以将任何以求和与标量乘法形式描述的线性问题转化为矩阵形式的表达。我们接下来要使用的求解工具均基于矩阵表示。

也许你会认为线性问题属于非常狭窄的问题类别。考虑到优化问题的广泛多样性，确实如此。但在实际应用中，这类问题频繁出现——频率之高以至于催生了一个专门研究它们的领域：线性规划。SciPy 库提供了求解此类问题的功能，我们将学习如何使用这些工具。