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.     

Global optimization in protein docking using clustering,underestimation and semidefinite programming

The underestimation of data points by a convex quadratic function is a useful tool for approximating the location of the global minima of potential energy functions that arise in protein-ligand docking problems. Determining the parameters that define the underestimator can be formulated as a convex quadratically constrained quadratic program and solved efficiently using algorithms for semidefinite programming (SDP). In this paper, we formulate and solve the underestimation problem using SDP and present numerical results for active site prediction in protein docking.     

Supervised dimensionality reduction via sequential semidefinite programming

Many dimensionality reduction problems end up with a trace quotient formulation. Since it is difficult to directly solve the trace quotient problem, traditionally the trace quotient cost function is replaced by an approximation such that the generalized eigenvalue decomposition can be applied. In contrast, we directly optimize the trace quotient in this work. It is reformulated as a quasi-linear semidefinite optimization problem, which can be solved globally and efficiently using standard off-the-shelf semidefinite programming solvers. Also this optimization strategy allows one to enforce additional constraints (for example, sparseness constraints) on the projection matrix. We apply this optimization framework to a novel dimensionality reduction algorithm. The performance of the proposed algorithm is demonstrated in experiments by several UCI machine learning benchmark examples, USPS handwritten digits as well as ORL and Yale face data.     

Parametrized model reduction based on semidefinite programming

A parametrized model in addition to the control and state-space variables depends on time-independent design parameters, which essentially define a family of models. The goal of parametrized model reduction is to approximate this family of models. In this paper, a reduction method for linear time-invariant (LTI) parametrized models is presented, which constitutes the development of a recently proposed reduction approach. Reduced order models are computed based on the finite number of frequency response samples of the full order model. This method uses a semidefinite relaxation, while enforcing stability on the reduced order model for all values of parameters of interest. As a main theoretical statement, the relaxation gap (the ratio between upper and lower bounds) is derived, which validates the relaxation. The proposed method is flexible in adding extra constraints (e.g., passivity can be enforced on reduced order models) and modifying the objective function (e.g., frequency weights can be added to the minimization criterion). The performance of the method is validated on a numerical example.     

Estimation of the disturbance structure from data using semidefinite programming and optimal weighting

Designing a state estimator for a linear state-space model requires knowledge of the characteristics of the disturbances entering the states and the measurements. In [Odelson, B. J., Rajamani, M. R., & Rawlings, J. B. (2006). A new autocovariance least squares method for estimating noise covariances. Automatica, 42(2), 303-308], the correlations between the innovations data were used to form a least-squares problem to determine the covariances for the disturbances. In this paper we present new and simpler necessary and sufficient conditions for the uniqueness of the covariance estimates. We also formulate the optimal weighting to be used in the least-squares objective in the covariance estimation problem to ensure minimum variance in the estimates. A modification to the above technique is then presented to estimate the number of independent stochastic disturbances affecting the states. This minimum number of disturbances is usually unknown and must be determined from data. A semidefinite optimization problem is solved to estimate the number of independent disturbances entering the system and their covariances.     

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.     

Stability and stabilization of aperiodic sampled-data control systems using robust linear matrix inequalities

Stability analysis of an aperiodic sampled-data control system is considered for application to networked and embedded control. The stability condition is described in a linear matrix inequality to be satisfied for all possible sampling intervals. Although this condition is numerically intractable, a tractable sufficient condition can be constructed with the mean value theorem. Special attention is paid to tightness of the sufficient condition for less conservative stability analysis. A region-dividing technique for the reduction of conservatism and generalization to stabilization are also discussed. An example demonstrates the efficacy of the approach.     

Efficient semidefinite solutions for TDOA-based source localization under unknown PS

Two efficient solutions via Semi-Definite Programming (SDP) are proposed for source localization problems using time difference of arrival (TDOA)-based ranging measurements when the propagation speed (PS) is unavailable and considered as a variable. For this problem, we propose a relaxed SDP (RSDP) solution, the performance of which is suboptimal. Accordingly, we propose a two-stage SDP method to improve the performance by applying the rank-reduction method. Besides, we also propose a penalty function-based SDP (PF-SDP) by introducing the penalty term. By doing so, the cost function becomes tighter so that the solution performs better. The simulated results show that the performance of two-stage SDP is sufficiently close to the Cramér-Rao Lower Bound (CRLB) accuracy at high noise levels. The PF-SDP outperforms the two-stage SDP in the presence of low noise levels.     

Symmetricity of the solution of semidefinite programming

Symmetricity of an optimal solution of Semi-Definite Programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.     

A new SQP algorithm based on semidefinite programming

The paper gives a new filter-SQP algorithm of the semidefinite programming through combining the sequence nonlinear algorithm of solving the semidefinite programming, low rank conversion, and filter method, which, under certain conditions, proves that the algorithm is global convergence.     

On semidefinite programming bounds for graph bandwidth

In this paper, we propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds reported in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoret. Comput. Sci. 235(1) (2000), pp. 25–42; J. Povh and F. Rendl, A copositive programming approach to graph partitioning, SIAM J. Optim. 18(1) (2007), pp. 223–241].     

A modified infeasible interior-point algorithm with full-Newton step for semidefinite optimization

ABSTRACT

Recently, Mansouri et al. (J. Optim. Theory Appl. 166: 605-618, 2015) presented an improved infeasible interior-point algorithm for linear optimization. Their algorithm has the shortcoming that the proximity measure may be still large when the duality gap approaches to zero. In this paper, we propose an infeasible interior-point algorithm for semidefinite optimization with a modified search direction. This modification is an attempt to decrease the value of the proximity measure, which is important to determine whether or not to perform centreing steps in the classical infeasible interior-point algorithms. Some preliminary numerical results show the benefit of the proposed algorithm as well.     

