Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于优化数学的论文，标题很长，叫《超越闭性假设的 Farkas 引理推广：基于 Fenchel-Rockafellar 对偶的构造性方法》。

别被这些术语吓到！我们可以用一个生动的**“寻宝与地图”**的故事来解释它的核心思想。

1. 核心问题：我们在找什么？

想象你是一位寻宝猎人（数学家）。

宝藏（ $b$ ）：是你想要找到的一个特定目标（比如一个向量）。
藏宝图（ $P$ ）：是一个巨大的、形状不规则的区域（数学上叫“锥”）。在这个区域里，你可以自由移动。
传送门（ $A$ ）：是一个魔法装置，能把你在藏宝图里的位置（ $x$ ）传送到另一个世界（ $Y$ ），变成一个新的位置（ $Ax$ ）。

你的问题是：
我能不能在藏宝图（ $P$ ）里找到一个点 $x$ ，使得通过传送门后，我正好落在宝藏 $b$ 的位置？
即：方程 $Ax = b$ 在 $x \in P$ 的约束下，有解吗？

2. 传统的“老地图”（经典的 Farkas 引理）

以前，数学家们有一个著名的工具叫Farkas 引理。它就像一张**“绝对真理的清单”**。

规则：如果宝藏 $b$ 在传送后的区域里，那么一定不存在某种“反向光线”能同时照亮 $b$ 却照不到藏宝图。
致命缺陷：这张老地图有一个严格的**“闭性”要求**。它假设传送后的区域必须是完美封闭的（没有缺口，边缘光滑）。
- 现实情况：在很多复杂的数学世界里，传送后的区域往往是有缺口的，或者边缘是破碎的（数学上叫“非闭”）。这时候，老地图就失效了，或者很难检查它是否适用。

3. 这篇论文的新发明：一张“智能导航仪”

这篇论文的作者（Camille, Emmanuel, Christophe）发明了一种新的导航方法，不需要地图是完美封闭的也能工作。

核心创意：把“找宝藏”变成“玩游戏”

他们不直接去硬碰硬地找 $x$ ，而是设计了一个双人对战游戏（原问题与对偶问题）：

玩家 A（原问题）：试图在藏宝图里找一个点，让传送后的误差最小。
玩家 B（对偶问题）：在另一个维度里，试图找到一个“裁判”（向量 $y$ ），来惩罚那些偏离宝藏的尝试。

关键突破点：

不再要求“完美封闭”：以前的方法要求藏宝图必须是“实心且封闭”的。新方法只要求藏宝图是由一个**“有界的、封闭的凸形状”**（比如一个球体或方块）生成的。哪怕生成的区域有缺口，只要源头是好的，新方法就能用。
构造性（Constructive）：这是最棒的地方！以前的方法只能告诉你“有解”或“无解”（像是一个黑盒）。新方法告诉你**“怎么找到它”**。
- 它告诉你：只要解开了玩家 B 的游戏（对偶问题），就能直接算出玩家 A 的解（原问题的 $x$ ）。
- 这就像：你不需要亲自去迷宫里乱撞，只要解开了迷宫入口的密码锁（对偶问题），迷宫的出口路径（ $x$ ）就会自动显示出来。

4. 两个层面的解决方案

论文提供了两种精度的解决方案：

近似解（ $\epsilon > 0$ ）：
- 比喻：如果找不到正好落在宝藏上的点，能不能找到离宝藏非常近（误差在 $\epsilon$ 以内）的点？
- 结果：新方法保证，只要宝藏在这个区域附近，你就能算出那个“非常近”的点。而且，这个计算过程是唯一且稳定的。
精确解（ $\epsilon = 0$ ）：
- 比喻：必须正好落在宝藏上。
- 结果：这更难。论文指出，这取决于“裁判”（对偶问题的解）是否存在。如果存在，我们就能通过简单的公式（投影或梯度）直接算出宝藏坐标。如果不存在，说明虽然理论上能到达，但数学上很难“构造”出那个具体的路径（就像你理论上能走到终点，但找不到具体的路标）。

5. 生活中的类比：做蛋糕

传统方法：要求你的模具（ $P$ ）必须是完美的、封闭的金属模具。如果模具边缘有点毛刺（非闭），你就没法用标准公式判断蛋糕能不能烤出来。
新方法：只要你的模具是由一块完整的、有边界的橡皮泥（ $K_r$ $K_{r}$ ）捏出来的就行。哪怕捏出来的形状有点奇怪、甚至有点漏气（非闭），只要你知道橡皮泥的原始形状，就能通过一个**“反向配方”**（对偶问题）算出：
1. 能不能做出这个蛋糕？
2. 如果能，具体的配方（ $x$ ）是什么？

6. 这篇论文有什么用？

