 Duality Gaps in Partially Nonconvex OptimizationThomas H\"ubner 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. Date: 2025-03, Revised 2026-08 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2503.02464 Access Statistics for this paper More papers in Papers from arXiv.org |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.