Block spin density matrix of the inhomogeneous AKLT model

We study the inhomogeneous generalization of a 1-dimensional AKLT spin chain model. Spins at each lattice site could be different. Under certain conditions, the ground state of this AKLT model is unique and is described by the Valence-Bond-Solid (VBS) state. We calculate the density matrix of a contiguous block of bulk spins in this ground state. The density matrix is independent of spins outside the block. It is diagonalized and shown to be a projector onto a subspace. We prove that for large block the density matrix behaves as the identity in the subspace. The von Neumann entropy coincides with Renyi entropy and is equal to the saturated value.      

Ensemble clustering using semidefinite programming with applications

In this paper, we study the ensemble clustering problem, where the input is in the form of multiple clustering solutions. The goal of ensemble clustering algorithms is to aggregate the solutions into one solution that maximizes the agreement in the input ensemble. We obtain several new results for this problem. Specifically, we show that the notion of agreement under such circumstances can be better captured using a 2D string encoding rather than a voting strategy, which is common among existing approaches. Our optimization proceeds by first constructing a non-linear objective function which is then transformed into a 0-1 Semidefinite program (SDP) using novel convexification techniques. This model can be subsequently relaxed to a polynomial time solvable SDP. In addition to the theoretical contributions, our experimental results on standard machine learning and synthetic datasets show that this approach leads to improvements not only in terms of the proposed agreement measure but also the existing agreement measures based on voting strategies. In addition, we identify several new application scenarios for this problem. These include combining multiple image segmentations and generating tissue maps from multiple-channel Diffusion Tensor brain images to identify the underlying structure of the brain.     

Conjugate gradients for symmetric positive semidefinite least-squares problems

The cgSLS (conjugate gradients for symmetric positive semidefinite least-squares) algorithm is presented. The algorithm exploits the cyclic property of invariant Krylov spaces to reduce the least-squares problem with a symmetric positive semidefinite matrix A to the minimization of the related energy function with the Hessian A on the range of A, so that a simple modification of the conjugate gradient (CG) method is applicable. At the same time, the algorithm generates approximations of the projection of the right-hand side to the range of A. The asymptotic rate of convergence of the new algorithm is proved to be the same as that of the CG method for the related consistent problem. An error bound in terms of the square root of the regular condition number of A is also given. The performance of the algorithm is demonstrated by numerical experiments.     

A maximum likelihood approach to density estimation with semidefinite programming

Density estimation plays an important and fundamental role in pattern recognition, machine learning, and statistics. In this article, we develop a parametric approach to univariate (or low-dimensional) density estimation based on semidefinite programming (SDP). Our density model is expressed as the product of a nonnegative polynomial and a base density such as normal distribution, exponential distribution, and uniform distribution. When the base density is specified, the maximum likelihood estimation of the polynomial is formulated as a variant of SDP that is solved in polynomial time with the interior point methods. Since the base density typically contains just one or two parameters, computation of the maximum likelihood estimate reduces to a one- or two-dimensional easy optimization problem with this use of SDP. Thus, the rigorous maximum likelihood estimate can be computed in our approach. Furthermore, such conditions as symmetry and unimodality of the density function can be easily handled within this framework. AIC is used to choose the best model. Through applications to several instances, we demonstrate flexibility of the model and performance of the proposed procedure. Combination with a mixture approach is also presented. The proposed approach has possible other applications beyond density estimation. This point is clarified through an application to the maximum likelihood estimation of the intensity function of a nonstationary Poisson process.     

Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme

This paper proposes two robust binary quadratically constrained quadratic programs (BQCQP) for wireless Orthogonal Frequency Division Multiple Access (OFDMA) networks. The first one is based on a scenario uncertainty approach from Kouvelis and Yu [1] and the second is based on an interval uncertainty approach from Bertsimas and Sim [2]. Both robust models allow to decide what modulations and what sub-carriers are going to be used by a particular user in the system depending on its bit rate requirements. Thus, we derive two robust semidefinite relaxations to compute lower bounds. Our numerical results show, in average near optimal integrality gaps of 4.12% and 1.15% under the scenario and interval approach when compared to the optimal solution of the problem derived by linearizing the two quadratic models with Fortet linearization method. Some comparison between the two robust approaches is also provided.     

Asset portfolio optimization using fuzzy mathematical programming

By morphing mean-variance optimization (MVO) portfolio model into semi-absolute deviation (SAD) model, we apply multi criteria decision making (MCDM) via fuzzy mathematical programming to develop comprehensive models of asset portfolio optimization (APO) for the investors’ pursuing either of the aggressive or conservative strategies.     

Restoration of matrix fields by second-order cone programming

Summary Wherever anisotropic behavior in physical measurements or models is encountered matrices provide adequate means to describe this anisotropy. Prominent examples are the diffusion tensor magnetic resonance imaging in medical imaging or the stress tensor in civil engineering. As most measured data these matrix-valued data are also polluted by noise and require restoration. The restoration of scalar images corrupted by noise via minimization of an energy functional is a well-established technique that offers many advantages. A convenient way to achieve this minimization is second-order cone programming (SOCP). The goal of this article is to transfer this method to the matrix-valued setting. It is shown how SOCP can be applied to minimize various energy functionals defined for matrix fields. These functionals couple the different matrix channels taking into account the relations between them. Furthermore, new functionals for the regularization of matrix data are proposed and the corresponding Euler–Lagrange equations are derived by means of matrix differential calculus. Numerical experiments substantiate the usefulness of the proposed methods for the restoration of matrix fields.