A Projection-Free Homeomorphic Lagrangian Method for Optimization with Convex Inequality and General Equality Constraints

Constrained optimization with convex inequality and general equality constraints arises throughout machine learning, power systems, and scientific computing. Classical first-order methods require either expensive projections onto the feasible region or optimization oracles, whereas recent projection-free reparameterization methods focus on problems without equality constraints. We propose **Hom-PALM**, a Homeomorphic Proximal Augmented Lagrangian Method that bridges this gap by reparameterizing inequality constraints onto the unit ball via a homeomorphism while handling equality constraints through an augmented Lagrangian framework in the original domain. This decomposition enables efficient ball-constrained subproblem solving while preserving the structure required for Lagrangian methods. A key challenge is that a naive combination of reparameterization with the Lagrangian framework yields suboptimal rates: each Lagrangian iteration requires solving a subproblem using an accelerated-based method; yet the homeomorphic mapping renders subproblems nonconvex with only hidden convexity, precluding standard accelerated rates. As our main technical contribution, we extend first-order acceleration to the projection-free setting without optimization oracles and integrate it within Hom-PALM, achieving **optimal** convergence rates for convex problems and best-known rates for nonconvex problems. For instance, Hom-PALM attains a rate of $\tilde{\mathcal{O}}({ϵ}^{-3})$ for nonconvex objectives with convex inequality and *nonlinear* equality constraints, matching the best-known complexity but with per-iteration cost of only $\tilde{\mathcal{O}}(n^2)$ without optimization oracles. We validate Hom-PALM on convex QCQP and Stiefel manifold optimization, demonstrating competitive performance.