We consider a parametric convex quadratic programming (CQP) relaxation for the quadratic knapsack problem (QKP). This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the QKP. We prove that the same perturbation approach, when applied in the context of semidefinite programming (SDP) relaxations of the QKP, cannot improve the upper bound given by the corresponding linear SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained alternating between optimizing the parametric quadratic relaxation over the perturbation and applying cutting planes generated by the valid inequalities proposed.

We present several solution techniques for the noisy single source localization problem, i.e. the Euclidean distance matrix completion problem with a single missing node to locate under noisy data. For the case that the sensor locations are fixed, we show that this problem is implicitly convex, and we provide a purification algorithm along with the SDP relaxation to solve it efficiently and accurately. For the case that the sensor locations are relaxed, we study a model based on facial reduction. We present several approaches to solve this problem efficiently, and we compare their performance with existing techniques in the literature. Our tools are semidefinite programming, Euclidean distance matrices, facial reduction, and the generalized trust region subproblem. We include extensive numerical tests.

In 1779, Leonhard Euler published a paper about Lambert's transcendental equation in the symmetric form x(alpha) - x(beta) = (alpha -beta) vx(alpha+beta). In the paper, he studied the series solution of this equation and other results based on an assumption which was not proved in the paper. Euler's paper gave the first series expanion for the so-called Lambert W function. In this work, we briefly review Euler's results and give a proof to modern standards of rigor of the series solution of Lambert's transcendental equation.