CVXOPT

CVXOPT 是一个用于凸优化问题的 Python 库。它提供了一系列用于求解凸优化问题的函数，包括线性规划、二次规划、二次约束等。CVXOPT 的 API 设计得非常直观，使得用户可以方便地定义和求解各种凸优化问题。

二次规划 (QP)

二次规划 (Quadratic Programming, QP) 是一种常见的凸优化问题，其目标函数为二次函数，约束条件为线性不等式。在 CVXOPT 中提供了 QP solver 来求解 QP 问题。

在金融领域，二次规划常用于资产组合优化。

下面我们来拆解一下这个词：

• Q - Quadratic (二次的)

  • “二次”指的是问题的核心目标像一个”碗”或者”山谷”。它的数学表达式里包含变量的平方，比如 x²。

  • 为什么”碗”这个形状很重要？因为它只有一个最低点。求解器的任务就是精准地找到这个碗底。如果是个平面，那就没有最低点了；如果坑坑洼洼，就会有很多个局部最低点，难以抉择。二次问题（QP）保证了我们能找到那个唯一的、全局的最低点。

• P - Programming (规划)

  • 这里的”规划”不是指我们平时说的写代码（Programming）。它是一个历史悠久的数学术语，意思是”做计划”或者”寻找最优方案”。

  • 所以，“二次规划”指的就是为二次型问题寻找最优解决方案的计划。

• Solver (求解器)

  • 这个最好理解，它就是执行这个计划的工具或引擎。你把问题描述给它，它内部有一套非常高效的算法，能自动、快速地帮你找到答案。

总结: 一个 QP 求解器 (QP Solver)，就是一个专门用来寻找”碗状”问题最低点的自动化数学工具。你需要做的就是告诉它你的”碗”长什么样（目标），以及你必须遵守的”规则边界”（约束），然后它就能帮你找到在这些边界内的最低点在哪里。

QP solver流程示例

问题描述

求解以下 QP 问题。

目标函数 (Minimize)： 2x₁² + x₂² + x₁x₂ + x₁ + x₂

约束条件 (Subject to)： - x₁ ≥ 0 - x₂ ≥ 0 - x₁ + x₂ = 1

“碗”就是目标函数: 2x₁² + x₂² + x₁x₂ + x₁ + x₂

“规则边界”就是约束条件: x₁ ≥ 0, x₂ ≥ 0, 和 x₁ + x₂ = 1

CVXOPT 里的 solvers.qp 就是那个能解决这个问题的求解器。

我们把使用这个库想象成 “给一个很厉害但一板一眼的厨师下订单” 的过程。这位厨师（CVXOPT）厨艺高超，但你必须用他唯一能看懂的、格式固定的订单（矩阵）来告诉他你要什么。

整个过程分为三步：

第 1 步：用大白话描述你的”目标”和”规则”

这一步是给自己看的，先理清思路。

• 我的目标是什么？(Objective)

  我想要一个”菜”（由原料 x₁ 和 x₂ 组成），它的”成本”由公式 2x₁² + x₂² + x₁x₂ + x₁ + x₂ 决定。我的目标是让这个成本最低。

• 我有什么规则？(Constraints)

  • 规则1：原料 x₁ 的用量不能是负数 (x₁ ≥ 0)。
  • 规则2：原料 x₂ 的用量也不能是负数 (x₂ ≥ 0)。
  • 规则3：两种原料的总用量必须正好是 1 (x₁ + x₂ = 1)。

第 2 步：把”目标”和”规则”翻译成”厨师的订单格式”（矩阵）

这是最关键的一步。这位厨师（CVXOPT）不认识我们的大白话，他只认识一张叫 P, q, G, h, A, b 的标准订单。我们必须把信息填进去。

• 填写 P 和 q (描述你的”目标”)

  厨师通过 P 和 q 来理解你想要的那个”成本函数”（那个”碗”）。

  • P 矩阵描述成本函数里二次项（带平方的项）的部分，它决定了”碗”的形状。
  • q 矩阵描述成本函数里一次项（不带平方的项）的部分，它决定了”碗”的位置。

  怎么填: 根据数学规则(后面介绍)，我们计算出

• 填写 G 和 h (描述你的”不严格”规则)

  厨师通过 G 和 h 来理解所有”小于等于”或”大于等于”的规则。

  我们的规则是 x₁ ≥ 0 和 x₂ ≥ 0。订单格式要求写成”小于等于”，所以我们改写成 −x₁ ≤ 0 和 −x₂ ≤ 0。

  怎么填: 我们把这个信息填入订单，得到

• 填写 A 和 b (描述你的”死规定”)

  厨师通过 A 和 b 来理解所有”必须正好等于”的死规定。

  我们的死规定是 x₁ + x₂ = 1。

  怎么填: 我们把这个信息填入订单，得到

现在，我们的订单填好了！我们已经成功把我们的想法，翻译成了计算机能懂的语言。

第 3 步：用 Python 代码把”订单”交给”厨师”

这一步就是写代码，把我们刚刚整理好的矩阵告诉 CVXOPT。

from cvxopt import matrix, solvers

# --- 把我们翻译好的订单内容写下来 ---

# 这是告诉厨师，我们目标"碗"的形状和位置
P = matrix([[4.0, 1.0], [1.0, 2.0]])
q = matrix([1.0, 1.0])

# 这是我们设定的"不能超过"的规则
G = matrix([[-1.0, 0.0], [0.0, -1.0]])
h = matrix([0.0, 0.0])

