Projective re-normalization for improving the behavior of a homogeneous conic linear system

In this paper we study the homogeneous conic system . We choose a point that serves as a normalizer and consider computational properties of the normalized system . We show that the computational complexity of solving F via an interior-point method depends only on the complexity value of the barrier for C and on the symmetry of the origin in the image set , where the symmetry of 0 in is

Sums of random symmetric matrices and quadratic optimization under orthogonality constraints

Let B _i be deterministic real symmetric m × m matrices, and ξ _i be independent random scalars with zero mean and “of order of one” (e.g., ). We are interested to know under what conditions “typical norm” of the random matrix is of order of 1. An evident necessary condition is , which, essentially, translates to ; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S _N is : for all Ω > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints , where F is quadratic in X = (X ₁,... ,X _k ). We show that when F is convex in every one of X _j , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices . Research was partly supported by the Binational Science Foundation grant #2002038.     

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid

We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special case of the problem’s class we study. We prove that under a certain mild assumption on the problem’s data, problem (RQ) admits an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge superlinearly to a global solution of (RQ) and show that the dependency of the number of iterations on the optimality tolerance grows as . This research is partially supported by the Israel Science Foundation, ISF grant #489-06.     

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.     

Uniform Comparison of Tails of (Non-Symmetric) Probability Measures and Their Symmetrized Counterparts with Applications

Let (, ) be a separable Banach space and let be a class of probability measures on , and let denote the symmetrization of . We provide two sufficient conditions (one in terms of certain quantiles and the other in terms of certain moments of relative to μ and , ) for the “uniform comparison” of the μ and measure of the complements of the closed balls of centered at zero, for every . As a corollary to these “tail comparison inequalities,” we show that three classical results (the Lévy-type Inequalities, the Kwapień-Contraction Inequality, and a part of the It?–Nisio Theorem) that are valid for the symmetric (but not for the general non-symmetric) independent -valued random vectors do indeed hold for the independent random vectors whose laws belong to any which satisfies one of the two noted conditions and which is closed under convolution. We further point out that these three results (respectively, the tail comparison inequalities) are valid for the centered log-concave, as well as, for the strictly α-stable (or the more general strictly (r, α) -semistable) α ≠ 1 random vectors (respectively, probability measures). We also present several examples which we believe form a valuable part of the paper.      

Poincaré inequality and Palais–Smale condition for the <Emphasis Type="Italic">p</Emphasis>-Laplacian

An improved Poincaré inequality and validity of the Palais-Smale condition are investigated for the energy functional on , 1 < p < ∞, where Ω is a bounded domain in , is a spectral (control) parameter, and is a given function, in Ω. Analysis is focused on the case λ = λ₁, where −λ₁ is the first eigenvalue of the Dirichlet p-Laplacian Δ _p on , λ₁ > 0, and on the “quadratization” of within an arbitrarily small cone in around the axis spanned by , where stands for the first eigenfunction of Δ _p associated with −λ₁.     

A note on curvature of α-connections of a statistical manifold

The family of α-connections ∇^(α) on a statistical manifold equipped with a pair of conjugate connections and is given as . Here, we develop an expression of curvature R ^(α) for ∇^(α) in relation to those for . Immediately evident from it is that ∇^(α) is equiaffine for any when are dually flat, as previously observed in Takeuchi and Amari (IEEE Transactions on Information Theory 51:1011–1023, 2005). Other related formulae are also developed. The work was conducted when the author was on sabbatical leave as a visiting research scientist at the Mathematical Neuroscience Unit, RIKEN Brain Science Institute, Wako-shi, Saitama 351-0198, Japan.     

Sharp estimates for intrinsic ultracontractivity on C 1,α-domains

Let be the first Dirichlet eigenfunction on a connected bounded C ^1,α-domain in and the corresponding Dirichlet heat kernel. It is proved that where λ₂ > λ₁ are the first two Dirichlet eigenvalues. This estimate is sharp for both short and long times. Bounded Lipschitz domains, elliptic operators on manifolds, and a general framework are also discussed. Supported in part by Creative Research Group Fund of the National Foundation of China (no. 10121101), the 973-Project in China and RFDP(20040027009).     

The Quasiapproximate $(\mathcal{U} + \mathcal{K})$ –Invariants of Essentially Normal Operators

For a class of essentially normal operators, we characterize their norm closures of –orbits. Moreover, we introduce a notion of the quasiapproximate – equivalence of essentially normal operators and determine completely the quasiapproximate –invariants. Finally, we give the canonical forms of essentially normal operators under this quasiapproximate –equivalence.     

