Finding curves on general spaces through quantitative topology,with applications to Sobolev and Poincaré inequalities

In many metric spaces one can connect an arbitrary pair of points with a curve of finite length, but in Euclidean spaces one can connect a pair of points with a lot of rectifiable curves, curves that are well distributed across a region. In the present paper we give geometric criteria on a metric space under which we can find similar families of curves. We shall find these curves by first solving a dual problem of building Lipschitz maps from our metric space into a sphere with good topological properties. These families of curves can be used to control the values of a function in terms of its gradient (suitably interpreted on a general metric space), and to derive Sobolev and Poincaré inequalities.The author is supported by the U.S. National Science Foundation and grateful to IHES for its hospitality.     

Embedding metric spaces in Euclidean space

In this paper, we give necessary and sufficient conditions for embedding a given metric space in Euclidean space. We shall introduce the notions of flatness and dimension for metric spaces and prove that a metric space can be embedded in Euclidean n-space if and only if the metric space is flat and of dimension less than or equal to n.     

An approximation algorithm for solving a problem of search for a vector subset

One of the problems in data analysis was earlier reduced to a specific NP-hard optimization problem of finding in a given vector set in the Euclidean space a subset of a given cardinality such that the subset consists of the vectors that are “close” to each other by the criterion of the minimum sum of squared distances. In the paper an efficient 2-approximation algorithm is proposed for solving this problem.     

Mappings of Domains in Rn and Their Metric Tensors

We consider quasi-isometric mappings of domains in multidimensional Euclidean spaces. We establish that a mapping depends continuously in the sense of the topology of Sobolev classes on its metric tensor to within isometry of the space. In the space of metric tensors we take the topology determined by means of almost everywhere convergence. We show that if the metric tensor of a mapping is continuous then the length of the image of a rectifiable curve is determined by the same formula as in the case of mappings with continuous derivatives. (Continuity of the metric tensor of a mapping does not imply continuity of its derivatives.)     

Space tensor conic programming

Space tensors appear in physics and mechanics. Mathematically, they are tensors in the three-dimensional Euclidean space. In the research area of diffusion magnetic resonance imaging, convex optimization problems are formed where higher order positive semi-definite space tensors are involved. In this short paper, we investigate these problems from the viewpoint of conic linear programming (CLP). We characterize the dual cone of the positive semi-definite space tensor cone, and study the CLP formulation and the duality of positive semi-definite space tensor conic programming.     

The stress-energy tensor for biharmonic maps

Using Hilbert’s criterion, we consider the stress-energy tensor associated to the bienergy functional. We show that it derives from a variational problem on metrics and exhibit the peculiarity of dimension four. First, we use this tensor to construct new examples of biharmonic maps, then classify maps with vanishing or parallel stress-energy tensor and Riemannian immersions whose stress-energy tensor is proportional to the metric, thus obtaining a weaker but high-dimensional version of the Hopf Theorem on compact constant mean curvature immersions. We also relate the stress-energy tensor of the inclusion of a submanifold in Euclidean space with the harmonic stress-energy tensor of its Gauss map. S. Montaldo was supported by PRIN-2005 (Italy): Riemannian Metrics and Differentiable Manifolds. C. Oniciuc was supported by a CNR-NATO (Italy) fellowship and by the Grant CEEX, ET, 5871/2006 (Romania).     

Approximation algorithms for some intractable problems of choosing a vector subsequence

We consider some intractable optimization problems of finding a subsequence in a finite sequence of vectors of the Euclidean space. We assume that the sought subsequence contains a fixed number of vectors close to each other under the criterion of the minimum sum of the squares of distances. Moreoveer, this subsequence has to satisfy the following condition: the difference between the indexes of each previous and next vectors of the sought subsequence is bounded with lower and upper constants. Some 2-approximation efficient algorithms for solving these problems are introduced.     

The problem of finding a subset of vectors with the maximum total weight

The NP-hardness is proved for the discrete optimization problems connected with maximizing the total weight of a subset of a finite set of vectors in Euclidean space, i.e., the Euclidean norm of the sum of the members. Two approximation algorithms are suggested, and the bounds for the relative error and time complexity are obtained. We give a polynomial approximation scheme in the case of a fixed dimension and distinguished a subclass of problems solvable in pseudopolynomial time. The results obtained are useful for solving the problem of choice of a fixed number of subsequences from a numerical sequence with a given number of quasiperiodical repetitions of the subsequence.     

