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
We extend Nesterov’s semidefinite programming (SDP) characterization of the cone of functions that can be expressed as sums of squares (SOS) of functions in finite dimensional linear functional spaces. Our extension is to algebraic systems that are endowed with a binary operation which map two elements of a finite dimensional vector space to another vector … Read more
In this paper we discuss convex underestimators for bivariate functions. We first present a method for deriving convex envelopes over the simplest two-dimensional polytopes, i.e., triangles. Next, we propose a technique to compute the value at some point of the convex envelope over a general two-dimensional polytope, together with a supporting hyperplane of the convex … Read more
Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. CitationTechnical Report CS-09-02, Department of … Read more
The algebraic reformulation of the BMV conjecture is equivalent to a family of dimensionfree tracial inequalities involving positive semidefinite matrices. Sufficient conditions for these to hold in the form of algebraic identities involving polynomials in noncommuting variables have been given by Markus Schweighofer and the second author. Later the existence of these certificates has been … Read more
We use smoothing techniques to solve approximately mildly structured semidefinite programs with many constraints. As smoothing techniques require a specific problem format, we introduce an alternative problem formulation that fulfills the structural assumptions. The resulting algorithm has a complexity that depends linearly both on the number of constraints and on the inverse of the accuracy. … Read more