A projected gradient method for optimization over density matrices

An ensemble of quantum states can be described by a Hermitian, positive semidefinite and unit trace matrix called density matrix. Thus, the study of methods for optimizing a certain function (energy, entropy) over the set of density matrices has a direct application to important problems in quantum information and computation. We propose a projected gradient method for solving such problems. By exploiting the geometry of the feasible set, which is the intersection of the cone of Hermitian positive semidefinite matrices with the hyperplane defined by the unit trace constraint, we describe an efficient procedure to compute the projection onto this set using the Frobenius norm. Some important applications, such as quantum state tomography, are described and numerical experiments illustrate the effectiveness of the method when compared to previous methods based on fixed-point iterations or semidefinite programming.     

Distributed control of systems over discrete Groups

This paper discusses distributed controller design and analysis for distributed systems with arbitrary discrete symmetry groups. We show how recent results for designing controllers for spatially interconnected systems, based on semidefinite programming, are applicable to a much larger class of interconnection topologies. We also show how to exploit the structure of the symmetry group to produce a hierarchy of decreasingly conservative analysis and synthesis conditions.     

Duality and eventually periodic systems

This paper employs semidefinite programming duality theory to develop new alternative linear matrix inequality (LMI) tools for eventually periodic systems. These tools are then utilized to rederive an important version of the Kalman–Yakubovich–Popov (KYP) Lemma for such systems, and further give new synthesis results. Copyright © 2005 John Wiley & Sons, Ltd.     

Control applications of nonlinear convex programming

Since 1984 there has been a concentrated effort to develop efficient interior-point methods for linear programming (LP). In the last few years researchers have begun to appreciate a very important property of these interior-point methods (beyond their efficiency for LP): they extend gracefully to nonlinear convex optimization problems. New interior-point algorithms for problem classes such as semidefinite programming (SDP) or second-order cone programming (SOCP) are now approaching the extreme efficiency of modern linear programming codes. In this paper we discuss three examples of areas of control where our ability to efficiently solve nonlinear convex optimization problems opens up new applications. In the first example we show how SOCP can be used to solve robust open-loop optimal control problems. In the second example, we show how SOCP can be used to simultaneously design the set-point and feedback gains for a controller, and compare this method with the more standard approach. Our final application concerns analysis and synthesis via linear matrix inequalities and SDP.     

Application of facial reduction to H ∞ state feedback control problem

One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from H _∞ control problems. For semidefinite programming (SDP) relaxations for combinatorial problems, it is known that when either an SDP relaxation problem or its dual is not strongly feasible, one may encounter such numerical difficulties. We discuss necessary and sufficient conditions to be not strongly feasible for an LMI problem obtained from H _∞ state feedback control problems and its dual. Moreover, we interpret the conditions in terms of control theory. In this analysis, facial reduction, which was proposed by Borwein and Wolkowicz, plays an important role. We show that the dual of the LMI problem is not strongly feasible if and only if there exist invariant zeros in the closed left-half plane in the system, and present a remedy to remove the numerical difficulty with the null vectors associated with invariant zeros in the closed left-half plane. Numerical results show that the numerical stability is improved by applying it.     

D-stability of polynomial matrices

Necessary and sufficient conditions are formulated for the zeros of an arbitrary polynomial matrix to belong to a given region D of the complex plane. The conditions stem from a general optimization methodology mixing quadratic and semidefinite programming, LFRs and rank-one LMIs. They are expressed as an LMI feasibility problem that can be tackled with widespread powerful interior-point methods. Most importantly, the D-stability conditions can be combined with other LMI conditions arising in robust stability analysis.     

Parallel Approximation Algorithms by Positive Linear Programming

Several sequential approximation algorithms for combinatorial optimization problems are based on the following paradigm: solve a linear or semidefinite programming relaxation, then use randomized rounding to convert fractional solutions of the relaxation into integer solutions for the original combinatorial problem. We demonstrate that such a paradigm can also yield parallel approximation algorithms by showing how to convert certain linear programming relaxations into essentially equivalent positive linear programming [LN] relaxations that can be near-optimally solved in NC. Building on this technique, and finding some new linear programming relaxations, we develop improved parallel approximation algorithms for Max Sat, Max Directed Cut, and Max k CSP. The Max Sat algorithm essentially matches the best approximation obtainable with sequential algorithms and has a fast sequential version. The Max k CSP algorithm improves even over previous sequential algorithms. We also show a connection between probabilistic proof checking and a restricted version of Max k CSP. This implies that our approximation algorithm for Max k CSP can be used to prove inclusion in P for certain PCP classes. Received November 1996; revised March 1997.     

