题解：P12532 [XJTUPC 2025] Primal Core Optimization: Attribute Balance
ShwStone
·
·
题解
给个不同的观察。
考虑题目涉及到的函数 L(x,y,z) = \max(x,y,z,0)-\min(x,y,z,0)，它满足下列条件：
正定性：
**绝对一次齐次性**：
$L(ax,ay,az,0) = |a|L(x,y,z,0)$，这要分 $a$ 的正负证明：
$a\ge 0$ 是平凡的，此时：
$$
\begin{aligned}
\max(ax,ay,az,0) &= a \max(x,y,z,0)\\
\min(ax,ay,az,0) &= a \min(x,y,z,0)\\
L(ax,ay,az) &= aL(x,y,z)
\end{aligned}
$$
$a < 0$ 时：
$$
\begin{aligned}
\max (ax,ay,az,0) &= a\min (x,y,z,0) \\
L(ax,ay,az) &= a(\min(x,y,z,0) - \max(x,y,z,0))\\
&= -aL(x,y,z)
\end{aligned}
$$
**三角不等式**：
我们记 $M_i=\max(x_i,y_i,z_i,0)$，$m_i=\min(x_i,y_i,z_i,0)$，则 $L(x_i,y_i,z_i) = M_i - m_i$。
另记 $M_{12} = \max(x_1+x_2,y_1+y_2,z_1+z_2,0)$，$m_{12} = \min(x_1+x_2,y_1+y_2,z_1+z_2,0)$，则有：$L(x_1+x_2,y_1+y_2,z_1+z_2)=M_{12} - m_{12}$。
由于 relu 函数 $\max(a,0)$ 显然有性质 $\max(a,0)+\max(b,0) \ge \max(a+b,0)$，不难推广到：
$$
M_1+M_2 \ge M_{12}
$$
同理，因为 $\min(a,0)$ 满足 $\min(a,0)+\min(b,0) \le \min(a+b,0)$，可以推广到：
$$
m_1+m_2\le m_{12}
$$
所以会有：
$$
\begin{aligned}
L(x_1,y_1,z_1) + L(x_2,y_2,z_2)&=M_1-m_1+M_2-m_2\\
&=(M_1+M_2)-(m_1+m_2)\\
&\ge M_{12} + m_{12}\\
&= L(x_1+x_2,y_1+y_2,z_1+z_2)
\end{aligned}
$$
由于 $L(x,y,z)$ 满足上面三个性质， $L$ 成功升格为 $\mathbb R^3$ 空间上的一个**范数**。我们记作 $\Vert\cdot\Vert_L$。
那么 $(\mathbb R^3,+, \Vert\cdot\Vert_L)$ 就是一个**赋范线性空间**。
这个范数可以诱导一个**度量**：$d(\mathbf u,\mathbf v) = \Vert \mathbf u - \mathbf v\Vert_L$。$(\mathbb R^3, d)$ 就是一个度量空间。
这时候，我们想知道的凸性什么的都已经是代数里的基本结论了。
而且，不难发现题目要求等价如下：
$$
\min_{\mathbf u\in \mathbb R^3} \sum_{i=1}^n d(\mathbf u, \mathbf x_i)
$$
如果是 $L_2$ 范数，结论是取 $\bf x_i$ 平均值；如果是 $L_1$ 范数，结论是取 $\bf x_i$ 每坐标分别的中位数。
由于所有范数在拓扑上的等价性，可以考虑一些乱搞做法：初值选在平均值或中位值，然后用一些一阶优化算法（梯度下降什么的）或者零阶优化算法（模拟退火、爬山什么的）。