On the Differentiability of Projected Trajectories and the Robust Convergence of Non-Convex Anti-Windup Gradient Flows

Adrian Hauswirth, Florian Dörfler, Andrew R. TeelIEEE Control. Syst. Lett 2020 · DOI

TL;DR

This paper introduces a novel anti-windup control strategy for systems with input saturation that aims to optimize a non-convex objective function. The authors prove that this strategy guarantees the convergence of the system's trajectory to a "first-order optimal point" of the optimization problem, even when the feasible set is non-convex. This work extends previous results by relaxing assumptions on both the objective function and the feasible set, offering a more general framework for feedback-based optimization.

What Problem Does This Paper Address?

Many real-world systems, particularly in areas like power systems and infrastructure control, involve optimization problems where the control inputs are subject to physical limitations (saturation). When controllers try to optimize a function under these constraints, especially when the function is non-convex, ensuring that the system reliably converges to a good solution can be challenging. Traditional gradient descent methods can struggle with these issues.

This paper focuses on a specific type of controller: "anti-windup gradient flows." These controllers are designed to handle input saturation by incorporating an anti-windup mechanism, which essentially prevents the integrator in the controller from accumulating excessive error when saturated. The authors are interested in understanding the convergence properties of these systems, particularly when the objective function is non-convex and the set of feasible solutions is also non-convex. Previous work had shown convergence under stricter conditions (e.g., convex objective functions and convex feasible sets). This paper aims to relax these assumptions and provide a more general theoretical guarantee.

Methods

The core of the paper's methodology lies in analyzing the behavior of "projected trajectories." A projected trajectory is what you get when you take the output of a controller and "project" it onto the set of feasible inputs. The authors then analyze a specific dynamical system that emulates a projected gradient flow using an anti-windup scheme.

Key techniques include:

  • Anti-Windup Control: The system is augmented with an anti-windup mechanism, which is crucial for handling actuator saturation and preventing integrator windup. This is formulated as a feedback loop involving the system state, the gradient of the objective function, and a term that penalizes the deviation from the feasible set.
  • Prox-Regular Sets: To handle non-convex feasible sets, the authors introduce the concept of "prox-regular sets." These are a generalization of convex sets that still allow for well-behaved projection operators. This is a key theoretical contribution that enables the analysis of non-convex constraints.
  • Directional Derivatives of Projection Maps: A significant portion of the paper is dedicated to studying the properties of the directional derivative of the projection map onto prox-regular sets. This is essential for analyzing the dynamics of the projected trajectories.
  • Invariance Principle: The authors leverage a standard invariance principle for differential inclusions. This principle helps to show that the system's trajectory converges to a specific set, which is then characterized as the set of critical points of the optimization problem.
  • Lyapunov-like Analysis: The paper uses a function related to the objective function and the projection to show that it is non-increasing along the system's trajectories, which is a key step in proving convergence.

What's new is the application of these techniques to the specific anti-windup gradient flow dynamics and the generalization to non-convex prox-regular sets.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Non-Convexity is Tractable: The most significant insight is that robust convergence to "good" solutions (first-order optimal points) is achievable even when the optimization problem involves non-convex objective functions and non-convex feasible sets. This is a substantial generalization of previous results.
  • Prox-Regular Sets as a Generalization: The introduction and use of prox-regular sets provide a powerful mathematical framework for handling non-convex constraints in optimization dynamics. This concept is likely to be useful beyond the scope of this specific paper.
  • Projected Trajectories are Key: The paper highlights the importance of studying "projected trajectories" themselves, not just the underlying continuous dynamics. These projected trajectories, which directly reflect the effect of saturation and projection, are shown to converge to the desired optimal points.
  • Anti-Windup as an Optimization Tool: The work demonstrates that anti-windup controllers, often seen as a way to mitigate performance degradation due to saturation, can also be viewed as a mechanism for implementing feedback-based optimization.

Key Results

  • Semi-Global Convergence: For non-convex feasible sets (prox-regular sets), the paper proves "semi-global" convergence. This means that for any compact set of initial conditions, there exists a threshold for the anti-windup gain (K) above which convergence to a first-order optimal point is guaranteed.
  • Global Convergence for Convex Sets: When the feasible set is convex (a special case of prox-regular sets), the convergence is "global" for any positive anti-windup gain (K > 0).
  • Characterization of Limit Set: The paper rigorously shows that the projected trajectories converge to the set of "critical points" of the optimization problem. For convex problems, this set corresponds to the global minimizers.
  • Properties of Projection Derivatives: As a byproduct, the paper establishes useful properties of the directional derivative of the projection map for prox-regular sets, which could be valuable for other research in this area.

Limitations and Future Work

  • Semi-Global vs. Global Convergence: While the paper achieves semi-global convergence for non-convex sets, global convergence for any K remains an open question for these cases.
  • Dependence on K: The convergence guarantee for non-convex sets depends on choosing K small enough, and this threshold can depend on the specific problem parameters.
  • Future Directions: The authors suggest exploring whether similar analysis techniques can be applied to other optimization dynamics, such as variable-metric gradient methods or saddle-point flows, especially those involving oblique projections. They also point to preliminary results and simulations in related work.

Summary updated

BibTeX
@article{hauswirth2020differentiability,
  author = {Adrian Hauswirth and Florian Dörfler and Andrew R. Teel},
  title = {{On the Differentiability of Projected Trajectories and the Robust Convergence of Non-Convex Anti-Windup Gradient Flows}},
  journal = {IEEE Control. Syst. Lett},
  year = {2020},
  doi = {10.1109/lcsys.2020.2988515},
}
Figure