Low-rank exploitation in semidefinite programming for control

Many control-related problems can be cast as semidefinite programs. Even though there exist polynomial time algorithms and excellent publicly available solvers, the time it takes to solve these problems can be excessive. What many of these problems have in common, in particular in control, is that some of the variables enter as matrix-valued variables. This leads to a low-rank structure in the basis matrices which can be exploited when forming the Newton equations. In this article, we describe how this can be done, and show how our code, called STRUL, can be used in conjunction with the semidefinite programming solver SDPT3. The idea behind the structure exploitation is classical and is implemented in LMI Lab, but we show that when using a modern semidefinite programming framework such as SDPT3, the computational time can be significantly reduced. Finally, we describe how the modelling language YALMIP has been changed in such a way that our code, which can be freely downloaded, can be interfaced using standard YALMIP commands. This greatly simplifies modelling and usage.     

Semidefinite spectral clustering

Multi-way partitioning of an undirected weighted graph where pairwise similarities are assigned as edge weights, provides an important tool for data clustering, but is an NP-hard problem. Spectral relaxation is a popular way of relaxation, leading to spectral clustering where the clustering is performed by the eigen-decomposition of the (normalized) graph Laplacian. On the other hand, semidefinite relaxation, is an alternative way of relaxing a combinatorial optimization, leading to a convex optimization. In this paper we employ a semidefinite programming (SDP) approach to the graph equipartitioning for clustering, where sufficient conditions for strong duality hold. The method is referred to as semidefinite spectral clustering, where the clustering is based on the eigen-decomposition of the optimal feasible matrix computed by SDP. Numerical experiments with several data sets, demonstrate the useful behavior of our semidefinite spectral clustering, compared to existing spectral clustering methods.     

A primal–dual semidefinite programming algorithm tailored to the variational determination of the two-body density matrix

The quantum many-body problem can be rephrased as a variational determination of the two-body reduced density matrix, subject to a set of N-representability constraints. The mathematical problem has the form of a semidefinite program. We adapt a standard primal–dual interior point algorithm in order to exploit the specific structure of the physical problem. In particular the matrix-vector product can be calculated very efficiently. We have applied the proposed algorithm to a pairing-type Hamiltonian and studied the computational aspects of the method. The standard N-representability conditions perform very well for this problem.     

Rank-one LMIs and Lyapunov's inequality

We describe a new proof of the well-known Lyapunov's matrix inequality about the location of the eigenvalues of a matrix in some region of the complex plane. The proof makes use of standard facts from quadratic and semidefinite programming. Links are established between the Lyapunov matrix, rank-one linear matrix inequalities (LMI), and the Lagrange multiplier arising in duality theory     

Convex inner approximations of nonconvex semialgebraic sets applied to fixed-order controller design

We describe an elementary algorithm to build convex inner approximations of nonconvex sets. Both input and output sets are basic semialgebraic sets given as lists of defining multivariate polynomials. Even though no optimality guarantees can be given (e.g. in terms of volume maximisation for bounded sets), the algorithm is designed to preserve convex boundaries as much as possible, while removing regions with concave boundaries. In particular, the algorithm leaves invariant a given convex set. The algorithm is based on Gloptipoly 3, a public-domain Matlab package solving nonconvex polynomial optimisation problems with the help of convex semidefinite programming (optimisation over linear matrix inequalities, or LMIs). We illustrate how the algorithm can be used to design fixed-order controllers for linear systems, following a polynomial approach.     

Kernel based support vector machine via semidefinite programming: Application to medical diagnosis

Support vector machine (SVM) is a well sound learning method and a robust classification procedure. Choosing a suitable kernel function in SVM is crucial for obtaining good performance; the difficulty is how to choose a suitable data transformation for the given problem. To this end, multiple kernel matrices, each of them corresponding to a given similarity measure, can be linearly combined. In this paper, the optimal kernel matrix, obtained as linear combination of known kernel matrices, is generated using a semidefinite programming approach. A suitable model formulation assures that the obtained kernel matrix is positive semidefinite and is optimal with respect to the dataset under consideration. The proposed approach has been applied to some very important medical diagnostic decision making problems and the results obtained by carrying out preliminary numerical experiments demonstrated the effectiveness of the proposed solution approach.     

