Certifying Infeasibility in Iterative Optimization

53 concepts28 papers

Most optimization algorithms are designed under an optimistic assumption: a feasible solution exists, and the goal is simply to find it. But what happens when constraints contradict one another? In safety-critical applications like model predictive control, robotics, or automated decision-making, knowing that a problem is impossible to solve is just as vital as finding an optimal point.

Historically, first-order optimization methods and splitting algorithms had a notorious blind spot when dealing with impossible tasks. When faced with an infeasible problem, they would typically loop indefinitely, hit arbitrary iteration limits, or return vague numerical errors. This left practitioners in the dark, unable to distinguish between a slow-to-converge problem and a fundamentally impossible one.

Modern optimization research has shifted this paradigm by answering a core question: How can an algorithm turn its own failure to converge into a rigorous mathematical proof of infeasibility? Instead of treating non-convergence as a dead end, modern frameworks exploit the structured geometry of an algorithm's divergence to generate formal "certificates" of infeasibility.

The Geometry of Divergence: Infimal Displacement

To understand how an iterative algorithm can prove a problem is impossible, consider operator splitting methods like Douglas-Rachford splitting or the Alternating Direction Method of Multipliers (ADMM). These algorithms operate by iteratively projecting points between different constraint sets. If the sets intersect, the iterates converge to a shared, feasible point.

If the sets do not intersect—a state known as strong infeasibility—the iterates are forced to wander. Crucially, they do not wander randomly. As demonstrated by Ryu et al., when a problem is strictly infeasible, the difference between consecutive iterates begins to align along a highly predictable, fixed direction known as the infimal displacement vector. This vector geometrically represents the shortest mathematical bridge between the non-intersecting constraint sets.

  Set A [   ]  <--- Infimal Displacement Vector --->  [   ] Set B

By tracking this fixed-point residual and normalizing the iterates, solvers can intercept this asymptotic behavior. As Banjac et al. show, the differences between consecutive steps in splitting algorithms converge cleanly to this vector, which functions as a formal certificate of infeasibility. This geometric regularity allows solvers like OSQP, developed by Banjac et al., to harvest mathematical proofs of primal and dual infeasibility directly from their own standard iterations without requiring separate diagnostic routines. A similar strategy is used by Ramdas et al. in primal-dual kernel spaces, where the algorithm simultaneously hunts for a separating hyperplane and a dual "witness" of non-separability.

Homogeneous Embeddings: Turning Infeasibility into Feasibility

An alternative, equally powerful intuition relies on a clever algebraic transformation: if an infeasible problem is difficult to diagnose, can we embed it into a larger problem that is guaranteed to be feasible?

This is the mechanism behind homogeneous self-dual embeddings. As explained by Raghunathan in the context of quadratic programming, we can introduce a single auxiliary variable, let's call it $\tau$, to scale the original constraints and objectives. This expands the problem by one dimension, creating a new, homogeneous system that always possesses a valid solution.

The magic of this approach lies in how the auxiliary variable behaves at the optimal solution of the transformed problem:

  • If $\tau > 0$: The auxiliary variable acts as a green light. The original problem is feasible, and its true solution can be recovered by scaling the embedded solution back down.
  • If $\tau = 0$: The auxiliary variable acts as a red light. It provides a clean mathematical certificate—often leveraging classical theorems like Farkas' Lemma, as discussed by Lai et al.—proving that the original constraints are fundamentally irreconcilable.

By utilizing this embedding, modular interior-point solvers like the one proposed by Tanneau et al. can handle unbounded or impossible problems gracefully, ensuring the solver terminates with a definitive proof rather than an uninformative numerical crash.

Acceleration and the Frontier of Weak Infeasibility

While detecting infeasibility via iterate divergence is reliable, waiting for iterates to diverge toward infinity can be computationally expensive. To mitigate this, researchers have integrated sequence acceleration techniques directly into the detection process.

For example, Fu et al. apply Anderson Acceleration to proximal splitting methods, showing that it dramatically speeds up both the discovery of a valid solution and the generation of an infeasibility certificate. In a similar vein, Yu et al. demonstrate that incorporating extrapolation steps into projected gradient methods allows solvers to automatically flag primal and dual infeasibility in conic optimization without relying on costly matrix inversions.

Despite these advances, a major theoretical and practical challenge remains: weak infeasibility. This occurs when the distance between two constraint sets is exactly zero, yet their intersection is still empty (for instance, a hyperbola approaching but never touching its asymptote).

In these pathological scenarios, the iterate differences that normally form the infimal displacement vector vanish to zero. As highlighted by both Banjac et al. and Park et al., weak infeasibility effectively blinds standard certificate-generating mechanisms. When a problem is weakly infeasible, algorithms can mistake the vanishing residuals for successful convergence, making the robust detection and certification of these boundary cases one of the most active frontiers in modern optimization theory.

Key Foundational Work

Measures and LMI for impulsive optimal control with applications to space rendezvous problems (2012) — contributed 1 concept elements to this direction.
A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_infeasibility_detection_98ee7ce5,
  title = {infeasibility detection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infeasibility-detection/rdr_98ee7ce56fe94bfabb202d51103ed496},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_infeasibility_detection_98ee7ce5_v1,
  title = {infeasibility detection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infeasibility-detection/rdr_98ee7ce56fe94bfabb202d51103ed496/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake