Abstract
This paper presents a convex sufficient condition for solving a system of nonlinear equations under parametric changes and proposes a sequential convex optimization method for solving robust optimization problems with nonlinear equality constraints. By bounding the nonlinearity with concave envelopes and using Brouwer's fixed point theorem, the sufficient condition is expressed in terms of closed-form convex inequality constraints. We extend the result to provide a convex sufficient condition for feasibility under bounded uncertainty. Using these conditions, a non-convex optimization problem can be solved as a sequence of convex optimization problems, with feasibility and robustness guarantees. We present a detailed analysis of the performance and complexity of the proposed condition. The examples in polynomial optimization and nonlinear network are provided to illustrate the proposed method.
Introduction
In the field of optimization, nonlinear equality constraints are notoriously difficult to manage. Unlike inequality constraints that define volumes, equality constraints define thin, non-convex manifolds. This makes finding feasible solutions challenging, and ensuring "robustness"—where a solution remains valid despite small fluctuations in parameters—nearly impossible with standard tools.
Traditional methods like Sequential Quadratic Programming (SQP) often struggle with inconsistent constraints or divergence when faced with these manifolds. Furthermore, most robust optimization techniques are tailored for inequalities; handling equalities under uncertainty is fundamentally harder because any parameter shift can move the "true" solution off the manifold entirely. This paper introduces Sequential Convex Restriction (SCRS) to bridge this gap, providing a framework that guarantees feasible, robust solutions within a convex neighborhood.
Methodology: The SCRS Framework
The SCRS approach transforms non-convex feasible regions into a sequence of convex "restricted" sets. Unlike convex relaxation, which expands the feasible set and may include invalid points, restriction shrinks the set to ensure every point within it is guaranteed to be feasible for the original nonlinear system.
1. Decomposed Representation and Fixed-Point Transformation
The process begins by breaking down complex nonlinear functions into linear combinations of simpler basis functions. The equality constraints, $f(x, u, w) = 0$, are then rewritten into a fixed-point form: $x = G(x, u, w)$. This transformation allows the application of Brouwer’s Fixed Point Theorem to certify the existence of a solution within a specific set.
2. Concave Envelopes
To achieve convexity, the nonlinearities are bounded using concave envelopes. This involves "sandwiching" curvy functions between a convex over-estimator and a concave under-estimator, as illustrated in the bounding of function $g(z, u)$.
3. Sequential Iteration
The algorithm starts at a nominal point, constructs a convex restricted feasible set around it, and solves an optimization problem within that set. The solution becomes the new nominal point for the next iteration. This process continues until convergence, effectively navigating the non-convex manifold through a series of convex steps.
Key Insights: Sparsity and Robustness
A critical discovery in this research is that the complexity of the convex restriction does not scale with the total number of variables. Instead, it scales with the "degree of sparsity"—the number of variables interacting within a single constraint. This makes SCRS highly scalable for large-scale systems like power grids or sensor networks.
Furthermore, robustness is integrated "for free." By incorporating uncertainty directly into the concave envelopes, the framework handles robust optimization with minimal additional computational overhead. SCRS can be viewed as a sophisticated trust-region method where the region is a "self-mapping polytope" that guarantees solution existence.
Experimental Validation and Results
The theory was validated through several mathematical benchmarks:
- Quadratic Equations: Visualized the projection of non-convex manifolds onto convex restricted spaces.
- Nonlinear Network Flow: Demonstrated the method's efficacy in sparse systems with local variable interactions.
- Polynomial Optimization: Showed that the algorithm asymptotically converges to Karush-Kuhn-Tucker (KKT) points, satisfying standard local optimality requirements.
Results indicate a clear trade-off: using more complex representations reduces conservatism (getting closer to the global optimum) but increases computational requirements. Crucially, unlike SQP, every iteration of SCRS is guaranteed to produce a point feasible for the original nonlinear system.
Conclusion and Future Work
While SCRS is inherently conservative due to the nature of restriction—potentially missing optima in narrow "nooks" of the feasible region—it provides unprecedented guarantees for feasibility and robustness in non-convex settings. Future work aims to apply this framework to the Optimal Power Flow (OPF) problem, where managing nonlinearities and renewable energy uncertainty is a critical real-world challenge.
Summary updated