# 这是我们设定的"必须等于"的死规定
A = matrix([[1.0, 1.0]])
b = matrix(1.0)

# --- 把这张"订单"正式交给"厨师"（求解器），让他开始工作 ---
sol = solvers.qp(P, q, G, h, A, b)

# --- 查看"厨师"给出的最终配方（最优解） ---
# sol['x'] 里就是我们想要的 x1 和 x2 的最佳用量
print("找到了能让成本最低的原料配比：")
print(sol['x'])

数学规则

目标函数

要理解这些矩阵的含义，首先需要了解 cvxopt.solvers.qp 所求解的二次规划问题的标准数学形式。其目标是找到一个向量 x，使得：

• 最小化 (Minimize)：
• 约束条件 (Subject to)： 其中 ≼ 表示逐元素小于等于。

下面我们来逐一解释每个矩阵和向量的含义。

矩阵和向量的含义

1. P 和 q：定义目标函数

   这两个参数共同构成了你需要最小化的目标函数，它是一个二次函数。

   • P (Matrix, 矩阵)：
     • 这是一个 n × n 的半正定矩阵（positive semi-definite），其中 n 是你要求解的变量 x 的维度。
     • 矩阵 P 描述了目标函数中所有变量的二次关系。在数学上，P 是目标函数 f(x) 的海森矩阵 (Hessian Matrix)，即由目标函数的二阶偏导数组成的方阵，描述了函数的局部曲率。
     • 格式：在 cvxopt 中，P 必须是 cvxopt.matrix 类型。
     • 计算方法：
       1. 写出目标函数 f(x) = 2x₁² + x₂² + x₁x₂ + x₁ + x₂。
       2. 计算 f(x) 对所有变量的一阶偏导（梯度 ∇f(x)）：
       3. 计算二阶偏导，构成海森矩阵 H：

为什么有

数学上，在目标函数中加入 是一个惯例。这样做可以使得求导后的形式变得简洁（例如，），但它不影响最优点的位置。cvxopt 的标准形式包含了这个 ，所以在定义 P 时，你不需要自己再乘以2。

• q (Vector, 向量)：
  • 这是一个 n × 1 的向量。
  • 向量 q 描述了目标函数中所有变量的线性关系。它是在剥离了二次项和常数项后，与 x 线性组合的系数向量。它影响了目标函数曲面的位置。
  • 格式：q 也必须是 cvxopt.matrix 类型。
  • 计算方法：
    • 审视目标函数 f(x) = 2x₁² + x₂² + x₁x₂ + x₁ + x₂。
    • 找出所有只与变量一次幂相乘的项：x₁ + x₂。
    • 将这部分写成向量内积的形式 q^Tx：
    • 对比系数可得 q₁ = 1, q₂ = 1。
  • 结果：

2. G 和 h：定义不等式约束

   这两个参数共同定义了问题中的不等式约束。标准形式 Gx ≼ h 要求所有不等式都是”小于等于”的形式，并且每一行代表一个独立的约束。≼ 符号代表逐元素比较。

   • G (Matrix, 矩阵)：
     • 这是一个 m × n 的矩阵，其中 m 是不等式约束的数量。
     • G 的每一行定义了一个线性不等式。例如，G 的第一行和 h 的第一个元素共同定义了第一个约束： G_1, 1x₁ + G_1, 2x₂ + ⋯ + G_1, nx_n ≤ h₁
     • 格式：cvxopt.matrix 类型。
   • h (Vector, 向量)：
     • 这是一个 m × 1 的向量。
     • 作用：h 包含了 m 个不等式约束的右侧边界值。
     • 格式：cvxopt.matrix 类型。
   • 计算方法：
     1. 逐一标准化：将每一个不等式约束都转换为 [...] ≤ [...] 的形式。
     • 约束1：x₁ ≥ 0 ⟹ −x₁ ≤ 0
     • 约束2：x₂ ≥ 0 ⟹ −x₂ ≤ 0
     2. 提取系数行向量(每个约束中x的系数)：
     • 对于 −x₁ ≤ 0，系数行向量是 ，右侧常数是 0。
     • 对于 −x₂ ≤ 0，系数行向量是 ，右侧常数是 0。
     3. 堆叠成矩阵：将所有系数行向量按顺序堆叠，形成矩阵 G，右侧常数堆叠成向量 h。
     • 结果：

3. A 和 b：定义等式约束

   这两个参数共同定义了问题中的等式约束（Ax = b）。

   • A (Matrix, 矩阵)：
     • 这是一个 p × n 的矩阵，其中 p 是等式约束的数量。
     • 作用：A 的每一行定义了一个线性等式约束。
     • 格式：cvxopt.matrix 类型。
   • b (Vector, 向量)：
     • 这是一个 p × 1 的向量。
     • 作用：b 包含了 p 个等式约束右侧的目标值。
     • 格式：cvxopt.matrix 类型。
   • 计算方法 (与G,h类似)：
     1. 审视等式：本例只有一个等式约束 x₁ + x₂ = 1。
     2. 提取系数行向量：，右侧常数为 1。
     3. 堆叠成矩阵：本例只有一行。
     • 结果：

总结：

• P, q：描述了你想最小化的”成本”函数。
• G, h：设定了变量 x 的活动范围（例如 x₁ ≥ 0 可以写成 −x₁ ≤ 0）。
• A, b：设定了变量 x 必须满足的精确关系（例如 x₁ + x₂ = 1）。