Publication 26-CNA-015

The Adaptive Variational Dual Method for Nonlinear Nonsquare Algebraic Equations

Amit Acharya
Department of Civil & Environmental Engineering
Center for Nonlinear Analysis
Carnegie Mellon University
Pittsburgh, PA 15213
acharyaamit@cmu.edu

Soummya Kar
Department of Electrical & Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
soummyak@andrew.cmu.edu

N. Sukumar
Department of Civil and Environmental Engineering
University of California
Davis, CA 95616
nsukumar@ucdavis.edu

Abstract: We study the Adaptive Variational Dual (AVD) method as a direct solver for nonlinear nonsquare systems, $G(U)=0,\quad G:\mathbb{R}^n\to\mathbb{R}^m,\quad m\neq n.$ A central question is not whether least-squares optimization is effective as an optimization problem, but whether obtaining critical points of $ \min_{U} \frac{1}{2}\|G(U)\|_2^2$ is a sufficiently reliable way to solve the original equations $G(U) = 0$. Another is to produce a first-order method with a convex variational structure for general systems of nonlinear equations, potentially useful for large systems of equations.

AVD retains the system $G(U) = 0$ as the primary object, introduces a variational dual formulation for it, and uses a sequence of convex optimization problems to solve it. In doing so, it adapts its computational mechanism to the local rectangular geometry through singular-value information. For overdetermined systems, structural dual null directions are removed from the active dual space; for underdetermined systems, primal nonuniqueness is distinguished from weak but genuinely active dual directions. The adaptive AVD scheme combines step-size controlled gradient flow and active-space Newton steps.

We present a series of numerical tests consisting of overdetermined, underdetermined, and square systems to compare the AVD scheme with nonlinear least squares. We show that the AVD method is consistently robust across overdetermined pathologies, unstable saddle selections, nonredundant neural network calibrations, and ill-conditioned systems, while least-squares often fails or terminates at non-root stationary states, operating within the standard protocol of finding critical points of the least squares functional. The numerical results indicate that the AVD method is a competitive candidate for solving nonlinear, nonsquare systems of equations.

Get the paper in its entirety as  26-CNA-015.pdf

---

«   Back to CNA Publications