A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

On the Maximization of (not necessarily) Convex Functions on Convex Sets

The global solutions of the problem of maximizing a convex function on a convex set were characterized by several authors using the Fenchel (approximate) subdifferential. When the objective function is quasiconvex it was considered the differentiable case or used the Clarke subdifferential. The aim of the present paper is to give necessary and sufficient optimality conditions using several subdifferentials adequate for quasiconvex functions. In this way we recover almost all the previous results related to such global maximization problems with simple proofs.     

Handelman’s hierarchy for the maximum stable set problem

The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope with non-empty interior can be represented as conic combination of products of the linear constraints defining the polytope. We relate the rank of Handelman’s hierarchy with structural properties of graphs. In particular we show a relation to fractional clique covers which we use to upper bound the Handelman rank for perfect graphs and determine its exact value in the vertex-transitive case. Moreover we show two upper bounds on the Handelman rank in terms of the (fractional) stability number of the graph and compute the Handelman rank for several classes of graphs including odd cycles and wheels and their complements. We also point out links to several other linear and semidefinite programming hierarchies.     

Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Solving sum-of-ratios fractional programs using efficient points

Constrained maximization of a sum of p1 ratios is a difficult nonconvex optimization problem (even if all functions involved are linear) with many applications in management sciences. In this paper, we first give a brief introductory survey of this problem. Then we propose a general branch-and-bound algorithm which uses rectangular partitions in the Euclidean space of dimension p. Theoretically, this algorithm is applicable under very general assumptions. Practically, we give an efficient implementation for fine fractions. Here the bounding procedures use dual constructions and the calculation of efficient points of a corresponding multiple-objective optimization problem. Finally, we present some promising numerical results     

Connectedness of efficient points in convex and convex transformable vector optimization

Given a convex vector optimization problem with respect to a closed ordering cone, we show the connectedness of the efficient and properly efficient sets. The Arrow–Barankin–Blackwell theorem is generalized to nonconvex vector optimization problems, and the connectedness results are extended to convex transformable vector optimization problems. In particular, we show the connectedness of the efficient set if the target function f is continuously transformable, and of the properly efficient set if f is differentiably transformable. Moreover, we show the connectedness of the efficient and properly efficient sets for quadratic quasiconvex multicriteria optimization problems.     

Problems with resource allocation constraints and optimization over the efficient set

The paper studies a nonlinear optimization problem under resource allocation constraints. Using quasi-gradient duality it is shown that the feasible set of the problem is a singleton (in the case of a single resource) or the set of Pareto efficient solutions of an associated vector maximization problem (in the case of $k>1$ resources). As a result, a nonlinear optimization problem under resource allocation constraints reduces to an optimization over the efficient set. The latter problem can further be converted into a quasiconvex maximization over a compact convex subset of $\mathbb{R }^k_+.$ Alternatively, it can be approached as a bilevel program and converted into a monotonic optimization problem in $\mathbb{R }^k_+.$ In either approach the converted problem falls into a common class of global optimization problems for which several practical solution methods exist when the number $k$ of resources is relatively small, as it often occurs.     

ON A SELF DUAL 3-SPHERE OF PETER MCMULLEN

We study an equifacetted self dual 3-sphere S _McM of Peter McMullen, [10], in particular its automorphism group A(S _McM ) and its relation to the Coxeter group H ₄ of the 600-cell. A closely related equifacetted polyhedral 3-sphere (240-cell) with 240 facets and 120 vertices has the same automorphism group. Both these 3-spheres and the polar dual of the last one cannot occur as the boundary complex of a (convex) 4-polytope with A(S _McM ) as their full Euclidean symmetry. It is an open problem, whether there exist one of these three 4-polytopes at all. Their combinatorial symmetry would differ from their Euclidean one within their whole realization space, similar to the example given in [3], see also [2]. Tackling these problems with methods from computational synthetic geometry [5] fail because of the large problem size. Therefore, a partial Euclidean symmetry assumption for the questionable polytope is natural. On the other hand, we show that even a certain subgroup of order 5 of the full combinatorial symmetry group A(S _McM ) of order 1200 cannot occur as a Euclidean symmetry for McMullen's questionable polytope. This revised version was published online in August 2006 with corrections to the Cover Date.     

Strict Minimality Conditions in Nondifferentiable Multiobjective Programming

In this paper, sufficient conditions for superstrict minima of order m to nondifferentiable multiobjective optimization problems with an arbitrary feasible set are provided. These conditions are expressed through the Studniarski derivative of higher order. If the objective function is Hadamard differentiable, a characterization for strict minimality of order 1 (which coincides with superstrict minimality in this case) is obtained.     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.     

On the connectedness of the efficient set for strictly quasiconvex vector minimization problems

