A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 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. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

Constrained energy problems with applications to orthogonal polynomials of a discrete variable

Given a positive measure Σ with gs > 1, we write Με ℳ^Σ if Μ is a probability measure and Σ—Μ is a positive measure. Under some general assumptions on the constraining measure Σ and a weight functionw, we prove existence and uniqueness of a measure λ^Σ _w that minimizes the weighted logarithmic energy over the class ℳ^Σ. We also obtain a characterization theorem, a saturation result and a balayage representation for the measure λ^Σ _w As applications of our results, we determine the (normalized) limiting zero distribution for ray sequences of a class of orthogonal polynomials of a discrete variable. Explicit results are given for the class of Krawtchouk polynomials. The research done by this author is in partial fulfillment of the Ph.D. requirements at the University of South Florida. The research done by this author was supported, in part, by U.S. National Science Foundation under grant DMS-9501130.     

Estimating a general function of a quadratic function

Let be an observation from a spherically symmetric distribution with unknown location parameter . For a general non-negative function c, we consider the problem of estimating c(||x − θ||²) under the usual quadratic loss. For p ≥ 5, we give sufficient conditions for improving on the unbiased estimator γ₀ of c(||x − θ||²) by competing estimators γ _s = γ₀ + s correcting γ₀ with a suitable function s. The main condition relies on a partial differential inequality of the form k Δs + s ² ≤ 0 for a certain constant k ≠ 0. Our approach unifies, in particular, the two problems of quadratic loss estimation and confidence statement estimation and allows to derive new results for these two specific cases. Note that we formally establish our domination results (that is, with no recourse to simulation).      

Subgroups of symplectic groups that contain a subsystem subgroup

Let Γ = GSp(2l, R) be the general symplectic group of rank l over a commutative ring R such that 2 ∈ R*; and let ν be a symmetric equivalence relation on the index set {1,…, l, −l,…, 1} all of whose classes contain at least 3 elements. In the present paper, we prove that if a subgroup H of Γ contains the group E_Γ(ν) of elementary block diagonal matrices of type ν, then H normalizes the subgroup generated by all elementary symplectic transvections T_ij(ξ) ∈ H. Combined with the previous results, this completely describes the overgroups of subsystem subgroups in this case. Similar results for subgroups of GL(n, R) were established by Z. I. Borewicz and the author in the early 1980s, while for GSp(2l, R) and GO(n, R) they have been announced by the author in the late 1980s, but a complete proof for the symplectic case has not been published before. Bibliography: 74 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 349, 2007, pp. 5–29.     

Inequalities of Maximum of Partial Sums and Weak Convergence for a Class of Weak Dependent Random Variables

In this paper, we establish a Rosenthal-type inequality of the maximum of partial sums for ρ^- -mixing random fields. As its applications we get the Hájeck -Rènyi inequality and weak convergence of sums of ρ^- -mixing sequence. These results extend related results for NA sequence and p^＊ -mixing random fields,     

Generating functions for plane partitions of a given shape

For fixed integers α and β, planar arrays of integers of a given shape, in which the entries decrease at least by α along rows and at least by β along columns, are considered. For various classes of these (α,β)-plane partitions we compute three different kinds of generating functions. By a combinatorial method, determinantal expressions are obtained for these generating functions. In special cases these determinants may be evaluated by a simple determinant lemma. All known results concerning plane partitions of a given shape are included. Thus our approach of a given shape provides a uniform proof method and yields numerous generalizations of known results.     

Some Properties of Solutions to a Second Order Elliptic Equation with Principal Part of Divergence Form with Potential Concentrated on a Hypersurface

A number of classical results of the theory of second order elliptic equations of divergence form in ℝ ^d, d ⩾ 2, is generalized to problems with singular potential concentrated on a hypersurface of codimension 1. Such results are required, for example, for describing photon crystals. Bibliography: 8 titles. __________ Translated from Problemy Matematicheskogo Analiza, No. 31, 2005, pp. 25–37.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Realization of a sum of sequences by a sum graph

It is shown that the realizability of the sequences ϕ=(a ₁,…, _a ), ψ=(b ₁,…,b _n ) and ϕ+ψ is a sufficient condition for the realizability of ϕ+ψ by a graph with a ϕ-factor ifb _i ≦1 fori=1,…,n. The condition is not sufficient in general. A necessary and sufficient condition for the realizability of ϕ+ψ by a graph with a ϕ-factor is given for the case that ϕ is realizable by a star and isolated vertices.     

Improving on the minimum risk equivariant estimator of a location parameter which is constrained to an interval or a half-interval

For location families with densitiesf ₀(x−θ), we study the problem of estimating θ for location invariant lossL(θ,d)=ρ(d−θ), and under a lower-bound constraint of the form θ≥a. We show, that for quite general (f ₀, ρ), the Bayes estimator δ _U with respect to a uniform prior on (a, ∞) is a minimax estimator which dominates the benchmark minimum risk equivariant (MRE) estimator. In extending some previous dominance results due to Katz and Farrell, we make use of Kubokawa'sIERD (Integral Expression of Risk Difference) method, and actually obtain classes of dominating estimators which include, and are characterized in terms of δ _U . Implications are also given and, finally, the above dominance phenomenon is studied and extended to an interval constraint of the form θ∈[a, b]. Research supported by NSERC of Canada.     

Supersonic longitudinal flow past a cylinder in the presence of a second coaxial cylinder in the wake

The compressible-gas complete Navier-Stokes equations are applied for a numerical analysis of the flow structure between two coaxial cylinders of equal radius set in tandem in a supersonic flow. The results for Re_∞=10⁴, M_∞=3 ω=0.75, Tw=1.08, when the distance between the coaxial cylinders is equal to two blunt-nose radii, show that the flow between the cylinders is subsonic and quasiperiodic. Translated from Obratnye Zadachi Estestvoznaniya, Published by Moscow University, Moscow, 1997, pp. 199–203.     

