A Lagrangian Dual Method with Self-Concordant Barriers for Multi-Stage Stochastic Convex Programming

This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.Mathematics Subject Classification (2000): 90C15, 90C51, 90C06, 90C25, 90C60Research is partially supported by NUS Academic Research Grant R-146-000-006-112     

Lower Bounds for n-Term Approximations of Plane Convex Sets and Related Topics

In this paper, we establish lower bounds for n-term approximations in the metric of L ²⁽I ² ) of characteristic functions of plane convex subsets of the square I ² with respect to arbitrary orthogonal systems. It is shown that, as n, these bounds cannot decrease more rapidly than .     

Recursive Construction of Optimal Self-Concordant Barriers for Homogeneous Cones

We give a recursive formula for optimal dual barrier functions on homogeneous cones. This is done in a way similar to the primal construction of Güler and Tunçel (Math. Program. 81(1):55–76, 1998) by means of the dual Siegel cone construction of Rothaus (Bull. Am. Math. Soc. 64:85–86, 1958). We use invariance of the primal barrier function with respect to a transitive subgroup of automorphisms and the properties of the duality mapping, which is a bijection between the primal and the dual cones. We give simple direct proofs of self-concordance of the primal optimal barrier and provide an alternative expression for the dual universal barrier function.     

Best Approximations of Convex Compact Sets by Balls in the Hausdorff Metric

We deduce an upper bound for the Hausdorff distance between a nonempty bounded set and the set of all closed balls in a strictly convex straight geodesic space X of nonnegative curvature. We prove that the set $\chi \left[ {\rm M} \right]$ of centers of closed balls approximating a convex compact set in the Hausdorff metric in the best possible way is nonempty _X [M] and is contained in M. Some other properties of $\chi \left[ {\rm M} \right]$ also are investigated.     

Canonical Theorems for Convex Sets

Let F be a family of pairwise disjoint compact convex sets in the plane such that none of them is contained in the convex hull of two others, and let r be a positive integer. We show that F has r disjoint ⌊ c _r n⌋ -membered subfamilies F _i (1 ≤ i ≤ r) such that no matter how we pick one element F _i from each F _i , they are in convex position, i.e., every F _i appears on the boundary of the convex hull of ⋃ _i=1 ^r F _i . (Here c _r is a positive constant depending only on r .) This generalizes and sharpens some results of Erdős and Szekeres, Bisztriczky and Fejes Tóth, Bárány and Valtr, and others. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p427.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received April 30, 1997, and in revised form August 5, 1997.     

Constructible Convex Sets

We investigate when closed convex sets can be written as countable intersections of closed half-spaces in Banach spaces. It is reasonable to consider this class to comprise the constructible convex sets since such sets are precisely those that can be defined by a countable number of linear inequalities, hence are accessible to techniques of semi-infinite convex programming. We also explore some model theoretic implications. Applications to set convergence are given as limiting examples.     

Finding Convex Sets in Convex Position

Let F{\cal{F}} denote a family of pairwise disjoint convex sets in the plane. F{\cal{F}} is said to be in convex position, if none of its members is contained in the convex hull of the union of the others. For any fixed k 3 5k\ge5, we give a linear upper bound on P_k(n)P_k(n), the maximum size of a family F{\cal{F}} with the property that any k members of F{\cal{F}} are in convex position, but no n are.     

Translating Finite Sets into Convex Sets

Let X be a reflexive Banach space, and let C X be a closed,convex and bounded set with empty interior. Then, for every > 0, there is a nonempty finite set F X with an arbitrarilysmall diameter, such that C contains at most .|F| points ofany translation of F. As a corollary, a separable Banach spaceX is reflexive if and only if every closed convex subset ofX with empty interior is Haar null. 2000 Mathematics SubjectClassification 46B20 (primary), 28C20 (secondary).     

Klee Theorem for Linearly Convex Sets

We prove a complex analog of the classical Klee theorem for strongly linearly convex closed sets.     

A Ramsey-Type Result for Convex Sets

