The rank function $\rank(\cdot)$ is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of $\rank(\cdot)$, and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the … Read more
Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more
We show that the simplex method can be interpreted as a cutting-plane method, assumed that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We compare the classic Dantzig pricing rule and the rule that derives from the … Read more
In the paper we prove that any nonconvex quadratic problem over some set $K\subset \mathbb{R}^n$ with additional linear and binary constraints can be rewritten as linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and … Read more
In this paper we focus on robust linear optimization problems with uncertainty regions defined by phi-divergences (for example, chi-squared, Hellinger, Kullback-Leibler). We show how uncertainty regions based on phi-divergences arise in a natural way as confidence sets if the uncertain parameters contain elements of a probability vector. Such problems frequently occur in, for example, optimization … Read more
Let $K \subset \mathbb R^n$ be a regular convex cone, let $e_1,\dots,e_n \in \partial K$ be linearly independent points on the boundary of a compact affine section of the cone, and let $x^* \in K^o$ be a point in the relative interior of this section. For $k = 1,\dots,n$, let $l_k$ be the line through … Read more
Given a graph $G=([n],E)$ and $w\in\R^E$, consider the integer program ${\max}_{x\in \{\pm 1\}^n} \sum_{ij \in E} w_{ij}x_ix_j$ and its canonical semidefinite programming relaxation ${\max} \sum_{ij \in E} w_{ij}v_i^Tv_j$, where the maximum is taken over all unit vectors $v_i\in\R^n$. The integrality gap of this relaxation is known as the Grothendieck constant $\ka(G)$ of $G$. We present … Read more
Due to its versatility, copositive optimization receives increasing interest in the Operational Research community, and is a rapidly expanding and fertile field of research. It is a special case of conic optimization, which consists of minimizing a linear function over a cone subject to linear constraints. The diversity of copositive formulations in different domains of … Read more
Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone of all completely positive symmetric nxn matrices, and its … Read more
In traditional multi-level graph drawing – known as Sugiyama’s framework – the number of crossings is considered one of the most important goals. Herein, we propose the alternative concept of optimizing the verticality of the drawn edges. We formally specify the problem, discuss its relative merits, and show that drawings that are good w.r.t. verticality … Read more