The adjoint state method for parametric definable optimization without smoothness or uniqueness

1. Problem Statement

The paper addresses the challenge of computing first-order information (gradients or gradient-like objects) for parametric optimization problems where the objective function and constraints may be non-smooth, and where primal and dual solutions may be non-unique.

The general problem is formulated as:
$$f(\theta) := \inf_{x \in \mathbb{R}^n} \{F(x, \theta) : G(x, \theta) \le 0, H(x, \theta) = 0\}$$
where:

• $\theta \in \mathbb{R}^q$ is the parameter vector.
• $F$ is the objective function (locally Lipschitz, potentially non-smooth).
• $G$ and $H$ are constraint functions (continuously differentiable).
• The value function $f(\theta)$ represents the optimal value for a given parameter.

The Core Difficulty:
Standard approaches to compute $\nabla f(\theta)$ rely on:

1. Differentiating the solution mapping: Assuming the minimizer $x^*(\theta)$ is unique and differentiable, then applying the chain rule. This fails when solutions are non-unique or non-smooth.
2. Implicit differentiation: Applying the Implicit Function Theorem to the KKT conditions. This requires strong regularity assumptions (e.g., strict complementarity, second-order sufficiency) that are often violated in practice (e.g., in machine learning, robust optimization, or control).
3. Subdifferentials: Using Clarke subdifferentials. The paper argues that standard subdifferentials are insufficient because the formal adjoint formula can produce "artifacts" (vectors that do not represent valid variational information) even for smooth problems if uniqueness is not guaranteed.

2. Methodology

The authors propose a rigorous framework based on two structural pillars: Definability and Conservative Calculus.

A. Definability (O-minimal Geometry)

The paper assumes that the functions $F, G, H$ belong to a common o-minimal structure (e.g., they are semialgebraic or definable in a structure allowing exponentials/logarithms).

• Why? Definable functions possess powerful "tame" properties: they have finite topological complexity, satisfy the Kurdyka-Łojasiewicz inequality, and their solution sets behave well under projection. This ensures that pathological behaviors (like infinite oscillations) do not occur, which is crucial for the validity of the adjoint formula.

B. Conservative Fields

Instead of relying on standard gradients or Clarke subdifferentials, the authors utilize conservative fields.

• Definition: A set-valued map $D\phi$ is a conservative field for a locally Lipschitz function $\phi$ if, for any absolutely continuous curve $u(t)$, the chain rule holds almost everywhere:
  $$\frac{d}{dt}\phi(u(t)) = \langle \dot{u}(t), v \rangle \quad \forall v \in D\phi(u(t)).$$
• Significance: Conservative fields generalize gradients. They allow for the selection of specific subgradients that satisfy the chain rule, even when the function is non-smooth or the solution set is multi-valued. This concept is central to modern differentiable programming and algorithmic differentiation (AD).

C. The Adjoint State Method (ASM)

The authors formalize the Adjoint State Method as a procedure to select a conservative field for the value function $f(\theta)$.

1. Solver: Assume access to a "primal-dual solver" that returns a tuple $(x^*, \lambda^*, \mu^*)$ satisfying the KKT conditions (feasibility, complementarity, stationarity) for a given $\theta$. Uniqueness is not required.
2. Adjoint Formula: Compute the vector $u$ using the partial derivative of the Lagrangian with respect to $\theta$:
   $$u = \nabla_\theta F(x^*, \theta) + \text{Jac}_\theta G(x^*, \theta)^T \lambda^* + \text{Jac}_\theta H(x^*, \theta)^T \mu^*$$
3. Key Insight: The set of all possible outputs $u$ generated by all valid primal-dual solutions forms a conservative field for the value function $f$.

3. Key Contributions

1. Generalization of the Adjoint Formula:
   The paper proves that the classical adjoint formula (Equation 1.2) yields a valid conservative field for the value function $f(\theta)$ under the Mangasarian-Fromovitz Constraint Qualification (MFCQ) and definability assumptions. This holds even if:

   • The objective $F$ is non-smooth.
   • The primal solution $x^*$ is non-unique.
   • The dual solution (Lagrange multipliers) is non-unique.

2. Necessity of Definability:
   The authors demonstrate that the definability assumption is sharp. They construct a counter-example (Claim 4.8) involving a fractal-like set where $F$ is locally Lipschitz, path-differentiable, and smooth almost everywhere, yet the adjoint formula fails to produce a conservative field if the definability condition is dropped. This justifies the restriction to o-minimal structures.

3. Resolution of "Artifacts":
   In non-unique settings, the adjoint formula can produce vectors that are not subgradients (artifacts). The paper shows that while individual outputs might be artifacts, the set of all outputs forms a conservative field. This means the method provides a valid oracle for first-order optimization algorithms (like gradient descent) with theoretical convergence guarantees, unlike standard subdifferential approaches which might be too loose or incorrect.

4. Computational Efficiency:
   The method is shown to be computationally efficient.

   • Cost: $Cost(ASM) \le Cost(\text{solver}) + \omega \cdot Cost(L)$.
   • Since most modern solvers (e.g., IPOPT, SNOPT) compute dual variables internally, obtaining the adjoint vector requires negligible additional cost compared to the primal solve.
   • It avoids the expensive computation of the Jacobian of the solution mapping required by implicit differentiation or automatic differentiation through the solver.

4. Main Results

• Theorem 2.4 (Smooth Case): If $F, G, H$ are semialgebraic and MFCQ holds, the ASM output is a selection of a conservative field for $f$.
• Theorem 4.6 (General Non-Smooth Case): For locally Lipschitz definable $F$ with a conservative field $DF$, the set-valued map $Df$ defined by the adjoint formula is a conservative field for the value function $f$.
• Inclusion Property: The Clarke subdifferential of the value function is contained within the convex hull of the adjoint outputs ($\partial_c f(\theta) \subseteq \text{conv}(Df(\theta))$), but the adjoint set is often tighter and more informative than the Clarke subdifferential in non-unique settings.

5. Significance and Applications

• Machine Learning & Deep Learning: Many modern architectures (e.g., Neural ODEs, hyperparameter tuning, meta-learning) involve nested optimization layers where solutions are non-unique and non-smooth. This paper provides the theoretical justification for using backpropagation (via adjoint methods) through these layers without requiring strict uniqueness assumptions.
• Engineering & Control: Applications in robust optimization, optimal design, and uncertainty quantification often involve non-convex or non-smooth constraints. The method allows for gradient-based optimization in these complex settings.
• Theoretical Foundation: It bridges the gap between variational analysis (nonsmooth optimization) and algorithmic differentiation. It clarifies that "differentiability" in the context of optimization solvers should be understood through the lens of conservative fields rather than classical differentiability or subdifferentials.
• Practical Implementation: The work suggests that existing primal-dual solvers can be directly coupled with the adjoint formula to create robust, first-order optimization pipelines for a wide class of difficult problems, leveraging the "cheap gradient principle" of automatic differentiation.

In summary, this paper establishes that the adjoint state method is not just a heuristic for smooth, unique problems, but a mathematically rigorous tool for a broad class of non-smooth, non-unique, parametric optimization problems, provided the underlying functions are definable.