On the local convergence of a family of Euler-Halley type iterations with a parameter

This paper aims to study the local convergence of a family of Euler-Halley type methods with a parameter α for solving nonlinear operator equations under the second-order generalized Lipschitz assumption. The radius r _α of the optimal convergence ball and the error estimation of the method corresponding to α are estimated for each α ∈ ( − ∞ , + ∞ ). For each α > 0, we get r _α  ≥ r _− α and the upper bound of the error estimation of the method with α > 0 is not larger than the one with α < 0. For each α ≤ 0, we get the precise value of r _α , which is closely linked to the dynamical property of the method applied to a real or a complex function, and the optimal error estimation, which decreases when α→0⁻. Results show that the method corresponding to α is better than the one corresponding to − α for each α > 0 and the Chebyshev-Euler method is the best among all methods in the family with α ∈ ( − ∞ , 0] from the view of both safe choice of the initial point and error estimation.     

The analytic torsion of a disc

In this article, we study the Reidemeister torsion and the analytic torsion of the m dimensional disc, with the Ray and Singer homology basis (Adv Math 7:145–210, 1971). We prove that the Reidemeister torsion coincides with a power of the volume of the disc. We study the additional terms arising in the analytic torsion due to the boundary, using generalizations of the Cheeger–Müller theorem. We use a formula proved by Brüning and Ma (GAFA 16:767–873, 2006) that predicts a new anomaly boundary term beside the known term proportional to the Euler characteristic of the boundary (Lück, J Diff Geom 37:263–322, 1993). Some of our results extend to the case of the cone over a sphere, in particular we evaluate directly the analytic torsion for a cone over the circle and over the two sphere. We compare the results obtained in the low dimensional cases. We also consider a different formula for the boundary term given by Dai and Fang (Asian J Math 4:695–714, 2000), and we compare the results. The results of these work were announced in the study of Hartmann et al. (BUMI 2:529–533, 2009).     

Inclusion sets for the singular values of a square matrix

The paper presents a general approach to deriving inclusion sets for the singular values of a matrix A = (a_ij) ∈ ℂ ^n×n. The key to the approach is the following result: If σ is a singular value of A, then a certain matrix C(σ, A) of order 2n, whose diagonal entries are σ² − | a_ii|², i = 1, …, n, is singular. Based on this result, we use known diagonal-dominance type nonsingularity conditions to obtain inclusion sets for the singular values of A. Scaled versions of the inclusion sets, allowing one, in particular, to obtain Ky Fan type results for the singular values, are derived by passing to the conjugated matrix D⁻¹C(σ, A)D, where D is a positive-definite diagonal matrix. Bibliography: 16 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 52–77.     

On eigenfunctions localized in a neighborhood of the lateral surface of a thin domain

We study the spectrum of the boundary-value problem for the Laplace operator in a thin domain Ω(ε) obtained by small perturbation of the cylinder Ω(ε)=ω×(-ε/2.ε/2) ⊂ ℝ³in a neighborhood of the lateral surface. The Dirichlet condition is imposed on the bases of the cylinder, and the Dirichlet condition or the Neumann condition is imposed on the remaining part of ∂Ω(ε). We construct and justify asymptotic formulas (as ε→+0) for eigenvalues and eigenfunctions. In view of a special form of the lateral surface, there are eigenfunctions of boundary-layer type that exponentially decrease far from the lateral surface. For the mixed boundary-value problem such a localization is possible in neighborhoods of local maxima of the curvature of the contour ∂ω. This property of eigenfunctions is a characteristic feature of the first points of the spectrum (in particular, the first eigenvalue) and, under the passage from Ω(h)₍₎ to Ω(h), the spectrum itself has perturbation O(h⁻²). Bibliography: 29 titles. Translated fromProblemy Matematicheskogo Analiza, No. 19, 1999, pp. 105–149.     

On the First Hitting Time of a One-dimensional Diffusion and a Compound Poisson Process

It is studied the first-passage time (FPT) of a time homogeneous one-dimensional diffusion, driven by the stochastic differential equation dX(t) = μ(X(t))dt + σ(X(t)) dB _t , X(0) = x ₀, through b + Y(t), where b > x ₀ and Y(t) is a compound Poisson process with rate λ > 0 starting at 0, which is independent of the Brownian motion B _t . In particular, the FPT density is investigated, generalizing a previous result, already known in the case when X(t) = μt + B _t , for which the FPT density is the solution of a certain integral equation. A numerical method is shown to calculate approximately the FPT density; some examples and numerical results are also reported.     

The Markov chain associated to a Pick function

To each function ϕ˜(ω) mapping the upper complex half plane ?⁺ into itself such that the coefficient of ω in the Nevanlinna integral representation is one, we associate the kernel p(y, dx) of a Markov chain on ℝ by

An integral test for a critical multitype spatially homogeneous branching particle process and a related reaction-diffusion system

An integral test (Theorem 5) is established for the dichotomy concerning local extinction and survival (even persistence) at late times for critical multitype spatially homogeneous branching particle systems in continuous time. Our conditions on the branching mechanism are close to the ones known from “classical” processes without motion component. This generalizes and complements results of López-Mimbela and Wakolbinger [LMW96] and others. Our approach is based on some genealogical tree analysis combined with the study of the long-term behavior of L ¹-norms of solutions of related systems of reaction-“diffusion” equations, which is perhaps also of some independent interest. Received: 13 August 1997 / Revised version: 12 May 1998 / Published online: 14 February 2000