Log-det semidefinite programming (SDP) problems are optimization problems that often arise from Gaussian graphic models. A log-det SDP problem with an l1-norm term has been examined in many methods, and the dual spectral projected gradient (DSPG) method by Nakagaki et al.~in 2020 is designed to efficiently solve the dual problem of the log-det SDP by … Read more
We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi-infinite QCQPs). Sufficient conditions for the exactness of SDP relaxations for QCQPs with finitely many constraints have been extensively studied, notably by Argue … Read more
We derive analytic formulas for the alternating projection method applied to the cone \(S^n_+\) of positive semidefinite matrices and an affine subspace. More precisely, we find recursive relations on parameters representing a sequence constructed by the alternating projection method. By applying these formulas, we analyze the alternating projection method in detail and show that the … Read more
Given a family of linear constraints and a linear objective function one can consider whether to apply a Linear Programming (LP) algorithm or use a Linear Superiorization (LinSup) algorithm on this data. In the LP methodology one aims at finding a point that fulfills the constraints and has the minimal value of the objective function … Read more
The Lov\’asz theta function $\theta(G)$ provides a very good upper bound on the stability number of a graph $G$. It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the … Read more
We introduce a family of symmetric convex bodies called generalized ellipsoids of degree \(d\) (GE-\(d\)s), with ellipsoids corresponding to the case of \(d=0\). Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids. We show that the conditions that the parameters of a GE must satisfy can be checked in strongly polynomial time, … Read more
We study quadratic programs with m ball constraints, and the strength of a lifted convex relaxation for it recently proposed by Burer (2024). Burer shows this relaxation is exact when m=2. For general m, Burer (2024) provides numerical evidence that this lifted relaxation is tighter than the Kronecker product based Reformulation Linearization Technique (RLT) inequalities … Read more
Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana’s dual has the following remarkable features: i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the … Read more
Finding good feasible points is crucial in mixed-integer programming. For this purpose we combine a sufficient condition for consistency, called granularity, with the moment-/sos-hierarchy from polynomial optimization. If the mixed-integer problem is granular, we obtain feasible points by solving continuous polynomial problems and rounding their optimal points. The moment-/sos-hierarchy is hereby used to solve those … Read more
Facial reduction is a pre-processing method aimed at reformulating a problem to ensure strict feasibility. The importance of constructing a robust model is widely recognized in the literature, and facial reduction has emerged an attractive approach for achieving robustness. In this note, we outline a facial reduction algorithm for a standard spectrahedra, the intersection of … Read more