Stochastic Programming with Multivariate Second Order Stochastic Dominance Constraints with Applications in Portfolio Optimization

In this paper we study optimization problems with multivariate stochastic dominance constraints where the underlying functions are not necessarily linear. These problems are important in multicriterion decision making, since each component of vectors can be interpreted as the uncertain outcome of a given criterion. We propose a penalization scheme for the multivariate second order stochastic dominance constraints. We solve the penalized problem by the level function methods, and a modified cutting plane method and compare them to the cutting surface method proposed in the literature. The proposed numerical schemes are applied to a generic budget allocation problem and a real world portfolio optimization problem.     

On Descriptions of Products of Simplices*

The authors give several new criteria to judge whether a simple convex polytope in a Euclidean space is combinatorially equivalent to a product of simplices. These criteria are mixtures of combinatorial, geometrical and topological conditions that are inspired by the ideas from toric topology. In addition, they give a shorter proof of a well known criterion on this subject.     

Sobolev spaces on an arbitrary metric measure space: Compactness of embeddings

We formulate a new definition of Sobolev function spaces on a domain of a metric space in which the doubling condition need not hold. The definition is equivalent to the classical definition in the case that the domain lies in a Euclidean space with the standard Lebesgue measure. The boundedness and compactness are examined of the embeddings of these Sobolev classes into L _q and C _α . We state and prove a compactness criterion for the family of functions L _p (U), where U is a subset of a metric space possibly not satisfying the doubling condition.     

关于随机赋范空间与随机内积空间的某些基本理论(英文)

首先提出随机度量空间定义的另一个提法,这提法不仅等价于原始的定义而且也使随机度量空间自动归入广义度量空间的框架,也考虑了关于拓扑结构的某些新的问题;循着同样的思路,对随机赋范空间的定义也作了新的处理并同时简化了随机赋范模的定义．其次本文也证明了一个Ｅ－范空间的商空间等距同构于一个典型的Ｅ－范空间;进一步,在概率赋范空间的框架下证明了一个概率赋伪范空间是伪内积生成空间的充要条件是它等距同构于一个Ｅ－内积空间,这回答了Ｃ．Ａｌｓｉｎａ与Ｂ．Ｓｃｈｗｅｉｚｅｒ等人新近提出的公开问题．最后,本文转向了它的中心部分──关于随机内积空间的研究,对随机内积空间中的特有且复杂的正交性作较系统的讨论,论证了只有几乎处处正交性才是唯一合理的正交性概念,在此基础上本文尤其将Ｇ．Ｓｔａｍｐａｃｃｈｉａ的在众多学科中都有多种用途的一般投影定理（或称变分不等式解存在性定理）以适当形式推广到完备实随机内积模上．     

On Optimization Problems with Set-Valued Objective Maps: Existence and Optimality

In this paper, we consider constrained optimization problems with set-valued objective maps. First, we define three types of quasi orderings on the set of all non-empty subsets of n-dimensional Euclidean space. Second, by using these quasi orderings, we define the concepts of lower semi-continuity for set-valued maps and investigate their properties. Finally, based on these results, we define the concepts of optimal solutions to constrained optimization problems with set-valued objective maps and we give some conditions under which these optimal solutions exist to the problems and give necessary and sufficient conditions for optimality.     

On an equivalence of topological vector space valued cone metric spaces and metric spaces

Scalarization method is an important tool in the study of vector optimization as corresponding solutions of vector optimization problems can be found by solving scalar optimization problems. Recently this has been applied by Du (2010) [14] to investigate the equivalence of vectorial versions of fixed point theorems of contractive mappings in generalized cone metric spaces and scalar versions of fixed point theorems in general metric spaces in usual sense. In this paper, we find out that the topology induced by topological vector space valued cone metric coincides with the topology induced by the metric obtained via a nonlinear scalarization function, i.e any topological vector space valued cone metric space is metrizable, prove a completion theorem, and also obtain some more results in topological vector space valued cone normed spaces.     

