On bar frameworks,stress matrices and semidefinite programming

A bar framework G(p) in r-dimensional Euclidean space is a graph G on the vertices 1, 2, . . . , n, where each vertex i is located at point p ⁱ in \mathbbR^r{\mathbb{R}^r} . Given a framework G(p) in \mathbbR^r{\mathbb{R}^r} , a problem of great interest is that of determining whether or not there exists another framework G(q), not obtained from G(p) by a rigid motion, such that ||q ⁱ − q ^j ||² = ||p ⁱ − p ^j ||² for each edge (i, j) of G. This problem is known as either the global rigidity problem or the universal rigidity problem depending on whether such a framework G(q) is restricted to be in the same r-dimensional space or not. The stress matrix S of a bar framework G(p) plays a key role in these and other related problems. In this paper, semidefinite programming (SDP) theory is used to address, in a unified manner, several problems concerning universal rigidity. New results are presented as well as new proofs of previously known theorems. In particular, we use the notion of SDP non-degeneracy to obtain a sufficient condition for universal rigidity, and we show that this condition yields the previously known sufficient condition for generic universal rigidity. We present new results concerning positive semidefinite stress matrices and we use a semidefinite version of Farkas lemma to characterize bar frameworks that admit a nonzero positive semidefinite stress matrix S.     

On the Real Zeros of Positive Semidefinite Biquadratic Forms

For a positive semidefinite biquadratic forms F in (3, 3) variables, we prove that, if F has a finite number but at least 7 real zeros 𝒵(F), then it is not a sum of squares. We show also that if F has at least 11 zeros, then it has infinitely many real zeros and it is a sum of squares. It can be seen as the counterpart for biquadratic forms as the results of Choi, Lam, and Reznick for positive semidefinite ternary sextics.

We introduce and compute some of the numbers BB _{n, m} which are set to be equal to sup |𝒵(F)| where F ranges over all the positive semidefinite biquadratic forms F in (n, m) variables such that |𝒵(F)| < ∞.

We also recall some old constructions of positive semidefinite biquadratic forms which are not sums of squares and we give some new families of examples.     

Tests for the mean direction of the Langevin distribution with large concentration parameter

In this paper we study the asymptotic behaviors of the likelihood ratio criterion (T_L^(s)), Watson statistic (T_W^(s)) and Rao statistic (T_R^(s)) for testing H_0s: μ (a given subspace) against H_1s: μ , based on a sample of size n from a p-variate Langevin distribution M_p(μ, κ) when κ is large. For the case when κ is known, asymptotic expansions of the null and nonnull distributions of these statistics are obtained. It is shown that the powers of these statistics are coincident up to the order κ⁻¹. For the case when κ is unknown, it is shown that T_R^(s) T_L^(s) T_W^(s) in their powers up to the order κ⁻¹.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

Jacobi osculating rank and isotropic geodesics on naturally reductive 3-manifolds

We study the Jacobi osculating rank of geodesics on naturally reductive homogeneous manifolds and we apply this theory to the 3-dimensional case. Here, each non-symmetric, simply connected naturally reductive 3-manifold can be given as a principal bundle M³(κ,τ) over a surface of constant curvature κ, such that the curvature of its horizontal distribution is a constant τ>0, with τ²≠κ. Then, we prove that the Jacobi osculating rank of every geodesic of M³(κ,τ) is two except for the Hopf fibers, where it is zero. Moreover, we determine all isotropic geodesics and the isotropic tangent conjugate locus.     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.     

The Plemelj Formula of Higher Order Partial Derivatives of the Bochner-Martinelli Type Integral

In this paper, by using the technique of integral transformation, we obtain the Plemelj formulas with the Cauchy principal value and the Hadamard principal value of mixed higher order partial derivatives for integral of the Bochner-Martinelli type on a closed smooth manifold ∂D in Cⁿ. From the Plemelj formulas and using the theory of complex partial differential equation, we prove that the problem of higher order boundary value D^κΦ⁺(t) = D^κΦ⁻(t) + f(t) is equivalent to a complex linear higher order partial differential equation. Moreover, given a proper condition of the Cauchy boundary value problem, the problem of higher order boundary value has a unique branch complex harmonic solution satisfying Φ⁻(∞) = 0 in Cⁿ\∂D.     

Semidefinite representations for finite varieties

