Local overlaps in special unfoldings of convex polyhedra

We define a notion of local overlaps in polyhedron unfoldings. We use this concept to construct convex polyhedra for which certain classes of edge unfoldings contain overlaps, thereby negatively resolving some open conjectures. In particular, we construct a convex polyhedron for which every shortest path unfolding contains an overlap. We also present a convex polyhedron for which every steepest edge unfolding contains an overlap. We conclude by analyzing a broad class of unfoldings and again find a convex polyhedron for which they all contain overlaps.     

Quasimonotone individual demand

Quasimonotone individual demand correspondences are characterized as those which can be rationalized (in a weak sense) by a complete, upper continuous, monotone, and convex preference relation. Moreover, it is shown that an arbitrary set of demand ob-servations can be rationalized by a reflexive, upper continuous, monotone and convex preference if and only if it is properly quasimonotone     

Extending dynamic convex risk measures from discrete time to continuous time: A convergence approach

We present an approach for the transition from convex risk measures in a certain discrete time setting to their counterparts in continuous time. The aim of this paper is to show that a large class of convex risk measures in continuous time can be obtained as limits of discrete time-consistent convex risk measures. The discrete time risk measures are constructed from properly rescaled (‘tilted’) one-period convex risk measures, using a d-dimensional random walk converging to a Brownian motion. Under suitable conditions (covering many standard one-period risk measures) we obtain convergence of the discrete risk measures to the solution of a BSDE, defining a convex risk measure in continuous time, whose driver can then be viewed as the continuous time analogue of the discrete ‘driver’ characterizing the one-period risk. We derive the limiting drivers for the semi-deviation risk measure, Value at Risk, Average Value at Risk, and the Gini risk measure in closed form.     

Convex combinations of continuous t-norms with the same diagonal function

The problem of whether a non-trivial convex combination of two continuous t-norms with the same diagonal function can be a t-norm is studied. It is shown that in both cases–of two nilpotent and of two strict t-norms–a non-trivial convex combination of t-norms with common diagonal function is associative only if the two t-norms involved coincide. For general continuous t-norms a similar result follows. An example of a convex class of non-continuous t-norms is also included.     

Optimal subgradient algorithms for large-scale convex optimization in simple domains

This paper describes two optimal subgradient algorithms for solving structured large-scale convex constrained optimization. More specifically, the first algorithm is optimal for smooth problems with Lipschitz continuous gradients and for Lipschitz continuous nonsmooth problems, and the second algorithm is optimal for Lipschitz continuous nonsmooth problems. In addition, we consider two classes of problems: (i) a convex objective with a simple closed convex domain, where the orthogonal projection onto this feasible domain is efficiently available; and (ii) a convex objective with a simple convex functional constraint. If we equip our algorithms with an appropriate prox-function, then the associated subproblem can be solved either in a closed form or by a simple iterative scheme, which is especially important for large-scale problems. We report numerical results for some applications to show the efficiency of the proposed schemes.     

Characterizations of ultrabarrelledness and barrelledness involving the singularities of families of convex mappings

Summary The paper reveals that ultrabarrelled spaces (respectively barrelled spaces) can be characterized by means of the density of the so-called weak singularities of families consisting of continuous convex mappings that are defined on an open absolutely convex set and take values in a locally full ordered topological linear space (respectively locally full ordered locally convex space). The idea to establish such characterizations arose from the observation that, in virtue of well-known results, the density of the singularities of families of continuous linear mappings allows to characterize both the ultrabarrelled spaces and the barrelled spaces.     

Slice-continuous sets in reflexive Banach spaces: convex constrained optimization and strict convex separation

The concept of continuous set has been used in finite dimension by Gale and Klee and recently by Auslender and Coutat. Here, we introduce the notion of slice-continuous set in a reflexive Banach space and we show that the class of such sets can be viewed as a subclass of the class of continuous sets. Further, we prove that every nonconstant real-valued convex and continuous function, which has a global minima, attains its infimum on every nonempty convex and closed subset of a reflexive Banach space if and only if its nonempty level sets are slice-continuous. Thereafter, we provide a new separation property for closed convex sets, in terms of slice-continuity, and conclude this article by comments.     

A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.     

Ein Approximationssatz für konvexe Körper

It is shown that a convex body in n-dimensional Euclidean space can be approximated by a sequence of smooth convex bodies in such a way that the principal radii of curvature converge in a certain sense. This fact is used to characterize those first surface measures of convex bodies which belong to polytopes. Furthermore it is proved that the support function of a convex body whose first surface measure has bounded density must have continuous first partial derivatives.     

Even valuations on convex bodies

The notion of even valuation is introduced as a natural generalization of volume on compact convex subsets of Euclidean space. A recent characterization theorem for volume leads in turn to a connection between even valuations on compact convex sets and continuous functions on Grassmannians. This connection can be described in part using generating distributions for symmetric compact convex sets. We also explore some consequences of these characterization results in convex and integral geometry.

     

Approximation of continuous set-valued maps by constant set-valued maps with image balls

It is shown that the problem of the best uniform approximation in the Hausdorff metric of a continuous set-valued map with finite-dimensional compact convex images by constant set-valued maps whose images are balls in some norm can be reduced to a visual geometric problem. The latter consists in constructing a spherical layer of minimal thickness which contains the complement of a compact convex set to a larger compact convex set.     

Metric Combinatorics of Convex Polyhedra: Cut Loci and Nonoverlapping Unfoldings

