你当前正在访问 Microsoft Azure Global Edition 技术文档网站。如果需要访问由世纪互联运营的 Microsoft Azure 中国技术文档网站，请访问 https://docs.azure.cn。

成本函数

项目
07/08/2022

优化问题使用一组变量进行描述，每个变量都具有一组可能值（或一个范围）。它们描述优化求解器必须做出的决策。

解决方案为其中的每个变量进行赋值。该变量描述上述每个决策的选项。

成本函数将一个数值（评分）与每个可能的解决方案关联后进行比较，并从中选择最有利方案（最优解，通常由最低成本值标识）。

注意

在物理学中，哈密顿算符承担成本函数的角色，其中成本值指代系统的“能量”。变量值的每个选项称为“状态”，最小的“能量”状态是“基态”。

实现

通常，成本函数实现可能会推迟到完整的引用表、黑盒实现，甚至是外部输入。不过，一种常用的方法是将其定义为问题变量和参数的数学表达式。

示例：查找整数 $x$、$y$（接近 $\pi$）的分数。

两个变量：$x$，$y$（整数 $\in [1..100]$）
成本函数：$$ \mathrm{cost} = \left| \frac{x}{y} - \pi \right| $$（当 $x/y \approx \pi$ 时，你希望成本降到最低）。
可能的解决方案：$[1..100] \times [1..100]$（$x$、$y$ 的独立选项）
简单估计值：$$ x=3\text{, }y=1 \quad\Rightarrow\quad \mathrm{cost}=\left|\frac31-\pi\right|=0.14159 $$
此值范围内的最佳解决方案：$$ x=22\text{, }y=7 \quad\Rightarrow\quad \frac{22}{7}\approx 3.14286\text{, }\mathrm{cost}\approx 0.00126 $$

注意

成本函数的最优解是分数最低的解；成本函数不需要 $\mathrm{cost}=0$。

约束

约束是指维持有效解决方案须保持的多个变量之间的关系。

违反约束的解决方案可以通过成本函数分配一个非常高的成本（惩罚），也可以经由求解器显式采样进行排除。

示例：在前面查找接近 $\pi$ 的分数的问题中，将 $x$ 和 $y$ 二者与相同的数字相乘生成一个等值的最优解（例如，$44/14$）。可以通过为非简化分数添加惩罚因子来避免这种情况：

$$ \mathrm{cost} = \left| \frac{x}{y} - \pi \right| + \underbrace{100(\gcd(x,y)-1)}_{\mathrm{penalty}}, $$

其中，$\gcd(x,y)$ 是 $x$ 和 $y$ 的最大公约数，以便圆括号中的因子逐渐转换为简化分数。此次添加后，最佳解决方案 $22/7$ 就是唯一的。

注意

单个变量的约束通常合并到各自的允许值集中，而不是约束。

参数化模型

通常，优化问题包括多个变量和构成成本函数的多个因子。选择特定的数学结构来表示这些成本函数很有帮助，这样只需指示针对特定问题构造成本函数所需的形参和变量位置。

示例：将一组 $N$ 数字分为等和的两个组。

输入参数：$w_0..w_{N-1}$，组中的数字
$N$ 变量：$x_0..x_{N-1}$，指示第一个组 ($x_i=+1$) 还是第二个组 ($x_i=-1$) 中 $i$-th 数字。
模型成本函数：$$ \mathrm{cost} = \left| \sum_i w_i x_i \right| $$

也就是说，始终在最后一个项目符号中构造窗体的成本函数，但你根据要解决的特定问题实例来调整参数 $w_i$。

例如，数字 $[18, 19, 36, 84, 163, 165, 243]$ 是成本函数的结果

$$ \mathrm{cost} = \left| 18x_0 + 19x_1 + 36x_2 + 84x_3 + 163x_4 + 165x_5 + 243x_6 \right|$$

注意

此示例只有两个 $\mathrm{cost}=0$ 的解（其中一个是另一个的镜像）。可以找到这些方案吗？

支持的模型

在 Microsoft QIO 求解器中实现的模型包括 Ising 模型和二次和多项式非受限二进制优化（QUBO 和 PUBO）问题。它们支持多种应用程序，因为可以将多个其他优化问题映射到它们。

示例：对于上一个数字集除法问题，可以将

绝对值替换为平方运算符（它也在 0 处具有最小值）以包含

$$ \mathrm{cost}' = \left(\sum_i w_ix_i\right)^2 = \sum_{ij} w_iw_jx_ix_j\text{ .} $$

相乘时，此成本函数的因子数量多于上一个示例，但它碰巧是 Microsoft QIO 求解器支持的多项式 (PUBO) 格式的函数（这种情况下则是 Ising 成本函数）。

伊辛成本函数

Ising 变量采用值 $x_i\in\{\pm1\}$，参数化 Ising 成本函数采用的格式如下

$$ \mathrm{cost} = \sum_k \mathrm{term}_k = \sum_k c_k\prod_i x_i\text{ .} $$

参与每个因子 $k$ 的参数 $c$ 和变量 $x_i$ 的 ID 会以输入的一部分列出。

例如，输入

"cost_function": {
  "type": "ising",
  "version": "2.0",
  "terms": [
    { "c":  3, "ids": [0, 1, 2] },
    { "c": -2, "ids": [0, 3] },
    { "c":  1, "ids": [2, 3] }
  ]
}

描述包含三个因子的 Ising 成本函数：$$ \mathrm{cost} = 3x_0x_1x_2 -2x_0x_3 + x_2x_3\text{ .} $$

注意

允许空 ids 数组（常量因子）或使用单个值（“本地字段”）的数组，但是在该因子内不能重复使用相同的变量 id。

注意

Ising 成本函数的定义不同于规范 Ising 模型哈密顿 $ \mathcal{H}=-\sum_{ij}J_{ij}\sigma_i\sigma_j $，该哈密顿量算符在统计力学中通常采用全局符号。因此，负因子常量 $c_k$ 会触发两个变量之间的磁形状交互。

PUBO 成本函数

对于二进制优化问题，变量采用值 $x_i\in\{0,1\}$，而成本函数采用的格式如下

$$ \mathrm{cost} = \sum_k \mathrm{term}_k = \sum_k c_k\prod_i x_i\text{ .} $$

例如，输入

"cost_function" {
  "type": "pubo",
  "version": "2.0",
  "terms": [
    { "c":  3, "ids": [0, 1, 2] },
    { "c": -2, "ids": [0, 3] },
    { "c":  1, "ids": [2, 3] }
  ]
}

描述包含 3 个因子的 PUBO 成本函数：$$ \mathrm{cost} = 3x_0x_1x_2 -2x_0x_3 + x_2x_3\text{ .} $$

尽管 PUBO 成本函数的格式与之前的 Ising 示例相同，但 PUBO 成本函数描述了不同的优化问题（允许的变量值集不同：$\{0,1\}$ vs $\{\pm1\}$）。

注意

PUBO 和 QUBO 由相同的成本函数进行处理；没有单独的 qubo 标识符。二次二进制优化问题是 PUBO 的一个特例，其中每个 ids 数组的长度最大为 2。