Given a family of n convex compact sets in the plane, one canalways choose n of them which are either pairwise disjoint orpairwise intersecting. On the other hand, there exists a familyof n segments in the plane such that the maximum size of a subfamilywith pairwise disjoint or pairwise intersecting elements inn^log2/log5 n^0·431.     

A Polynomial Cutting Surfaces Algorithm for the Convex Feasibility Problem Defined by Self-Concordant Inequalities

Consider a nonempty convex set in ^m which is defined by a finite number of smooth convex inequalities and which admits a self-concordant logarithmic barrier. We study the analytic center based column generation algorithm for the problem of finding a feasible point in this set. At each iteration the algorithm computes an approximate analytic center of the set defined by the inequalities generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise either an existing inequality is shifted or a new inequality is added into the system. As the number of iterations increases, the set defined by the generated inequalities shrinks and the algorithm eventually finds a solution of the problem. The algorithm can be thought of as an extension of the classical cutting plane method. The difference is that we use analytic centers and convex cuts instead of arbitrary infeasible points and linear cuts. In contrast to the cutting plane method, the algorithm has a polynomial worst case complexity of O(Nlog 1/) on the total number of cuts to be used, where N is the number of convex inequalities in the original problem and is the maximum common slack of the original inequality system.     

Extremal Convex Planar Sets

Each convex planar set K has a perimeter C, a minimum width E, an area A, and a diameter D. The set of points (E,C, A^1/2, D) corresponding to all such sets is shown to occupy a cone in the non-negative orthant of R⁴with its vertex at the origin. Its three-dimensional cross section S in the plane D = 1 is investigated. S lies in a rectangular parallelepiped in R³. Results of Lebesgue, Kubota, Fukasawa, Sholander, and Hemmi are used to determine some of the boundary surfaces of S, and new results are given for the other boundary surfaces. From knowledge of S, all inequalities among E, C ,A, and D can be found.     

On the Riemannian Geometry Defined by Self-Concordant Barriers and Interior-Point Methods

Abstract. We consider the Riemannian geometry defined on a convex set by the Hessian of a self-concordant barrier function, and its associated geodesic curves. These provide guidance for the construction of efficient interior-point methods for optimizing a linear function over the intersection of the set with an affine manifold. We show that algorithms that follow the primal—dual central path are in some sense close to optimal. The same is true for methods that follow the shifted primal—dual central path among certain infeasible-interior-point methods. We also compute the geodesics in several simple sets.     

New Combinations of Convex Sets

The family of convex sets in a (finite dimensional) real vector space admits several unary and binary operations – dilatation, intersection, convex hull, vector sum – which preserve convexity. These generalize to convex functions, where there are in fact further operations of this kind. Some of the latter may be regarded as combinations of two such operations, acting on complementary subspaces. In this paper, a general theory of such mixed operations is introduced, and some of its consequences developed.     

A Helly-Type Theorem for Unions of Convex Sets

We prove that for any d, k ≥ 1 there are numbers q = q(d,k) and h = h(d,k) such that the following holds: Let be a family of subsets of the d-dimensional Euclidean space, such that the intersection of any subfamily of consisting of at most q sets can be expressed as a union of at most k convex sets. Then the Helly number of is at most h. We also obtain topological generalizations of some cases of this result. The main result was independently obtained by Alon and Kalai, by a different method. Received April 14, 1995, and in revised form August 1, 1995.     

Intersecting Convex Sets by Rays

What is the smallest number τ=τ(n) such that for any collection of n pairwise disjoint convex sets in d-dimensional Euclidean space, there is a point such that any ray (half-line) emanating from it meets at most τ sets of the collection? This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996). We show the following:Given any collection \({\mathcal{C}}\) of n pairwise disjoint compact convex sets in d-dimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most \(\frac{dn+1}{d+1}\) members of \({\mathcal{C}}\).There exist collections of n pairwise disjoint (i) equal-length segments or (ii) disks in the Euclidean plane such that from any point there is a ray that meets at least \(\frac{2n}{3}-2\) of them.We also determine the asymptotic behavior of τ(n) when the convex bodies are fat and of roughly equal size.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.     

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.