Semidefinite Characterization and Computation of Zero-Dimensional Real Radical Ideals

For an ideal I??[x] given by a set of generators, a new semidefinite characterization of its real radical I(V _?(I)) is presented, provided it is zero-dimensional (even if I is not). Moreover, we propose an algorithm using numerical linear algebra and semidefinite optimization techniques, to compute all (finitely many) points of the real variety V _?(I) as well as a set of generators of the real radical ideal. The latter is obtained in the form of a border or Gröbner basis. The algorithm is based on moment relaxations and, in contrast to other existing methods, it exploits the real algebraic nature of the problem right from the beginning and avoids the computation of complex components.     

Semidefinite approximations for quadratic programs over orthogonal matrices

Finding global optimum of a non-convex quadratic function is in general a very difficult task even when the feasible set is a polyhedron. We show that when the feasible set of a quadratic problem consists of orthogonal matrices from \mathbbR^n×k{\mathbb{R}^{n\times k}} , then we can transform it into a semidefinite program in matrices of order kn which has the same optimal value. This opens new possibilities to get good lower bounds for several problems from combinatorial optimization, like the Graph partitioning problem (GPP), the Quadratic assignment problem (QAP) etc. In particular we show how to improve significantly the well-known Donath-Hoffman eigenvalue lower bound for GPP by semidefinite programming. In the last part of the paper we show that the copositive strengthening of the semidefinite lower bounds for GPP and QAP yields the exact values.     

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 − κ(p))p, where κ(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.     

Non-Commutative Harmonic and Subharmonic Polynomials

The paper introduces a notion of the Laplace operator of a polynomial p in noncommutative variables x = (x ₁,…, x _g ). The Laplacian Lap[p, h] of p is a polynomial in x and in a noncommuting variable h. When all variables commute we have Lap[p, h] = h ²Δ _x p where Δ _x p is the usual Laplacian. A symmetric polynomial in symmetric variables will be called harmonic if Lap[p, h] = 0 and subharmonic if the polynomial q(x, h) :=  Lap[p, h] takes positive semidefinite matrix values whenever matrices X ₁,…, X _g , H are substituted for the variables x ₁,…, x _g , h. In this paper we classify all homogeneous symmetric harmonic and subharmonic polynomials in two symmetric variables. We find there are not many of them: for example, the span of all such subharmonics of any degree higher than 4 has dimension 2 (if odd degree) and 3 (if even degree). Hopefully, the approach here will suggest ways of defining and analyzing other partial differential equations and inequalities. Dedicated to Israel Gohberg on the occasion of his 80^th birthday. All authors were partially supported by J.W. Helton’s grants from the NSF and the Ford Motor Co. and J. A. Hernandez was supported by a McNair Fellowship.     

D.C. Versus Copositive Bounds for Standard QP

The standard quadratic program (QPS) is min_xεΔx^TQx, where is the simplex Δ = {x ⩽ 0 ∣ ∑_i=1ⁿ x_i = 1}. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One class of ‘d.c.’ (for ‘difference between convex’) bounds for QPS is based on writing Q=S−T, where S and T are both positive semidefinite, and bounding x^T Sx (convex on Δ) and −x^Tx (concave on Δ) separately. We show that the maximum possible such bound can be obtained by solving a semidefinite programming (SDP) problem. The dual of this SDP problem corresponds to adding a simple constraint to the well-known Shor relaxation of QPS. We show that the max d.c. bound is dominated by another known bound based on a copositive relaxation of QPS, also obtainable via SDP at comparable computational expense. We also discuss extensions of the d.c. bound to more general quadratic programming problems. For the application of QPS to bounding the stability number of a graph, we use a novel formulation of the Lovasz ϑ number to compare ϑ, Schrijver’s ϑ′, and the max d.c. bound.     

An Extension of Sums of Squares Relaxations to Polynomial Optimization Problems Over Symmetric Cones

This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let and be a finite dimensional real vector space and a symmetric cone embedded in ; examples of and include a pair of the N-dimensional Euclidean space and its nonnegative orthant, a pair of the N-dimensional Euclidean space and N-dimensional second-order cones, and a pair of the space of m × m real symmetric (or complex Hermitian) matrices and the cone of their positive semidefinite matrices. Sums of squares relaxations are further extended to a polynomial optimization problem over , i.e., a minimization of a real valued polynomial a(x) in the n-dimensional real variable vector x over a compact feasible region , where b(x) denotes an - valued polynomial in x. It is shown under a certain moderate assumption on the -valued polynomial b(x) that optimal values of a sequence of sums of squares relaxations of the problem, which are converted into a sequence of semidefinite programs when they are numerically solved, converge to the optimal value of the problem. Research supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

A convex polynomial that is not sos-convex

A multivariate polynomial p(x)?=?p(x ₁, . . . , x _n ) is sos-convex if its Hessian H(x) can be factored as H(x)?= M ^T (x) M(x) with a possibly nonsquare polynomial matrix M(x). It is easy to see that sos-convexity is a sufficient condition for convexity of p(x). Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of a semidefinite program, which can be solved efficiently. Motivated by this computational tractability, it is natural to study whether sos-convexity is also a necessary condition for convexity of polynomials. In this paper, we give a negative answer to this question by presenting an explicit example of a trivariate homogeneous polynomial of degree eight that is convex but not sos-convex.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R ₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

The small dispersion limit of the korteweg-de vries equation. ii

In Part I* we have shown, see Theorem 2.10, that as the coefficient of u^xxx tends to zero, the solution of the initial value problem for the KdV equation tends to a limit u in the distribution sense. We have expressed u by formula (3.59), where ψ^x is the partial derivative with respect to x of the function ψ* defined in Theorem 3.9 as the solution of the variational problem formulated in (2.16), (2.17). ψ* is uniquely characterized by the variational condition (3.34); its partial derivatives satisfy (3.51) and (3.52), where I is the set I^o defined in (3.36). In Section 4 we show that for t<t^b, I consists of a single interval, and the u satisfies u ^t — 6uu ^x = 0; here t^b is the largest time interval in which (12) has a continuous solution. In Section 5 we show that when I consists of a finite number of intervals, u can be described by Whitham's averaged equation or by the multiphased averaged equations of Flaschka, Forest, and McLaughlin. Equation numbers refer to Part I.     

Properties of balanced and perfect matrices

In this paper we define wheel matrices and characterize some properties of matrices that are perfect but not balanced. A consequence of our results is that if a matrixA is perfect then we can construct a polynomial number of submatricesA _I,,A _n ofA such thatA is balanced if and only if all the submatricesA ₁,,A _n ofA are perfect. This implies that if the problem of testing perfection is polynomially solvable, then so is the problem of testing balancedness.Partial support under NSF Grants DMS-8606188, ECS-8800281 and DDM-8800281.     

The additive subgroup generated by a polynomial

SupposeR is a prime ring with the centerZ and the extended centroidC. Letp(x ₁, …,x _n) be a polynomial overC in noncommuting variablesx ₁, …,x _n. LetI be a nonzero ideal ofR andA be the additive subgroup ofRC generated by {p(a ₁, …,a _n):a ₁, …,a _n ∈I}. Then eitherp(x ₁, …,x _n) is central valued orA contains a noncentral Lie ideal ofR except in the only one case whereR is the ring of all 2 × 2 matrices over GF(2), the integers mod 2.     

M-P invertible matrices and unitary groups over Fq2

The Moor-Penrose generalized inverses (M-P inverses for short) of matrices over a finite field F_q ² which is a generalization of the Moor-Penrose generalized inverses over the complex field, are studied in the present paper. Some necessary and sufficient conditions for anm xn matrixA over F_q ² having an M-P inverse are obtained, which make clear the set ofm xn matrices over F_q ² having M-P inverses and reduce the problem of constructing and enumerating the M-P invertible matrices to that of constructing and enumerating the non-isotropic subspaces with respect to the unitary group. Based on this reduction, both the construction problem and the enumeration problem are solved by borrowing the results in geometry of unitary groups over finite fields.     

Approximate D-optimal designs of experiments on the convex hull of a finite set of information matrices

In the paper we solve the problem of D _ℋ-optimal design on a discrete experimental domain, which is formally equivalent to maximizing determinant on the convex hull of a finite set of positive semidefinite matrices. The problem of D _ℋ-optimality covers many special design settings, e.g., the D-optimal experimental design for multivariate regression models. For D _ℋ-optimal designs we prove several theorems generalizing known properties of standard D-optimality. Moreover, we show that D _ℋ-optimal designs can be numerically computed using a multiplicative algorithm, for which we give a proof of convergence. We illustrate the results on the problem of D-optimal augmentation of independent regression trials for the quadratic model on a rectangular grid of points in the plane.     

Local Minima and Convergence in Low-Rank Semidefinite Programming

The low-rank semidefinite programming problem LRSDP_r is a restriction of the semidefinite programming problem SDP in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and prove the optimal convergence of a slight variant of the successful, yet experimental, algorithm of Burer and Monteiro [5], which handles LRSDP_r via the nonconvex change of variables X=RR^T. In addition, for particular problem classes, we describe a practical technique for obtaining lower bounds on the optimal solution value during the execution of the algorithm. Computational results are presented on a set of combinatorial optimization relaxations, including some of the largest quadratic assignment SDPs solved to date.This author was supported in part by NSF Grant CCR-0203426.This author was supported in part by NSF Grants CCR-0203113 and INT-9910084 and ONR grant N00014-03-1-0401.     

Multiplicity computation of modules overk[x1,…,xn] and an application to weyl algebras

Let A = k[x₁,…,x_n] be the polynomial algebra over a field kof characteristic 0Ian ideal of A, M = A/Iand ^αHP _I the (affine) Hilbert polynomial of M. By further exploring the algorithmic procedure given in [CLO'] for deriving the existence of ^αHP _I , we compute the leading coefficient of ^αHP _I by looking at the leading monomials of a Grobner basis of Iwithout computing ^αHP _I . Using this result and the filtered-graded transfer of Grobner basis obtained in [LW] for (noncommutative) solvable polynomial algebras (in the sense of [K-RW]), we are able to compute the multiplicity of a cyclic module over the Weyl algebra A _n (k) without computing the Hilbert polynomial of that module, and consequently to give a quite easy algorithmic characterization of the “smallest“ modules over Weyl algebras. Using the same methods as before, we also prove that the tensor product of two cyclic modules over the Weyl algebras has the multiplicity which is equal to the product of the multiplicities of both modules. The last result enables us to construct examples of “smallest“ irreducible modules over Weyl algebras.     

Left Annihilators of Commutators with Derivation on Right Ideals

Abstract

Let R be a prime ring of characteristic different from 2, d a non-zero derivation of R, I a non-zero right ideal of R, a ∈ R, S ₄(x ₁,…, x ₄) the standard polynomial in 4 variables. Suppose that, for any x, y ∈ I, a[d([x, y]), [x, y]] = 0. If S ₄(I, I, I, I)I ≠ 0, then aI = ad(I) = 0.     

Specializations of Multigradings and the Arithmetical Rank of Lattice Ideals

In this article, we study specializations of multigradings and apply them to the problem of the computation of the arithmetical rank of a lattice ideal I _{L 𝒢}  ? K[x ₁,…, x _n ]. The arithmetical rank of I _{L 𝒢} equals the ?-homogeneous arithmetical rank of I _{L 𝒢} , for an appropriate specialization ? of 𝒢. To the lattice ideal I _{L 𝒢} and every specialization ? of 𝒢, we associate a simplicial complex. We prove that combinatorial invariants of the simplicial complex provide lower bounds for the ?-homogeneous arithmetical rank of I _{L 𝒢} .     

On reduced semidefinite programs for second order moment bounds with applications

We show that the complexity of computing the second order moment bound on the expected optimal value of a mixed integer linear program with a random objective coefficient vector is closely related to the complexity of characterizing the convex hull of the points \(\{{1 \atopwithdelims (){\varvec{x}}}{1 \atopwithdelims (){\varvec{x}}}' \ | \ {\varvec{x}} \in {\mathcal {X}}\}\) where \({\mathcal {X}}\) is the feasible region. In fact, we can replace the completely positive programming formulation for the moment bound on \({\mathcal {X}}\), with an associated semidefinite program, provided we have a linear or a semidefinite representation of this convex hull. As an application of the result, we identify a new polynomial time solvable semidefinite relaxation of the distributionally robust multi-item newsvendor problem by exploiting results from the Boolean quadric polytope. For \({\mathcal {X}}\) described explicitly by a finite set of points, our formulation leads to a reduction in the size of the semidefinite program. We illustrate the usefulness of the reduced semidefinite programming bounds in estimating the expected range of random variables with two applications arising in random walks and best–worst choice models.     

Absolute value programming

We investigate equations, inequalities and mathematical programs involving absolute values of variables such as the equation Ax+B|x| = b, where A and B are arbitrary m× n real matrices. We show that this absolute value equation is NP-hard to solve, and that solving it with B = I solves the general linear complementarity problem. We give sufficient optimality conditions and duality results for absolute value programs as well as theorems of the alternative for absolute value inequalities. We also propose concave minimization formulations for absolute value equations that are solved by a finite succession of linear programs. These algorithms terminate at a local minimum that solves the absolute value equation in almost all solvable random problems tried.     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).