CS Paper Radar

Convex Reformulation of Minkowski-Sum Outer Approximation for Matrix Ellipsoids in Data-Driven Control

Taira Kaminaga, Hampei Sasahara

eess.SY math.OC ·submitted 2026-11-02 05:27 UTC · v1

Abstract

Approximating Minkowski sums of matrix ellipsoids by a single matrix ellipsoid provides a tractable description of noise bounds for controller design from noisy data. Existing linear matrix inequality (LMI) conditions can be used to compute such approximations, but directly solving the resulting optimization problems can be computationally expensive. This paper develops an efficient method for finding a minimum-volume outer matrix ellipsoid under these LMI conditions. Although the corresponding problem for ordinary vector-valued ellipsoids is convex, the objective function in the matrix-valued case is nonconvex. We find that the problem admits an equivalent convex reformulation, which resolves this difficulty. We first eliminate the matrix variables using equivalent LMI transformations and objective monotonicity, leaving one positive scalar variable per matrix ellipsoid in the sum. We then show that the objective becomes convex after a logarithmic change of variables. The resulting problem contains neither LMI constraints nor matrix variables and can therefore be solved efficiently. Numerical experiments confirm that the proposed method is substantially faster than the LMI-based method. An application to data-driven control further illustrates the tradeoff between guaranteed control performance and computation time.

Comment
8 pages, 6 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Lifted Hessian-Riemannian Gradient Flow for LQR Synthesis under Passivity Constraints

eess.SY math.OC ·2026-11-16 ·Armin Gießler, Sören Hohmann
theory similarity 0.63
Abstract

The static state-feedback gain that renders a linear system passive at an external port and minimizes a linear quadratic regulator (LQR) cost cannot be computed by convex optimization, since the passivity certificate and the LQR cost are coupled bilinearly through the common gain. A previous indirect approach restricts the gain to a convex inner approximation of the passivity region, which is conservative and whose construction scales exponentially with the number of gain entries. This paper proposes a direct approach. The set of strictly passivating gains is the image of a convex lifted set of inverse storage matrices and transformed gains. We describe this set by a strict linear matrix inequality and an affine equality for every feedthrough matrix with positive semidefinite symmetric part, including feedthrough matrices with a singular symmetric part, and minimize the LQR cost over it by a gradient flow whose metric is the Hessian of a logarithmic barrier. For multi-input systems, this Hessian is singular along gain changes that preserve the storage function, and we complete the metric along these directions by the metric of the gain space. We prove that the flow exists for all times, that every gain along the flow is strictly passivating with an explicit storage function, and that the cost decreases monotonically while the gains remain in a compact set of stabilizing gains. Numerical examples show that the flow attains a lower cost than the indirect approach, that the completion is required for multi-input systems, and that the flow can converge to a local minimizer on nonconvex passivity regions.

0.28

Globally Certified Invariant-Ellipsoid Control from Data

eess.SY ·2026-09-30 ·Ngoc Tuan Dinh, Egor Dogadin, Alexey Peregudin
theory similarity 0.63
Abstract · 6 pages, 2 figures. Submitted jointly to IEEE Control Systems Letters (L-CSS) and the American Control Conference (ACC)

This letter develops a data-based method for designing state feedback for a discrete-time linear system under bounded disturbances. For each admissible feedback gain and scalar design parameter, a Lyapunov equation determines an invariant ellipsoid: a region that the state cannot leave under the permitted disturbances. We optimise the gain and parameter to minimise a trace-based measure of the resulting output enclosure. At each parameter value, value iteration gives a lower cost bound, while separate controller evaluation gives an achievable upper bound. These bounds also let us assess whole parameter intervals without evaluating every point. We prove that the search stops after finitely many evaluations with a stabilising state-feedback gain whose objective is within any prescribed absolute tolerance of the infimum over the chosen ellipsoid family. Neither an initially stabilising gain nor attainment of the infimum is assumed. The guarantee assumes exact arithmetic and a sufficiently informative batch of exact measurements, including disturbances during data collection; the resulting feedback uses only the state. A position--velocity example illustrates the bounds, controller checks, and computational cost.

0.32

A Controllability Gramain Shaping with LMI Constraints under Bures--Wasserstein Distance

eess.SY math.OC ·2026-08-20 ·Koju Nishimoto, Yuki Onishi, Riku Funada, Mitsuji Sampei
published similarity 0.58
Abstract · 8 pages, 4 figures. Accepted for presentation at the 65th IEEE Conference on Decision and Control (CDC 2026), Honolulu, HI, USA,December 15-…

This paper proposes a controller design method for shaping the controllability Gramian into a desired form to design the effect from exogenous inputs to the system state. Using the Bures--Wasserstein distance, we formulate the shaping problem as the minimization of the distance between the system Gramian and a desired Gramian, and the objective function is shown to be strictly convex on the set of symmetric positive definite matrices. In addition, by deriving a semidefinite programming formulation via a linear matrix inequality (LMI), computational efficiency is improved and additional LMI constraints can be incorporated. When the exogenous input is modeled as Gaussian white noise, the proposed framework is closely related to $H_2$ control, which can be interpreted as a special case of optimal transport. Numerical examples demonstrate anisotropic controllability design for a guidance robot and verify the ability to impose additional directional constraints through LMIs. The numerical examples also confirm that the proposed method approaches $H_2$ control as the desired Gramian tends to zero.

0.34

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.58
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

