Search

This paper introduces a new storage-optimal first-order method, CertSDP, for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the exact QMP-like SDPs, is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a certificate of strict complementarity to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently. Our algorithms for strongly convex minimax problems with inexact prox maps may be of independent interest. We accompany our theoretical results with preliminary numerical experiments suggesting that CertSDP significantly outperforms current state-of-the-art methods on large sparse exact QMP-like SDPs. [ABSTRACT FROM AUTHOR]

Invariant measures encode the long-time behaviour of a dynamical system. In this work, we propose an optimization-based method to discover invariant measures directly from data gathered from a system. Our method does not require an explicit model for the dynamics and allows one to target specific invariant measures, such as physical and ergodic measures. Moreover, it applies to both deterministic and stochastic dynamics in either continuous or discrete time. We provide convergence results and illustrate the performance of our method on data from the logistic map and a stochastic double-well system, for which invariant measures can be found by other means. We then use our method to approximate the physical measure of the chaotic attractor of the Rössler system, and we extract unstable periodic orbits embedded in this attractor by identifying discrete-time periodic points of a suitably defined Poincaré map. This final example is truly data-driven and shows that our method can significantly outperform previous approaches based on model identification. [ABSTRACT FROM AUTHOR]

We study a pessimistic stochastic bilevel program in the context of sequential two-player games, where the leader makes a binary here-and-now decision, and the follower responds with a continuous wait-and-see decision after observing the leader's action and revelation of uncertainty. We assume that only the information regarding the mean, covariance, and support is known. We formulate the problem as a distributionally robust (DR) two-stage problem. The pessimistic DR bilevel program is shown to be equivalent to a generic two-stage distributionally robust stochastic (nonlinear) program with both a random objective and random constraints under proper conditions of ambiguity sets. Under continuous distributions, using linear decision rule approaches, we construct upper bounds on the pessimistic DR bilevel program based on (1) a 0-1 semidefinite programming (SDP) approximation and (2) an exact 0-1 copositive programming reformulation. When the ambiguity set is restricted to discrete distributions, an exact 0-1 SDP reformulation is developed, and explicit construction of the worst-case distribution is derived. To further improve the computation of the proposed 0-1 SDPs, a cutting-plane framework is developed. Moreover, based on a mixed-integer linear programming approximation, another cutting-plane algorithm is proposed. Extensive numerical studies are conducted to demonstrate the effectiveness of the proposed approaches on a facility location problem. History: Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0168) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0168). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

We study the upper bounds for A(n, d), the maximum size of codewords with length n and Hamming distance at least d. Schrijver studied the Terwilliger algebra of the Hamming scheme and proposed a semidefinite program to bound A(n, d). We derive more sophisticated matrix inequalities based on a split Terwilliger algebra to improve Schrijver's semidefinite programming bounds on A(n, d). In particular, we improve the semidefinite programming bounds on A(18, 4) to 6551. [ABSTRACT FROM AUTHOR]

In this paper, unconstrained minimization with block-circulant structured polynomials is studied. A specifically designed method is presented to show that it can solve problems with sizes much larger than the classical Lasserre's semidefinite relaxation. The proposed approach is in the same spirit of Lasserre's relaxation but with a careful exploration of the underlying circulant structure, which helps reducing the sizes of the result semidefinite program problems significantly. Despite of the reduction, a certification for the global optimality is derived as well. [ABSTRACT FROM AUTHOR]

