We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the … Read more
Embedding randomization procedures in the Alternating Direction Method of Multipliers (ADMM) has recently attracted an increasing amount of interest as a remedy to the fact that the direct n-block generalization of ADMM is not necessarily convergent ($n \geq 3$). Even if, in practice, the introduction of such techniques could mitigate the diverging behaviour of the … Read more
We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation – transforming the original problem into a constrained problem in a higher dimensional space – to define a sequence of suitable quadratic penalty subproblems with increasing penalty … Read more
Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest … Read more
A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more
We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball $r \le \|x\| \le R$ intersected with a full-dimensional second order cone (SOC) constraint of the form $\|x – c\| \le b^T x – a$. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) … Read more
The focus in this work is interior-point methods for quadratic optimization problems with linear inequality constraints where the system of nonlinear equations that arise are solved with Newton-like methods. In particular, the concern is the system of linear equations to be solved at each iteration. Newton systems give high quality solutions but there is an … Read more
A small polygon is a polygon of unit diameter. The maximal area of a small polygon with $n=2m$ vertices is not known when $m\ge 7$. Finding the largest small $n$-gon for a given number $n\ge 3$ can be formulated as a nonconvex quadratically constrained quadratic optimization problem. We propose to solve this problem with a … Read more
The routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant maximum number of requests by assigning lightpaths at minimum network resource usage level, while ensuring the provided services remain functional in case of a … Read more
We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a … Read more