A lower bound on the performance of the quadratic discriminant function

The quadratic discriminant function is often used to separate two classes of points in a multidimensional space. When the two classes are normally distributed, this results in the optimum separation. In some cases however, the assumption of normality is a poor one and the classification error is increased. The current paper derives an upper bound for the classification error due to a quadratic decision surface. The bound is strict when the class means and covariances and the quadratic discriminant surface satisfy certain specified symmetry conditions.     

New lower bound for the Hilbert number in piecewise quadratic differential systems

We study the number of limit cycles bifurcating from a piecewise quadratic system. All the differential systems considered are piecewise in two zones separated by a straight line. We prove the existence of 16 crossing limit cycles in this class of systems. If we denote by $H_p(n)$ the extension of the Hilbert number to degree n piecewise polynomial differential systems, then $H_p(2)\ge 16$. As fas as we are concerned, this is the best lower bound for the quadratic class. Moreover, in the studied cases, all limit cycles appear nested bifurcating from a period annulus of a isochronous quadratic center.     

A metrical lower bound on the star discrepancy of digital sequences

In this paper we study uniform distribution properties of digital sequences over a finite field of prime order. In 1998 it was shown by Larcher that for almost all $s$ -dimensional digital sequences $\mathcal{S }$ the star discrepancy $D_N^*$ satisfies an upper bound of the form $D_N^*(\mathcal{S })=O((\log N)^s (\log \log N)^{2+\varepsilon })$ for any $\varepsilon >0$ . Generally speaking it is much more difficult to obtain good lower bounds for specific sequences than upper bounds. Here we show that Larchers result is best possible up to some $\log \log N$ term. More detailed, we prove that for almost all $s$ -dimensional digital sequences $\mathcal{S }$ the star discrepancy satisfies $D_N^*(\mathcal{S }) \ge c(q,s) (\log N)^s \log \log N$ for infinitely many $N \in \mathbb{N }$ , where $c(q,s)>0$ only depends on $q$ and $s$ but not on $N$ .     

Some properties of the lower bound of optimal values in interval convex quadratic programming

One of the fundamental problems in interval quadratic programming is to compute the range of optimal values. In this paper, we derive some results on the lower bound of interval convex quadratic programming. We first develop complementary slackness conditions of a quadratic program and its Dorn dual. Then, some interesting and useful characteristics of the lower bound of interval quadratic programming are established based on these conditions. Finally, illustrative examples and remarks are given to get an insight into the problem discussed.     

An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided.     

Approximating quadratic programming with bound and quadratic constraints

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

Gilmore-Lawler bound of quadratic assignment problem

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.      

The lower bound on independence number

Let G be a graph with degree sequence ( d_v). If the maximum degree of any subgraph induced by a neighborhood of G is at most m, then the independence number of G is at least , where f_m+1( x) is a function greater than for x> 0. For a weighted graph G = ( V, E, w), we prove that its weighted independence number (the maximum sum of the weights of an independent set in G) is at least where w_v is the weight of v.     

The lower bound of the number of non-overlapping triangles

András Bezdek proved that if a convexn-gon andn points are given, then the points and the sides of the polygon can be renumbered so that at least [n/3] triangles spanned by theith point and theith side (i=1,2,…n) are mutually non-overlapping. In this paper, we show that at least [n/2] mutually non-overlapping triangles can be constructed. This lower bound is best possible.     

On the structure of quadratic congruential sequences

Sequences of integers defined by a quadratic congruential formula are divided into non-overlapping subsequences of length d. The structure of the set of the resulting points in the d-dimensional Euclidean space R^d is studied. The analysis is restricted to the case of sequences with maximal period length since such sequences are of special interest in connection with pseudo random number generation.     

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     

Lucas sequences and quadratic orders

We consider the Lucas sequences (U _n ) _{n ≥ 0} defined by U ₀ = 0, U ₁ = 1, and U _n =  PU _n–1 – QU _n–2 for non-zero integral parameters P, Q such that Δ = P ² – 4Q is not a square. We use the arithmetic of the quadratic order with discriminant Δ to investigate the zeros and the period length of the sequence (U _n ) _{n ≥ 0} modulo a positive integer d coprime to Q. For a prime p not dividing Q, we give precise formulas for p-powers, we determine the p-adic value of U _n , and we connect the results with class number relations for quadratic orders.     

Upper bound for the size of quadratic Siegel disks

If is an irrational number, we let {p_n/q_n}_n0, be the approximants given by its continued fraction expansion. The Bruno series B() is defined as

Algorithms for bound constrained quadratic programming problems

Summary We present an algorithm which combines standard active set strategies with the gradient projection method for the solution of quadratic programming problems subject to bounds. We show, in particular, that if the quadratic is bounded below on the feasible set then termination occurs at a stationary point in a finite number of iterations. Moreover, if all stationary points are nondegenerate, termination occurs at a local minimizer. A numerical comparison of the algorithm based on the gradient projection algorithm with a standard active set strategy shows that on mildly degenerate problems the gradient projection algorithm requires considerable less iterations and time than the active set strategy. On nondegenerate problems the number of iterations typically decreases by at least a factor of 10. For strongly degenerate problems, the performance of the gradient projection algorithm deteriorates, but it still performs better than the active set method.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer programming formulation. These observations lead to a new lower bound scheme that yields fast approximation of the time-indexed bound. Several techniques are developed to facilitate the effective use of the new lower bound in branch-and-bound. Numerical experiments are conducted on 375 benchmark problems of the total weighted tardiness problem from OR-Library. Results obtained with our new method are spectacular; we are able to solve all 125 open problems to optimality.     

Rigidity and the lower bound theorem 1

Summary For an arbitrary triangulated (d-1)-manifold without boundaryC withf ₀ vertices andf ₁ edges, define . Barnette proved that (C)0. We use the rigidity theory of frameworks and, in particular, results related to Cauchy's rigidity theorem for polytopes, to give another proof for this result. We prove that ford4, if (C)=0 thenC is a triangulated sphere and is isomorphic to the boundary complex of a stacked polytope. Other results: (a) We prove a lower bound, conjectured by Björner, for the number ofk-faces of a triangulated (d-1)-manifold with specified numbers of interior vertices and boundary vertices. (b) IfC is a simply connected triangulatedd-manifold,d4, and (lk(v, C))=0 for every vertexv ofC, then (C)=0. (lk(v,C) is the link ofv inC.) (c) LetC be a triangulatedd-manifold,d3. Then Ske1₁( _d+2) can be embedded in skel₁ (C) iff (C)>0. ( _d is thed-dimensional simplex.) (d) IfP is a 2-simpliciald-polytope then . Related problems concerning pseudomanifolds, manifolds with boundary and polyhedral manifolds are discussed.