In this paper, a subspace limited BFGS algorithm is proposed for bound constrained optimization. The global convergence will be established under some suitable conditions. Numerical results show that this method is more competitive than the normal method does. ArticleDownload View PDF
We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more
Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the … Read more
We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability distributions over these instances–including the uniform distribution–we show several … Read more
Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie … Read more
Solvers for semidefinite programming (SDP) have evolved a great deal in the last decade, and their development continues. In order to further support and encourage this development, we present a new test set of SDP instances. These instances arise from recent applications of SDP in coding theory, computational geometry, graph theory and structural design. Most … Read more
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more
We extend a recently proposed alternating minimization algorithm to the case of recovering blurry multichannel (color) images corrupted by impulsive rather than Gaussian noise. The algorithm minimizes the sum of a multichannel extension of total variation (TV), either isotropic or anisotropic, and a data fidelity term measured in the L1-norm. We derive the algorithm by … Read more
Semidefinite relaxations often provide excellent starting points for nonconvex problems with multiple local minimizers. This work aims to find a local minimizer within a certain neighborhood of the starting point and with a small objective value. Several approaches are motivated and compared with each other. CitationReport, Mathematisches Institut, Universitaet Duesseldorf, August 2008.ArticleDownload View PDF
In this paper we derive new upper bounds for the densities of measurable sets in R^n which avoid a finite set of prescribed distances. The new bounds come from the solution of a linear programming problem. We apply this method to obtain new upper bounds for measurable sets which avoid the unit distance in dimensions … Read more