Duality Gaps in Partially Nonconvex Optimization

[2503.02464] Duality Gaps in Partially Nonconvex Optimization Skip to main content Search Submit Donate Log in Economics > Theoretical Economics arXiv:2503.02464 (econ) [Submitted on 4 Mar 2025 ( v1 ), last revised 24 Aug 2026 (this version, v3)] Title: Duality Gaps in Partially Nonconvex Optimization Authors: Thomas Hübner View PDF HTML (experimental) Abstract: We study duality gaps in separable optimization problems that contain both convex and nonconvex functions. Classical bounds on the duality gap of such partially nonconvex problems depend solely on the nonconvex functions. As a result, a problem with many convex functions has no tighter bound than one with none at all. To understand the impact of convex functions on the duality gap beyond the worst case, we analyze a probabilistic setting in which the convex hulls of the functions' epigraphs are independent and identically distributed. Using the Shapley-Folkman lemma, we derive lower bounds on the distribution of the duality gap that depend on both the number of convex and nonconvex functions. These bounds show that zero or small duality gaps become increasingly likely as convex functions outnumber nonconvex ones. This way, they support the intuition that "nearly convex" problems tend to have smaller duality gaps than "purely nonconvex" ones, an intuition that the classical worst-case bounds do not capture. Finally, we use these results to understand why zero or vanishingly small duality gaps occur so frequently in the welfare maximization problems underlying European electricity auctions, drawing on empirical results spanning 281 days in 2023 across 9 countries. To shed light on the economic reasons behind this, we present alternative proofs that exploit the connection between duality gaps and the existence of Walrasian equilibria. Subjects: Theoretical Economics (econ.TH) MSC classes: 90C46 (Primary) 91B50 (Secondary) Cite as: arXiv:2503.02464 [econ.TH] (or arXiv:2503.02464v3 [econ.TH] for this version) https://doi.org/10.48550/arXiv.2503.02464 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Thomas Hübner [ view email ] [v1] Tue, 4 Mar 2025 10:18:37 UTC (703 KB) [v2] Tue, 5 Aug 2025 16:09:40 UTC (363 KB) [v3] Mon, 24 Aug 2026 16:17:13 UTC (49 KB) Full-text links: Access Paper: View PDF HTML (experimental) TeX Source view license Current browse context: econ.TH < prev | next > new | recent | 2025-03 Change to browse by: econ References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Duality Gaps in Partially Nonconvex Optimization#670324
• On the $Ω(n)$ SDP relaxation gap for Submodular Box-Constrained Quadratic Programming#974624
• Conditional generative models enable targeted exploration of MAX phase design space.#1001027
• Isolation of scalar Allen-Cahn local minimizers#999483
• Effective correlation and decorrelation for newforms, and weak subconvexity for $L$-functions#160804