We introduce a new masked spectral bound for the maximum-entropy sampling problem. This bound is a continuous generalization of the very effective spectral partition bound. Optimization of the masked spectral bound requires the minimization of a nonconvex, nondifferentiable function over a semidefiniteness constraint. We describe a nonlinear affine scaling algorithm to approximately minimize the bound. … Read more
Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more
This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more
This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \|X_{\cT}(\nu)\|, \|S_{\cT}(\nu)\| \} … Read more
This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in … Read more
This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown … Read more
The standard quadratic program (QPS) is $\min_{x\in\Delta} x’Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One … Read more
We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, or the (partial) closure of such a set (constrained case). We show that in the univariate case ($n=1$), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced … Read more
An interesting recent trend in optimization is the application of semidefinite programming techniques to new classes of optimization problems. In particular, this trend has been successful in showing that under suitable circumstances, polynomial optimization problems can be approximated via a sequence of semidefinite programs. Similar ideas apply to conic optimization over the cone of copositive … Read more
Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for … Read more