Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems

We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the optimal solution, and (iv) the level of degeneracy of the optimal solution. We compute these measures for the SDPLIB suite problem instances and measure the sample correlation (CORR) between these measures and IPM iteration counts (solved using the software SDPT3) when these measures have finite values. Our conclusions are roughly as follows: the aggregate geometry measure is highly correlated with IPM iterations (CORR = 0.901), and provides a very good explanation of IPM iterations, particularly for problem instances with solutions of small norm and aspect ratio. The condition measure C(d) is also correlated with IPM iterations, but less so than the aggregate geometry measure (CORR = 0.630). The near-absence of strict complementarity is weakly correlated with IPM iterations (CORR = 0.423). The level of degeneracy of the optimal solution is essentially uncorrelated with IPM iterations. This research has been partially supported through the MIT-Singapore Alliance.     

Characterization of Gromov hyperbolic short graphs

To decide when a graph is Gromov hyperbolic is,in general,a very hard problem.In this paper,we solve this problem for the set of short graphs(in an informal way,a graph G is r-short if the shortcuts in the cycles of G have length less than r):an r-short graph G is hyperbolic if and only if S9r(G)is finite,where SR(G):=sup{L(C):C is an R-isometric cycle in G}and we say that a cycle C is R-isometric if dC(x,y)≤dG(x,y)+R for every x,y∈C.     

On the behavior of the homogeneous self-dual model for conic convex optimization

There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model's behavior are precisely controlled independent of the problem instance: (i) the sizes of ɛ-optimal solutions, and (ii) the maximum distance of ɛ-optimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point solvers such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the ɛ-optimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous self-dual model that might improve the resulting solution time in practice. This research has been partially supported through the MIT-Singapore Alliance.     

Embeddability of multiple cones

The main result of this paper is that if X is a Peano continuum such that its nth cone Cn(X) embeds into Rn+2 then X embeds into S². This solves a problem proposed by W. Rosicki.     

On the duality operator of a convex cone

Let C be a convex set in Rⁿ. For each y?C, the cone of C at y, denoted by cone(y, C), is the cone {α(x ? y): α ? 0 and x?C}. If K is a cone in Rⁿ, we shall denote by $\text{K}{}^1$ its dual cone and by F(K) the lattice of faces of K. Then the duality operator of K is the mapping $\text{d}{}_{\mathrm{K}}\text{: F(K) → F(K}{}^1\text{)}$ given by $\text{d}{}_{\mathrm{K}}\text{(F) = (}\text{span}\text{F)}{}^{\mathrm{\perp }}\text{∩ K}{}^1$. Properties of the duality operator d_K of a closed, pointed, full cone K have been studied before. In this paper, we study d_K for a general cone K, especially in relation to d_{cone(y, K)}, where y?K. Our main result says that, for any closed cone K in Rⁿ, the duality operator d_K is injective (surjective) if and only if the duality operator d_{cone(y, K)} is injective (surjective) for each vector y?K ～ [K ∩ (? K)]. In the last part of the paper, we obtain some partial results on the problem of constructing a compact convex set C, which contains the zero vector, such that cone (0, C) is equal to a given cone.     

Schauder estimates for a class of second order elliptic operators on a cube

We consider a class of second order elliptic operators on a d-dimensional cube S_d. We prove that if the coefficients are of class C^k+δ(S_d), with k=0,1 and δ∈(0,1), then the corresponding elliptic problem admits a unique solution u belonging to C^k+2+δ(S_d) and satisfying non-standard boundary conditions involving only second order derivatives.     

Fourier frequencies in affine iterated function systems

We examine two questions regarding Fourier frequencies for a class of iterated function systems (IFS). These are iteration limits arising from a fixed finite families of affine and contractive mappings in Rd, and the “IFS” refers to such a finite system of transformations, or functions. The iteration limits are pairs (X,μ) where X is a compact subset of Rd (the support of μ), and the measure μ is a probability measure determined uniquely by the initial IFS mappings, and a certain strong invariance axiom. The two questions we study are: (1) existence of an orthogonal Fourier basis in the Hilbert space L²(X,μ); and (2) explicit constructions of Fourier bases from the given data defining the IFS.     