We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space ℝ[x ₁, . . . ,x _n ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreover, we prove the finite convergence of a hierarchy of semidefinite relaxations introduced by Lasserre. Semidefinite approximations can be constructed by considering truncated combinatorial moment matrices; rank conditions are given (in a grid case) that ensure that the approximation solves the original problem to optimality. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

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.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

The representability number of a chain

For each pair of linear orderings (L,M), the representability number repr_M(L) of L in M is the least ordinal α such that L can be order-embedded into the lexicographic power . The case is relevant to utility theory. The main results in this paper are as follows. (i) If κ is a regular cardinal that is not order-embeddable in M, then repr_M(κ)=κ; as a consequence, for each κω₁. (ii) If M is an uncountable linear ordering with the property that A×_lex2 is not order-embeddable in M for each uncountable AM, then for any ordinal α; in particular, . (iii) If L is either an Aronszajn line or a Souslin line, then .     

Estimation of a Normal Covariance Matrix with Incomplete Data under Stein′s Loss

Suppose that we have (n − a) independent observations from N_p(0, Σ) and that, in addition, we have a independent observations available on the last (p − c) coordinates. Assuming that both observations are independent, we consider the problem of estimating Σ under the Stein′s loss function, and show that some estimators invariant under the permutation of the last (p − c) coordinates as well as under those of the first c coordinates are better than the minimax estimators of Eaten. The estimators considered outperform the maximum likelihood estimator (MLE) under the Stein′s loss function as well. The method involved here is computation of an unbiased estimate of the risk of an invariant estimator considered in this article. In addition we discuss its application to the problem of estimating a covariance matrix in a GMANOVA model since the estimation problem of the covariance matrix with extra data can be regarded as its canonical form.     

The Complexity of Indefinite Elliptic Problems with Noisy Data

We study the complexity of second-order indefinite elliptic problems −div(au) +bu=f(with homogeneous Dirichlet boundary conditions) over ad-dimensional domain Ω, the error being measured in theH¹(Ω)-norm. The problem elementsfbelong to the unit ball ofW^{r, p}, (Ω), wherep [2, ∞] andr>d/p. Information consists of (possibly adaptive) noisy evaluations off,a, orb(or their derivatives). The absolute error in each noisy evaluation is at most δ. We find that thenth minimal radius for this problem is proportional ton^−r/d+ δ and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds on the -complexity (minimal cost of calculating an -approximation) for this problem, said bounds depending on the costc(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ-noisy evaluation isc(δ) = δ^−s(fors> 0), then the complexity is proportional to (1/)^{d/r + s}.     

A Singular Riesz Product in the Nevai Class and Inner Functions with the Schur Parameters in ∩p>2 l

There exist singular Riesz products dσ=∏^∞_κ=1 (1+Re(α_κζ^n_κ)) on the unit circle with the parameters (a_n)_n0 of orthogonal polynomials in L²(dσ) satisfying ∑^∞_n=0 |a_n|^p<+∞ for every p, p>2. The Schur parameters of the inner factor of the Cauchy integral ∫ (ζ−z)⁻¹ dσ(ζ), σ being such a Riesz product, belong to ∩_p>2 l^p.     

Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3

The best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is Θ(n^3.5logn); but the best combinatorial algorithms have approximation ratio 4/5 only, achieved in O(n²) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477–504; E. Halperin, et al., J. Algorithms 53 (2004) 169–185]. Here we present an improved combinatorial approximation, which is a 5/6-approximation algorithm that runs in O(n²) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3.     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

Computing Vertex Connectivity: New Bounds from Old Techniques

The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ³ + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ₁nmlog(n²/m)) where κ₁ ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n²/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.     

Dissecting the Stanley partition function

Let p(n) denote the number of unrestricted partitions of n. For i=0, 2, let p_i(n) denote the number of partitions π of n such that . Here denotes the number of odd parts of the partition π and π^′ is the conjugate of π. Stanley [Amer. Math. Monthly 109 (2002) 760; Adv. Appl. Math., to appear] derived an infinite product representation for the generating function of p₀(n)-p₂(n). Recently, Swisher [The Andrews–Stanley partition function and p(n), preprint, submitted for publication] employed the circle method to show that

(i)

and that for sufficiently large n

(ii)

In this paper we study the even/odd dissection of the Stanley product, and show how to use it to prove (i) and (ii) with no restriction on n. Moreover, we establish the following new result:

Two proofs of this surprising inequality are given. The first one uses the Göllnitz–Gordon partition theorem. The second one is an immediate corollary of a new partition inequality, which we prove in a combinatorial manner. Our methods are elementary. We use only Jacobi's triple product identity and some naive upper bound estimates.     

Nonexistence of backward self-similar blowup solutions to a supercritical semilinear heat equation

We consider a Cauchy problem for a semilinear heat equation

with p>p_S where p_S is the Sobolev exponent. If u(x,t)=(T−t)^−1/(p−1)φ((T−t)^−1/2x) for xR^N and t[0,T), where φ is a regular positive solution of

(P)

then u is called a backward self-similar blowup solution. It is immediate that (P) has a trivial positive solution κ≡(p−1)^−1/(p−1) for all p>1. Let p_L be the Lepin exponent. Lepin obtained a radial regular positive solution of (P) except κ for p_S<p<p_L. We show that there exist no radial regular positive solutions of (P) which are spatially inhomogeneous for p>p_L.