On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

On numerical optimization theory of infinite kernel learning

In Machine Learning algorithms, one of the crucial issues is the representation of the data. As the given data source become heterogeneous and the data are large-scale, multiple kernel methods help to classify “nonlinear data”. Nevertheless, the finite combinations of kernels are limited up to a finite choice. In order to overcome this discrepancy, a novel method of  “infinite”  kernel combinations is proposed with the help of infinite and semi-infinite programming regarding all elements in kernel space. Looking at all infinitesimally fine convex combinations of the kernels from the infinite kernel set, the margin is maximized subject to an infinite number of constraints with a compact index set and an additional (Riemann–Stieltjes) integral constraint due to the combinations. After a parametrization in the space of probability measures, it becomes semi-infinite. We adapt well-known numerical methods to our infinite kernel learning model and analyze the existence of solutions and convergence for the given algorithms. We implement our new algorithm called “infinite” kernel learning (IKL) on heterogenous data sets by using exchange method and conceptual reduction method, which are well known numerical techniques from solve semi-infinite programming. The results show that our IKL approach improves the classifaction accuracy efficiently on heterogeneous data compared to classical one-kernel approaches.     

On the interaction of δ-shocks and contact vacuum states

We study the pressureless gas equations, with piecewise constant initial data. In the immediate solution, δ-shocks and contact vacuum states arise and even meet (interact) eventually. A solution beyond the “interaction” is constructed. It shows that the δ-shock will continue with the velocity it attained instantaneously before the time of interaction, and similarly, the contact vacuum state will move past the δ-shock with a velocity value prior to the interaction. We call this the “no-effect-from-interaction” solution. We prove that this solution satisfies a family of convex entropies (in the Lax’s sense). Next, we construct an infinitely large family of weak solutions to the “interaction”. Suppose further that any of these solutions satisfy a convex entropy, it is necessary and suffcient that these solutions reduce to only the “no-effect-from-interaction” solution. In [1], Bouchut constructed another entropy satisfying solution. As with other previous papers, it is obvious that it will not be sufficient that a “correct” solution satisfies a convex entropy, in a non-strictly hyperbolic conservation laws system.     

On the interaction of δ-shocks and contact vacuum states

We study the pressureless gas equations, with piecewise constant initial data. In the immediate solution, δ-shocks and contact vacuum states arise and even meet (interact) eventually. A solution beyond the “interaction” is constructed. It shows that the δ-shock will continue with the velocity it attained instantaneously before the time of interaction, and similarly, the contact vacuum state will move past the δ-shock with a velocity value prior to the interaction. We call this the “no-effect-from-interaction” solution. We prove that this solution satisfies a family of convex entropies (in the Lax’s sense). Next, we construct an infinitely large family of weak solutions to the “interaction”. Suppose further that any of these solutions satisfy a convex entropy, it is necessary and suffcient that these solutions reduce to only the “no-effect-from-interaction” solution. In [1], Bouchut constructed another entropy satisfying solution. As with other previous papers, it is obvious that it will not be sufficient that a “correct” solution satisfies a convex entropy, in a non-strictly hyperbolic conservation laws system. Research done in the University of Michigan-Ann Arbor, submission from Temasek Laboratories, National University of Singapore.     

Turing cones and set theory of the reals

We investigate Turing cones as sets of reals, and look at the relationship between Turing cones, measures, Baire category and special sets of reals, using these methods to show that Martin's proof of Turing Determinacy (every determined Turing closed set contains a Turing cone or is disjoint from one) does not work when you replace “determined” with “Blackwell determined”. This answers a question of Tony Martin. Received: 6 December 1999 / Revised version: 28 June 2000 Published online: 3 October 2001     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

A sequential iteration algorithm with non-monotoneous behaviour in the method of projections onto convex sets

The method of projections onto convex sets to find a point in the intersection of a finite number of closed convex sets in a Euclidean space, may lead to slow convergence of the constructed sequence when that sequence enters some narrow “corridor” between two or more convex sets. A way to leave such corridor consists in taking a big step at different moments during the iteration, because in that way the monotoneous behaviour that is responsible for the slow convergence may be interrupted. In this paper we present a technique that may introduce interruption of the monotony for a sequential algorithm, but that at the same time guarantees convergence of the constructed sequence to a point in the intersection of the sets. We compare experimentally the behaviour concerning the speed of convergence of the new algorithm with that of an existing monotoneous algorithm.     

On growth and covering theorems of quasi-convex mappings in the unit ball of a complex banach space

A class of biholomorphic mappings named “quasi-convex mapping” is introduced in the unit ball of a complex Banach space. It is proved that this class of mappings is a proper subset of the class of starlike mappings and contains the class of convex mappings properly, and it has the same growth and covering theorems as the convex mappings. Furthermore, when the Banach space is confined to ℂⁿ, the “quasi-convex mapping” is exactly the “quasi-convex mapping of type A” introduced by K. A. Roper and T. J. Suffridge.     

Nonuniqueness results for X-ray problems with point sources

