We introduce a semidefinite relaxation for optimal control of linear systems with time scaling. These problems are inherently nonconvex, since the system dynamics involves bilinear products between the discretization time step and the system state and controls. The proposed relaxation is closely related to the standard second-order semidefinite relaxation for quadratic constraints, but we carefully select a subset of the possible bilinear terms and apply a change of variables to achieve empirically tight relaxations while keeping the computational load light. We further extend our method to handle piecewise-affine (PWA) systems by formulating the PWA optimal-control problem as a shortest-path problem in a graph of convex sets (GCS). In this GCS, different paths represent different mode sequences for the PWA system, and the convex sets model the relaxed dynamics within each mode. By combining a tight convex relaxation of the GCS problem with our semidefinite relaxation with time scaling, we can solve PWA optimal-control problems through a single semidefinite program.

Can we accelerate the convergence of gradient descent without changing the algorithm—just by judiciously choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed Silver Stepsize Schedule optimizes strongly convex functions in \(\kappa ^{\log _{\rho } 2} \approx \kappa ^{0.7864}\) iterations, where \(\rho =1+\sqrt {2}\) is the silver ratio and κ is the condition number. This is intermediate between the textbook unaccelerated rate κ and the accelerated rate \(\kappa ^{1/2}\) due to Nesterov in 1983. The non-strongly convex setting is conceptually identical, and standard black-box reductions imply an analogous partially accelerated rate \(\varepsilon ^{-\log _{\rho } 2} \approx \varepsilon ^{-0.7864}\) . We conjecture and provide partial evidence that these rates are optimal among all stepsize schedules. The Silver Stepsize Schedule is constructed recursively in a fully explicit way. It is non-monotonic, fractal-like, and approximately periodic of period \(\kappa ^{\log _{\rho } 2}\) . This leads to a phase transition in the convergence rate: initially super-exponential (acceleration regime), then exponential (saturation regime). The core algorithmic intuition is hedging between individually suboptimal strategies—short steps and long steps—since bad cases for the former are good cases for the latter, and vice versa. Properly combining these stepsizes yields faster convergence due to the misalignment of worst-case functions. The key challenge in proving this speedup is enforcing long-range consistency conditions along the algorithm’s trajectory. We do this by developing a technique that recursively glues constraints from different portions of the trajectory, thus removing a key stumbling block in previous analyses of optimization algorithms. More broadly, we believe that the concepts of hedging and multi-step descent have the potential to be powerful algorithmic paradigms in a variety of contexts in optimization and beyond. This article publishes and extends the first author’s 2018 master’s thesis (advised by the second author)—which established for the first time that judiciously choosing stepsizes can enable acceleration in convex optimization. Prior to this thesis, the only such result was for the special case of quadratic optimization, due to Young in 1953.

Inverse Reinforcement Learning (IRL) and Reinforcement Learning from Human Feedback (RLHF) are pivotal methodologies in reward learning, which involve inferring and shaping the underlying reward function of sequential decision-making problems based on observed human demonstrations and feedback. Most prior work in reward learning has relied on prior knowledge or assumptions about decision or preference models, potentially leading to robustness issues. In response, this paper introduces a novel linear programming (LP) framework tailored for offline reward learning. Utilizing pre-collected trajectories without online exploration, this framework estimates a feasible reward set from the primal-dual optimality conditions of a suitably designed LP, and offers an optimality guarantee with provable sample efficiency. Our LP framework also enables aligning the reward functions with human feedback, such as pairwise trajectory comparison data, while maintaining computational tractability and sample efficiency. We demonstrate that our framework potentially achieves better performance compared to the conventional maximum likelihood estimation (MLE) approach through analytical examples and numerical experiments.

The coordinate descent (CD) method is a classical optimization algorithm that has seen a revival of interest because of its competitive performance in machine learning applications. A number of recent papers provided convergence rate estimates for their deterministic (cyclic) and randomized variants that differ in the selection of update coordinates. These estimates suggest randomized coordinate descent (RCD) performs better than cyclic coordinate descent (CCD), although numerical experiments do not provide clear justification for this comparison. In this paper, we provide examples and more generally problem classes for which CCD (or CD with any deterministic order) is faster than RCD in terms of asymptotic worst-case convergence. Furthermore, we provide lower and upper bounds on the amount of improvement on the rate of CCD relative to RCD, which depends on the deterministic order used. We also provide a characterization of the best deterministic order (that leads to the maximum improvement in convergence rate) in terms of the combinatorial properties of the Hessian matrix of the objective function.

The joint spectral radius (JSR) of a set of matrices characterizes the maximal asymptotic growth rate of an infinite product of matrices of the set. This quantity appears in a number of applications including the stability of switched and hybrid systems. Many algorithms exist for estimating the JSR but not much is known about how to generate an infinite sequence of matrices with an optimal asymptotic growth rate. To the best of our knowledge, the currently known algorithms select a small sequence with large spectral radius using brute force (or branch-and-bound variants) and repeats this sequence infinitely.

Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction, and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry---in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gröbner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gröbner bases algorithms in many cases. The reason is because all computations are done on “smaller” rings of size equal to the treewidth of the graph (instead of the total number of variables). In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization, and differential equations.