Performance of first-order methods for smooth convex minimization: a novel approach

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. Our approach relies on the observation that by definition, the worst-case behavior of a black-box optimization method is by itself an optimization problem, which we call the performance estimation problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance.     

On the proximal point method in Hadamard spaces

Proximal point method is one of the most influential procedure in solving nonlinear variational problems. It has recently been introduced in Hadamard spaces for solving convex optimization, and later for variational inequalities. In this paper, we study the general proximal point method for finding a zero point of a maximal monotone set-valued vector field defined on a Hadamard space and valued in its dual. We also give the relation between the maximality and Minty’s surjectivity condition, which is essential for the proximal point method to be well-defined. By exploring the properties of monotonicity and the surjectivity condition, we were able to show under mild assumptions that the proximal point method converges weakly to a zero point. Additionally, by taking into account the metric subregularity, we obtained the local strong convergence in linear and super-linear rates.     

Local Tensor Valuations

The local Minkowski tensors are valuations on the space of convex bodies in Euclidean space with values in a space of tensor measures. They generalize at the same time the intrinsic volumes, the curvature measures and the isometry covariant Minkowski tensors that were introduced by McMullen and characterized by Alesker. In analogy to the characterization theorems of Hadwiger and Alesker, we give here a complete classification of all locally defined tensor measures on convex bodies that share with the local Minkowski tensors the basic geometric properties of isometry covariance and weak continuity.     

Sobolev classes of Banach space-valued functions and quasiconformal mappings

We give a definition for the class of Sobolev functions from a metric measure space into a Banach space. We give various characterizations of Sobolev classes and study the absolute continuity in measure of Sobolev mappings in the “borderline case”. We show under rather weak assumptions on the source space that quasisymmetric homeomorphisms belong to a Sobolev space of borderline degree; in particular, they are absolutely continuous. This leads to an analytic characterization of quasiconformal mappings between Ahlfors regular Loewner spaces akin to the classical Euclidean situation. As a consequence, we deduce that quasisymmetric maps respect the Cheeger differentials of Lipschitz functions on metric measure spaces with borderline Poincaré inequality. J. H. supported by NSF grant DMS9970427. P. K. supported by the Academy of Finland, project 39788. N. S. supported in part by Enterprise Ireland. J. T. T. supported by an NSF Postdoctoral Research Fellowship.     

Method of forces for direction finding in interactive multicriterion optimization applications

The main purpose of this paper is to derive, illustrate, and validate a method of direction finding for use in multicriterion interactive optimization applications. A secondary purpose is to consider electronic spreadsheet operation as an instance of interactive multicriterion optimization and to test the new method in a spreadsheet model for aggregate production planning. The method derived here amounts to virtual direct specification of the gradient direction, but does so by an appeal to the simple physical notion of forces applied to the criteria. It is demonstrated that the idea is easily grasped and also gives effective performance in the application tested.The authors are indebted to Professor Carl Langenhop, Mathematics Department, Southern Illinois University at Carbondale for several useful suggestions.     

On geometric vector fields of Minkowski spaces and their applications

As it is well-known, a Minkowski space is a finite dimensional real vector space equipped with a Minkowski functional F. By the help of its second order partial derivatives we can introduce a Riemannian metric on the vector space and the indicatrix hypersurface S:=F⁻¹(1) can be investigated as a Riemannian submanifold in the usual sense.Our aim is to study affine vector fields on the vector space which are, at the same time, affine with respect to the Funk metric associated with the indicatrix hypersurface. We give an upper bound for the dimension of their (real) Lie algebra and it is proved that equality holds if and only if the Minkowski space is Euclidean. Criteria of the existence is also given in lower dimensional cases. Note that in case of a Euclidean vector space the Funk metric reduces to the standard Cayley-Klein metric perturbed with a nonzero 1-form.As an application of our results we present the general solution of Matsumoto's problem on conformal equivalent Berwald and locally Minkowski manifolds. The reasoning is based on the theory of harmonic vector fields on the tangent spaces as Riemannian manifolds or, in an equivalent way, as Minkowski spaces. Our main result states that the conformal equivalence between two Berwald manifolds must be trivial unless the manifolds are Riemannian.