Let be any finite set with no three points on a line. Then we construct explicitly families of bounded Borel sets which are not uniquely determined by their X-ray images from the points inX. This result is in sharp contrast to the known uniqueness results for convex sets (Hammer's X-ray problem). This research was partially supported by the Italian “Consiglio Nazionale delle Ricerche.”     

Baire property and axiom of choice

We show that without using inaccessible cardinals it is possible to get models of “ZF+all sets of reals have the Baire property +DC(ω₁)” and “ZFC+all projective sets have the Baire property+the union of less than ω₂ many meager sets is meager”, answering two well-known open questions of Woodin and Judah, respectively. The authors would like to thank the Israel Academy of Sciences BSF for partial support. The second author would like to thank the Landau Center for Mathematical Analysis, supported by the Minerva Foundation (Germany).     

How canonical is the canonical model? A comment on Aumann's interactive epistemology

Aumann (1989) argued that the natural partitions on the space of all maximally consistent sets of formulas in multi-player S5 logic are necessarily “commonly known” by the players. We show, however, that there are many other sets of partitions on this space that conform with the formulas that build the states – as many as there are subsets of the continuum! Thus, assuming a set of partitions on this space is “common knowledge” is an informal but meaningful meta-assumption.     

Variable metric bundle methods: From conceptual to implementable forms

To minimize a convex function, we combine Moreau-Yosida regularizations, quasi-Newton matrices and bundling mechanisms. First we develop conceptual forms using “reversal” quasi-Newton formulae and we state their global and local convergence. Then, to produce implementable versions, we incorporate a bundle strategy together with a “curve-search”. No convergence results are given for the implementable versions; however some numerical illustrations show their good behaviour even for large-scale problems.     

Uniformly convex spaces,bead spaces,and equivalence conditions

The notion of a metric bead space was introduced in the preceding paper (L.Pasicki: Bead spaces and fixed point theorems, Topology Appl., vol. 156 (2009), 1811–1816) and it was proved there that every bounded set in such a space (provided the space is complete) has a unique central point. The bead spaces themselves can be considered in particular as natural extensions of convex sets in uniformly convex spaces. It appears that normed bead spaces are identical with uniformly convex spaces. On the other hand the “metric” approach leads to new elementary conditions equivalent to the uniform convexity. The initial part of the paper contains the proof that discus spaces (they seem to have a richer structure) are identical with bead spaces.     

Generalized breadths,circular Cantor sets,and the least area UCC

We develop a technique suitable for determining the minimal area convex set that can cover certain prescribed regular polygons. As a side effect we improve the well-known “circle-and-triangle” lower bound on the least area Universal Convex Cover (UCC). Dedicated to the memory of Zs. Baranyai     

On duality gap in linear conic problems

In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and (D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing examples of closed convex cone in \mathbbR⁴{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B) established by Shapiro and Nemirovski.     

Toric Kempf-Ness sets

In the theory of algebraic group actions on affine varieties, the concept of a Kempf-Ness set is used to replace the categorical quotient by the quotient with respect to a maximal compact subgroup. Using recent achievements of “toric topology,” we show that an appropriate notion of a Kempf-Ness set exists for a class of algebraic torus actions on quasiaffine varieties (coordinate subspace arrangement complements) arising in the Batyrev-Cox “geometric invariant theory” approach to toric varieties. We proceed by studying the cohomology of these “toric” Kempf-Ness sets. In the case of projective nonsingular toric varieties the Kempf-Ness sets can be described as complete intersections of real quadrics in a complex space. Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2008, Vol. 263, pp. 159–172.     

On the role of convexity in isoperimetry,spectral gap and concentration

We show that for convex domains in Euclidean space, Cheeger’s isoperimetric inequality, spectral gap of the Neumann Laplacian, exponential concentration of Lipschitz functions, and the a-priori weakest requirement that Lipschitz functions have arbitrarily slow uniform tail-decay, are all quantitatively equivalent (to within universal constants, independent of the dimension). This substantially extends previous results of Maz’ya, Cheeger, Gromov–Milman, Buser and Ledoux. As an application, we conclude a sharp quantitative stability result for the spectral gap of convex domains under convex perturbations which preserve volume (up to constants) and under maps which are “on-average” Lipschitz. We also provide a new characterization (up to constants) of the spectral gap of a convex domain, as one over the square of the average distance from the “worst” subset having half the measure of the domain. In addition, we easily recover and extend many previously known lower bounds on the spectral gap of convex domains, due to Payne–Weinberger, Li–Yau, Kannan–Lovász–Simonovits, Bobkov and Sodin. The proof involves estimates on the diffusion semi-group following Bakry–Ledoux and a result from Riemannian Geometry on the concavity of the isoperimetric profile. Our results extend to the more general setting of Riemannian manifolds with density which satisfy the CD(0,∞) curvature-dimension condition of Bakry-émery. Supported by NSF under agreement #DMS-0635607.     

A Variational Proof of Alexandrov’s Convex Cap Theorem

We give a variational proof of the existence and uniqueness of a convex cap with the given metric on the boundary. The proof uses the concavity of the total scalar curvature functional (also called Hilbert-Einstein functional) on the space of generalized convex caps. As a by-product, we prove that generalized convex caps with the fixed metric on the boundary are globally rigid, that is uniquely determined by their curvatures. Research for this article was supported by the DFG Research Unit 565 “Polyhedral Surfaces”.     

A KAM phenomenon for singular holomorphic vector fields

Let X be a germ of holomorphic vector field at the origin of Cⁿ and vanishing there. We assume that X is a good perturbation of a “nondegenerate” singular completely integrable system. The latter is associated to a family of linear diagonal vector fields which is assumed to have nontrivial polynomial first integrals (they are generated by the so called “resonant monomials”). We show that X admits many invariant analytic subsets in a neighborhood of the origin. These are biholomorphic to the intersection of a polydisc with an analytic set of the form “resonant monomials = constants”. Such a biholomorphism conjugates the restriction of X to one of its invariant varieties to the restriction of a linear diagonal vector field to a toric variety. Moreover, we show that the set of “frequencies” defining the invariant sets is of positive measure.     

An Existence Result for a Problem with Critical Growth and Lack of Strict Convexity

We prove the existence of a nontrivial solution for a quasilinear elliptic equation involving a nonlinearity having critical growth and a convex principal part, which is not required to be strictly convex. Supported by MURST, Project “Variational Methods and Nonlinear Differential Equations”.