Polyhedral approximation in mixed-integer convex optimization

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro.     

Smooth approximation of convex bodies

We describe a general approximation procedure for convex bodies which shows, in particular, that a body of constant width can be approximated, in the Hausdorff metric, by bodies of constant width with analytic boundaries (in fact, with algebraic support functions). Moreover, the approximating bodies have (at least) the same symmetries as the original one.     

Volume approximation of convex bodies by inscribed polytopes

Dedicated to the memory of my dear friend Professor Dr. Wilfried Nöbauer (1928–1988)     

Polyhedral metrics on the boundaries of convex compact quasi-Fuchsian manifolds

We show the existence of a convex compact subset in a quasi-Fuchsian manifold such that the induced metric on the boundary of the subset coincides with a prescribed hyperbolic polyhedral metric.     

The initial convergence rate of adaptive methods for polyhedral approximation of convex bodies

The convergence rate at the initial stage is analyzed for a previously proposed class of asymptotically optimal adaptive methods for polyhedral approximation of convex bodies. Based on the results, the initial convergence rate of these methods can be evaluated for arbitrary bodies (including the case of polyhedral approximation of polytopes) and the resources sufficient for achieving optimal asymptotic properties can be estimated.     

The cross-section body, plane sections of convex bodies and approximation of convex bodies, I

For a convex body K ^d we investigate three associated bodies, its intersection body IK (for 0int K), cross-section body CK, and projection body IIK, which satisfy IKCKIIK. Conversely we prove CKconst₁(d)I(K–x) for some xint K, and IIKconst₂ (d)CK, for certain constants, the first constant being sharp. We estimate the maximal k-volume of sections of 1/2(K+(-K)) with k-planes parallel to a fixed k-plane by the analogous quantity for K; our inequality is, if only k is fixed, sharp. For L ^d a convex body, we take n random segments in L, and consider their Minkowski average D. We prove that, for V(L) fixed, the supremum of V(D) (with also nN arbitrary) is minimal for L an ellipsoid. This result implies the Petty projection inequality about max V((IIM)*), for M ^d a convex body, with V(M) fixed. We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, the volumes of sections of convex bodies and the volumes of sections of their circumscribed cylinders. For fixed n, the pth moments of V(D) (1p<) also are minimized, for V(L) fixed, by the ellipsoids. For k=2, the supremum (nN arbitrary) and the pth moment (n fixed) of V(D) are maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 41.     

Random approximation and the vertex index of convex bodies

We prove that there exists an absolute constant \({\alpha > 1}\) with the following property: if K is a convex body in \({{\mathbb R}^n}\) whose center of mass is at the origin, then a random subset \({X\subset K}\) of cardinality \({{\rm card}(X)=\lceil\alphan\rceil }\) satisfies with probability greater than \({1-e^{-c_1n}}\)

$$K\subseteq c_2n\, {\rm conv}(X),$$

where \({c_1, c_2 > 0}\) are absolute constants. As an application we show that the vertex index of any convex body K in \({{\mathbb R}^n}\) is bounded by \({c_3n^2}\), where \({c_3 > 0}\) is an absolute constant, thus extending an estimate of Bezdek and Litvak for the symmetric case.

     

Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets

In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time.     

Notes on Klee’s paper “Polyhedral sections of convex bodies”

In sections 2 and 3 two methods for proving the non existence of certain universal Banach spaces, are presented. In section 4 it is proved that every infinite-dimensional conjugate Banach space has a two-dimensional subspace whose unit cell is not a polygon. The research reported in this document has been sponsored by the Air Force Office of Scientific Research under Grant AF EOAR 66-18, through the European Office of Aerospace Research (OAR) United States Air Force.     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense. Supported by OTKA grants 043520 and 049301, and by the EU Marie Curie grants Discconvgeo, Budalggeo and PHD. Authors’ addresses: Károly J. B?r?czky, Alfréd Rényi Institute of Mathematics, P.O. Box 127, Budapest H–1364, Hungary, and Department of Geometry, Roland E?tv?s University, Pázmány Péter sétány 1/C, Budapest 1117, Hungary; Salvador S. Gomis, Department of Mathematical Analysis, University of Alicante, 03080 Alicante, Spain; Péter Tick, Gyűrű utca 24, Budapest H–1039, Hungary     

Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges

For a given convex body K in Bbb R³{Bbb R}^3 with C ² boundary, let P ^c _n be the circumscribed polytope of minimal volume with at most n edges, and let P ⁱ _n be the inscribed polytope of maximal volume with at most n edges. Besides presenting an asymptotic formula for the volume difference as n tends to infinity in both cases, we prove that the typical faces of P ^c _n and P ⁱ _n are asymptotically regular triangles and squares, respectively, in a suitable sense.     

Spectral approximation for compact integral operators by degenerate kernel methods

We establish a new improved error estimate for the solution of the integral equation eigenvalue problem by degenerate kernel methods. In [6] these estimates were proved under the assumption of normality of the original kernel as well as of the approximating degenerate kernel. Now we consider any compact integral operator and a general Banach space situation, in contrast to the Hilbert space setting in [6], This will be done by combining the techniques in [6] with the suitably transformed estimates of [5]. Our results show that degenerate kernel methods have, besides their overall property of furnishing easy approximations to eigenfunctions, for eigenvalues an order of convergence comparable to quadrature methods.