Linear Time-Varying Parameter Estimation: Maximum A Posteriori Approach via Semidefinite Programming

We study the problem of identifying a linear time-varying output map from measurements and linear time-varying system states, which are perturbed with Gaussian observation noise and process uncertainty, respectively. Employing a stochastic model as prior knowledge for the parameters of the unknown output map, we reconstruct their estimates...

The Chvátal–Gomory procedure for integer SDPs with applications in combinatorial optimization

In this paper we study the well-known Chvátal–Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the...

On the Dual of the Lovász Theta Prime Number for the Disjunctive Product of Graphs

The Lovász theta function, and the variants of it given by Schrijver and Szegedy are upper bounds on the independence number of a graph. These functions play an important role in several optimization problems, such as the Cohn-Elkies bound for optimal sphere packing densities.<br/><br/>This thesis covers the properties of these functions. The...

A Recursive Theta Body for Hypergraphs

The theta body of a graph, introduced by Grötschel, Lovász, and Schrijver (in 1986), is a tractable relaxation of the independent-set polytope derived from the Lovász theta number. In this paper, we recursively extend the theta body, and hence the theta number, to hypergraphs. We obtain fundamental properties of this extension and relate it...

On Integrality in Semidefinite Programming for Discrete Optimization

It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been...

A solver for clustered low-rank SDPs arising from multivariate polynomial (matrix) programs

In this thesis, we give a primal-dual interior point method specialized to clustered low-rank semidefinite programs. We introduce multivariate polynomial matrix programs, and we reduce these to clustered low-rank semidefinite programs. This extends the work of Simmons-Duffin [J. High Energ. Phys. 1506, no. 174 (2015)] from...

Complete positivity and distance-avoiding sets

We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning...

A numerical evaluation of the bounded degree sum-of-squares hierarchy of Lasserre, Toh, and Yang on the pooling problem

The bounded degree sum-of-squares (BSOS) hierarchy of Lasserre et al. (EURO J Comput Optim 1–31, 2015) constructs lower bounds for a general polynomial optimization problem with compact feasible set, by solving a sequence of semi-definite programming (SDP) problems. Lasserre, Toh, and Yang prove that these lower bounds converge to the optimal...

Optimizing quantum entanglement distillation

Quantum entanglement is a physical resource that is essential for many quantum information processing tasks, such as quantum communication and quantum computing. Although entanglement is essential for practical implementations in those fields, it is hard to create and transmit entanglement reliably. External factors introduce noise which may...

Moment methods in extremal geometry

In this thesis we develop techniques for solving problems in extremal geometry. We give an infinite dimensional generalization of moment techniques from polynomial optimization. We use this to construct semidefinite programming hierarchies for approximating optimal packing densities and ground state energies of particle systems. For this we...

On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also give the tight worst-case...

Ranging energy optimization for robust sensor positioning based on semidefinite programming

Sensor positioning is an important task of location-aware wireless sensor networks. In most sensor positioning systems, sensors and beacons need to emit ranging signals to each other. Sensor ranging energy should be low to prolong system lifetime, but sufficiently high to fulfill prescribed accuracy requirements. This motivates us to investigate...

Interior Point Methods for Semidefinite Programming