A successive difference-of-convex method for a class of two-stage nonconvex nonsmooth stochastic conic program via SVI

This paper proposes a successive difference-of-convex method that leverages Moreau envelopes and the progressive hedging algorithm to solve a class of challenging two-stage nonconvex nonsmooth stochastic conic programs by reformulating them as nonmonotone nonsmooth stochastic variational inequalities, with theoretical convergence guarantees and numerical validation via an extended Markowitz model.

The Gist

Imagine you are the captain of a massive ship trying to navigate through a stormy ocean. You have to make a decision right now (the "First Stage") about your course, but you know the weather is unpredictable. You can't see the future, but you have a weather forecast that suggests several possible storm scenarios (Scenario A, Scenario B, Scenario C, etc.).

Once the storm actually hits (the "Second Stage"), you will have to make adjustments based on what actually happened. Your goal is to pick a starting course that minimizes your total risk and fuel cost, considering all possible storms you might face.

This is the core of a Two-Stage Stochastic Program.

Now, imagine this problem gets even harder:

1. The map is broken: The rules for navigating aren't smooth lines; they have jagged cliffs and sudden drops (Non-smooth).
2. The ocean is weird: The water doesn't flow in simple curves; it has complex, twisted currents (Non-convex).
3. The rules are strict: You must stay within specific invisible cones (Conic constraints), like staying inside a specific channel.

This is the Two-Stage Nonconvex Nonsmooth Stochastic Conic Program that the paper tackles. It's a nightmare for standard math solvers because they usually get stuck on the jagged cliffs or confused by the twisted currents.

The Paper's Solution: The "SDC-PHM" Method

The authors, Chao Zhang and Di Wang, propose a clever new way to solve this mess. They call it the Successive Difference-of-Convex (SDC) method, combined with a technique called Progressive Hedging (PHM).

Here is how it works, using simple analogies:

1. The "Smoothie" Trick (Moreau Envelope)

The problem has "jagged" parts (nonsmooth terms) that are hard to calculate. Imagine trying to roll a boulder over a field of sharp rocks. It's impossible.

• The Fix: The authors use a mathematical tool called the Moreau Envelope. Think of this as pouring a thick layer of soft foam over the sharp rocks. The rocks are still there underneath, but the surface is now smooth enough to roll a ball over.
• The Catch: The foam makes the path slightly different from the original. So, they don't just do it once. They do it repeatedly, making the foam layer thinner and thinner (approaching zero) with each step. This is the "Successive" part.

2. The "Unfolding" Trick (Difference-of-Convex)

Even with the foam, the path is still tricky because it's "non-convex" (it has hills and valleys that might trap you).

• The Fix: They realize that any tricky, wiggly path can be thought of as the difference between two simple, smooth paths (one going up, one going down).
• The Strategy: In each step, they approximate the tricky path by straightening out one of the simple paths and adding a little "brake" (regularization) to keep the solution from jumping around too wildly. This turns the impossible problem into a simple, convex one that standard computers can solve easily.

3. The "Team Huddle" (Progressive Hedging)

You have thousands of possible storm scenarios (scenarios). Solving for all of them at once is like trying to solve a giant puzzle with 10,000 pieces all at once.

• The Fix: They use Progressive Hedging. Imagine a team of 10,000 people, each holding a piece of the puzzle representing one storm scenario.
  • Everyone solves their own piece independently (parallel processing).
  • Then, they all meet in the middle (a "huddle") to compare notes.
  • If Person A's piece doesn't fit with Person B's, they adjust their pieces slightly to agree.
  • They repeat this "solve and huddle" cycle until everyone's pieces fit together perfectly.

Why is this paper a big deal?

1. It handles the "Impossible": Previous methods could only solve smooth, simple problems. This method can handle the jagged, broken, and twisted problems that appear in real life (like financial portfolios with strict rules).
2. It's a "KKT" Hunter: In math, a KKT point is like finding the "Golden Spot" where all the rules and goals are perfectly balanced. The authors prove that their method doesn't just find a solution; it finds this Golden Spot, even in these messy, non-smooth environments.
3. Real-World Test: They tested this on a Stock Market Portfolio problem (an extension of the famous Markowitz model).
   • The Goal: Invest money to get the best return with the least risk, but also try to own as few different stocks as possible (to save on fees). This "fewest stocks" rule is the "jagged" part.
   • The Result: Their method found a portfolio with very few stocks (highly efficient) and did it faster than standard methods, even though the problem was mathematically harder!

The Bottom Line

The authors built a new mathematical "Swiss Army Knife." It takes a problem that is too messy for standard tools, smooths out the rough edges temporarily, breaks the problem into smaller pieces that a team can solve together, and then refines the solution until it's perfect.

They proved it works mathematically and showed it works in practice, helping investors make better decisions in a chaotic, uncertain world.

Technical Summary

Here is a detailed technical summary of the paper "A successive difference-of-convex method for a class of two-stage nonconvex nonsmooth stochastic conic program via SVI" by Chao Zhang and Di Wang.

1. Problem Statement

The paper addresses a class of Two-Stage Nonconvex Nonsmooth Stochastic Conic Programs (T-NNS-SCP). This problem formulation is designed to model complex decision-making under uncertainty where:

• Two-Stage Structure: Decisions are made in two stages: "here-and-now" (first-stage) before uncertainty is realized, and "wait-and-see" (second-stage) after uncertainty is resolved.
• Nonconvexity and Nonsmoothness: Both the first-stage and second-stage objective functions contain nonsmooth terms (e.g., sparsity-inducing penalties like $\ell_0$-norm or non-Lipschitz functions) that are composed with affine mappings. These terms can be nonconvex and even discontinuous.
• Conic Constraints: The problem includes constraints defined by symmetric closed convex cones (e.g., second-order cones, nonnegative cones, positive semidefinite cones).
• Scale: The problem involves a potentially large number of scenarios ($K$), making direct solution methods computationally prohibitive.

