Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

A Solver for large-scale indefinite quadratic programs

Based on an active set strategy, a method for solving linearly constrained indefinite quadratic programs to solve the corresponding system of equations at each iteration is presented. The algorithm takes two descent directions to strictly decrease the value of objective function and obtains a suitable step to maintain feasibility. Computational results on a range of quadratic test problems are given.     

Rank restrictions on the quadratic form in indefinite quadratic programming

Summary A quadratic programming problem, whereq(x) =a ^T x +x ^T Qx is an indefinite objective function, can be solved withSwarup's approach of optimizing (c ^T x + )(d ^T x + ) only if the rank ofQ is two; ifQ is definite, the rank ofQ must be one.

---

Zusammenfassung Ein quadratisches Optimierungsproblem, in demq(x) =a ^T x +x ^T Qx eine indefinite Zielfunktion ist, kann mitSwarups Optimierungsansatz (c ^T x + )(d ^T x + ) nur gelöst werden, wenn der Rang vonQ gleich zwei ist; wennQ definit ist, muß der Rang vonQ gleich eins sein.

     

Global multi-parametric optimal value bounds and solution estimates for separable parametric programs

In this tutorial, a strategy is described for calculating parametric piecewise-linear optimal value bounds for nonconvex separable programs containing several parameters restricted to a specified convex set. The methodology is based on first fixing the value of the parameters, then constructing sequences of underestimating and overestimating convex programs whose optimal values respectively increase or decrease to the global optimal value of the original problem. Existing procedures are used for calculating parametric lower bounds on the optimal value of each underestimating problem and parametric upper bounds on the optimal value of each overestimating problem in the sequence, over the given set of parameters. Appropriate updating of the bounds leads to a nondecreasing sequence of lower bounds and a nonincreasing sequence of upper bounds, on the optimal value of the original problem, continuing until the bounds satisfy a specified tolerance at the value of the parameter that was fixed at the outset. If the bounds are also sufficiently tight over the entire set of parameters, according to criteria specified by the user, then the calculation is complete. Otherwise, another parameter value is selected and the procedure is repeated, until the specified criteria are satisfied over the entire set of parameters. A parametric piecewise-linear solution vector approximation is also obtained. Results are expected in the theory, computations, and practical applications. The general idea of developing results for general problems that are limits of results that hold for a sequence of well-behaved (e.g., convex) problems should be quite fruitful.     

A computational comparison of some branch and bound methods for indefinite quadratic programs

The aim of this paper is to discuss different branch and bound methods for solving indefinite quadratic programs. In these methods the quadratic objective function is decomposed in a d.c. form and the relaxations are obtained by linearizing the concave part of the decomposition. In this light, various decomposition schemes have been considered and studied. The various branch and bound solution methods have been implemented and compared by means of a deep computational test.      

Lipschitz continuity of the optimal value function and KKT solution set in indefinite quadratic programs

When all the involved data in indefinite quadratic programs change simultaneously,we show the locally Lipschtiz continuity of the KKT set of the quadratic programming problem firstly, then we establish the locally Lipschtiz continuity of the KKT solution set. Finally, the similar conclusion for the corresponding optimal value function is obtained.     

On lower bounds for a class of quadratic 0, 1 programs

We present a new method of obtaining lower bounds for a class of quadratic 0, 1 programs that includes the quadratic assignment problem. The method generates a monotonic sequence of lower bounds and may be interpreted as a Lagrangean dual ascent procedure. We report on a computational comparison of our bounds with earlier work in [2] based on subgradient techniques.     

Approximation algorithms for indefinite quadratic programming

We consider-approximation schemes for indefinite quadratic programming. We argue that such an approximation can be found in polynomial time for fixed andt, wheret denotes the number of negative eigenvalues of the quadratic term. Our algorithm is polynomial in 1/ for fixedt, and exponential int for fixed. We next look at the special case of knapsack problems, showing that a more efficient (polynomial int) approximation algorithm exists.Part of this work was done while the author was visiting Sandia National Laboratories, Albuquerque, New Mexico, supported by the U.S. Department of Energy under contract DE-AC04-76DP00789. Part of this work was also supported by the Applied Mathematical Sciences Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000 and in part by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS 8920550.     

A direct active set algorithm for large sparse quadratic programs with simple bounds

