Constrained Optimization via Constraint-Induced Geometry: Implicit Feasible Dynamics and Optimality from Stationarity

Abstract

We introduce Gravidy, a geometry-aware framework for constrained optimization in which constraints are encoded directly into the dynamics, so the motion remains feasible by construction. The geometric mechanism depends on the feasible set: componentwise reparameterizations and induced Hessian geometries for the nonnegative orthant and box constraints, Fisher-Shahshahani and KL geometry for the simplex, and canonical Riemannian geometry for the Stiefel manifold. We derive feasible continuous-time flows and implicit discretizations adapted to each geometry. On the vector domains, the implicit updates admit exact Bregman-proximal interpretations, yielding monotone descent and convergence guarantees for convex objectives, linear contraction under relative strong convexity, and a Kurdyka-Lojasiewicz analysis for nonconvex problems under compact-interiority, decrease, and relative-error assumptions. We also show that convergent trajectories generated from the interior recover the Karush-Kuhn-Tucker conditions on the orthant, simplex, and box. The same holds for convergent implicit sequences generated from the interior when their stepsizes are bounded away from zero. On the Stiefel manifold, stationarity of the canonical Riemannian gradient is equivalent to the usual first-order optimality condition. The algorithms combine large implicit outer steps with problem-adapted Newton, modified Gauss-Newton, Newton-KKT, and Newton-Krylov inner solvers. Numerical experiments on nonnegative, simplex-constrained, box-constrained, and orthogonality-constrained problems show rapid convergence to high accuracy in a small number of outer iterations while preserving feasibility of accepted iterates. A sparse elastic-obstacle experiment further shows that the orthant construction can exploit large structured systems directly. This illustrates their accuracy and ability to exploit sparsity in sparse settings.

Revised and extended version with theoretical clarifications, improved positioning, updated numerical results, and a new sparse elastic-obstacle experiment