Given linear matrix inequalities (LMIs) L_1 and L_2, it is natural to ask: (Q1) when does one dominate the other, that is, does L_1(X) PsD imply L_2(X) PsD? (Q2) when do they have the same solution set? Such questions can be NP-hard. This paper describes a natural relaxation of an LMI, based on substituting matrices … Read more
Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual … Read more
Channel-optimized index assignment of source codewords is arguably the simplest way of improving transmission error resilience, while keeping the source and/or channel codes intact. But optimal design of index assignment is an in- stance of quadratic assignment problem (QAP), one of the hardest optimization problems in the NP-complete class. In this paper we make a … Read more
The class of sufficient matrices is important in the study of the linear complementarity problem(LCP) – some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap. In this paper we show that the handicap of a sufficient matrix may be exponential … Read more
The SDPA (SemiDefinite Programming Algorithm) Project launched in 1995 has been known to provide high-performance packages for solving large-scale Semidefinite Programs (SDPs). SDPA Ver. 6 solves efficiently large-scale dense SDPs, however, it required much computation time compared with other software packages, especially when the Schur complement matrix is sparse. SDPA Ver. 7 is now completely … Read more
Interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In … Read more
Given a compact parameter set $Y\subset R^p$, we consider polynomial optimization problems $(P_\y$) on $R^n$ whose description depends on the parameter $y\in Y$. We assume that one can compute all moments of some probability measure $\varphi$ on $Y$, absolutely continuous with respect to the Lebesgue measure (e.g. $Y$ is a box or a simplex and … Read more
We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness … Read more
We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature — the cut, boolean quadric, multicut and clique partitioning polytopes — are faces of binary … Read more
We present a mathematical framework for the so-called multidisciplinary free material optimization (MDFMO) problems, a branch of structural optimization in which the full material tensor is considered as a design variable. We extend the original problem statement by a class of generic constraints depending either on the design or on the state variables. Among the … Read more