Error bounds for infinite systems of convex inequalities without Slater’s condition

The feasible set of a convex semi–infinite program is described by a possibly infinite system of convex inequality constraints. We want to obtain an upper bound for the distance of a given point from this set in terms of a constant multiplied by the value of the maximally violated constraint function in this point. Apart from this Lipschitz case we also consider error bounds of H?lder type, where the value of the residual of the constraints is raised to a certain power.?We give sufficient conditions for the validity of such bounds. Our conditions do not require that the Slater condition is valid. For the definition of our conditions, we consider the projections on enlarged sets corresponding to relaxed constraints. We present a condition in terms of projection multipliers, a condition in terms of Slater points and a condition in terms of descent directions. For the Lipschitz case, we give five equivalent characterizations of the validity of a global error bound.?We extend previous results in two directions: First, we consider infinite systems of inequalities instead of finite systems. The second point is that we do not assume that the Slater condition holds which has been required in almost all earlier papers. Received: April 12, 1999 / Accepted: April 5, 2000?Published online July 20, 2000     

On Uniform Global Error Bounds for Convex Inequalities

This paper studies the existence of a uniform global error bound when a convex inequality g 0, where g is a closed proper convex function, is perturbed. The perturbation neighborhoods are defined by small arbitrary perturbations of the epigraph of its conjugate function. Under certain conditions, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if g satisfies the Slater condition and the solution set is bounded or its recession function satisfies the Slater condition. The results are used to derive lower bounds on the distance to ill-posedness.     

Perturbation analysis of a condition number for convex inequality systems and global error bounds for analytic systems

In this paper several types of perturbations on a convex inequality system are considered, and conditions are obtained for the system to be well-conditioned under these types of perturbations, where the well-conditionedness of a convex inequality system is defined in terms of the uniform boundedness of condition numbers under a set of perturbations. It is shown that certain types of perturbations can be used to characterize the well-conditionedness of a convex inequality system, in which either the system has a bounded solution set and satisfies the Slater condition or an associated convex inequality system, which defines the recession cone of the solution set for the system, satisfies the Slater condition. Finally, sufficient conditions are given for the existence of a global error bound for an analytic system. It is shown that such a global error bound always holds for any inequality system defined by finitely many convex analytic functions when the zero vector is in the relative interior of the domain of an associated convex conjugate function.     

Spherical complexes and radial projections of polytopes

Using the techniques of Gale diagrams a simple criterion is given for determining when a given spherical complex onS ⁿ⁻¹ ⊂E ⁿ is the radial projection, from the centre ofS ⁿ⁻¹, of a convex polytope. Previously a criterion was known only for the casen=2.     

A geometric inequality and the complexity of computing volume

The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2 ⁿ . This implies that no polynomial time algorithm can compute the volume of a convex set (given by an oracle) with less than exponential relative error. A lower bound on the complexity of computing width can also be deduced.Dedicated to my teacher Kõváry Károly     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Maximal distance for robotic simulation: The convex case

Given two hyper-rectangles inE ⁿ with sides having surface normals in the directions of the axes, each containing a set that touches all 2n sides of its containing hyper-rectangle, it is important to have an easily calculated upper bound on the distance between the sets, for use in a branch and bound algorithm applicable in collision avoidance in robotic simulation. In a previous paper, such a bound was given under the hypothesis that the sets are connected. Here, we consider the case where the sets are convex.The work of the second author was supported in part by the Natural Sciences and Engineering Research Council of Canada. The drawings were prepared by K. Stewart.     

Random walks in a convex body and an improved volume algorithm

