4. 罚函数法基本原理

在量子优化约束建模中，罚函数法是最常用、也最容易被低估的一类技术。它的核心思想非常直接：把带约束的优化问题转化为一个无约束（或更易处理）的优化问题，让违反约束的代价以“罚项”的形式叠加到目标函数上。这样，求解器只需要面对一个统一的能量函数，而不必在搜索过程中显式维护可行性。

设原始问题为：在约束 g(x) ≤ 0 下最小化 f(x)。罚函数法构造新的目标：

F(x) = f(x) + P(x)
P(x) = λ · max(0, g(x))²   （外点罚函数，二次罚项）

其中 λ 为罚系数。当解满足约束时，罚项为零，能量等于原目标；当解违反约束时，罚项为正，把该解“推”回可行域附近。罚函数的作用机制可以理解为：在能量景观上人为抬升不可行区域的地势，使全局最低点尽量落在可行域内。

外点罚函数与内点罚函数

外点罚函数从可行域外部逼近最优解。它允许迭代点暂时不可行，通过逐步增大 λ，使不可行解的罚项越来越大，最终迫使最优解收敛到可行边界。其优点是初始点可以任意选取，实现简单；缺点是中间解可能不可行，且 λ 过大时能量景观变得陡峭，数值条件变差。

内点罚函数（又称障碍函数法）则要求迭代点始终位于可行域内部，通过在边界附近设置“障碍”阻止解穿越约束边界。常见形式为对数障碍：

F(x) = f(x) − μ · Σ ln(−g_i(x))

当 g_i(x) 趋近于 0（即接近边界）时，对数项趋于负无穷，形成能量壁垒。内点法适合严格可行初始点已知的场景，但无法处理等式约束，且对初始点的可行性要求较高。

罚项设计对解空间与能量景观的影响

罚项设计直接决定了能量景观的形状，进而影响量子优化（如 QAOA、量子退火）的搜索行为。三个关键参数需要权衡：

• 罚系数 λ 的量级：λ 太小，不可行解仍可能成为全局最低点，约束形同虚设；λ 太大，可行域与不可行域之间形成陡峭悬崖，能隙变小，量子算法难以穿越。经验上 λ 应略大于原目标函数在可行域边界处的梯度量级。
• 罚项阶数：二次罚项平滑可导，适合梯度类与连续变量方法；线性罚项（λ·max(0,g)）在边界处不可导，但对应量子比特映射时往往更节省辅助比特。
• 约束缩放：不同约束的量纲差异会导致罚项失衡。应先对每个约束做归一化，使 g_i(x) 在违反时大致处于同一数量级，再统一设置 λ。

从解空间角度看，罚函数并不真正“删除”不可行解，而是给它们附加高能量。这意味着解空间维度不变，但低能区域被重新塑形。对量子优化而言，这既是优点（无需复杂的可行解编码），也是风险（不可行态仍占用希尔伯特空间，可能干扰搜索）。

简单约束的罚项构造示例

考虑一个 4 比特的背包式约束：选择物品数不超过 2，即 Σ x_i ≤ 2，x_i ∈ {0,1}。构造罚项：

P(x) = λ · max(0, Σx_i − 2)²

示例：x = (1,1,1,0)，Σx_i = 3，违反量 = 1
P = λ · 1² = λ
若 λ = 5，则该状态能量比可行状态高出 5

在伊辛模型映射中，平方项需要引入辅助比特或利用多项式归约。一种常见做法是将 max(0, s−2) 展开为对违反量的惩罚，并用辅助变量表示超出部分。实际实现时，建议先用小规模枚举验证：对全部 2⁴ = 16 个状态计算 F(x)，确认最低能量状态确实落在可行域内，再扩展到更大规模。

总结来说，罚函数法把约束“软化”为能量代价，外点法从外部压入、内点法从内部顶住边界。罚项设计的关键在于 λ 量级、罚项阶数与约束归一化三者的协调。一个可靠的实践习惯是：先用小规模全枚举检验罚项是否把全局最优锁定在可行域，再进入量子求解阶段。