Optimal input design via Frank-Wolfe

eess.SY math.OC ·2026-09-08 ·Fethi Bencherki, Bruce Lee, Nikolai Matni, Anders Rantzer
similarity 0.58
Abstract · 7 pages, 4 figures

We study optimal input design over a finite horizon for linear dynamical systems. The goal is to minimize a weighted inverse-covariance (information) criterion subject to an energy budget. The set of covariances achievable by causal policies is convex but lacks a tractable explicit description, ruling out projection-based methods. We show that Frank--Wolfe applies naturally: each linear minimization subproblem is a budget-constrained finite-horizon linear quadratic (LQ) problem, solvable by a Riccati recursion and one-dimensional bisection over a Lagrange multiplier. Using smoothness of the objective over the feasible set, we establish an $\mathcal{O}(1/M)$ convergence rate for the objective value, while strong convexity yields an $\mathcal{O}(1/\sqrt{M})$ rate for the iterates. We further extend the framework to input design for system identification with unknown dynamics and adaptive online LQR, and illustrate the approach numerically.

0.28

Improved Leverage Score Sampling for Constrained Active Linear Regression

cs.LG stat.MLmath.NA ·2026-11-18 ·Aarshvi Gajjar, Syamantak Kumar, Aditya Makkar, Christopher Musco, Joey Zhou
top venuetheory similarity 0.57
Abstract · To appear in NeurIPS 2026 (Spotlight)

In this paper we study active learning for constrained linear regression. Given a design matrix $A\in\mathbb{R}^{n\times d}$, a constraint set $C\subseteq\mathbb{R}^d$, and query access to $b\in\mathbb{R}^n$, we seek an approximate solution to $\min_{x\in C}\|Ax-b\|_2^2$ using as few queries as possible. This problem arises in many scientific and engineering applications, and randomized leverage score sampling provides a powerful method to solve it. However, existing leverage score methods ignore the constraint or encode it through ridge regularization, suffering unfavorable query complexity for anisotropic constraint sets. We propose ellipsoid-regularized leverage scores, where we approximate the constraint set by an outer ellipsoid and use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the query complexity is governed by an anisotropic effective dimension $d_{\text{eff}}(C)\le d$. With appropriate parameters, $O(d_{\text{eff}}(C)\log d/\varepsilon^2)$ queries suffice to return a point in $C$ with objective value at most $(1+\varepsilon)$ times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make $d_{\text{eff}}(C)$ much smaller than $d$. For convex constraints, we improve the dependence on $\varepsilon$ from $1/\varepsilon^2$ to $1/\varepsilon$. We also prove two lower bounds: first, the $d/\varepsilon^2$ dependence is unavoidable without convexity assumptions on $C$, and second, in some regimes, the effective dimension dependence $d_{\mathrm{eff}}(C)/\varepsilon$ is necessary for ellipsoidal constraints. Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget.

0.34

lapanda: A Matrix-Free Differentiable Solver for Nonconvex Constrained Optimization Layers

cs.LG math.OCeess.SY ·2026-09-27 ·Yuankun Chen, Zifei Nie, Kangyu Lin, Ján Drgoňa, Liang Wu
similarity 0.57
Abstract

Differentiable optimization brings the structural guarantees of mathematical optimization to network pipelines, allowing them to be trained end-to-end. However, its application remains challenging for nonconvex constrained problems, as existing differentiable solvers often suffer from limited modeling expressiveness due to their reliance on specialized problem structures, while also incurring substantial computation time and memory overhead in both the forward and backward passes. To address these challenges, we propose lapanda, a matrix-free differentiable solver for nonconvex optimization with general constraints. It reformulates the problem to a sequence of augmented Lagrangian subproblems, each handled by a first-order inner solver through a proximal averaged quasi-Newton algorithm with adaptive linesearch, thus enabling efficient forward optimization. We establish local well-posedness of the solution map and convergence of the outer iterations, and further derive a sensitivity alignment between the original problem and the final subproblem in the backward pass, demonstrating that the subproblem sensitivity, which can be computed efficiently in a matrix-free manner, provides a principled approximation to the exact optimizer sensitivity. We evaluate lapanda on nonconvex constrained Rosenbrock benchmarks, imitation learning with several representative constrained optimal control problems, and embedded robotic obstacle-avoidance tasks. Compared with state-of-the-art differentiable solvers, lapanda delivers substantial reductions in computation time and memory footprint while maintaining reliable constraint satisfaction and learning performance.

0.18

Convex Safety Filtering via Spectral Selection for Nonconvex Safe Sets

eess.SY math.OC ·2026-10-08 ·Juan Augusto Paredes Salazar, James Usevitch, Ankit Goel
theory similarity 0.56
Abstract · 7 pages, 3 figures, submitted to the ACC 2027

The discrete-time control barrier function condition for a safe set that is a union of convex sets is nonconvex in the control input. For safe sets defined by a matrix concave function through the number of its nonnegative eigenvalues, this paper shows that the set is a union of convex sets, and that the nonconvexity arises because at least one member of the union must hold, not every member. Selecting eigenvectors of the matrix function at the current state yields a convex input constraint that acts only on the eigenvalues determining membership in the set. This constraint is implied by the matrix-wide condition of prior work, and it guarantees a geometric lower bound on each of those eigenvalues along closed-loop trajectories. A double-integrator simulation with a polytope obstacle and a spectrahedron obstacle compares the proposed filter with the matrix-wide condition.

0.25