Shor’s r-algorithm is an iterative method for unconstrained optimization, designed for minimizing nonsmooth functions, for which its reported success has been considerable. Although some limited convergence results are known, nothing seems to be known about the algorithm’s rate of convergence, even in the smooth case. We study how the method behaves on convex quadratics, proving … Read more
We consider relaxations for nonconvex quadratically constrained quadratic programming (QCQP) based on semidefinite programming (SDP) and the reformulation-linearization technique (RLT). From a theoretical standpoint we show that the addition of a semidefiniteness condition removes a substantial portion of the feasible region corresponding to product terms in the RLT relaxation. On test problems we show that … Read more
Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze two algorithms for the problem of computing a $(1 + \eps)$-approximation to the radius of the minimum enclosing ball of $\cA$. The first algorithm is closely related to the Frank-Wolfe algorithm with a proper initialization applied to the dual formulation of … Read more
Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation … Read more
The classical parameterised integer feasibility problem is as follows. Given a rational matrix $A \in \mathbb{Q}^{m \times n}$ and a rational polyhedron $Q \subseteq \mathbb{R}^m$, decide, whether there exists a point $b \in Q$ such that $A x \leq b$ is integer infeasible. Our main result is a polynomial algorithm to solve a slightly more … Read more
In this work, a semi-obnoxious facility must be located in the Euclidean plane to give service to a group of customers. Simultaneously, a set of populated areas, with shapes approximated via polygons, must be protected from the negative effects derived from that facility. The problem is formulated as a margin maximization model, following a strategy … Read more
We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l_1-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian … Read more
A recursive trust-region method is introduced for the solution of bound-constrained nonlinear nonconvex optimization problems for which a hierarchy of descriptions exists. Typical cases are infinite-dimensional problems for which the levels of the hierarchy correspond to discretization levels, from coarse to fine. The new method uses the infinity norm to define the shape of the … Read more
The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are based on Branch-and-Price, with lower bounds computed by Dantzig-Wolfe reformulation and column generation. In this paper we propose a … Read more
In a paper published 1978, McEliece, Rodemich and Rumsey improved Lov\’asz’ bound for the Maximum Clique Problem. This strengthening has become well-known under the name Lov\’asz-Schrijver bound and is usually denoted by $\theta’$. This article now deals with situations where this bound is not exact. To provide instances for which the gap between this bound … Read more