Session IV — Inverse Problems and Optimization

Monday, October 26 · 2:00–3:30 p.m.
Ballroom B
Chair: Chrysoula Tsogka

Hybrid Subspace Levenberg-Marquardt Method in Large Scale Nonlinear Least Square Problem

Minh Duc Hoang · UC Davis

The Levenberg-Marquardt (LM) algorithm is widely used for nonlinear least-squares problems, but its computational cost can be prohibitive for large-scale inverse problems. At the same time, many inverse problems are effectively low-dimensional, with only a few directions in parameter space strongly informed by the data. In this talk, I present an adaptive hybrid subspace LM (HSLM) method that exploits this structure by building a compact subspace from complementary directions that capture different features of the problem. A deterministic adequacy monitor expands the subspace only when needed to ensure that it contains sufficient descent information. This allows HSLM to reduce computational cost while preserving the key convergence properties of LM-type methods. I will also present numerical experiments on neural network training showing that HSLM scales more efficiently with problem size than the LM and the Krylov-subspace LM while achieving comparable convergence behavior.

Mathematical Modeling and Optimization of Active Acoustic Masking

Hong Zhou · Naval Postgraduate School

We develop mathematical and computational methods for modeling and optimizing active acoustic masking in three-dimensional environments. The objective is to reduce the detectability of an acoustic source within specified sensor regions by exploiting interference between the source and strategically designed secondary acoustic fields. The framework considers both self-masking and masking produced by optimized secondary sources. We formulate the masking problem as an optimization problem subject to acoustic propagation constraints and investigate numerical methods for identifying effective interference configurations. Numerical examples demonstrate how source and sensor geometry, propagation characteristics, and source placement affect masking performance. Applications include undersea stealth, acoustic signature management, and secure underwater communications.

Curvature batching gives single-exponential integer quadratic programming

Robert Hildebrand · Virginia Tech

Integer quadratic programming (IQP), min{x^TQx+c^Tx : Ax≤b, x∈Z^n}, was only recently shown to lie in NP, and Lokshtanov's FPT algorithm in n and the largest coefficient L gives no explicit running time. We give the first single-exponential algorithm for IQP, running in (nL)^{O(n²)}·poly(φ), with sharper bounds for structured matrices such as totally unimodular A. The key is curvature batching: we classify kernel directions by the sign of their quadratic curvature, and when no negative-curvature direction exists, all gradient constraints can be imposed in a single batch, replacing the determinant squarings of sequential branching with one polynomial inflation and leaving an ILP. We extend this to MIQP with q continuous variables in (nL)^{O(n²(q+1))}·poly(φ), with no convexity assumption on the continuous block, and decide unboundedness in (m+n)^{O(n)}·poly(φ), independent of coefficient magnitudes.

Parametric Cut Generation for MILPs

Acadia Larsen · UC Davis

The tasks of cut selection and generation are important subproblems of branch and cut algorithms for solving mixed integer linear programs. In SCIP, an open-source MILP solver, these subproblems are treated as separate tasks. Gomory's Mixed Integer cuts, an effective family of cuts in practice, can be recognized as intersection cuts generated from a cut generating function. We introduce parametricCutGeneration, an open-source Python package for generating one row intersection cuts generated by parameterized cut generating functions for SCIP via PySCIPOpt. parametricCutGeneration combines the tasks of cut selection and generation by solving optimization problems over a space of parameterized cut generating functions. To define optimization problems over a space of parameterized cut generating functions, we explore combinatorial and geometric properties of the space. An initial report of attempts at parametric cut generation over problems from MIPLIB 2017.

The Global Topology of Orthogonally Decomposable Tensor Landscapes

Chunyin Siu · Stanford University

The homogeneous form associated with a symmetric tensor, restricted to the sphere, is the objective of the best rank-one approximation problem and, with random coefficients, the energy of a mean-field spin glass. Its critical points have been studied extensively, but the global organization of the landscape they form is far less understood. We study this global structure for positive orthogonally decomposable tensors. Exploiting the fact that the gradient flow decouples across coordinates, we determine the persistent homology of the sublevel and superlevel filtrations in closed form, for every homological dimension q, every ambient dimension D and every tensor order k, via a recurrence in the ambient dimension. Taking the coefficients to be random, we further prove laws of large numbers for the resulting persistence diagrams, describing the typical global topology of a spin-glass-like energy landscape. We illustrate our results with numerical computations and simulations.