We give a randomized algorithm using O(n⁷ log² n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n⁶ log⁴ n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n⁵ log⁴ n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n⁶ log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc.     

Error Control in Polytope Computations

This paper presents solutions for numerical computation on convex hulls; computational algorithms that ensure logical consistency and accuracy are proposed. A complete numerical error analysis is presented. It is shown that a global error bound for vertex-facet adjacency does not exist under logically consistent procedures. To cope with practical requirements, vertex preconditioned polytope computations are introduced using point and hyperplane adjustments. A global bound on vertex-facet adjacency error is affected by the global bound on vertices; formulas are given for a conservative choice of global error bounds.     

Convex bodies with extremal volumes having prescribed brightness in finitely many directions

We consider the class of convex bodies in ⁿ with prescribed projection (n – 1)-volumes along finitely many fixed directions. We prove that in such a class there exists a unique body (up to translation) with maximumn-volume. The maximizer is a centrally symmetric polytope and the normal vectors to its facets depend only on the assigned directions.Conditions for the existence of bodies with minimumn-volume in the class defined above are given. Each minimizer is a polytope, and an upper bound for the number of its facets is established.Work partially supported by Istituto di Analisi Globale e Applicazioni, CNR, Firenze.     

Minimization of convex functions on the convex hull of a point set

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in R ⁿ is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in R ^m , which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.     

Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

A model of the coNP-complete non-Hamilton tour decision problem for directed graphs

A truncated permutation matrix polytope is defined as the convex hull of a proper subset of n-permutations represented as 0/1 matrices. We present a linear system that models the coNP-complete non-Hamilton tour decision problem based upon constructing the convex hull of a set of truncated permutation matrix polytopes. Define polytope P^n–1 as the convex hull of all n-1 by n-1 permutation matrices. Each extreme point of P^n–1 is placed in correspondence (a bijection) with each Hamilton tour of a complete directed graph on n vertices. Given any n vertex graph G_n, a polynomial sized linear system F⁽ⁿ⁾ is constructed for which the image of its solution set, under an orthogonal projection, is the convex hull of the complete set of extrema of a subset of truncated permutation matrix polytopes, where each extreme point is in correspondence with each Hamilton tour not in G_n. The non-Hamilton tour decision problem is modeled by F⁽ⁿ⁾ such that G_n is non-Hamiltonian if and only if, under an orthogonal projection, the image of the solution set of F⁽ⁿ⁾ is P^n–1. The decision problem Is the projection of the solution set of F⁽ⁿ⁾=P^n–1? is therefore coNP-complete, and this particular model of the non-Hamilton tour problem appears to be new.Dedicated to the 250+ families in Kelowna BC, who lost their homes due to forest fires in 2003.I visited Ted at his home in Kelowna during this time - his family opened their home to evacuees and we shared happy and sad times with many wonderful people.     

Gemischte volumina in Kanalscharen

A canal class of convex bodies inn-dimensional Euclidean space consists of all convex bodies which have the same orthogonal projection on some hyperplane. In such a canal class, improved versions of the general Brunn-Minkowski theorem and of the Aleksandrov-Fenchel inequalities for mixed volumes are valid. Partial results on the equality cases are obtained. As an application, a translation theorem of the Aleksandrov-Fenchel-Jessen type is proved.     

Minimum L1-Distance Projection onto the Boundary of a Convex Set: Simple Characterization

We show that the minimum distance projection in the L ₁-norm from an interior point onto the boundary of a convex set is achieved by a single, unidimensional projection. Application of this characterization when the convex set is a polyhedron leads to either an elementary minmax problem or a set of easily solved linear programs, depending upon whether the polyhedron is given as the intersection of a set of half spaces or as the convex hull of a set of extreme points. The outcome is an easier and more straightforward derivation of the special case results given in a recent paper by Briec (Ref. 1).     

Surrogate methods for linear inequalities

Three algorithms are developed and validated for finding a pointx inR ⁿ that satisfies a given system of inequalities,Axb. A andb are a given matrix and a given vector inR ^m×n andR ^m , respectively, with the rows ofA assumed normalized. The algorithms are iterative and are based upon the orthogonal projection of an infeasible point onto the manifold of the bounding hyperplanes of some of the given constraints. The choice of the active constraints and the actual projection are accomplished through the use of surrogate constraints.This work was supported in part by the City University of New York Research Center. The author thanks Professor D. Goldfarb for suggesting the problem and also for his valuable literature information and time. The word surrogate was borrowed from one of his works.     

Global minimum test problem construction

A method is presented for the construction of test problems for which the global minimum point is known.Given a bounded convex polyhedron inR ⁿ , and a selected vertex, a concave quadratic function is constructed which attains its global minimum at the selected vertex. In general, this function will also have many other local minima.This research was supported in part by NSF Grant MCS 81-01214.     

Block-Coordinate Gradient Descent Method for?Linearly Constrained Nonsmooth Separable Optimization

We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, with the coordinate block chosen by a Gauss-Southwell-q rule based on sufficient predicted descent. We establish global convergence to first-order stationarity for this method and, under a local error bound assumption, linear rate of convergence. If f is convex with Lipschitz continuous gradient, then the method terminates in O(n ²/ε) iterations with an ε-optimal solution. If P is separable, then the Gauss-Southwell-q rule is implementable in O(n) operations when m=1 and in O(n ²) operations when m>1. In the special case of support vector machines training, for which f is convex quadratic, P is separable, and m=1, this complexity bound is comparable to the best known bound for decomposition methods. If f is convex, then, by gradually reducing the weight on P to zero, the method can be adapted to solve the bilevel problem of minimizing P over the set of minima of f+δ _X , where X denotes the closure of the feasible set. This has application in the least 1-norm solution of maximum-likelihood estimation. This research was supported by the National Science Foundation, Grant No. DMS-0511283.     

A Note on Error Bounds for Convex and Nonconvex Programs

Given a single feasible solution and a single infeasible solution of a mathematical program, we provide an upper bound to the optimal dual value. We assume that satisfies a weakened form of the Slater condition. We apply the bound to convex programs and we discuss its relation to Hoffman-like bounds. As a special case, we recover a bound due to Mangasarian [11] on the distance of a point to a convex set specified by inequalities.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.