Quadratic programming with one negative eigenvalue is NP-hard

We show that the problem of minimizing a concave quadratic function with one concave direction is NP-hard. This result can be interpreted as an attempt to understand exactly what makes nonconvex quadratic programming problems hard. Sahni in 1974 [8] showed that quadratic programming with a negative definite quadratic term (n negative eigenvalues) is NP-hard, whereas Kozlov, Tarasov and Haijan [2] showed in 1979 that the ellipsoid algorithm solves the convex quadratic problem (no negative eigenvalues) in polynomial time. This report shows that even one negative eigenvalue makes the problem NP-hard.This author's work 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.     

Matrix factorizations in optimization of nonlinear functions subject to linear constraints

Several ways of implementing methods for solving nonlinear optimization problems involving linear inequality and equality constraints using numerically stable matrix factorizations are described. The methods considered all follow an active constraint set approach and include quadratic programming, variable metric, and modified Newton methods.Part of this work was performed while the author was a visitor at Stanford University. This research was supported in part by the National Science Foundation under Grant GJ 36472 and in part by the Atomic Energy Commission Contract No. AT(04-3)-326PA30.     

On the generic splitting of quadratic forms in characteristic 2

In [9] and [10] Knebusch established the basic facts of generic splitting theory of quadratic forms over a field of characteristic different from 2. This paper is related to [11] and [13] where Knebusch and Rehmann generalized partially this theory to a field of characteristic 2. More precisely, we begin with a complete characterization of quadratic forms of height 1 (we don't exclude anisotropic quadratic forms with quasi-linear part of dimension at least 1). This allows us to extend the notion of degree to characteristic 2. We prove some results on excellent forms and splitting tower of a quadratic form. Some results on quadratic forms of height 2 and degree 1 or 2 are given. Received: 6 March 2000; in final form: 5 October 2001 / Published online: 17 June 2002     

Compactified Jacobians of curves with spine decompositions

A curve, that is, a connected, reduced, projective scheme of dimension 1 over an algebraically closed field, admits two types of compactifications of its (generalized) Jacobian: the moduli schemes of P-quasistable torsion-free, rank-1 sheaves and Seshadri’s moduli schemes of S-equivalence classes of semistable torsion-free, rank-1 sheaves. Both are constructed with respect to a choice of polarization. The former are fine moduli spaces which were shown to be complete; here we show that they are actually projective. The latter are just coarse moduli spaces. Here we give a sufficient condition for when these two types of moduli spaces are equal. Eduardo Esteves is Supported by CNPq, Processos 301117/04-7 and 470761/06-7, by CNPq/FAPERJ, Processo E-26/171.174/2003, and by the Institut Mittag–Leffler (Djursholm, Sweden).     

Quadratic forms of a matric-t variate

Summary Crowther [2] studied the distribution of a quadratic form in a matrix normal variate. This, in some sense, is extended by De Waal [4]. They represented the density function of this quadratic form in terms of generalized Hayakawa polynomials. Application of some specific results of these authors facilitates the derivation of distributions of quadratic forms of the matric-t variate. Attention is also given to the distributions of the characteristic roots and the trace of this quadratic matrix. Special cases are considered and some useful integrals are formulated. Financially supported by the CSIR and the University of the Orange Free State     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

Perturbed collocation and Runge-Kutta methods

Summary It is well known thatsome implicit Runge-Kutta methods are equivalent to collocation methods. This fact permits very short and natural proofs of order andA, B, AN, BN-stability properties for this subclass of methods (see [9] and [10]). The present paper answers the natural question, ifall RK methods can be considered as a somewhat perturbed collocation. After having introduced this notion we give a proof on the order of the method and discuss their stability properties. Much of known theory becomes simple and beautiful.     

The two-well problem in three dimensions

We study properties of generalized convex hulls of the set with . If K contains no rank-1 connection we show that the quasiconvex hull of K is trivial if H belongs to a certain (large) neighbourhood of the identity. We also show that the polyconvex hull of K can be nontrivial if H is sufficiently far from the identity, while the (functional) rank-1 convex hull is always trivial. If the second well is replaced by a point then the polyconvex hull is trivial provided that there are no rank-1 connections. Received: March 25, 1999 / Accepted: April 23, 1999     

How to get around a simple quadratic fold

Summary We analyse from a theoretical point of view a computational technique previously introduced [2, 5] for tracing branches of solutions of nonlinear equations near simple quadratic folds.Supported in part by an M.P.I. 40% grantSupported in part by a C.N.R. grant     

The Existence of Good Extensible Polynomial Lattice Rules

Extensible (polynomial) lattice rules have been introduced recently and they are convenient tools for quasi-Monte Carlo integration. It is shown in this paper that for suitable infinite families of polynomial moduli there exist generating parameters for extensible rank-1 polynomial lattice rules such that for all these infinitely many moduli and all dimensions s the quantity R ^(s) and the star discrepancy are small. The case of Korobov-type polynomial lattice rules is also considered.Received April 30, 2002; in revised form August 21, 2002 Published online April 4, 2003     

Directional approximation of the jacobians in ROW-methods

In this paper a new technique for avoiding exact Jacobians in ROW methods is proposed. The Jacobiansf' _n are substituted by matricesA _n satisfying a directional consistency conditionA _n f _n =f' _n f _n +O(h). In contrast to generalW-methods this enables us to reduce the number of order conditions and we construct a 2-stage method of order 3 and families of imbedded 4-stage methods of order 4(3). The directional approximation of the Jacobians has been realized via rank-1 updating as known from quasi-Newton methods.     

Determination of elliptic curves with everywhere good reduction over real quadratic fields

All elliptic curves having everywhere good reduction over \Bbb Q(?{29})\Bbb Q(\sqrt {29}) are determined by studying the fields of 2- and 3-division points. As a byproduct of the argument, the elliptic curves over some real quadratic fields are determined. Though part of the result are already obtained in [2], [4], [5], [10], the proof given in the present paper is simpler.     

Structured multi-way arrays and their applications

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.     

The split-step θ-methods for stochastic delay Hopfield neural networks

In this paper, we construct a new split-step numerical method for stochastic delay Hopfield neural networks. The main aim of this paper is to investigate the mean-square stability of this split-step θ-methods for stochastic delay Hopfield neural networks. It is proved that the split-step θ-methods are mean-square stable under suitable conditions. Numerical experiments verify the numerical stability results obtained from theory. A comparison between this work and Ronghua et al. [8] is also discussed in the example.     

Optimal solution of nonlinear equations satisfying a Lipschitz condition

Summary For a given nonnegative we seek a pointx ^* such that |f(x ^*)| wheref is a nonlinear transformation of the cubeB=[0,1] ^m into (or ^p ,p>1) satisfying a Lipschitz condition with the constantK and having a zero inB.The information operator onf consists ofn values of arbitrary linear functionals which are computed adaptively. The pointx ^* is constructed by means of an algorithm which is a mapping depending on the information operator. We find an optimal algorithm, i.e., algorithm with the smallest error, which usesn function evaluations computed adaptively. We also exhibit nearly optimal information operators, i.e., the linear functionals for which the error of an optimal algorithm that uses them is almost minimal. Nearly optimal information operators consists ofn nonadaptive function evaluations at equispaced pointsx _j in the cubeB. This result exhibits the superiority of the T. Aird and J. Rice procedure ZSRCH (IMSL library [1]) over Sobol's approach [7] for solving nonlinear equations in our class of functions. We also prove that the simple search algorithm which yields a pointx ^*=x _k such that is nearly optimal. The complexity, i.e., the minimal cost of solving our problem is roughly equal to (K/) ^m .     

The switching game on unions of oriented matroids

In 1986, Hamidoune and Las Vergnas [3] introduced an oriented matroid version of the so-called Shannon’s switching game. They conjectured that the classification of the directed switching game on oriented matroids is identical to the classification of the non-oriented version. In this note, we support this conjecture by showing its validity for an infinite class of oriented matroids obtained as unions of rank-1 and/or rank-2 uniform oriented matroids.     

An Existential Divisibility Lemma for Global Fields

We generalize the Existential Divisibility Lemma by Th. Pheidas [7] to all global fields K of characteristic not 2, and for all sets of primes that are inert in a quadratic extension L of K. We also remove the conditions in real and ramifying primes, which were present in Pheidas’ version. As a Corollary, we recover the known fact that the set of integral elements at a prime in a global field is existentially definable. The first author is a Research Assistant of the Research Foundation – Flanders (FWO – Vlaanderen). Work partially supported by the European Community’s Human Potential Programme under contract HPRN-CT-2002-00287.