An admissible dual internal point method for a linear semidefinite programming problem

We consider a linear semidefinite programming problem. To solve this problem, we propose a dual numerical method from the class of affine scaling methods. We use Ostrovskii’s theorem to establish its local convergence. We also show results for test problems.     

Consistent Shape Maps via Semidefinite Programming

Recent advances in shape matching have shown that jointly optimizing the maps among the shapes in a collection can lead to significant improvements when compared to estimating maps between pairs of shapes in isolation. These methods typically invoke a cycle‐consistency criterion — the fact that compositions of maps along a cycle of shapes should approximate the identity map. This condition regularizes the network and allows for the correction of errors and imperfections in individual maps. In particular, it encourages the estimation of maps between dissimilar shapes by compositions of maps along a path of more similar shapes. In this paper, we introduce a novel approach for obtaining consistent shape maps in a collection that formulates the cycle‐consistency constraint as the solution to a semidefinite program (SDP). The proposed approach is based on the observation that, if the ground truth maps between the shapes are cycle‐consistent, then the matrix that stores all pair‐wise maps in blocks is low‐rank and positive semidefinite. Motivated by recent advances in techniques for low‐rank matrix recovery via semidefinite programming, we formulate the problem of estimating cycle‐consistent maps as finding the closest positive semidefinite matrix to an input matrix that stores all the initial maps. By analyzing the Karush‐Kuhn‐Tucker (KKT) optimality condition of this program, we derive theoretical guarantees for the proposed algorithm, ensuring the correctness of the recovery when the errors in the inputs maps do not exceed certain thresholds. Besides this theoretical guarantee, experimental results on benchmark datasets show that the proposed approach outperforms state‐of‐the‐art multiple shape matching methods.     

An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs

This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. For Tseitin instances based on toroidal grid graphs, we present an explicit semidefinite programming problem with dimension linear in the size of the Tseitin instance, and prove that it characterizes the satisfiability of these instances, thus providing an explicit certificate of satisfiability or unsatisfiability. Research partially supported by the Natural Sciences and Engineering Research Council of Canada.     

New fuzzy control model and dynamic output feedback parallel distributed compensation

A new fuzzy modeling based on fuzzy linear fractional transformations model is introduced. This new representation is shown to be a flexible tool for handling complicated nonlinear models. Particularly, the new fuzzy model provides an efficient and tractable way to handle the output feedback parallel distributed compensation problem. We demonstrate that this problem can be given a linear matrix inequality characterization and hence is immediately solvable through available semidefinite programming codes. The capabilities of the new fuzzy modeling is illustrated through numerical examples.     

A robust constrained model predictive control scheme for norm‐bounded uncertain systems with partial state measurements

A robust model predictive control scheme for a class of constrained norm‐bounded uncertain discrete‐time linear systems is developed under the hypothesis that only partial state measurements are available for feedback. The proposed strategy involves a two‐phase procedure. Initialization phase is devoted to determining an admissible, though not optimal, linear memoryless controller capable to formally address the input rate constraint; then, during on‐line phase, predictive capabilities complement the designed controller by means of N steps free control actions in a receding horizon fashion. These additive control actions are obtained by solving semidefinite programming problems subject to linear matrix inequalities constraints. As computational burden grows linearly with the control horizon length, an example is developed to show the effectiveness of the proposed approach for realistic control problems: the design of a flight control law for a flexible unmanned over‐actuated aircraft, where the states of the flexibility dynamics are not measurable, is discussed, and a numerical implementation of the controller within a nonlinear simulation environment testifies the validity of the proposed approach and the possibility to implement the algorithm on an onboard computer.     

Spectral Algorithms for Unique Games

We give a new algorithm for Unique Games which is based on purely spectral techniques, in contrast to previous work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment. The approximation guarantee depends only on the completeness of the game, and not on the alphabet size, while the running time depends on spectral properties of the Label-Extended graph associated with the instance of Unique Games.