A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A note on biquadratic forms

It is shown that semidefinite quadratic forms in two by n variables are sums of squares of bilinear forms.     

Approximating quadratic programming with bound and quadratic constraints

Received May 20, 1997 / Revised version received March 9, 1998 Published online October 9, 1998     

A note on moment inequality for quadratic forms

Moment inequality for quadratic forms of random vectors is of particular interest in covariance matrix testing and estimation problems. In this paper, we prove a Rosenthal-type inequality, which exhibits new features and certain improvement beyond the unstructured Rosenthal inequality of quadratic forms when dimension of the vectors increases without bound. Applications to test the block diagonal structures and detect the sparsity in the high-dimensional covariance matrix are presented.     

A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality. Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999     

Bound constrained quadratic programming via piecewise quadratic functions

1 , the smallest eigenvalue of a symmetric, positive definite matrix, and is solved by Newton iteration with line search. The paper describes the algorithm and its implementation including estimation of λ₁, how to get a good starting point for the iteration, and up- and downdating of Cholesky factorization. Results of extensive testing and comparison with other methods for constrained QP are given. Received May 1, 1997 / Revised version received March 17, 1998 Published online November 24, 1998     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

An interior Newton method for quadratic programming

We propose a new (interior) approach for the general quadratic programming problem. We establish that the new method has strong convergence properties: the generated sequence converges globally to a point satisfying the second-order necessary optimality conditions, and the rate of convergence is 2-step quadratic if the limit point is a strong local minimizer. Published alternative interior approaches do not share such strong convergence properties for the nonconvex case. We also report on the results of preliminary numerical experiments: the results indicate that the proposed method has considerable practical potential. Received October 11, 1993 / Revised version received February 20, 1996 Published online July 19, 1999     

Testing optimality for quadratic 0-1 problems

Received June 4, 1996 / Revised version received November 19, 1997 Published online November 24, 1998     

On quasi-reduced quadratic forms

With the help of continued fractions, we plan to list all the elements of the set Q△ = {aX2 ＋ bXY ＋ cY2 ： a,b, c ∈Z, b2 - 4ac = △ with 0 ≤ b 〈 √△}of quasi-reduced quadratic forms of fundamental discriminant △. As a matter of fact, we show that for each reduced quadratic form f = aX2 ＋ bXY ＋ cY2 = （a, b, c） of discriminant △〉0（and of sign σ（f） equal to the sign of a）, the quadratic forms associated with f and defined by {〈a＋bu＋cu2,b＋2cu.c〉},with 1≤σ（f）u≤b/2｜c｜ （whenever they exist）, 〈c,-b-2cu,a＋bu＋cu2〉 with b/2｜c｜≤σ（f）u≤[w（f）]=[b＋√△/2｜c｜], are all different from one another and build a set I（f） whose cardinality is #I（f）={1＋[ω（f）],when（2c）｜b,[ω（f）],when （2c）｜b. If f and g are two different reduced quadratic forms, we show that I（f） ∩ I（g） = Ф. Our main result is that the set Q△ is given by the disjoint union of all I（f） with f running through the set of reduced quadratic forms of discriminant △〉0. This allows us to deduce a formula for #（Q△） involving sums of partial quotients of certain continued fractions.     

Continuity properties of the Karush-Kuhn-Tucker point set in quadratic programming problems

Received March 18, 1996 / Revised version received August 8, 1997 Published online November 24, 1998     

On the definity of quadratic forms subject to linear constraints

A short proof is given of the necessary and sufficient conditions for the positivity and nonnegativity of a quadratic form subject to linear constraints.     

A characterization of ill-posed data instances for convex programming

Given a data instance of a convex program, we provide a collection of conic linear systems such that the data instance is ill-posed if and only if at least one of those systems is satisfied. This collection of conic linear systems is derived from a characterization of the boundary of the set of primal and dual feasible data instances associated with the given convex program. Received: September 1998 / Accepted: August 2000?Published online October 26, 2001     

Basis- and partition identification for quadratic programming and linear complementarity problems

Optimal solutions of interior point algorithms for linear and quadratic programming and linear complementarity problems provide maximally complementary solutions. Maximally complementary solutions can be characterized by optimal partitions. On the other hand, the solutions provided by simplex–based pivot algorithms are given in terms of complementary bases. A basis identification algorithm is an algorithm which generates a complementary basis, starting from any complementary solution. A partition identification algorithm is an algorithm which generates a maximally complementary solution (and its corresponding partition), starting from any complementary solution. In linear programming such algorithms were respectively proposed by Megiddo in 1991 and Balinski and Tucker in 1969. In this paper we will present identification algorithms for quadratic programming and linear complementarity problems with sufficient matrices. The presented algorithms are based on the principal pivot transform and the orthogonality property of basis tableaus. Received April 9, 1996 / Revised version received April 27, 1998? Published online May 12, 1999     

A note on Spector's quantifier-free rule of extensionality

In this note we show that the so-called weakly extensional arithmetic in all finite types, which is based on a quantifier-free rule of extensionality due to C. Spector and which is of significance in the context of G?del"s functional interpretation, does not satisfy the deduction theorem for additional axioms. This holds already for Π⁰ ₁-axioms. Previously, only the failure of the stronger deduction theorem for deductions from (possibly open) assumptions (with parameters kept fixed) was known. Received: 11 March 1999 / Published online: 21 December 2000     

Universal octonary diagonal forms over some real quadratic fields

In this paper, we will prove there are infinitely many integers n such that n ²— 1 is square-free and admits universal octonary diagonal quadratic forms. Received: November 2, 1998.     

Extensions of representations of integral quadratic forms

Let N and M be quadratic ?-lattices, and K be a sublattice of N. A representation σ:K→M is said to be extensible to N if there exists a representation ρ:N→M such that ρ | _K =σ. We prove in this paper a local–global principle for extensibility of representation, which is a generalization of the main theorems on representations by positive definite ?-lattices by Hsia, Kitaoka and Kneser (J. Reine Angew. Math. 301:132–141, 1978) and Jöchner and Kitaoka (J. Number Theory 48:88–101, 1994). Applications to almost n-universal lattices and systems of quadratic equations with linear conditions are discussed.