控制理论：比如控制火箭或机器人。有时候控制指令的范围不是完美的，新方法能帮你判断能不能把火箭送到指定位置，并算出推力指令。
逆问题：比如医学成像（CT/MRI）。从模糊的图像反推人体内部结构。新方法能告诉你反推是否可行，并给出重建图像的具体算法。
非凸优化：甚至可以把这种方法“放松”一下，用来处理那些不是凸的（形状很怪、有凹陷）的复杂区域。

总结

这篇论文就像给数学家们发了一套**“万能导航仪”。
以前的 Farkas 引理像是一张“死板的地图”，只适用于完美封闭的世界。
这篇论文提供了一套“动态算法”，它不要求世界是完美的，只要源头是清晰的，它就能通过“对偶游戏”，不仅告诉你“能不能”，还能手把手教你“怎么做”**（构造性解）。

它把高深的数学优化问题，从“只能判断”变成了“可以计算”，并且放宽了对世界“完美性”的苛刻要求。

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于优化理论中Farkas 引理推广的学术论文的详细技术总结。该论文由 Camille Pouchol, Emmanuel Trélat 和 Christophe Zhang 撰写，发表于 arXiv (2026)。

1. 研究问题 (Problem Statement)

Farkas 引理是优化领域的基础工具，用于判断线性方程 $Ax = b$ 在锥约束 $x \in P$ 下是否有解（即 $b \in A(P)$ ）。

经典设定：通常假设 $P$ 是闭凸锥，且像集 $A(P)$ 是闭集。
现有局限：
1. $A(P)$ 的闭性假设往往难以验证，且在许多实际应用中不成立。
2. 现有的推广（如 Hernandez-Lerma 和 Lasserre 的工作）虽然去除了 $A(P)$ 闭性的假设，但通常仍要求 $P$ 本身是闭的，且证明过程复杂、非构造性，得到的条件涉及两个变量，难以直接使用。
本文目标：在不假设 $A(P)$ 甚至 $P$ 是闭集的情况下，建立 Farkas 引理的新形式。特别是针对由有界闭凸集生成的锥，提供构造性的充要条件，以解决精确解（Exact Solvability）和近似解（Approximate Solvability）问题。

2. 方法论 (Methodology)

作者提出了一种基于原对偶优化对和Fenchel-Rockafellar 对偶理论的新方法。

辅助优化问题构建：
为了寻找满足 $\|Ax - b\| \le \varepsilon$ 的 $x \in P$ ，作者定义了一个无约束的凸优化问题 $(P_\varepsilon)$ ：
$\inf_{x \in X} F_\varepsilon(x) := \frac{1}{2} j_{K_r}^2(x) + \delta_{\{x \in X, \|Ax-b\|_Y \le \varepsilon\}}(x)$
其中：
- $P = \text{cone}(K_r)$ ， $K_r$ 是包含原点的有界闭凸集。
- $j_{K_r}$ 是 $K_r$ 的Minkowski 范数（Gauge function）。
- $\delta$ 是示性函数。
- 当 $\varepsilon=0$ 时，对应精确解问题； $\varepsilon > 0$ 时，对应近似解问题。
Fenchel-Rockafellar 对偶：
利用 Fenchel-Rockafellar 对偶理论，推导出上述原问题的对偶问题 $(D_\varepsilon)$ ：
$\inf_{y \in Y} J_\varepsilon(y) := \frac{1}{2} \sigma_{K_r}^2(A^*y) - \langle b, y \rangle_Y + \varepsilon \|y\|_Y$
其中 $\sigma_{K_r}$ 是 $K_r$ 的支撑函数（Support function）。
- 关键优势：对偶目标函数 $J_\varepsilon$ 在整个空间 $Y$ 上是无约束且连续的（因为 $K_r$ 有界， $\sigma_{K_r}$ 是 Lipschitz 连续的），这与以往文献中受线性约束的对偶问题不同，极大地简化了数值求解。
强对偶性：
证明了在给定假设下，原问题与对偶问题之间满足强对偶性（Strong Duality），即 $\inf P_\varepsilon = -\inf D_\varepsilon$ 。
构造性恢复：
通过一阶最优性条件（KKT 条件），建立原变量 $x$ 与对偶变量 $y$ 之间的关系：
$x \in \sigma_{K_r}(A^*y) \partial \sigma_{K_r}(A^*y)$
这使得一旦求得对偶解 $y^*$ ，即可构造出原问题的解 $x^*$ 。

3. 主要贡献 (Key Contributions)

