On Squared-Variable Formulations
SIAM Journal on Optimization · 31.12.2025 · 35 (4) · 2265-2293
DOI: 10.1137/23m1608343 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 10.10.2025. Verfasst von Lijun Ding und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 34 Literaturangaben.
Abstract (Originalsprache)
We revisit a formulation technique for inequality constrained optimization problems that has been known for decades: the substitution of squared variables for nonnegative variables. Using this technique, inequality constraints are converted to equality constraints via the introduction of a squared-slack variable. Such formulations have the superficial advantage that inequality constraints can be dispensed with altogether. But there are clear disadvantages, not least being that first-order optimal points for the squared-variable reformulation may not correspond to first-order optimal points for the original problem because the Lagrange multipliers may have the wrong sign. Extending previous results, this paper shows that points satisfying approximate second-order optimality conditions for the squared-variable reformulation also, under certain conditions, satisfy approximate second-order optimality conditions for the original formulation and vice versa. Such results allow us to adapt complexity analysis of methods for equality constrained optimization to account for inequality constraints. On the algorithmic side, we examine squared-variable formulations for several interesting problem classes, including bound-constrained quadratic programming, linear programming, and nonnegative matrix factorization. We show that algorithms built on these formulations are surprisingly competitive with standard methods. For linear programming, we also examine the relationship between the squared-variable approach and primal-dual interior-point methods.
Zitieren
APA
Ding, L., & Wright, S. J. (2025). On Squared-Variable Formulations. SIAM Journal on Optimization, 35(4), 2265-2293. https://doi.org/10.1137/23m1608343
Vancouver
Ding L, Wright SJ. On Squared-Variable Formulations. SIAM Journal on Optimization. 2025;35(4):2265-2293. doi:10.1137/23m1608343
BibTeX
@article{Ding2025,
author = {Ding, Lijun and Wright, Stephen J.},
title = {On Squared-Variable Formulations},
journal = {SIAM Journal on Optimization},
year = {2025},
volume = {35},
number = {4},
pages = {2265--2293},
doi = {10.1137/23m1608343}
}
EUVIMED