Metraipolis › archive › dc_3da92c8bf8ab

Discrete Potential Optimization for Absolute Value Equations: A Sign-Flip Framework with Polynomial Complexity — arXiv:2609.12763

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12763
License (as archived)
CC0-1.0
Archived
2026-10-16T03:44:24.455Z
SHA-256 of the archived text
ffc11d0302772a0c93db0c107388591f55d6b4b9dd6f93f4f765153833212311
Stable URL of this page
https://metraipolis.com/documento/dc_3da92c8bf8ab

How to cite

Discrete Potential Optimization for Absolute Value Equations: A Sign-Flip Framework with Polynomial Complexity — arXiv:2609.12763 — arXiv (en), https://arxiv.org/abs/2609.12763 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3da92c8bf8ab (Metraipolis archive dc_3da92c8bf8ab, sha256 ffc11d0302772a0c93db0c107388591f55d6b4b9dd6f93f4f765153833212311)
BibTeX
@misc{dc3da92c8bf8ab,
  title = {Discrete Potential Optimization for Absolute Value Equations: A Sign-Flip Framework with Polynomial Complexity — arXiv:2609.12763},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12763},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3da92c8bf8ab; sha256 ffc11d0302772a0c93db0c107388591f55d6b4b9dd6f93f4f765153833212311},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12763. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Solving the AVE $Ax - |x| = b$ is generally NP-hard. Existing approaches mostly operate in continuous variable spaces, with the notable exception of Rohn's sign-accord algorithm, which incurs an exponential worst-case bound of $2^n$ iterations. To overcome this bottleneck, we develop a discrete potential optimization (DPO) framework over the sign-vector set $\{-1, 1\}^n$. Under the $1$-norm condition $\|A^{-1}\|_1 < 1/2$, we establish that the AVE solution corresponds exactly to the global maximizer of this discrete potential function. When $\|A^{-1}\|_1$ is uniformly upper bounded by $1/2$, for rational inputs with maximum magnitude $L$, we develop a unified polynomial-time framework for sign-flip algorithms, which excludes Rohn's sign-accord algorithm. Within this framework, specific single-flip mechanisms (including our new steepest and Gauss-Southwell rules) terminate in $\mathcal{O}(n^2\log(nL))$ iterations, while full-flip updates (equivalent to the classical GNM) require only $\mathcal{O}(n\log(nL))$ iterations. We further relax the assumption by requiring that the spectral radius $\rho(|A^{-1}|)$ be uniformly upper bounded by $1/2$ via rational diagonal scaling. Moreover, a uniformly randomized $m$-flip approach is proven to achieve an expected iteration bound of $\mathcal{O}\bigl(n^3 \log(nL)/m\bigr)$ without requiring explicit diagonal preconditioning. As a corollary, GNM solves the AVE in $\mathcal{O}(n^2 \log(nL))$ iterations, improving on the prior result of finite termination under the stricter condition that $\rho(|A^{-1}|)$ is less than~$1/3$. Crucially, by equivalently reformulating linear complementarity problems (LCPs) as AVEs, we extend this DPO framework to yield GNM and pivot-type methods with polynomial iteration complexity for LCPs. Numerical experiments validate the practical efficiency of GNM and the structural robustness of the proposed sign-flip approaches.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.12763 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:15:38.814Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).