Phase retrieval in real or complex Hilbert spaces is the task of recovering a vector, up to an overall unimodular multiplicative constant, from magnitudes of linear measurements. In this paper, we assume that the vector is normalized, but retain only qualitative, binary information about the measured magnitudes by comparing them with a threshold. In more specific, geometric terms, we choose a sequence of subspaces in a real or complex Hilbert space and only record whether a given vector is closer to the subspace than to the complementary subspace. The subspaces have half the dimension of the Hilbert space and are independent, uniformly distributed with respect to the action of the orthogonal or unitary groups. The main goal of this paper is to find a feasible algorithm for approximate recovery based on the information gained about the vector from these binary questions and to establish error bounds for its approximate recovery. We provide a pointwise bound for fixed input vectors and a uniform bound that controls the worst-case scenario among all inputs. Both bounds hold with high probability with respect to the choice of the subspaces. For real or complex vectors of dimension n, the pointwise bound requires m ≥ C δ - 2 n log (n) and the uniform bound m ≥ C δ - 2 n 2 log (δ - 1 n) binary questions in order to achieve an accuracy of δ . The accuracy δ is measured by the operator norm of the difference between the rank-one orthogonal projections corresponding to the normalized input vector and its approximate recovery. [ABSTRACT FROM AUTHOR]

This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre's hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence. [ABSTRACT FROM AUTHOR]

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry present in a given problem, is large enough. We present similar sufficient conditions under which the projected epigraph of the SDP gives the convex hull of the epigraph in the original QCQP. Our results also imply new sufficient conditions for the tightness (as well as convex hull exactness) of a second order cone program relaxation of simultaneously diagonalizable QCQPs. [ABSTRACT FROM AUTHOR]

We study optimal control problems in the multivariate linear‐quadratic‐Gaussian framework under rational inattention. We propose a three‐step procedure to solve this problem using semidefinite programming and derive the optimal signal structure without strong prior restrictions. We analyze both the transition dynamics of the optimal posterior covariance matrix and its steady state. We characterize the optimal information structure for some special cases and develop numerical algorithms for general cases. Applying our methods to solve three multivariate economic models, we obtain some results qualitatively different from the literature. [ABSTRACT FROM AUTHOR]

In joint radar-communications (JRC) applications such as secure military receivers, often the radar and communications signals are overlaid in the received signal. In these passive listening outposts, the signals and channels of both radar and communications are unknown to the receiver. The ill-posed problem of recovering all signal and channel parameters from the overlaid signal is termed as dual-blind deconvolution (DBD). In this work, we investigate DBD for a multi-antenna receiver. We model the radar and communications channels with a few (sparse) continuous-valued parameters such as time delays, Doppler velocities, and directions-of-arrival (DoAs). To solve this highly ill-posed DBD, we propose to minimize the sum of multivariate atomic norms (SoMAN) that depend on unknown parameters. To this end, we devise an exact semidefinite program using theories of positive hyperoctant trigonometric polynomials (PhTP). Our theoretical analyses show that the minimum number of samples and antennas required for perfect recovery is logarithmically dependent on the maximum of the number of radar targets and communications paths rather than their sum. We show that our approach is easily generalized to include several practical issues such as gain/phase errors and additive noise. Numerical experiments show the exact parameter recovery for different JRC scenarios. • Multi-antenna dual-blind deconvolution (M-DBD) is a general formulation for ISAC receiver. • Atomic norm minimization exploits sparsity to estimate the unknown continuous-valued variables. • Strong theoretical guarantees for exact recovery. • Generalization for practical scenarios with gain/phase errors in the receiver. [ABSTRACT FROM AUTHOR]

Multiple point clouds registration is a prerequisite step for geometry object observation from multiple viewpoints. Most algorithms depend on pose graph or relative poses, and they make the results ambiguous and inconsistent with the original point clouds. However, the existing algorithms based on original data can almost exclusively be applied to simulated data. In this paper, a practical semiautomatic global registration algorithm is proposed. A objective function is proposed; it utilizes correspondences between point cloud pairs directly to describe this problem, making the algorithm easy to interface with other point cloud matching algorithms. Moreover, it can be effectively approximated by semidefinite programming. Since no automatic algorithm can guarantee the correctness of the correspondences, a manual strategy is proposed to filter the correspondences and find the correlation between point clouds. Based on the correlation, irrelevant point clouds can be removed easily in the point cloud set or divide the set into multiple independent parts. Besides, a postprocessing strategy based on the correlation is proposed for refining the results. The qualitative and quantitative experimental results demonstrate that the approach achieves more accurate and robust performance than previous algorithms. [ABSTRACT FROM AUTHOR]