In an important paper, Burer recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum … Read more
We present an alternating direction method based on an augmented Lagrangian framework for solving semidefinite programming (SDP) problems in standard form. At each iteration, the algorithm, also known as a two-splitting scheme, minimizes the dual augmented Lagrangian function sequentially with respect to the Lagrange multipliers corresponding to the linear constraints, then the dual slack variables … Read more
We consider a generalization of the well known greedy algorithm, called $m$-step greedy algorithm, where $m$ elements are examined in each iteration. When $m=1$ or $2$, the algorithm reduces to the standard greedy algorithm. For $m=3$ we provide a complete characterization of the independence system, called trioid, where the $m$-step greedy algorithm guarantees an optimal … Read more
This paper proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with N nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2, …, … Read more
In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. We propose primal-dual interior point methods based on the unscaled and scaled Newton methods, which correspond to the AHO, HRVW/KSH/M and NT search directions in linear SDP problems. We analyze local behavior of our proposed methods and show their … Read more
A so-called Standard Bi-Quadratic Optimization Problem (StBQP) consists in minimizing a bi-quadratic form over the Cartesian product of two simplices (so this is different from a Bi-Standard QP where a quadratic function is minimized over the same set). An application example arises in portfolio selection. In this paper we present a bi-quartic formulation of StBQP, … Read more
The binding of peptide fragments of extracellular peptides to class II MHC is a crucial event in the adaptive immune response. Each MHC allotype generally binds a distinct subset of peptides and the enormous number of possible peptide epitopes prevents their complete experimental characterization. Computational methods can utilize the limited experimental data to predict the … Read more
In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second moment matrix of the nonnegative objective coefficients is assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a … Read more
We consider the complexity of gap-free duals in semidefinite programming. Using the theory of homogeneous cones we provide a new representation of Ramana’s gap-free dual and show that the new formulation has a much better complexity than originally proved by Ramana. CitationCOR@L Technical Report, Lehigh UniversityArticleDownload View PDF
Expanding an electrical transmission network requires heavy investments that need to be carefully planned, often at a regional or national level. We study relevant theoretical and practical aspects of transmission expansion planning, set as a bilinear programming problem with mixed 0-1 variables. We show that the problem is NP-hard and that, unlike the so-called Network … Read more