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]

What is the minimum number of guesses needed on average to guess a realization of a random variable correctly? The answer to this question led to the introduction of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider the guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, both numerically and analytically, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion. [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]

This paper studies bilevel polynomial optimization. We propose a method to solve it globally by using polynomial optimization relaxations. Each relaxation is obtained from the Karush-Kuhn-Tucker (KKT) conditions for the lower level optimization and the exchange technique for semi-infinite programming. For KKT conditions, Lagrange multipliers are represented as polynomial or rational functions. The Moment-sum-of-squares relaxations are used to solve the polynomial optimization relaxations. Under some general assumptions, we prove the convergence of the algorithm for solving bilevel polynomial optimization problems. Numerical experiments are presented to show the efficiency of the method. [ABSTRACT FROM AUTHOR]

Load aggregators can use demand response programs to motivate residential users toward reducing electricity demand during peak time periods. This article proposes a demand response algorithm for residential users, while accounting for uncertainties in the load demand and electricity price, users’ privacy concerns, and power flow constraints imposed by the distribution network. To address the uncertainty issues, we develop a deep reinforcement learning (DRL) algorithm using an actor-critic method. We apply federated learning to enable users to determine the neural network parameters in a decentralized fashion without sharing private information (e.g., load demand, users’ potential discomfort due to load scheduling). To tackle the nonconvex power flow constraints, we apply convex relaxation and transform the problem of updating the neural network parameters into a sequence of semidefinite programs (SDPs). Simulations on an IEEE 33-bus test feeder with 32 households show that the proposed demand response algorithm can reduce the peak load by 33% and the expected cost of each user by 13%. Also, we demonstrate the scalability of the proposed algorithm in 330-bus and 1650-bus feeders with real-time pricing scheme. [ABSTRACT FROM AUTHOR]

This paper proposes an algorithm for computing the maximum (or minimum) complementarity eigenvalues of tensors. We formulate this as proper polynomial optimization problems that can be efficiently solved by Lasserre type semidefinite relaxations. The algorithm is proved to have finite convergence for generic tensors. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the Hermitian completely positive (HCP) matrix, which has a Hermitian completely positive (HCP) decomposition with all real and imaginary parts of the decomposition vectors being nonnegative. Some properties of the Hermitian completely positive matrix are given. A semidefinite algorithm is also proposed for checking whether a Hermitian matrix is HCP or not. If a matrix is not HCP, a certificate for it can be obtained; if it is, an HCP decomposition can be obtained. [ABSTRACT FROM AUTHOR]

Motivated by connected and automated vehicle (CAV) technologies, this paper proposes a data-driven optimization-based Model Predictive Control (MPC) modeling framework for the Cooperative Adaptive Cruise Control (CACC) of a string of CAVs under uncertain traffic conditions. The proposed data-driven optimization-based MPC modeling framework aims to improve the stability, robustness, and safety of longitudinal cooperative automated driving involving a string of CAVs under uncertain traffic conditions using Vehicle-to-Vehicle (V2V) data. Based on an online learning-based driving dynamics prediction model, we predict the uncertain driving states of the vehicles preceding the controlled CAVs. With the predicted driving states of the preceding vehicles, we solve a constrained Finite-Horizon Optimal Control problem to predict the uncertain driving states of the controlled CAVs. To obtain the optimal acceleration or deceleration commands for the CAVs under uncertainties, we formulate a Distributionally Robust Stochastic Optimization (DRSO) model (i.e. a special case of data-driven optimization models under moment bounds) with a Distributionally Robust Chance Constraint (DRCC). The predicted uncertain driving states of the immediately preceding vehicles and the controlled CAVs will be utilized in the safety constraint and the reference driving states of the DRSO-DRCC model. To solve the minimax program of the DRSO-DRCC model, we reformulate the relaxed dual problem as a Semidefinite Program (SDP) of the original DRSO-DRCC model based on the strong duality theory and the Semidefinite Relaxation technique. In addition, we propose two methods for solving the relaxed SDP problem. We use Next Generation Simulation (NGSIM) data to demonstrate the proposed model in numerical experiments. The experimental results and analyses demonstrate that the proposed model can obtain string-stable, robust, and safe longitudinal cooperative automated driving control of CAVs by proper settings, including the driving-dynamics prediction model, prediction horizon lengths, and time headways. Computational analyses are conducted to validate the efficiency of the proposed methods for solving the DRSO-DRCC model for real-time automated driving applications within proper settings. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the complex completely positive tensor, which has a symmetric complex decomposition with all real and imaginary parts of the decomposition vectors being non-negative. Some properties of the complex completely positive tensor are given. A semidefinite algorithm is also proposed for checking whether a complex tensor is complex completely positive or not. If a tensor is not complex completely positive, a certificate for it can be obtained; if it is complex completely positive, a complex completely positive decomposition can be obtained. [ABSTRACT FROM AUTHOR]