In this paper, we investigate the connectedness of the efficient solution set for vector minimization problems defined by a continuous vector-valued strictly quasiconvex functionf=(f ₁,...,f _m ) _T and a convex compact setX. It is shown that the efficient solution set is connected if one component off is strongly quasiconvex onX.The author would like to thank Professor H. P. Benson and the referees for many valuable comments and for pointing out some errors in the previous draft.Formerly, Assistant, Department of Applied Mathematics, Shanghai Jiao Tong University, Shanghai, China.     

The Mean-Partition Problem

In mean-partition problems the goal is to partition a finite set of elements, each associated with a d-vector, into p disjoint parts so as to optimize an objective, which depends on the averages of the vectors that are assigned to each of the parts. Each partition is then associated with a d × p matrix whose columns are the corresponding averages and a useful approach in studying the problem is to explore the mean-partition polytope, defined as the convex hull of the set of matrices associated with feasible partitions.     

非光滑向量极值问题的真有效解与最优性条件

讨论了赋范线性空间中非光滑向量极值问题的Hatley,Borwein,Benson真有效解之间的关系,指出了它们共同的标量极值问题的等价刻画,建立了问题（VMP）的广义KT-真有效解的充分条件,并给出了向量极小值问题在锥局部凸、拟凸、伪凸等条件下的最优性条件。     

On two-stage convex chance constrained problems

In this paper we develop approximation algorithms for two-stage convex chance constrained problems. Nemirovski and Shapiro (Probab Randomized Methods Des Uncertain 2004) formulated this class of problems and proposed an ellipsoid-like iterative algorithm for the special case where the impact function f (x, h) is bi-affine. We show that this algorithm extends to bi-convex f (x, h) in a fairly straightforward fashion. The complexity of the solution algorithm as well as the quality of its output are functions of the radius r of the largest Euclidean ball that can be inscribed in the polytope defined by a random set of linear inequalities generated by the algorithm (Nemirovski and Shapiro in Probab Randomized Methods Des Uncertain 2004). Since the polytope determining r is random, computing r is difficult. Yet, the solution algorithm requires r as an input. In this paper we provide some guidance for selecting r. We show that the largest value of r is determined by the degree of robust feasibility of the two-stage chance constrained problem—the more robust the problem, the higher one can set the parameter r. Next, we formulate ambiguous two-stage chance constrained problems. In this formulation, the random variables defining the chance constraint are known to have a fixed distribution; however, the decision maker is only able to estimate this distribution to within some error. We construct an algorithm that solves the ambiguous two-stage chance constrained problem when the impact function f (x, h) is bi-affine and the extreme points of a certain “dual” polytope are known explicitly. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

Levels Sets Infimal Convolution and Level Addition

A sufficient criterion is established for the infimal convolution of two functions having connected level sets to share the same property without being exact. As a consequence, the infimal convolution of quasiconvex functions on a real line is quasiconvex. However, this is not true on a space of higher dimension, which is illustrated by an example in R ². Furthermore, connectedness of level sets and local-global minimum properties of functions are analyzed under level addition. Continuity properties of level set maps are also studied in relation with local-global minimum properties.     

Permutohedra and minimal matrices

The notions of minimality, π-uniqueness and additivity originated in discrete tomography. They have applications to Kronecker products of characters of the symmetric group and arise as the optimal solutions of quadratic transportation problems. Here, we introduce the notion of real-minimality and give geometric characterizations of all these notions for a matrix A, by considering the intersection of the permutohedron determined by A with the transportation polytope in which A lies. We also study the computational complexity of deciding if the properties of being additive, real-minimal, π-unique and minimal hold for a given matrix, and show how to efficiently construct some matrix with any of these properties.     

Primal—Dual Methods for Vertex and Facet Enumeration

Every convex polytope can be represented as the intersection of a finite set of halfspaces and as the convex hull of its vertices. Transforming from the halfspace (resp. vertex) to the vertex (resp. halfspace) representation is called vertex enumeration (resp. facet enumeration ). An open question is whether there is an algorithm for these two problems (equivalent by geometric duality) that is polynomial in the input size and the output size. In this paper we extend the known polynomially solvable classes of polytopes by looking at the dual problems. The dual problem of a vertex (resp. facet) enumeration problem is the facet (resp. vertex) enumeration problem for the same polytope where the input and output are simply interchanged. For a particular class of polytopes and a fixed algorithm, one transformation may be much easier than its dual. In this paper we propose a new class of algorithms that take advantage of this phenomenon. Loosely speaking, primal—dual algorithms use a solution to the easy direction as an oracle to help solve the seemingly hard direction. Received July 31, 1997, and in revised form March 8, 1998.     

Set containment characterization for quasiconvex programming

Dual characterizations of containment of a convex set, defined by quasiconvex constraints, in a convex set, and in a reverse convex set, defined by a quasiconvex constraint, are provided. Notions of quasiconjugate for quasiconvex functions, H-quasiconjugate and R-quasiconjugate, play important roles to derive characterizations of the set containments.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.