Motzkin Decomposable Sets

Theodore Motzkin proved, in 1936, that any polyhedral convex set can be expressed as the (Minkowski) sum of a polytope and a polyhedral convex cone. We have provided several characterizations of the larger class of closed convex sets, Motzkin decomposable, in finite dimensional Euclidean spaces which are the sum of a compact convex set with a closed convex cone. These characterizations involve different types of representations of closed convex sets as the support functions, dual cones and linear systems whose relationships are also analyzed. The obtaining of information about a given closed convex set F and the parametric linear optimization problem with feasible set F from each of its different representations, including the Motzkin decomposition, is also discussed. Another result establishes that a closed convex set is Motzkin decomposable if and only if the set of extreme points of its intersection with the linear subspace orthogonal to its lineality is bounded. We characterize the class of the extended functions whose epigraphs are Motzkin decomposable sets showing, in particular, that these functions attain their global minima when they are bounded from below. Calculus of Motzkin decomposable sets and functions is provided.

Duality in Constrained DC-Optimization via Toland’s Duality Approach

2000 Mathematics Subject Classification: 90C48, 49N15, 90C25

Dense Subdifferentiability and Trustworthiness for Arbitrary Subdifferentials

2000 Mathematics Subject Classification: 49J52, 49J50, 58C20, 26B09.

Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions

In this paper we consider the problem of learning an n × n kernel matrix from m(1) similarity matrices under general convex loss. Past research have extensively studied the m = 1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well knownMirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m2 log n 2) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n × n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL,which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVMsolver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

Turbulence modeling for flows around convex features giving rapid eddy distortion

Reynolds averaged Navier-Stokes model performances in the stagnation and wake regions for turbulent flows with relatively large Lagrangian length scales (generally larger than the scale of geometrical features) approaching small cylinders (both square and circular) is explored. The effective cylinder (or wire) diameter based Reynolds number, ReW ≤ 2.5 × 103. The following turbulence models are considered: a mixing-length; standard Spalart and Allmaras (SA) and streamline curvature (and rotation) corrected SA (SARC); Secundov's νt-92; Secundov et al.'s two equation νt-L; Wolfshtein's k-l model; the Explicit Algebraic Stress Model (EASM) of Abid et al.; the cubic model of Craft et al.; various linear k-ε models including those with wall distance based damping functions; Menter SST, k-ω and Spalding's LVEL model. The use of differential equation distance functions (Poisson and Hamilton-Jacobi equation based) for palliative turbulence modeling purposes is explored. The performance of SA with these distance functions is also considered in the sharp convex geometry region of an airfoil trailing edge. For the cylinder, with ReW ≈ 2.5 × 103 the mixing length and k-l models give strong turbulence production in the wake region. However, in agreement with eddy viscosity estimates, the LVEL and Secundov νt-92 models show relatively little cylinder influence on turbulence. On the other hand, two equation models (as does the one equation SA) suggest the cylinder gives a strong turbulence deficit in the wake region. Also, for SA, an order or magnitude cylinder diameter decrease from ReW = 2500 to 250 surprisingly strengthens the cylinder's disruptive influence. Importantly, results for ReW ≪ 250 are virtually identical to those for ReW = 250 i.e. no matter how small the cylinder/wire its influence does not, as it should, vanish. Similar tests for the Launder-Sharma k-ε, Menter SST and k-ω show, in accordance with physical reality, the cylinder's influence diminishing albeit slowly with size. Results suggest distance functions palliate the SA model's erroneous trait and improve its predictive performance in wire wake regions. Also, results suggest that, along the stagnation line, such functions improve the SA, mixing length, k-l and LVEL results. For the airfoil, with SA, the larger Poisson distance function increases the wake region turbulence levels by just under 5%. © 2007 Elsevier Inc. All rights reserved.

Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Highly accurate and efficient evaluation of randomising set index functions

Randomising set index functions can reduce the number of conflict misses in data caches by spreading the cache blocks uniformly over all sets. Typically, the randomisation functions compute the exclusive ors of several address bits. Not all randomising set index functions perform equally well, which calls for the evaluation of many set index functions. This paper discusses and improves a technique that tackles this problem by predicting the miss rate incurred by a randomisation function, based on profiling information. A new way of looking at randomisation functions is used, namely the null space of the randomisation function. The members of the null space describe pairs of cache blocks that are mapped to the same set. This paper presents an analytical model of the error made by the technique and uses this to propose several optimisations to the technique. The technique is then applied to generate a conflict-free randomisation function for the SPEC benchmarks. (C) 2003 Elsevier Science B.V. All rights reserved.

Computing Distance Functions from Generalized Sources on Weighted Polyhedral Surfaces

We present algorithms for computing approximate distance functions and shortest paths from a generalized source (point, segment, polygonal chain or polygonal region) on a weighted non-convex polyhedral surface in which obstacles (represented by polygonal chains or polygons) are allowed. We also describe an algorithm for discretizing, by using graphics hardware capabilities, distance functions. Finally, we present algorithms for computing discrete k-order Voronoi diagrams

Solvability and spectral properties of integral equations on the real line: I. Weighted spaces of continuous functions

We consider in this paper the solvability of linear integral equations on the real line, in operator form (λ−K)φ=ψ, where and K is an integral operator. We impose conditions on the kernel, k, of K which ensure that K is bounded as an operator on . Let Xa denote the weighted space as |s|→∞}. Our first result is that if, additionally, |k(s,t)|⩽κ(s−t), with and κ(s)=O(|s|−b) as |s|→∞, for some b>1, then the spectrum of K is the same on Xa as on X, for 01. As an example where kernels of this latter form occur we discuss a boundary integral equation formulation of an impedance boundary value problem for the Helmholtz equation in a half-plane.

Entire functions uniformly bounded on balls of a Banach space

Let X be an in�finite-dimensional complex Banach space. Very recently, several results on the existence of entire functions on X bounded on a given ball B1 � X and unbounded on another given ball B2 � X have been obtained. In this paper we consider the problem of �finding entire functions which are uniformly bounded on a collection of balls and unbounded on the balls of some other collection. RESUMEN. Sea X un espacio de Banach complejo de dimensión infinita. En este trabajo, los autores estudian el problema de encontrar una función entera en X que esté uniformemente acotada en una colección de de bolas en X y que no esté acotada en las bolas de otra colección.

Tables of the Bessel functions, Y₀(x), Y₁(x), K₀(x), K₁(x), 0 <̳ x <̳ 1.

Bibliography: p. ix.

On Averaging Null Sequences of Real-Valued Functions

If ξ is a countable ordinal and (fk) a sequence of real-valued functions we define the repeated averages of order ξ of (fk). By using a partition theorem of Nash-Williams for families of finite subsets of positive integers it is proved that if ξ is a countable ordinal then every sequence (fk) of real-valued functions has a subsequence (f'k) such that either every sequence of repeated averages of order ξ of (f'k) converges uniformly to zero or no sequence of repeated averages of order ξ of (f'k) converges uniformly to zero. By the aid of this result we obtain some results stronger than Mazur’s theorem.

Asplund Functions and Projectional Resolutions of the Identity

*Supported by the Grants AV ˇCR 101-97-02, 101-90-03, GA ˇCR 201-98-1449, and by the Grant of the Faculty of Civil Engineering of the Czech Technical University No. 2003.