The general form is:
$$\min_{x} c(x) + r_1(x) + \sum_{i=1}^K p_i [\vartheta(x, \xi_i)]$$
subject to conic constraints, where $\vartheta(x, \xi_i)$ is the optimal value of a second-stage problem containing similar nonsmooth and nonconvex terms.

2. Methodology

The authors propose a Successive Difference-of-Convex (SDC) method combined with the Progressive Hedging Method (PHM), referred to as SDC-PHM. The methodology proceeds through the following steps:

A. Reformulation via Stochastic Variational Inequality (SVI)

Instead of solving the optimization problem directly, the authors first define a KKT point for the T-NNS-SCP. Under mild conditions (Robinson Constraint Qualification), they prove that a KKT point is a necessary optimality condition. They then transform the KKT conditions into an equivalent nonmonotone nonsmooth two-stage Stochastic Variational Inequality (SVI).

B. Successive Difference-of-Convex (SDC) Approximation

To handle the nonconvex and nonsmooth terms, the authors employ the Moreau envelope:

1. Smoothing: The nonsmooth terms are approximated by their Moreau envelopes, which are smooth but still nonconvex.
2. DC Decomposition: The Moreau envelope is expressed as a Difference-of-Convex (DC) function: $P_{0,\rho}(w) = \frac{1}{2\rho}\|w\|^2 - D_{\rho, P_0}(w)$.
3. Linearization: In each iteration, the convex part of the DC decomposition is linearized around the current iterate, and a quadratic regularization term is added.
4. Resulting Subproblem: This process transforms the original difficult problem into a sequence of smooth, convex two-stage Stochastic Programs.

C. Solving Subproblems via Progressive Hedging (PHM)

The linearized subproblems are equivalent to maximal monotone two-stage SVIs. These are solved approximately using the Progressive Hedging Method (PHM).

• PHM is a decomposition method that handles the block-angular structure of the two-stage problem efficiently by solving subproblems for each scenario in parallel.
• The authors establish rigorous stopping criteria for the inner PHM loop to ensure the overall SDC algorithm converges.

3. Key Contributions

1. Novel Problem Class: The paper introduces and formalizes the T-NNS-SCP model, which generalizes existing models by allowing nonconvex, nonsmooth, and non-Lipschitz regularizers in both stages, alongside general conic constraints.
2. Theoretical Framework (KKT & SVI):
   • Defines a KKT point for this specific class of problems and proves it is a necessary optimality condition under mild assumptions (Basic Qualification and RCQ).
   • Establishes an equivalence between the KKT conditions and a nonmonotone nonsmooth two-stage SVI.
3. Algorithm Design (SDC-PHM):
   • Proposes a novel algorithm that combines SDC (for handling nonconvexity/nonsmoothness via Moreau envelopes) and PHM (for handling the two-stage stochastic structure).
   • Proves that the generated sequence has accumulation points, and any accumulation point is a KKT point of the original problem.
4. Convergence Analysis: Provides rigorous convergence proofs under assumptions regarding the boundedness of the objective functions and the existence of Slater points.
5. Extension to Portfolio Optimization: Demonstrates the practical applicability by extending the Markowitz mean-variance model to include $\ell_0$-norm sparsity constraints and second-order cone (SOC) constraints.

4. Numerical Results

The authors tested the SDC-PHM method on a two-stage extension of the Markowitz portfolio selection model with 40 assets and varying scenario sizes ($K = 1000, 3000, 5000$). They compared four models:

• Model A: Proposed model (Nonconvex, Nonsmooth $\ell_0$, SOC constraints).
• Model B: Nonconvex, Nonsmooth $\ell_0$, No SOC constraints.
• Model C: Convex, No $\ell_0$, with SOC constraints.
• Model D: Convex, No $\ell_0$, No SOC constraints.

Key Findings:

• Sparsity: Models A and B (with $\ell_0$) successfully produced sparse portfolios (average ~14 non-zero assets) compared to Models C and D (24–32 non-zero assets).
• Constraint Satisfaction: The inclusion of SOC constraints (Model A vs. B) effectively limited the deviation between first and second-stage decisions, keeping the SOC metric within bounds.
• Computational Efficiency: Surprisingly, the SDC-PHM for the nonconvex/discontinuous Models A and B converged faster (in terms of CPU time and iterations) than the standard PHM used for the convex Models C and D.
  • Reason: The $\ell_0$-regularization term induces rapid sparsity, causing the cardinality of the decision vector to drop quickly. This leads to faster reduction in the objective value and faster convergence of the algorithm.
• Accuracy: The method achieved low KKT residuals and feasibility errors, confirming the quality of the approximate solutions.

5. Significance

• Bridging Theory and Practice: The paper provides a robust theoretical foundation for solving a class of stochastic programs that were previously considered too difficult due to the combination of nonconvexity, nonsmoothness, and conic constraints.
• Overcoming PHM Limitations: While PHM is traditionally restricted to convex problems, this work extends its applicability to general nonconvex two-stage problems via the SDC framework.
• Efficiency: The results challenge the intuition that nonconvex problems are always harder to solve than convex ones in this context, showing that specific structures (like sparsity-inducing penalties) can accelerate convergence.
• Application: The successful application to a sparse portfolio optimization model demonstrates the method's utility in financial engineering and risk management, where sparsity and robustness (via conic constraints) are critical.

In summary, this paper presents a mathematically rigorous and computationally effective approach for a broad class of complex stochastic optimization problems, offering a new tool for handling nonconvexity and nonsmoothness in two-stage decision-making under uncertainty.