Boundedly connected sets and the distance to the intersection of two sets

We prove that if (X,d) is a metric space, C is a closed subset of X and x∈X, then the distance of x to R∩S agrees with the maximum of the distances of x to R and S, for every closed subsets R,S⊂C such that C=R∪S, if and only if C is x-boundedly connected.     

The Dirichlet-to-Neumann operator on rough domains

We consider a bounded connected open set Ω⊂Rd whose boundary Γ has a finite (d−1)-dimensional Hausdorff measure. Then we define the Dirichlet-to-Neumann operator D₀ on L₂(Γ) by form methods. The operator −D₀ is self-adjoint and generates a contractive C₀-semigroup S=(St)_t>0 on L₂(Γ). We show that the asymptotic behaviour of St as t→∞ is related to properties of the trace of functions in H¹(Ω) which Ω may or may not have.     

Essential self-adjointness of Dirichlet operators on a path space with Gibbs measures via an SPDE approach

The main objective of this paper is to prove the essential self-adjointness of Dirichlet operators in L²(μ) where μ is a Gibbs measure on an infinite volume path space C(R,Rd). This operator can be regarded as a perturbation of the Ornstein-Uhlenbeck operator by a nonlinearity and corresponds to a parabolic stochastic partial differential equation (= SPDE, in abbreviation) on R. In view of quantum field theory, the solution of this SPDE is called a P₁(?)-time evolution.     

Asymptotic behavior of a stochastic growth process associated with a system of interacting branching random walksComportement asymptotique d'un processus stochastique de croissance associé à un système de marches aléatoires en interaction

We study a continuous time growth process on $\text{Z}{}^{\mathrm{d}}$ (d?1) associated to the following interacting particle system: initially there is only one simple symmetric continuous time random walk of total jump rate one located at the origin; then, whenever a random walk visits a site still unvisited by any other random walk, it creates a new independent random walk starting from that site. Let us call P_d the law of such a process and S⁰_d(t) the set of sites, visited by all walks by time t. We prove that there exists a bounded, non-empty, convex set $\text{C}{}_{\mathrm{d}}\text{?}\text{R}{}^{\mathrm{d}}$, such that for every ε>0, P_d-a.s. eventually in t, the set S_d⁰(t) is within an ε neighborhood of the set [C_dt], where for $\text{A?}\text{R}{}^{\mathrm{d}}$ we define $\text{[A]:=A∩}\text{Z}{}^{\mathrm{d}}$. Moreover, for d large enough, the set C_d is not a ball under the Euclidean norm. We also show that the empirical density of particles within S_d⁰(t) converges weakly to a product Poisson measure of parameter one. To cite this article: A.F. Ram??rez, V. Sidoravicius, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 821–826.     

The source location problem with local 3-vertex-connectivity requirements

Let G=(V,E) be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex v∈V has an integer valued demand d(v)?0. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices with the minimum cardinality such that there are at least d(v) vertex-disjoint paths between S and each vertex v∈V-S. In this paper, we show that the problem with d(v)?3, v∈V can be solved in linear time. Moreover, we show that in the case where d(v)?4 for some vertex v∈V, the problem is NP-hard.     

Analysis of nonsmooth vector-valued functions associated with infinite-dimensional second-order cones

Given a Hilbert space H, the infinite-dimensional Lorentz/second-order cone K is introduced. For any x∈H, a spectral decomposition is introduced, and for any function f:R→R, we define a corresponding vector-valued function f^H(x) on Hilbert space H by applying f to the spectral values of the spectral decomposition of x∈H with respect to K. We show that this vector-valued function inherits from f the properties of continuity, Lipschitz continuity, differentiability, smoothness, as well as s-semismoothness. These results can be helpful for designing and analyzing solution methods for solving infinite-dimensional second-order cone programs and complementarity problems.     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Average width and optimal recovery of the anisotropic classesW r H α (R d ) in the metricC k (R d )

