A Sum of Squares Characterization of Perfect Graphs

We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of … Read more

Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more

Presolving for Mixed-Integer Semidefinite Optimization

This paper provides a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The considered methods include adding linear constraints, bounds relying on 2 × 2 minors of the semidefinite constraints, bound tightening based on solving … Read more

Applications of stochastic mixed-integer second-order cone optimization

Second-order cone programming problems are a tractable subclass of convex optimization problems and there are known polynomial algorithms for solving them. Stochastic second-order cone programming problems have also been studied in the past decade and efficient algorithms for solving them exist. A new class of interest to optimization community and practitioners is the mixed-integer version … Read more

Optimal error bounds in the absence of constraint qualifications with applications to the p-cones and beyond

We prove tight Hölderian error bounds for all p-cones. Surprisingly, the exponents differ in several ways from those that have been previously conjectured; moreover, they illuminate p-cones as a curious example of a class of objects that possess properties in 3 dimensions that they do not in 4 or more. Using our error bounds, we … Read more

Log-domain interior-point methods for convex quadratic programming

Applying an interior-point method to the central-path conditions is a widely used approach for solving quadratic programs. Reformulating these conditions in the log-domain is a natural variation on this approach that to our knowledge is previously unstudied. In this paper, we analyze log-domain interior-point methods and prove their polynomial-time convergence. We also prove that they … Read more

Efficient Joint Object Matching via Linear Programming

Joint object matching, also known as multi-image matching, namely, the problem of finding consistent partial maps among all pairs of objects within a collection, is a crucial task in many areas of computer vision. This problem subsumes bipartite graph matching and graph partitioning as special cases and is NP-hard, in general. We develop scalable linear … Read more

Solving a Class of Cut-Generating Linear Programs via Machine Learning

Cut-generating linear programs (CGLPs) play a key role as a separation oracle to produce valid inequalities for the feasible region of mixed-integer programs. When incorporated inside branch-and-bound, the cutting planes obtained from CGLPs help to tighten relaxations and improve dual bounds. However, running the CGLPs at the nodes of the branch-and-bound tree is computationally cumbersome … Read more

Bishop-Phelps cones given by an equation in Banach spaces

In this work, we study Bishop-Phelps cones (briefly, BP cones) given by an equation in Banach spaces. Due to the special form, these cones enjoy interesting properties. We show that nontrivial BP cones given by an equation form a “large family” in some sense in any Banach space and they can be used to characterize … Read more

Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables

We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients … Read more