This paper studies stochastic optimization problems with polynomials. We propose an optimization model with sample averages and perturbations. The Lasserre-type Moment-SOS relaxations are used to solve the sample average optimization. Properties of the optimization and its relaxations are studied. Numerical experiments are presented. [ABSTRACT FROM AUTHOR]

In this paper, we study the higher-degree tensor eigenvalue complementarity problem (HDTEiCP). We give an upper bound for the number of the higher-degree complementarity eigenvalues for the generic HDTEiCP. A semidefinite relaxation algorithm is proposed for computing all the higher-degree complementarity eigenvalues sequentially, as well as the corresponding eigenvectors, and the convergence of the algorithm is discussed. Some numerical results are also given. [ABSTRACT FROM AUTHOR]

P -tensor and P 0 -tensor are introduced in tensor complementarity problem, which have wide applications in game theory. In this paper, we establish SDP relaxation algorithms for detecting P (P 0) -tensor. We first reformulate P (P 0) -tensor detection problem as polynomial optimization problems. Then we propose the SDP relaxation algorithms for solving the reformulated polynomial optimization problems. Numerical examples are reported to show the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The extended trust region subproblem has been the focus of several research recently. Under various assumptions, strong duality and certain SOCP/SDP relaxations have been proposed for several classes of it. Due to its importance, in this paper, without any assumption on the problem, we apply the widely used alternating direction method of multipliers (ADMM) to solve it. The convergence of ADMM iterations to the first order stationary conditions is established. On several classes of test problems, the quality of the solution obtained by the ADMM for medium scale problems is compared with the SOCP/SDP relaxation. Moreover, the applicability of the method for solving large scale problems is shown by solving several large instances.

In this paper, we study the completely positive (CP) tensor program, which is a linear optimization problem with the cone of CP tensors and some linear constraints. We reformulate it as a linear program over the cone of moments, then construct a hierarchy of semidefinite relaxations for solving it. We also discuss how to find a best CP approximation of a given tensor. Numerical experiments are presented to show the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

We consider the problem of efficiently computing the derivative of the solution map of a convex cone program, when it exists. We do this by implicitly differentiating the residual map for its homogeneous self-dual embedding, and solving the linear systems of equations required using an iterative method. This allows us to efficiently compute the derivative operator, and its adjoint, evaluated at a vector. These correspond to computing an approximate new solution, given a perturbation to the cone program coefficients (i.e., perturbation analysis), and to computing the gradient of a function of the solution with respect to the coefficients. Our method scales to large problems, with numbers of coefficients in the millions. We present an open-source Python implementation of our method that solves a cone program and returns the derivative and its adjoint as abstract linear maps; our implementation can be easily integrated into software systems for automatic differentiation. [ABSTRACT FROM AUTHOR]

Abstract Verifying the positive semi-definiteness of a symmetric space tensor is an important and challenging topic in tensor computation. In this paper, we develop two methods to address the problem based on the theory of nonnegative polynomials which enables us to establish semi-definite programs to examine the positive semi-definiteness of a given symmetric space tensor. Moreover, using the similar idea, we can show that the minimal H -eigenvalue of a symmetric space tensor must be the optimal value of a semi-definite program. Computational results and discussions are provided to illustrate the significance of the results and the effectiveness of the proposed methods. Highlights • We find two methods to verify the positive semi-definiteness of a symmetric space tensor. • The first method could verify the positive semi-definiteness of a symmetric space tensor in polynomial time. • The second method could verify the positive semi-definiteness of a symmetric space tensor in the large order case. • We discuss the method how to solve the H-eigenvalue of a symmetric space tensor. [ABSTRACT FROM AUTHOR]

Semidefinite programming is an important optimization task, often used in time-sensitive applications. Though they are solvable in polynomial time, in practice they can be too slow to be used in online, i.e. real-time applications. Here we propose to solve feasibility semidefinite programs using artificial neural networks (NNs). Given the optimization constraints as an input, a NN outputs values for the optimization parameters such that the constraints are satisfied, both for the primal and the dual formulations of the task. We train the network without having to exactly solve the semidefinite program even once, thus avoiding the possibly time-consuming task of having to generate many training samples with conventional solvers. The NN method is only inconclusive if both the primal and dual models fail to provide feasible solutions. Otherwise we always obtain a certificate, which guarantees false positives to be excluded. As a proof-of-principle demonstration, we examine the performance of the method on a hierarchy of quantum information tasks, the Navascués–Pironio–Acín hierarchy applied to the Bell scenario. We demonstrate that the trained NN gives decent accuracy, while showing orders of magnitude increase in speed compared to a traditional solver, once trained. The network does not have to be retrained for similarly structured problems, giving the promise for being a fast solver for these types of problems.