Some Explicit Distributions Related to the First Exit Time from a Bounded Interval for Certain Functionals of Brownian Motion

Let (B _t ) _{t≥ 0} be standard Brownian motion starting at y and set X _t = for , with V(y) = y ^γ if y≥ 0, V(y) = −K(−y)^γ if y≤ 0, where γ and K are some given positive constants. Set . In this paper, we provide some formulas for the probability distribution of the random variable as well as for the probability (or b)}. The formulas corresponding to the particular cases x = a or b are explicitly expressed by means of hypergeometric functions.      

Corrector–predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path

Two corrector–predictor interior point algorithms are proposed for solving monotone linear complementarity problems. The algorithms produce a sequence of iterates in the neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm can be implemented in arithmetic operations, where n is the dimension of the problems, is a constant, and m is the maximum order of the predictor and the corrector. If then both algorithms have iteration complexity. They are superlinearly convergent even for degenerate problems.      

Differential inclusions for differential forms

We study necessary and sufficient conditions for the existence of solutions in of the problem where is a given set. Special attention is given to the case of the curl (i.e. k = 1), particularly in dimension 3. Some applications to the calculus of variations are also stated.     

Unstable extremal surfaces of the “Shiffman functional” spanning rectifiable boundary curves

In this paper we derive a sufficient condition for the existence of extremal surfaces of a parametric functional with a dominant area term, which do not furnish global minima of within the class of H ^1,2-surfaces spanning an arbitrary closed rectifiable Jordan curve that merely has to satisfy a chord-arc condition. The proof is based on the “mountain pass result” of (Jakob in Calc Var 21:401–427, 2004) which yields an unstable -extremal surface bounded by an arbitrary simple closed polygon and Heinz’ ”approximation method” in (Arch Rat Mech Anal 38:257–267, 1970). Hence, we give a precise proof of a partial result of the mountain pass theorem claimed by Shiffman in (Ann Math 45:543–576, 1944) who only outlined a very sketchy and partially incorrect proof.     

The Monge Problem in Banach Spaces

In this paper, we generalize the Kantorovich functional to K?the-spaces for a cost or a profit function. We examine the convergence of probabilities with respect to this functional for some K?the-spaces. We study the Monge problem: Let be a K?the-space, P and Q two Borel probabilities defined on a Polish space M and a cost function . A K?the functional is defined by (P, Q) = inf where is the law of X. If c is a profit function, we note . (P, Q) = sup Under some conditions, we show the existence of a Monge function, φ, such that , or .      

AnO(\sqrt n L) iteration bound primal-dual cone affine scaling algorithm for linear programmingiteration bound primal-dual cone affine scaling algorithm for linear programming

In this paper we introduce a primal-dual affine scaling method. The method uses a search-direction obtained by minimizing the duality gap over a linearly transformed conic section. This direction neither coincides with known primal-dual affine scaling directions (Jansen et al., 1993; Monteiro et al., 1990), nor does it fit in the generic primal-dual method (Kojima et al., 1989). The new method requires main iterations. It is shown that the iterates follow the primal-dual central path in a neighbourhood larger than the conventional neighbourhood. The proximity to the primal-dual central path is measured by trigonometric functions.     

On minimum delta set values in block monoids over cyclic groups

The difference in length between two distinct factorizations of an element in a Dedekind domain or in the corresponding block monoid is an object of study in the theory of non-unique factorizations. It provides an alternate way, distinct from what the elasticity provides, of measuring the degree of non-uniqueness of factorizations. In this paper, we discuss the difference in consecutive lengths of irreducible factorizations in block monoids of the form where . We will show that the greatest integer r, denoted by , which divides every difference in lengths of factorizations in can be immediately determined by considering the continued fraction of . We then consider the set including necessary and sufficient conditions (which depend on p) for a value to be an element of . 2000 Mathematics Subject Classification Primary—20M14, 11A55, 20D60, 11A51 Parts of this work are contained in the first author’s Doctoral Dissertation written at the University of North Carolina at Chapel Hill under the direction of the third author.     

How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds

By refining a variant of the Klee–Minty example that forces the central path to visit all the vertices of the Klee–Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is , we prove that solving this n-dimensional linear optimization problem requires at least 2 ⁿ −1 iterations. Dedicated to Professor Emil Klafszky on the occasion of his 70th birthday.     

Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm

In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex–concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency . Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.