Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910050536128512 |
|---|---|
| author | Pouchol, Camille Trélat, Emmanuel Zhang, Christophe |
| author_facet | Pouchol, Camille Trélat, Emmanuel Zhang, Christophe |
| contents | Farkas' lemma is an ubiquitous tool in optimisation, as it provides necessary and sufficient conditions to have $b \in A(P)$, where $P$ is a closed convex cone, $A$ is a (continuous) linear mapping and $b$ is a fixed vector. The standard underlying hypothesis is the closedness of $A(P)$, which is not always satisfied and can be difficult to check. We devise a new method to generalise Farkas' lemma, based on a primal-dual pair of optimisation problems and Fenchel-Rockafellar duality theory. We work under the sole hypothesis that $P$ be generated by a closed bounded convex set. This hypothesis is weaker than in previous generalisations of Farkas' lemma, which almost all require that $A(P)$ be closed, or, in few cases, that only $P$ be closed. In our case, $P$ (and a fortiori $A(P)$) is not necessarily closed; we uncover necessary and sufficient conditions both for $b \in A(P)$ and $b \in \overline{A(P)}$. For a given $\e \geq 0$, we exhibit constructive characterisations of $x \in P$ such that $\|Ax-b\| \leq \e$ when it exists, by means of optimality conditions. For $\e = 0$, these strongly rely on whether the dual problem admits a solution, and we discuss conditions under which it does. Finally, we also explain how, upon relaxation, we may apply our method to a nonconvex cone. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11859 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality Pouchol, Camille Trélat, Emmanuel Zhang, Christophe Optimization and Control Farkas' lemma is an ubiquitous tool in optimisation, as it provides necessary and sufficient conditions to have $b \in A(P)$, where $P$ is a closed convex cone, $A$ is a (continuous) linear mapping and $b$ is a fixed vector. The standard underlying hypothesis is the closedness of $A(P)$, which is not always satisfied and can be difficult to check. We devise a new method to generalise Farkas' lemma, based on a primal-dual pair of optimisation problems and Fenchel-Rockafellar duality theory. We work under the sole hypothesis that $P$ be generated by a closed bounded convex set. This hypothesis is weaker than in previous generalisations of Farkas' lemma, which almost all require that $A(P)$ be closed, or, in few cases, that only $P$ be closed. In our case, $P$ (and a fortiori $A(P)$) is not necessarily closed; we uncover necessary and sufficient conditions both for $b \in A(P)$ and $b \in \overline{A(P)}$. For a given $\e \geq 0$, we exhibit constructive characterisations of $x \in P$ such that $\|Ax-b\| \leq \e$ when it exists, by means of optimality conditions. For $\e = 0$, these strongly rely on whether the dual problem admits a solution, and we discuss conditions under which it does. Finally, we also explain how, upon relaxation, we may apply our method to a nonconvex cone. |
| title | Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.11859 |