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

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.      

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 central limit theorems for kernel density estimators

Let be the classical kernel density estimator based on a kernel K and n independent random vectors X _i each distributed according to an absolutely continuous law on . It is shown that the processes , , converge in law in the Banach space , for many interesting classes of functions or sets, some -Donsker, some just -pregaussian. The conditions allow for the classical bandwidths h _n that simultaneously ensure optimal rates of convergence of the kernel density estimator in mean integrated squared error, thus showing that, subject to some natural conditions, kernel density estimators are ‘plug-in’ estimators in the sense of Bickel and Ritov (Ann Statist 31:1033–1053, 2003). Some new results on the uniform central limit theorem for smoothed empirical processes, needed in the proofs, are also included.      

Blaschke’s problem for hypersurfaces

We solve Blaschke’s problem for hypersurfaces of dimension . Namely, we determine all pairs of Euclidean hypersurfaces that induce conformal metrics on M ⁿ and envelop a common sphere congruence in .     

MIP reformulations of the probabilistic set covering problem

In this paper, we address the following probabilistic version (PSC) of the set covering problem: where A is a 0-1 matrix, is a random 0-1 vector and is the threshold probability level. We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at deriving an equivalent MIP reformulation of (PSC), the latter is used as a strengthening device to obtain a stronger formulation. Simplifications of the MIP model which result when one of the following conditions hold are briefly discussed: A is a balanced matrix, A has the circular ones property, the components of are pairwise independent, the distribution function of is a stationary distribution or has the disjunctive shattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. This test-bed was created using deterministic instances from the literature and consists of probabilistic variants of the set covering model and capacitated versions of facility location, warehouse location and k-median models. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to a fraction of a second. Anureet Saxena’s research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133. Vineet Goyal’s research was supported in part by NSF grant CCF-0430751 and ITR grant CCR-0122581.     

A {\mathsf{D}}-induced duality and its applications

This paper attempts to extend the notion of duality for convex cones, by basing it on a prescribed conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the nonnegativity of the inner-product is replaced by a pre-specified conic ordering, defined by a convex cone , and the inner-product itself is replaced by a general multi-dimensional bilinear mapping. This new type of duality is termed the -induced duality in the paper. We further introduce the notion of -induced polar sets within the same framework, which can be viewed as a generalization of the -induced dual cones and is convenient to use for some practical applications. Properties of the extended duality, including the extended bi-polar theorem, are proven. Furthermore, attention is paid to the computation and approximation of the -induced dual objects. We discuss, as examples, applications of the newly introduced -induced duality concepts in robust conic optimization and the duality theory for multi-objective conic optimization. Research supported in part by the Foundation ‘Vereniging Trustfonds Erasmus Universiteit Rotterdam’ in The Netherlands, and in part by Hong Kong RGC Earmarked Grants CUHK4174/03E and CUHK418406.     

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.      

Well-posedness of constrained minimization problems via saddle-points

In this paper, it is proved a very general well-posedness result for a class of constrained minimization problems of which the following is a particular case: Let X be a Hausdorff topological space and let be two non-constant functions such that, for each , the function has sequentially compact sub-level sets and admits a unique global minimum in X. Then, for each , the restriction of J to has a unique global minimum, say , toward which every minimizing sequence converges. Moreover, the functions and are continuous in .     

Increasing functions and inverse Santaló inequality for unconditional functions

Let be a convex function and be its Legendre tranform. It is proved that if is invariant by changes of signs, then . This is a functional version of the inverse Santaló inequality for unconditional convex bodies due to J. Saint Raymond. The proof involves a general result on increasing functions on together with a functional form of Lozanovskii’s lemma. In the last section, we prove that for some c > 0, one has always . This generalizes a result of B. Klartag and V. Milman.      

Calderón–Zygmund estimates for higher order systems with p(x) growth

For weak solutions of higher order systems of the type , for all , with variable growth exponent p : Ω → (1,∞) we prove that if with , then . We should note that we prove this implication both in the non-degenerate (μ > 0) and in the degenerate case (μ = 0).     

Logical Extensions of Aristotle’s Square