This paper concerns the problems of the average widths and the optimal recovery of the anisotropic Hölder classesW ^r H ^α (R ^d ) of smooth functions defined on the Euclidean spaceR ^d in the metricC ^k (R ^d ). The weak asymptotic behavior is established for the corresponding quantities.     

On second-order duality for a class of nondifferentiable minimax fractional programming problem with (C,α,ρ,d)-convexity

In this paper, we derive appropriate duality theorems for three second-order dual models of a nondifferentiable minimax fractional programming problem under second-order (C,α,ρ,d)-convexity assumptions. A nontrivial example has also been exemplified to show the existence of second-order (C,α,ρ,d)-convex functions. Several known results including many recent works are obtained as special cases.     

The metaplectic representation,Weyl operators and spectral theory

Let X be the Grassmannian of Lagrangian subspaces of R²ⁿ and π: Θ → X the bundle of negative half-forms. We construct a canonical imbedding S(Rⁿ)_even → C^∞(Θ) which intertwines the metaplectic representation of M_p(n) on S(Rⁿ) with the induced representation of M_p(n) on C^∞(Θ). This imbedding converts the algebra of Weyl operators into an algebra of pseudodifferential operators and enables us to prove theorems about the spectral properties of Weyl operators by reducing them to standard facts about pseudodifferential operators. For instance we are able to prove a Weyl theorem on the asymptotic growth of eigenvalues with an “optimal” error estimate for such operators and an analogue of the Helton clustering theorem and the Chazarain-Duistermaat-Guillemin trace formula.     

Fitting enclosing cylinders to data in R n

A simple iterative algorithm is given for finding a stationary point of the (non-convex) problem of finding the smallest enclosing (n–d)-cylinder to discrete data in R ⁿ , that is a cylinder whose axis is a d-dimensional linear manifold. An important special case is the problem of finding the smallest enclosing (usual) cylinder, when n=3 and d=1. The method is based on the solution of a sequence of second order cone programming problems, which can be efficiently solved by interior point methods and for which good software packages are available.     

An Extension of a Theorem of Yao and Yao

In this paper we study N _d (k), the smallest positive integer such that any nice measure μ in $\mathbb{R}^{d}$ can be partitioned into N _d (k) convex parts of equal measure so that every hyperplane avoids at least k of them. A theorem of Yao and Yao states that N _d (1)≤2 ^d . Among other results, we obtain the bounds N _d (2)≤3?2 ^d?1 and N _d (1)≥C?2 ^d/2 for some constant C. We then apply these results to a problem on the separation of points and hyperplanes.     

A second-order cone cutting surface method: complexity and application

We present an analytic center cutting surface algorithm that uses mixed linear and multiple second-order cone cuts. Theoretical issues and applications of this technique are discussed. From the theoretical viewpoint, we derive two complexity results. We show that an approximate analytic center can be recovered after simultaneously adding p second-order cone cuts in O(plog (p+1)) Newton steps, and that the overall algorithm is polynomial. From the application viewpoint, we implement our algorithm on mixed linear-quadratic-semidefinite programming problems with bounded feasible region and report some computational results on randomly generated fully dense problems. We compare our CPU time with that of SDPLR, SDPT3, and SeDuMi and show that our algorithm outperforms these software packages on problems with fully dense coefficient matrices. We also show the performance of our algorithm on semidefinite relaxations of the maxcut and Lovasz theta problems. M.R. Oskoorouchi’s work has been completed with the support of the partial research grant from the College of Business Administration, California State University San Marcos, and the University Professional Development Grant. J.E. Mitchell’s material is based upon work supported by the National Science Foundation under Grant No. 0317323. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.