Knowledge

从 QUBO penalty 到 p-bit exchange：为什么同一个投资组合约束可以有两种建模方式

1. 先把投资组合问题写成数学对象

假设我们从 \(N\) 只候选股票里选出 \(K\) 只。用二进制向量 \(x\) 表示是否选择每只股票：选中就是 1，未选中就是 0。

x_i \in \{0,1\},\quad x_i = \begin{cases} 1, & \text{选择第 } i \text{ 只股票},\\ 0, & \text{不选择第 } i \text{ 只股票}. \end{cases}

如果只允许选 \(K\) 只股票，约束就是所有 1 的数量必须等于 \(K\)。

\sum_{i=1}^{N} x_i = K

投资组合目标通常同时考虑风险和收益。这里的 \(\mu\) 是股票的平均收益向量，\(\Sigma\) 是协方差矩阵；\(\lambda\) 控制我们多重视风险，\(\gamma\) 控制我们多重视收益。

\begin{aligned} \min_{x \in \{0,1\}^{N}} \quad E(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x,\\ \text{s.t.}\quad \sum_{i=1}^{N} x_i &= K. \end{aligned}

风险项

\(x^\top \Sigma x\) 衡量被选股票之间共同波动带来的组合风险，越小越稳定。

收益项

\(\mu^\top x\) 是被选股票的收益之和，前面有负号，所以收益越高，能量越低。

基数约束

\(\sum_i x_i=K\) 表示必须正好选 \(K\) 只股票。难点就在于如何让算法遵守这个约束。

2. Penalty QUBO：把约束塞进目标函数

QUBO 的全称是 Quadratic Unconstrained Binary Optimization，意思是“二次、无约束、二进制优化”。如果算法只接受无约束问题，一个常见做法是把约束违反程度变成惩罚项。

\begin{aligned} E_{\text{penalty}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x + A\left(\sum_{i=1}^{N}x_i-K\right)^2,\\ x_i &\in \{0,1\}. \end{aligned}

这里 \(A\) 是 penalty strength。若选中的股票数不是 \(K\)，平方项就会变大；若刚好选 \(K\) 只，惩罚项为 0。

\left(\sum_{i=1}^{N}x_i-K\right)^2 = 0 \quad \Longleftrightarrow \quad \sum_{i=1}^{N}x_i = K

这个 penalty 仍然是二次项，因为二进制变量满足 \(x_i^2=x_i\)。展开后可以看见它如何改变 QUBO 系数。

\begin{aligned} \left(\sum_i x_i-K\right)^2 &= \left(\sum_i x_i\right)^2 -2K\sum_i x_i +K^2\\ &= \sum_i x_i^2 +2\sum_{i<j}x_i x_j -2K\sum_i x_i +K^2\\ &= (1-2K)\sum_i x_i +2\sum_{i<j}x_i x_j +K^2. \end{aligned}

所以 penalty QUBO 实际上给每个变量增加线性偏置，也给每一对变量增加二次耦合。

\begin{aligned} E_{\text{penalty}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x\\ &\quad + A(1-2K)\sum_i x_i + 2A\sum_{i<j}x_i x_j + AK^2. \end{aligned}

如果用标准 p-bit 单 bit 翻转来搜索，状态通常会先从 \(x\in\{0,1\}^N\) 转成 Ising spin \(m\in\{-1,+1\}^N\)。常用映射是：

m_i = 2x_i - 1, \quad x_i = \frac{m_i+1}{2}.

在 Ising 形式下，一个 p-bit 根据当前其他 p-bit 形成的 local field 随机更新。若能量写成如下形式：

E(m) = -\frac{1}{2}\sum_{i\ne j}J_{ij}m_i m_j -\sum_i h_i m_i +C,

那么第 \(i\) 个 p-bit 取 \(+1\) 的概率可以写为：

\Pr(m_i=+1\mid m_{\setminus i}) = \frac{1} {1+\exp\left(-2\beta H_i\right)}, \quad H_i=h_i+\sum_{j\ne i}J_{ij}m_j.

\(J_{ij}\) — 耦合 (Coupling)

资产 \(i\) 与 \(j\) 之间的交互强度。由协方差 \(\Sigma\) 与惩罚项 \(A\) 通过 QUBO→Ising 变换得到。\(J_{ij}>0\) 表示两资产倾向于同向 spin。

\(h_i\) — 外场 (External Field)

单个资产 \(i\) 的独立偏置。来自收益项与惩罚项的线性部分。\(h_i\) 越大，该 p-bit 越倾向于取 \(+1\)（即选中该股票）。

\(H_i\) — 局部场 (Local Field)

在给定其他 p-bit 状态下，第 \(i\) 个 p-bit "感受到" 的总输入电流：\(H_i = h_i + \sum_{j\neq i} J_{ij} m_j\)。它综合了外场和所有邻居的影响。

\(\beta\) — 反温度 (Inverse Temperature)

\(\beta = 1/T\)。\(\beta\) 小（高温）→ 采样更随机、更愿意探索；\(\beta\) 大（低温）→ 更偏向低能量状态。退火过程让 \(\beta\) 逐渐增大。

\(C\) — 常数项 (Constant)

Ising 能量中不依赖 spin 构型的偏移量。由 QUBO→Ising 映射时产生，不影响采样概率（因为在指数差中互相抵消）。

\(m_i \in \{-1,+1\}\) — p-bit / Ising Spin

由二进制选择变量 \(x_i\) 通过 \(m_i = 2x_i - 1\) 映射而来：选中的股票对应 \(m=+1\)，未选中的对应 \(m=-1\)。

写 constrained portfolio

加入 penalty

转成 QUBO/Ising

单 bit p-bit 更新

Penalty 的核心代价

\(A\) 太小，算法可能偏爱收益高但不满足 \(K\) 的组合；\(A\) 太大，惩罚项会压过真实的风险-收益结构，使搜索空间变得陡峭，温度和系数缩放更难调。

3. p-bit exchange：不惩罚约束，而是永远待在可行空间里

exchange 方法的想法很直接：既然我们必须始终选 \(K\) 只股票，那每一步就不要翻转一个 bit，而是“一进一出”。卖出一只已选股票，同时买入一只未选股票。

x' = x - e_o + e_i, \quad x_o=1, \quad x_i=0.

这里 \(e_o\) 和 \(e_i\) 是单位向量：\(e_o\) 只在卖出股票的位置为 1，\(e_i\) 只在买入股票的位置为 1。

为什么这会自动保持 \(K\)？因为总数先减 1 再加 1。

\sum_j x'_j = \sum_j x_j -1 +1 = K.

因此 exchange 方法的目标函数可以只保留真实的风险和收益，不需要 cardinality penalty。

\begin{aligned} \min_{x \in \Omega_K} \quad E_{\text{exchange}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x,\\ \Omega_K &= \left\{ x\in\{0,1\}^{N}: \sum_i x_i=K \right\}. \end{aligned}

一次交换的能量变化可以快速计算。令 \(\delta=e_i-e_o\)，那么 \(x'=x+\delta\)。

\begin{aligned} \Delta E_{o,i} &= E(x+\delta)-E(x)\\ &= \lambda \left( 2\delta^\top\Sigma x + \delta^\top\Sigma\delta \right) - \gamma\delta^\top\mu. \end{aligned}

把 \(\delta=e_i-e_o\) 展开，就得到更接近程序实现的公式。若缓存 \(g=\Sigma x\)，就不需要每一步重算完整的矩阵乘法。

\Delta E_{o,i} = \lambda \left[ 2(g_i-g_o) + \Sigma_{ii} + \Sigma_{oo} - 2\Sigma_{io} \right] - \gamma(\mu_i-\mu_o).

有了每个候选交换的 \(\Delta E\)，p-bit exchange 可以按 heat-bath 分布随机选择下一步。低能量交换更可能被选中，但高能量交换也有一定概率出现，以便跳出局部最优。

\Pr(o,i\mid x) = \frac{ \exp\left(-\beta \Delta E_{o,i}\right) }{ Z(x) }, \quad Z(x) = \sum_{o\in S(x)} \sum_{i\notin S(x)} \exp\left(-\beta \Delta E_{o,i}\right).

程序里可以用 Gumbel-max 技巧等价采样，避免显式构造归一化概率表。

(o^\star,i^\star) = \arg\max_{(o,i)} \left[ -\beta \Delta E_{o,i} + G_{o,i} \right], \quad G_{o,i}\sim\operatorname{Gumbel}(0,1).

PS-REX 在此基础上放置多个副本：高温副本负责探索，低温副本负责收敛；相邻温度副本之间偶尔交换状态。

0<\beta_1<\beta_2<\cdots<\beta_R.

\Pr(\text{swap }a,b) = \min \left( 1, \exp\left[ (\beta_a-\beta_b) \left(E(x_a)-E(x_b)\right) \right] \right).

初始化可行组合

枚举/抽样一进一出交换

按 \(\Delta E\) 采样

始终保持 \(K\)

4. 两种路线的关键差别

问题

Penalty QUBO

p-bit exchange

约束如何处理？

把 \(\sum_i x_i=K\) 变成 \(A(\sum_i x_i-K)^2\)。

把搜索动作限制为一进一出，状态天然可行。

目标函数里有什么？

风险、收益、约束惩罚三部分。

只有风险和收益；约束不进入能量。

可能出现不可行状态吗？

会。搜索过程中经常有 \(\sum_i x_i\ne K\)。

不会。只要初始状态可行，之后每一步都可行。

主要调参难点是什么？

需要选择合适的 penalty strength \(A\)。

需要选择温度/β、候选交换数量、副本数。

一句话总结

Penalty QUBO 是“允许算法走出可行空间，但用惩罚把它拉回来”；p-bit exchange 是“从一开始就只允许算法在可行空间内部移动”。

Knowledge

From QUBO Penalties to p-bit Exchange: Two Ways to Handle the Same Portfolio Constraint

1. Writing the portfolio problem as mathematics

Suppose we choose exactly \(K\) assets from \(N\) candidates. A binary vector \(x\) records whether each asset is selected.

x_i \in \{0,1\},\quad x_i = \begin{cases} 1, & \text{asset } i \text{ is selected},\\ 0, & \text{asset } i \text{ is not selected}. \end{cases}

The fixed-cardinality constraint says that the number of selected assets must be exactly \(K\).

\sum_{i=1}^{N} x_i = K

The objective balances risk and return. Here \(\mu\) is the mean-return vector, \(\Sigma\) is the covariance matrix, \(\lambda\) controls the weight on risk, and \(\gamma\) controls the reward for return.

\begin{aligned} \min_{x \in \{0,1\}^{N}} \quad E(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x,\\ \text{s.t.}\quad \sum_{i=1}^{N} x_i &= K. \end{aligned}

Risk term

\(x^\top \Sigma x\) measures the joint volatility of the selected assets. Lower is more stable.

Return term

\(\mu^\top x\) is the total selected return. The minus sign means higher return lowers the energy.

Cardinality constraint

\(\sum_i x_i=K\) means the solver must select exactly \(K\) assets. The modeling question is how to enforce it.

2. Penalty QUBO: moving the constraint into the objective

QUBO stands for Quadratic Unconstrained Binary Optimization. If a solver accepts only unconstrained binary objectives, a common trick is to turn the constraint violation into a penalty term.

\begin{aligned} E_{\text{penalty}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x + A\left(\sum_{i=1}^{N}x_i-K\right)^2,\\ x_i &\in \{0,1\}. \end{aligned}

The parameter \(A\) is the penalty strength. If the selected count differs from \(K\), the squared term is positive; if the count equals \(K\), the penalty is zero.

\left(\sum_{i=1}^{N}x_i-K\right)^2 = 0 \quad \Longleftrightarrow \quad \sum_{i=1}^{N}x_i = K

The penalty is still quadratic because binary variables satisfy \(x_i^2=x_i\). Expanding it shows how it changes the QUBO coefficients.

\begin{aligned} \left(\sum_i x_i-K\right)^2 &= \left(\sum_i x_i\right)^2 -2K\sum_i x_i +K^2\\ &= \sum_i x_i^2 +2\sum_{i<j}x_i x_j -2K\sum_i x_i +K^2\\ &= (1-2K)\sum_i x_i +2\sum_{i<j}x_i x_j +K^2. \end{aligned}

Thus the penalty adds both linear biases and pairwise couplings.

\begin{aligned} E_{\text{penalty}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x\\ &\quad + A(1-2K)\sum_i x_i + 2A\sum_{i<j}x_i x_j + AK^2. \end{aligned}

For a standard single-bit p-bit update, the binary vector is often mapped to Ising spins \(m\in\{-1,+1\}^N\):

m_i = 2x_i - 1, \quad x_i = \frac{m_i+1}{2}.

If the Ising energy is written as

E(m) = -\frac{1}{2}\sum_{i\ne j}J_{ij}m_i m_j -\sum_i h_i m_i +C,

then p-bit \(i\) is sampled from the local field generated by the current state of all other p-bits.

\Pr(m_i=+1\mid m_{\setminus i}) = \frac{1} {1+\exp\left(-2\beta H_i\right)}, \quad H_i=h_i+\sum_{j\ne i}J_{ij}m_j.

\(J_{ij}\) — Coupling

The interaction strength between assets \(i\) and \(j\), derived from the covariance \(\Sigma\) and the penalty \(A\) via the QUBO→Ising transformation. \(J_{ij}>0\) means the two spins favor the same direction.

\(h_i\) — External Field

The independent bias of asset \(i\), coming from the linear part of the return and penalty terms. A larger \(h_i\) biases the p-bit toward \(+1\) (selected).

\(H_i\) — Local Field

The total input current "felt" by p-bit \(i\) given all other p-bits: \(H_i = h_i + \sum_{j\neq i} J_{ij} m_j\). It combines the external field with all neighbor influences.

\(\beta\) — Inverse Temperature

\(\beta = 1/T\). Small \(\beta\) (high \(T\)) → more random, exploratory sampling; large \(\beta\) (low \(T\)) → strongly biased toward low-energy states. Annealing gradually increases \(\beta\).

\(C\) — Constant Offset

The spin-independent shift in the Ising energy, produced during the QUBO→Ising mapping. It cancels out in probability ratios and does not affect sampling.

\(m_i \in \{-1,+1\}\) — p-bit / Ising Spin

Mapped from the binary variable \(x_i\) via \(m_i = 2x_i - 1\): a selected stock corresponds to \(m=+1\), an unselected one to \(m=-1\).

Write constrained portfolio

Add penalty

Convert to QUBO/Ising

Update one p-bit at a time

The core cost of penalties

If \(A\) is too small, the solver may prefer high-return but infeasible portfolios. If \(A\) is too large, the penalty can dominate the true risk-return structure and make coefficient scaling and annealing harder.

3. p-bit exchange: never leaving the feasible space

The exchange idea is simple: if the portfolio must always contain \(K\) assets, do not flip one bit at a time. Instead, perform a one-out/one-in move: remove one selected asset and add one unselected asset.

x' = x - e_o + e_i, \quad x_o=1, \quad x_i=0.

The vectors \(e_o\) and \(e_i\) are unit vectors: \(e_o\) marks the removed asset, and \(e_i\) marks the added asset.

This preserves cardinality because the selected count decreases by one and then increases by one.

\sum_j x'_j = \sum_j x_j -1 +1 = K.

Therefore the exchange objective contains only the real risk-return terms. The constraint is handled by the move set, not by a penalty in the energy.

\begin{aligned} \min_{x \in \Omega_K} \quad E_{\text{exchange}}(x) &= \lambda x^\top \Sigma x - \gamma \mu^\top x,\\ \Omega_K &= \left\{ x\in\{0,1\}^{N}: \sum_i x_i=K \right\}. \end{aligned}

A swap can be scored quickly. Let \(\delta=e_i-e_o\), so \(x'=x+\delta\).

\begin{aligned} \Delta E_{o,i} &= E(x+\delta)-E(x)\\ &= \lambda \left( 2\delta^\top\Sigma x + \delta^\top\Sigma\delta \right) - \gamma\delta^\top\mu. \end{aligned}

Expanding \(\delta=e_i-e_o\) gives a form close to the implementation. If \(g=\Sigma x\) is cached, the solver does not need to recompute the full quadratic energy each step.

\Delta E_{o,i} = \lambda \left[ 2(g_i-g_o) + \Sigma_{ii} + \Sigma_{oo} - 2\Sigma_{io} \right] - \gamma(\mu_i-\mu_o).

Given all candidate swap costs, p-bit exchange samples the next move from a heat-bath distribution. Lower-energy swaps are more likely, while higher-energy swaps remain possible so the search can escape local optima.

\Pr(o,i\mid x) = \frac{ \exp\left(-\beta \Delta E_{o,i}\right) }{ Z(x) }, \quad Z(x) = \sum_{o\in S(x)} \sum_{i\notin S(x)} \exp\left(-\beta \Delta E_{o,i}\right).

The implementation can use the Gumbel-max trick to sample from this distribution without explicitly normalizing all probabilities.

(o^\star,i^\star) = \arg\max_{(o,i)} \left[ -\beta \Delta E_{o,i} + G_{o,i} \right], \quad G_{o,i}\sim\operatorname{Gumbel}(0,1).

PS-REX adds multiple replicas. Hot replicas explore; cold replicas exploit. Neighboring-temperature replicas occasionally swap states.

0<\beta_1<\beta_2<\cdots<\beta_R.

\Pr(\text{swap }a,b) = \min \left( 1, \exp\left[ (\beta_a-\beta_b) \left(E(x_a)-E(x_b)\right) \right] \right).

Initialize feasible portfolio

Generate one-out/one-in swaps

Sample using \(\Delta E\)

Always preserve \(K\)

4. The key difference

Question

Penalty QUBO

p-bit exchange

How is the constraint handled?

Convert \(\sum_i x_i=K\) into \(A(\sum_i x_i-K)^2\).

Restrict moves to one-out/one-in swaps, so every state is feasible.

What appears in the objective?

Risk, return, and constraint penalty.

Only risk and return; the constraint is not part of the energy.

Can the search visit infeasible states?

Yes. During search, \(\sum_i x_i\ne K\) can occur.

No. If the initial state is feasible, every later state is feasible.

Main tuning issue?

Choosing the penalty strength \(A\).

Choosing temperature/β, candidate-swap limit, and replica count.

One-sentence takeaway

Penalty QUBO lets the solver leave the feasible space and tries to pull it back with an energy penalty; p-bit exchange only allows moves inside the feasible space from the beginning.