We start from the geometrical-logical extension of Aristotle’s square in [6,15] and [14], and study them from both syntactic and semantic points of view. Recall that Aristotle’s square under its modal form has the following four vertices: A is □α, E is , I is and O is , where α is a logical formula and □ is a modality which can be defined axiomatically within a particular logic known as S5 (classical or intuitionistic, depending on whether is involutive or not) modal logic. [3] has proposed extensions which can be interpreted respectively within paraconsistent and paracomplete logical frameworks. [15] has shown that these extensions are subfigures of a tetraicosahedron whose vertices are actually obtained by closure of by the logical operations , under the assumption of classical S5 modal logic. We pursue these researches on the geometrical-logical extensions of Aristotle’s square: first we list all modal squares of opposition. We show that if the vertices of that geometrical figure are logical formulae and if the sub-alternation edges are interpreted as logical implication relations, then the underlying logic is none other than classical logic. Then we consider a higher-order extension introduced by [14], and we show that the same tetraicosahedron plays a key role when additional modal operators are introduced. Finally we discuss the relation between the logic underlying these extensions and the resulting geometrical-logical figures.      

Necessary and sufficient conditions for tight equi-difference conflict-avoiding codes of weight three

A conflict-avoiding code (CAC) C of length n and weight k is a collection of k-subsets of such that holds for any , , where . A CAC with maximum code size for given n and k is called optimal. Furthermore, an optimal CAC C is said to be tight equi-difference if holds and any codeword has the form . The concept of a CAC is motivated from applications in multiple-access communication systems. In this paper, we give a necessary and sufficient condition to construct tight equi-difference CACs of weight k = 3 and characterize the code length n’s admitting the condition through a number theoretical approach.      

A Marstrand theorem for measures with polytope density

Given and any centrally symmetric convex polytope , define we prove that if a Radon measure μ has the property then s is an integer. For the case Θ is the Euclidean ball, this result was first proved by Marstrand in 1955 for Hausdorff measure in the plane (Marstrand in Proc Lond Math Soc 3(4):257–302, 1954) and later for general Radon measures in (Marstrand in Trans Am Math Soc 205:369–392, 1964).     

Positivity of the spherically averaged atomic one-electron density

We investigate the positivity of the spherically averaged atomic one-electron density . For a which stems from a physical ground state we prove that for r ≥ 0. This article may be reproduced in its entirety for non-commercial purposes.     

Bifurcations of Positive and Negative Continua in Quasilinear Elliptic Eigenvalue Problems

The main result of this work is a Dancer-type bifurcation result for the quasilinear elliptic problem

A Slow Transient Diffusion in a Drifted Stable Potential

We consider a diffusion process X in a random potential of the form , where is a positive drift and is a strictly stable process of index with positive jumps. Then the diffusion is transient and converges in law towards an exponential distribution. This behaviour contrasts with the case where is a drifted Brownian motion and provides an example of a transient diffusion in a random potential which is as “slow” as in the recurrent setting.      

Selections of lattice-ordered Groups

It is well known that the quasitorsion class of archimedean -groups is the class of -groups G such that every closed convex -subgroup is a polar, and it is also well known that the class of -groups G such that every convex -subgroup is a polar is a torsion class. By defining a selection on -groups, these two results are generalized to show, whenever and are selections on -groups, the class of -groups G such that is a radical class. Three selections in particular — all convex -subgroups, all polars, and all closed convex -subgroups — and the radical classes determined by them are studied in some detail. Received March 7, 2006; accepted in final form August 29, 2006.     

A geometric analysis of Renegar’s condition number,and its interplay with conic curvature

For a conic linear system of the form Ax ∈K, K a convex cone, several condition measures have been extensively studied in the last dozen years. Among these, Renegar’s condition number is arguably the most prominent for its relation to data perturbation, error bounds, problem geometry, and computational complexity of algorithms. Nonetheless, is a representation-dependent measure which is usually difficult to interpret and may lead to overly conservative bounds of computational complexity and/or geometric quantities associated with the set of feasible solutions. Herein we show that Renegar’s condition number is bounded from above and below by certain purely geometric quantities associated with A and K; furthermore our bounds highlight the role of the singular values of A and their relationship with the condition number. Moreover, by using the notion of conic curvature, we show how Renegar’s condition number can be used to provide both lower and upper bounds on the width of the set of feasible solutions. This complements the literature where only lower bounds have heretofore been developed.