In the world of optimization, nonconvexity is usually a nightmare. However, a classical result called the Shapley-Folkman theorem offers a glimmer of hope for a specific class of problems: those that are "separable." It suggests that if you have a sum of many small nonconvex functions subject to a few linear constraints, the "duality gap"—the distance between the hard nonconvex problem and its easy convex relaxation—is actually quite small and doesn't grow with the number of functions.
The problem? The Shapley-Folkman theorem is an existence proof. It tells you a good solution exists, but it doesn't tell you how to find it. This paper by Dubois-Taine and d’Aspremont provides a systematic, two-stage algorithmic framework to finally bridge that gap.
TL;DR
This paper introduces a constructive, two-stage approach to solve large-scale nonconvex separable optimization problems with linear constraints. By combining the Frank-Wolfe algorithm with Carathéodory trimming techniques, the authors provide a practical way to find primal solutions that satisfy the tight duality gap bounds predicted by the Shapley-Folkman theorem.
What Problem Does This Paper Address?
The authors focus on separable nonconvex optimization problems of the form: $$\text{minimize } \sum_{i=1}^n f_i(x_i) \quad \text{subject to } \sum_{i=1}^n A_i x_i \le b$$ where $f_i$ are nonconvex functions. These problems appear everywhere, from power plant scheduling (Unit Commitment) to resource allocation and feature selection.
While the Shapley-Folkman (SF) theorem guarantees that the duality gap is bounded by a constant proportional to the number of constraints ($m$) rather than the number of variables ($n$), most existing methods to reach this bound are either non-constructive, randomized, or restricted to specific cases like Mixed-Integer Linear Programs (MILPs). The challenge is to find a "primal" solution (a real setting for $x$) that actually achieves this theoretical near-optimality in a computationally efficient way.
Methods
The authors propose a two-stage "Approximation and Trimming" pipeline:
-
Stage 1: Approximation via Frank-Wolfe The algorithm starts by solving a smooth convex objective designed to approximate the optimal dual value. Crucially, the authors show that the "Linear Minimization Oracle" (the core step of Frank-Wolfe) for this objective is equivalent to computing the Fenchel conjugates of the component functions $f_i$. This makes the first stage highly efficient for any problem where these conjugates are tractable. The output is a large convex combination of many points.
-
Stage 2: Trimming via Carathéodory The solution from Stage 1 is "too complex"—it involves too many points to satisfy the SF bounds. The second stage "trims" this down to a sparse representation using at most $n+m+1$ elements.
-
For smaller problems, they use an Exact Carathéodory algorithm ($O(Np^2)$ complexity).
- For large-scale problems, they use Approximate Carathéodory via the Min-Norm Point (MNP) or Fully-Corrective Frank-Wolfe (FCFW) algorithms, which provide a faster, sparser approximation.
Datasets
The paper evaluates the method on two primary synthetic benchmarks modeled after real-world infrastructure challenges:
- Unit Commitment (UC) Problem: Scheduling $n$ power plants over $N$ time steps to meet electricity demand at minimum cost. The nonconvexity arises from the "on/off" nature of plants and their minimum/maximum capacities.
- Plug-in Electric Vehicle (PEV) Charging: Optimizing the charging schedule for a fleet of $n$ vehicles under network power constraints.
The authors provide the code to reproduce these experiments on GitHub.
Key Insights and Ideas
- The Conjugate Connection: The most elegant insight is that the hard part of the Frank-Wolfe iteration (the LMO) reduces to a simple Fenchel conjugate calculation. If you can compute the conjugate of your nonconvex $f_i$, you can run this algorithm.
- Sparsity Equals Near-Optimality: The "trimming" stage isn't just a post-processing step; it is the mechanism that enforces the Shapley-Folkman bound. By forcing the solution to be represented by only a few points, you ensure that most components of the sum behave "linearly," minimizing the impact of nonconvexity.
- MNP over FCFW: For the trimming stage, the Min-Norm Point algorithm was found to be significantly more efficient than Fully-Corrective Frank-Wolfe as the number of variables $n$ grows, making it the preferred choice for practical applications.
Key Results
- Theoretical Recovery: The method theoretically recovers classical duality gap bounds (like those from Aubin and Ekeland) plus a small error term $O(1/\sqrt{K})$ that decreases with the number of iterations $K$.
- Superior Performance: In numerical tests on the Unit Commitment problem, the algorithm found solutions with duality gaps much smaller than the theoretical worst-case bounds.
- Scalability: The first stage scales linearly with the number of units ($n$), and the second stage (using MNP) handles $n=1000$ efficiently, whereas exact Carathéodory methods become prohibitively slow around $n=200$.
Limitations and Future Work
- Conjugate Tractability: The method's "killer app" status depends on the Fenchel conjugates of $f_i$ being easy to compute. If the component functions are themselves high-dimensional or lack a closed-form conjugate, the LMO becomes a bottleneck.
- Constraint Scaling: While the gap doesn't grow with $n$, it does scale with the number of constraints $m$. For problems with a very high number of global constraints, the duality gap might still be significant.
- Feasibility in Nonconvex Domains: If the domains $X_i$ are nonconvex (like the "on/off" state of a power plant), the trimmed solution might require a "primalization" step to ensure it is strictly feasible. The authors suggest a perturbation approach to handle this, but more automated ways to ensure feasibility remain an area for exploration.
Summary updated