今天分享2024年阿里巴巴数学竞赛决赛（应用与计算赛道）第 4 题的个人解答.
T4. 考虑如下两个优化问题：
和
其中 $ x := [x_1^T, \cdots, x_n^T]^T \in \mathbb{R}^m (m, n \in \mathbb{N}) $，且对于 $ i = 1, \cdots, n $，$ x_i \in \mathbb{R}^{m_i} (m_i \in \mathbb{N}) $，满足 $\sum_{i=1}^n m_i = m$. 函数 $ f : \mathbb{R}^m \rightarrow \mathbb{R} $ 和 $ \mathbf{g} : \mathbb{R}^m \rightarrow \mathbb{R}^p (p \in \mathbb{N}) $ 是多仿射的，即对任意 $ i \in \{1, \cdots, n\} $，在固定下标在 $\{1, \cdots, N\} \setminus \{i\} $ 中的块后，它们对 $ x_i $ 是仿射函数。这里，我们称一个函数 $ h : \mathbb{R}^q \rightarrow \mathbb{R}^r (q, r \in \mathbb{N}) $ 是仿射的，若对任意 $ a \in \mathbb{R} $ 以及 $ y^{(1)}, y^{(2)} \in \mathbb{R}^q $，有
对任意 $ i \in \{1, \cdots, n\} $，集合 $ \mathcal{F}_i \subseteq \mathbb{R}^{m_i} $ 是一个有界多面体。函数 $ \mathbf{g} $ 在 $ \times_{i=1}^n \mathcal{F}_i $ 上非负，其中 “$\times$” 表示集合的笛卡尔积. 此外，在问题 (B) 中，标量 $ \beta $ 是一个实数，$\mathbf{1}_p $ 代表 $ p $ 维全一向量.
请证明如下三个结论：
(1) 对任意 $ \beta \in \mathbb{R} $，问题 (B) 至少有一个最优解是可行的极点（即极点最优解）.
(2) 存在 $ \bar{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \bar{\beta} $，问题 (B) 的极点最优解都是问题 (A) 的最优解.
(3) 存在 $ \tilde{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \tilde{\beta} $，问题 (A) 和 (B) 的最优解集合相同.
(1) $Proof.$
假设 $x^\ast$ 为非极点的最优解，考虑 $x^\ast$ 为多边形的内点(边界点情况类似)，任取一个方向向量 $d$，构造函数
由于，$f$ 和 $g$ 均为仿射函数，故 $\varphi$ 为关于 $t$ 的 $1$ 次函数，但由于 $x^\ast$ 为最优解，故 $\varphi (t)$ 不能是增函数，否则在沿 $d$ 的反方向上可以找到更小的值，与$x^\ast$ 为最优解矛盾，同理也不能是减函数，只能为常值函数。
同时，由于存在极值点的多面体中一定不包含直线(这句话的证明参考 《Introduction to Linear Optimization》 第 2.5 节)，故沿着 $d$ 或 $-d$ 方向可以走到多面体的区域边界，类似地，按照上面的构造方法沿着边界方向继续走，可以到找一个极点最优解。
(2) $Proof.$
显然问题 (B) 的目标函数为问题 (A) 的Lagrange对偶形式，记
则问题 (A) 可以写为如下等价形式
问题 (B) 可以写为如下形式
对满足约束 $x_i \in \mathcal{F}_i, i = 1, \cdots, n$ 的 $x$ 有
问题 (B) 的最优解取到的最小值一定小于等于相同的可行解在问题 (A) 上的取值，由线性规划的强对偶性知，问题 (B) 和问题 (A) 具有相同的最优值，故若问题 (B) 的最优解是问题 (A) 的可行解，那么就能证明问题 (B) 的最优解都是问题 (A) 的最优解。
因此只需证明对于问题 (B) 的最优解，存在 $ \bar{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \bar{\beta} $，问题 (B) 的最优解都满足问题 (A) 的约束条件即可。
记 $S$ 为 $g(x) = 0$ 的解集，则当 $\mathop{\min}\limits_{x \in S} f(x) \leq \mathop{\min}\limits_{x \notin S} f(x) + \beta {g}(x)^\top \mathbf{1}_p$ 时，问题 (B) 的最优解 $x^\ast \in S$，即 $x^\ast$ 满足问题 (A) 的约束条件。
由 $\mathop{\min}\limits_{x \notin S} f(x) + \beta {g}(x)^\top \mathbf{1}_p \geq \mathop{\min}\limits_{x \notin S} f(x) + \mathop{\min}\limits_{x \notin S} \beta {g}(x)^\top \mathbf{1}_p$，只需 $\mathop{\min}\limits_{x \notin S} f(x) + \mathop{\min}\limits_{x \notin S} \beta {g}(x)^\top \mathbf{1}_p \geq \mathop{\min}\limits_{x \in S} f(x)$ 即可，由函数 $ \mathbf{g} $ 在 $ \times_{i=1}^n \mathcal{F}_i $ 上非负解出
显然问题 (B) 的极点最优解属于其最优解，故存在这样一个 $\bar{\beta}$ 使得问题 (B) 的极点最优解都是问题 (A) 的最优解。
(3) $Proof.$
取 $\tilde{\beta} = \max\left\{\bar{\beta},0\right\}$，由 (2) 可知，当 $\beta \geq \tilde{\beta}$ 时，问题 (B) 的最优解都是问题 (A) 的最优解，下面只需要证明问题 (A) 的最优解都是问题 (B) 的最优解即可。
由函数 $ \mathbf{g} $ 在 $ \times_{i=1}^n \mathcal{F}_i $ 上非负和 $\beta \geq 0$，可得
故问题 (A) 的最优解取到的最小值一定小于等于相同的可行解在问题 (B) 上的取值，同样地由线性规划的强对偶性知，问题 (B) 和问题 (A) 具有相同的最优值，且问题 (A) 的可行解一定是问题 (B) 的可行解，故问题 (A) 的最优解一定是问题 (B) 的最优解。
综上所述，存在 $ \tilde{\beta} \in \mathbb{R} $，使得对任意 $ \beta \geq \tilde{\beta} $，问题 (A) 和 (B) 的最优解集合相同。