更弱的假设条件：
- 不再要求 $A(P)$ 是闭集。
- 不再要求 $P$ 本身是闭集。
- 核心假设：锥 $P$ 由一个包含原点的有界闭凸集 $K_r$ 生成（即 $P = \text{cone}(K_r)$ ）。这一假设比 $P$ 闭性更弱，涵盖了大量非闭锥的情况。
构造性证明：
- 与以往非构造性的存在性证明不同，本文的方法提供了显式的构造途径。
- 通过求解无约束凸优化问题（对偶问题），并利用最优性条件，可以直接构造出满足精度 $\varepsilon$ 的解 $x_\varepsilon$ 。
统一的框架：
- 同时处理近似可解性（ $\varepsilon > 0$ ）和精确可解性（ $\varepsilon = 0$ ）。
- 将结果推广到非凸锥：通过松弛技术，将非凸锥 $P$ 松弛为其凸包生成的锥 $P_r$ ，并在特定条件下（如极值点假设）保证解落在原非凸锥中。
新的 Farkas 型替代定理：
给出了 $b \in A(P)$ 和 $b \in \overline{A(P)}$ 的充要条件，形式更加紧凑且易于计算。

4. 主要结果 (Key Results)

4.1 闭凸锥情形 (Closed Convex Cone)

若 $P$ 是闭凸锥，取 $K_r = P \cap B(0,1)$ ：

近似解： $b \in \overline{A(P)}$ 当且仅当 $\forall y \in Y, (A^*y)_+ = 0 \implies \langle b, y \rangle \le 0$ 。
精确解： $b \in A(P)$ 当且仅当 $\exists C > 0, \forall y \in Y, \langle b, y \rangle \le C \|(A^*y)_+\|$ 。
构造性：若对偶问题有解 $y^*$ ，则原问题解为 $x^* = (A^*y^*)_+$ （投影到锥上）。

4.2 有界闭凸集生成锥情形 (Cone generated by bounded closed convex set)

若 $P = \text{cone}(K_r)$ ， $K_r$ 有界闭凸：

充要条件：
- $b \in \overline{A(P)} \iff \forall y \in Y, \sigma_{K_r}(A^*y) = 0 \implies \langle b, y \rangle \le 0$ 。
- $b \in A(P) \iff \exists C > 0, \forall y \in Y, \langle b, y \rangle \le C \sigma_{K_r}(A^*y)$ 。
构造性：若对偶解 $y^*$ $y^{*}$ 存在，则 $x^* \in \sigma_{K_r}(A^*y^*) \partial \sigma_{K_r}(A^*y^*)$ $x^{*} \in σ_{K_{r}} (A^{*} y^{*}) \partial σ_{K_{r}} (A^{*} y^{*})$ 。
- 若满足非退化条件（ $A^*y$ 不在 $K_r$ 的奇异向量集中），则 $x^*$ 唯一确定。

4.3 一般锥与非凸情形 (General and Nonconvex Cones)

通过定义 $K_r = \text{conv}(K)$ （ $K$ 生成非凸锥 $P$ ），将问题转化为凸锥 $P_r$ 上的问题。
引入假设 (E)： $K_r$ 的极值点包含在 $K$ 中（ $\text{ext}(K_r) \subset K$ ）。
结论：在假设 (H)（非退化）和 (E) 下，若 $b \in A(P_r)$ ，则 $b \in A(P)$ ，且构造出的解 $x^*$ 实际上属于原非凸锥 $P$ 。这类似于最优控制中的“bang-bang"原理。

4.4 对偶解的存在性与几何解释

讨论了何时对偶问题能取到极小值（Dual Attainment）。
引入了**共享法向量（Shared Normal Vectors）**的概念：对偶解存在当且仅当集合 $A^{-1}(b)$ 和 $\lambda^* K$ 在接触点 $x^*$ 处共享非零法向量。
指出了在无限维空间中，即使原问题有解，对偶问题也可能没有解（即无法构造出 $x^*$ 的显式公式），并给出了反例。但在有限维空间中，对偶解总是存在的。

5. 意义与影响 (Significance)

理论突破：打破了 Farkas 引理长期依赖 $A(P)$ 或 $P$ 闭性的限制，将适用范围扩展到了更广泛的非闭锥和由有界集生成的锥。
算法友好性：提出的方法将可行性问题转化为无约束凸优化问题。由于对偶目标函数性质良好（连续、无约束），非常适合使用现代一阶算法（如 Chambolle-Pock 算法）进行数值求解。
构造性价值：不仅判断“是否有解”，还能在满足条件时显式构造出解（或近似解），这对于控制理论、逆问题等需要实际解的应用场景至关重要。
应用前景：
- 控制理论：处理无限维空间中的线性系统可控性问题。
- 逆问题：在约束条件下求解线性方程。
- 非凸优化：通过松弛和极值点理论，为非凸锥上的可行性问题提供了解决思路。

总结：这篇文章通过巧妙结合 Fenchel-Rockafellar 对偶和辅助优化问题，为 Farkas 引理提供了一个强大、通用且具备构造性的新框架，显著降低了理论假设门槛，并为数值实现提供了清晰的路径。