We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more
The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more
In this paper we propose an inexact proximal point method to solve constrained minimization problems with locally Lipschitz quasiconvex objective functions. Assuming that the function is also bounded from below, lower semicontinuous and using proximal distances, we show that the sequence generated for the method converges to a stationary point of the problem. Citation July … Read more
In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more
In constraining iterative processes, the algorithmic operator of the iterative process is pre-multiplied by a constraining operator at each iterative step. This enables the constrained algorithm, besides solving the original problem, also to find a solution that incorporates some prior knowledge about the solution. This approach has been useful in image restoration and other image … Read more
In this paper we propose a randomized block coordinate non-monotone gradient (RBCNMG) method for minimizing the sum of a smooth (possibly nonconvex) function and a block-separable (possibly nonconvex nonsmooth) function. At each iteration, this method randomly picks a block according to any prescribed probability distribution and typically solves several associated proximal subproblems that usually have … Read more
This paper considers a bilevel nonlinear program (NLP) whose lower-level problem satisfies a linear independence constraint qualification (LICQ) and a strong second-order condition (SSOC). One would expect the resulting mathematical program with complementarity constraints (MPCC), whose constraints are the first-order optimality conditions of the lower-level NLP, to satisfy an MPEC-LICQ. We provide an example which … Read more
The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm … Read more
For a long time, the bilevel programming problem has essentially been considered as a special case of mathematical programs with equilibrium constraints (MPECs), in particular when the so-called KKT reformulation is in question. Recently though, this widespread believe was shown to be false in general. In this paper, other aspects of the difference between both … Read more
The problem of finding sparse solutions to underdetermined systems of linear equations is very common in many fields as e.g. in signal/image processing and statistics. A standard tool for dealing with sparse recovery is the ℓ1-regularized least-squares approach that has recently attracted the attention of many researchers. In this paper, we describe a new version … Read more