We show how a direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. All of the necessary factorizations can be carried out in a static data structure that is set up before the numeric computation begins. The space required for these factorizations is no larger than that required for a single sparse Cholesky factorization of the Hessian of the quadratic. We propose several improvements to this basic algorithm: a new way to find a search direction in the indefinite case that allows us to free more than one variable at a time and a new heuristic method for finding a starting point. These ideas are motivated by the two-norm trust region problem. Additionally, we also show how projection techniques can be used to add several constraints to the active set at each iteration. Our experimental results show that an algorithm with these improvements runs much faster than the basic algorithm for positive definite problems and finds local minima with lower function values for indefinite problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000.     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU ² log(Un ² m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ.     

Tight bounds for popping algorithms

We sharpen run‐time analysis for algorithms under the partial rejection sampling framework. Our method yields improved bounds for: the cluster‐popping algorithm for approximating all‐terminal network reliability; the cycle‐popping algorithm for sampling rooted spanning trees; and the sink‐popping algorithm for sampling sink‐free orientations. In all three applications, our bounds are not only tight in order, but also optimal in30 constants.     

New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds

There are many applications related to singly linearly constrained quadratic programs subjected to upper and lower bounds. In this paper, a new algorithm based on secant approximation is provided for the case in which the Hessian matrix is diagonal and positive definite. To deal with the general case where the Hessian is not diagonal, a new efficient projected gradient algorithm is proposed. The basic features of the projected gradient algorithm are: 1) a new formula is used for the stepsize; 2) a recently-established adaptive non-monotone line search is incorporated; and 3) the optimal stepsize is determined by quadratic interpolation if the non-monotone line search criterion fails to be satisfied. Numerical experiments on large-scale random test problems and some medium-scale quadratic programs arising in the training of Support Vector Machines demonstrate the usefulness of these algorithms. This work was supported by the EPRSC in UK (no. GR/R87208/01) and the Chinese NSF grants (no. 10171104 and 40233029).     

Class numbers of indefinite binary quadratic forms

We determine the asymptotic average sizes of the class numbers of indefinite binary quadratic forms when ordered by the sizes of their corresponding fundamental units. The proofs make use of the Selberg trace formula.     

The distribution of hermitian indefinite quadratic forms

Hermitian quadratic forms in complex Gaussian random variables is considered in this article. Various representations of the exact densities for the central, non central, singular and nonsingular cases are given. Particular cases are shown to agree with the results obtained by others in connection with various applications in communication theory, multichannel antennas, vehicular transportations and other related problems     

Local minima for indefinite quadratic knapsack problems

We consider the complexity of finding a local minimum for the nonconvex Quadratic Knapsack Problem. Global minimization for this example of quadratic programming is NP-hard. Moré and Vavasis have investigated the complexity of local minimization for the strictly concave case of QKP; here we extend their algorithm to the general indefinite case. Our main result is an algorithm that computes a local minimum in O(n(logn)²) steps. Our approach involves eliminating all but one of the convex variables through parametrization, yielding a nondifferentiable problem. We use a technique from computational geometry to address the nondifferentiable problem.Supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, Department of Energy, under contract W-31-109-Eng-38, in part by a Fannie and John Hertz Foundation graduate fellowship, and in part by Department of Energy grant DE-FG02-86ER25013.A000.     

The minima of indefinite binary quadratic forms

The study of the minima of indefinite binary quadratic forms has a long history and the classical results concerning the determination of such minima are stated in terms of the continued fraction expansion of the roots. These results are recast in geometric terms. Using this, and well-known geometric properties of the modular group, some necessary and sufficient conditions for a certain class of quadratic forms to have positive unattained minima are obtained.     

On minima of rational indefinite quadratic forms

Let f(x) be an indefinite quadratic form with real coefficients in n variables with nonzero determinant d. The collection of all values of $\text{v(f) = |d|}{}^{\mathrm{<mtext>?1</mtext><mtext>n</mtext>}}\text{inf}\text{|f(x)|}$, where infimum is taken over x ∈ Zⁿ such that f(x) ≠ 0 (x ≠ 0) is called the spectrum of nonzero minima (spectrum of minima) of such forms. The spectrum is said to be discrete if for every δ > 0, there are only finitely many values of v(f) > δ. It is proved that for rational quadratic forms in n ≥ 3 variables and real quadratic forms in n ≥ 21 variables the spectra of nonzero minima are discrete. Also the spectra of minima of indefinite ternary and quaternary rational quadratic forms are discrete.