Let S be the boundary of a convex polytope of dimension d+1, or more generally let S be a convex polyhedral pseudomanifold. We prove that S has a polyhedral nonoverlapping unfolding into , so the metric space S is obtained from a closed (usually nonconvex) polyhedral ball in by identifying pairs of boundary faces isometrically. Our existence proof exploits geodesic flow away from a source point v∈S, which is the exponential map to S from the tangent space at v. We characterize the cut locus (the closure of the set of points in S with more than one shortest path to v) as a polyhedral complex in terms of Voronoi diagrams on facets. Analyzing infinitesimal expansion of the wavefront consisting of points at constant distance from v on S produces an algorithmic method for constructing Voronoi diagrams in each facet, and hence the unfolding of S. The algorithm, for which we provide pseudocode, solves the discrete geodesic problem. Its main construction generalizes the source unfolding for boundaries of three-polytopes into . We present conjectures concerning the number of shortest paths on the boundaries of convex polyhedra, and concerning continuous unfolding of convex polyhedra. We also comment on the intrinsic nonpolynomial complexity of nonconvex manifolds. The first author was partially supported by the National Science Foundation, and he acknowledges the Mathematisches Forschungsinstitut Oberwolfach for a stimulating research environment during the week-long program on Topological and Geometric Combinatorics (April, 2003). Most of this work was completed while the first author was at the Massachusetts Institute of Technology (Cambridge, MA) and the Mathematical Sciences Research Institute (Berkeley, CA). The second author was partially supported by the National Security Agency and the National Science Foundation. He thanks the organizers of the “Second Geometry Meeting dedicated to A.D. Aleksandrov” held at the Euler International Mathematical Institute in St. Petersburg (June, 2002), where these results were originally presented.     

Constructive Solution of Inverse Parametric Linear/Quadratic Programming Problems

Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.     

Convex combinations of nilpotent triangular norms

In this paper we deal with the open problem of convex combinations of continuous triangular norms stated by Alsina, Frank, and Schweizer [C. Alsina, M.J. Frank, B. Schweizer, Problems on associative functions, Aequationes Math. 66 (2003) 128-140, Problems 5 and 6]. They pose a question whether a non-trivial convex combination of triangular norms can ever be a triangular norm. The main result of this paper gives a negative answer to the question for any pair of continuous Archimedean triangular norms with different supports. With the help of this result we show that a non-trivial convex combination of nilpotent t-norms is never a t-norm. The main result also gives an alternative proof to the result presented by Ouyang and Fang [Y. Ouyang, J. Fang, Some observations about the convex combination of continuous triangular norms, Nonlinear Anal., 68 (11) (2008) 3382-3387, Theorem 3.1]. In proof of the main theorem we utilize the Reidmeister condition known from the web geometry.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.      

Approximation theory for generalized young measures

Young measures can be understood as certain linear continuous functionals on a space of Caratheodory integrands, which gives a basis for their various generalizations. The (generalized) Young measures can be approximated by several techniques classified here according to the shape (convex/nonconvex) and dimensionality (finite/infinite) of the resulting set of all (semi)discretized generalized Young measures. A general theory for convex approximations is developed here and illustrative applications to a relaxed optimization problem are given to compare various techniques.     

On the Euler characteristic of finite unions of convex sets

The Euler characteristic plays an important role in many subjects of discrete and continuous mathematics. For noncompact spaces, its homological definition, being a homotopy invariant, seems not as important as its role for compact spaces. However, its combinatorial definition, as a finitely additive measure, proves to be more applicable in the study of singular spaces such as semialgebraic sets, finitely subanalytic sets, etc. We introduce an interesting integral by means of which the combinatorial Euler characteristic can be defined without the necessity of decomposition and extension as in the traditional treatment for polyhedra and finite unions of compact convex sets. Since finite unions of closed convex sets cannot be obtained by cutting convex sets as in the polyhedral case, a separate treatment of the Euler characteristic for functions generated by indicator functions of closed convex sets and relatively open convex sets is necessary, and this forms the content of this paper.     

Least-norm linear programming solution as an unconstrained minimization problem

It is shown that the dual of the problem of minimizing the 2-norm of the primal and dual optimal variables and slacks of a linear program can be transformed into an unconstrained minimization of a convex parameter-free globally differentiable piecewise quadratic function with a Lipschitz continuous gradient. If the slacks are not included in the norm minimization, one obtains a minimization problem with a convex parameter-free quadratic objective function subject to nonnegativity constraints only.     

Fitting piecewise linear continuous functions

We consider the problem of fitting a continuous piecewise linear function to a finite set of data points, modeled as a mathematical program with convex objective. We review some fitting problems that can be modeled as convex programs, and then introduce mixed-binary generalizations that allow variability in the regions defining the best-fit function’s domain. We also study the additional constraints required to impose convexity on the best-fit function.     

Refold rigidity of convex polyhedra

We show that every convex polyhedron may be unfolded to one planar piece, and then refolded to a different convex polyhedron. If the unfolding is restricted to cut only edges of the polyhedron, we identify several polyhedra that are “edge-refold rigid” in the sense that each of their unfoldings may only fold back to the original. For example, each of the 43,380 edge unfoldings of a dodecahedron may only fold back to the dodecahedron, and we establish that 11 of the 13 Archimedean solids are also edge-refold rigid. We begin the exploration of which classes of polyhedra are and are not edge-refold rigid, demonstrating infinite rigid classes through perturbations, and identifying one infinite nonrigid class: tetrahedra.