Model-based compressed sensing refers to compressed sensing with extra structure about the underlying sparse signal known a priori. Recent work has demonstrated that both for deterministic and probabilistic models imposed on the signal, this extra information can be successfully exploited to enhance recovery performance. In particular, weighted ℓ1-minimization with suitable choice of weights has been shown to improve performance in the so-called non-uniform sparse model of signals. In this paper, we consider a full generalization of the non-uniform sparse model with very mild assumptions. We prove that when the measurements are obtained using a matrix with independent identically distributed Gaussian entries, weighted ℓ1-minimization successfully recovers the sparse signal from its measurements with overwhelming probability. We also provide a method to choose these weights for any general signal model from the non-uniform sparse class of signal models.

In the past decade there has been a surge of interest in algebraic approaches to optimization problems defined by multivariate polynomials. Fundamental mathematical challenges that arise in this area include understanding the structure of nonnegative polynomials, the interplay between efficiency and complexity of different representations of algebraic sets, and the development of effective algorithms. Remarkably, and perhaps unexpectedly, convexity provides a new viewpoint and a powerful framework for addressing these questions. This naturally brings us to the intersection of algebraic geometry, optimization, and convex geometry, with an emphasis on algorithms and computation. This emerging area has become known as convex algebraic geometry.

We study the problem of approximating the joint spectral radius (JSR) of a finite set of matrices. Our approach is based on the analysis of the underlying switched linear system via inequalities imposed between multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of graphs called path-complete graphs, and show that any such graph gives rise to a method for proving stability of the switched system. This enables us to derive several asymptotically tight hierarchies of semidefinite programming relaxations that unify and generalize many existing techniques such as common quadratic, common sum of squares, maximum/minimum-of-quadratics Lyapunov functions. We characterize all path-complete graphs consisting of two nodes on an alphabet of two matrices and compare their performance. For the general case of any set of n x n matrices we propose semidefinite programs of modest size that approximate the JSR within a multiplicative factor of 1/4√n of the true value. We establish a notion of duality among path-complete graphs and a constructive converse Lyapunov theorem for maximum/minimum-of-quadratics Lyapunov functions.

We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically.

BACKGROUND: Current approaches to parameter estimation are often inappropriate or inconvenient for the modelling of complex biological systems. For systems described by nonlinear equations, the conventional approach is to first numerically integrate the model, and then, in a second a posteriori step, check for consistency with experimental constraints. Hence, only single parameter sets can be considered at a time. Consequently, it is impossible to conclude that the "best" solution was identified or that no good solution exists, because parameter spaces typically cannot be explored in a reasonable amount of time. RESULTS: We introduce a novel approach based on semidefinite programming to directly identify consistent steady state concentrations for systems consisting of mass action kinetics, i.e., polynomial equations and inequality constraints. The duality properties of semidefinite programming allow to rigorously certify infeasibility for whole regions of parameter space, thus enabling the simultaneous multi-dimensional analysis of entire parameter sets. CONCLUSION: Our algorithm reduces the computational effort of parameter estimation by several orders of magnitude, as illustrated through conceptual sample problems. Of particular relevance for systems biology, the approach can discriminate between structurally different candidate models by proving inconsistency with the available data.

A multivariate polynomial is a sum of squares (SOS) if it can be written as a sum of squares of other polynomials, i.e., p(x) = ∑ q2;i;(x), q_i(x) e R[x;1;, …, x;n;].If p(x) is SOS then p(x) ≥ 0 for all x e R n, thus making the sum of squares condition a quite natural sufficient test for polynomial nonnegativity.The existence of a decomposition of a multivariate polynomial as a sum of squares is a basic question in pure and applied mathematics. Its rich algebraic and geometric structure has been analyzed in detail in the past, notably by Reznick and coauthors [1], but until very recently the computational implications have not been fully explored. In the last few years there have been some very interesting new developments surrounding sums of squares, that have produced a wide array of results linking foundational questions in real algebra with computational possibilities arising from convex optimization. The possibility of effective computation of SOS decompositions also has important practical consequences, as they can be used in the formulation of easily verifiable certificates of the emptiness of semialgebraic sets via the Positivstellensatz, a central result in real algebraic geometry.In this talk we present an overview of this novel research area, that combines symbolic and numeric techniques from real algebra and optimization. Particularly exciting is the recent availability of efficient approaches, based on convex optimization, for its effective computation. Most of them employ semidefinite programming (SDP) [5] as the essential computational tool. SDP is a class of optimization problems, where the feasible set is the intersection of an affine subspace and the convex cone of positive semidefinite matrices. We will review the basics of SDP, emphasizing its algebraic characterization and properties, as well as some interesting open problems.Along the way, we will learn how to compute sum of squares decompositions for multivariate polynomials using semidefinite programming, how to certify the results using rounding techniques, and how to obtain structured infeasibility certificates for real solutions of systems of polynomial equations and inequalities. The developed techniques unify and generalize many well-known existing methods.The methods introduced in [3, 4] have been significantly strengthened to exploit problem-specific algebraic and numerical structure; see for instance [2]. The basic ideas and algorithms, as well as these recent extensions, will be illustrated with examples drawn from a broad range of domains, including dynamical systems, geometric theorem proving and quantum mechanics.