The volumetric barrier for convex quadratic constraints

Let where and _i is an n×n positive semidefinite matrix. We prove that the volumetric and combined volumetric-logarithmic barriers for are and self-concordant, respectively. Our analysis uses the semidefinite programming (SDP) representation for the convex quadratic constraints defining , and our earlier results on the volumetric barrier for SDP. The self-concordance results actually hold for a class of SDP problems more general than those corresponding to the SDP representation of .Mathematics Subject Classification (1991):90C25, 90C30     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.     

Optimal 3-terminal cuts and linear programming

Given an undirected graph G=(V,E) and three specified terminal nodes t ₁,t ₂,t ₃, a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c _e is specified for each e∈E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is -hard, and in fact, is max- -hard. An approximation algorithm having performance guarantee has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most times the optimal LP value. It is proved here that can be improved to , and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee . In addition, we show that is best possible for this algorithm. Research of this author was supported by NSERC PGSB. Research supported by a grant from NSERC of Canada.     

Analysis of nonsmooth vector-valued functions associated with second-order cones

Let be the Lorentz/second-order cone in . For any function f from to , one can define a corresponding function f^soc(x) on by applying f to the spectral values of the spectral decomposition of x with respect to . We show that this vector-valued function inherits from f the properties of continuity, (local) Lipschitz continuity, directional differentiability, Fréchet differentiability, continuous differentiability, as well as (-order) semismoothness. These results are useful for designing and analyzing smoothing methods and nonsmooth methods for solving second-order cone programs and complementarity problems.Mathematics Subject Classification (1991): 26A27, 26B05, 26B35, 49J52, 90C33, 65K05     

The feasibility pump

In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min{c^Tx:Ax≥b,x_j integer ∀j ∈ }. Trivially, a feasible solution can be defined as a point x* ∈ P:={x:Ax≥b} that is equal to its rounding , where the rounded point is defined by := x*_j if j ∈ and := x*_j otherwise, and [·] represents scalar rounding to the nearest integer. Replacing “equal” with “as close as possible” relative to a suitable distance function Δ(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.     

Greedy splitting algorithms for approximating multiway partition problems

Given a system (V,T,f,k), where V is a finite set, is a submodular function and k2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition ={V₁,V₂,...,V_k} of V that satisfiesfor all i and minimizes f(V₁)+f(V₂)+···+f(V_k), where is a k-partition of hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20Acknowledgement This research is partially supported by the Scientific Grant-in-Aid from Ministry of Education, Science, Sports and Culture of Japan. The authors would like to thank the anonymous referees for their valuable comments and suggestions.     

A -algorithm for convex minimization

For convex minimization we introduce an algorithm based on -space decomposition. The method uses a bundle subroutine to generate a sequence of approximate proximal points. When a primal-dual track leading to a solution and zero subgradient pair exists, these points approximate the primal track points and give the algorithm's , or corrector, steps. The subroutine also approximates dual track points that are -gradients needed for the method's -Newton predictor steps. With the inclusion of a simple line search the resulting algorithm is proved to be globally convergent. The convergence is superlinear if the primal-dual track points and the objective's -Hessian are approximated well enough. Dedicated to Terry Rockafellar who has had a great influence on our work via strong support for proximal points and for structural definitions that involve tangential convergence. On leave from INRIA Rocquencourt Research of the first author supported by the National Science Foundation under Grant No. DMS-0071459 and by CNPq (Brazil) under Grant No. 452966/2003-5. Research of the second author supported by FAPERJ (Brazil) under Grant No.E26/150.581/00 and by CNPq (Brazil) under Grant No. 383066/2004-2.     

Critical extreme points of the 2-edge connected spanning subgraph polytope

In this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if is a non-integer minimal extreme point of P(G), then G and can be reduced, by means of some reduction operations, to a graph G' and an extreme point of P(G') where G' and satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral. Received: May, 2004 Part of this work has been done while the first author was visiting the Research Institute for Discrete Mathematics, University of Bonn, Germany.     

On the gap between the quadratic integer programming problem and its semidefinite relaxation

Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap We establish the uniqueness of the SDR solution and prove that if and only if γ_r:=n⁻¹max{x^TVV^Tx:x ∈ {-1, 1}ⁿ}=1 where V is an orthogonal matrix whose columns span the (r–dimensional) null space of D−Q and where D is the unique SDR solution. We also give a test for establishing whether that involves 2^r−1 function evaluations. In the case that γ_r<1 we derive an upper bound on γ which is tighter than Thus we show that `breaching' the SDR gap for the QIP problem is as difficult as the solution of a QIP with the rank of the cost function matrix equal to the dimension of the null space of D−Q. This reduced rank QIP problem has been recently shown to be solvable in polynomial time for fixed r.     

Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

2-universal -lattices over real quadratic fields

Let be a real quadratic field with m a square-free positive rational integer, and be the ring of integers in F. An -lattice L on a totally positive definite quadratic space V over F is called r-universal if L represents all totally positive definite -lattices l with rank r over . We prove that there exists no 2-universal -lattice over F with rank less than 6, and there exists a 2-universal -lattice over F with rank 6 if and only if m=2, 5. Moreover there exists only one 2-universal -lattice with rank 6, up to isometry, over .     

Quotients of a universal locally projective polytope of type {5,3,5}

This article examines the universal polytope (of type {5,3,5}) whose facets are dodecahedra, and whose vertex figures are hemi-icosahedra. The polytope is proven to be finite, and the structure of its group is identified. This information is used to classifiy the quotients of the polytope. A total of 145 quotients are found, including 69 section regular polytopes with the same facets and vertex figures as . Mathematics Subject Classification (2000): 51M20, 20F65, 52B15 An erratum to this article is available at .     

An approximation algorithm for the general max-min resource sharing problem

We propose an approximation algorithm for, the general max-min resource sharing problem with M nonnegative concave constraints on a convex set B. The algorithm is based on a Lagrangian decomposition method and it uses a c-approximation algorithm (called approximate block solver) for a simpler maximization problem over the convex set B. We show that our algorithm achieves within iterations or calls to the approximate block solver a solution for the general max-min resource sharing problem with approximation ratio The algorithm is faster and simpler than the previous known approximation algorithms for the problem [12, 13] Research of the author was supported in part by EU Thematic Network APPOL, Approximation and Online Algorithms, IST-2001-30012, by EU Project CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems, IST-2001-33135 and by DFG Project, Entwicklung und Analyse von Approximativen Algorithmen für Gemischte und Verallgemeinerte Packungs- und überdeckungsprobleme, JA 612/10-1. Part of this work was done while visiting the Department of Computer Science at ETH Zürich. An extended abstract of this paper appeared in SWAT 2004, Scandinavian Workshop on Algorithm Theory, LNCS 3111, 311–322.     

On some class of sets with multi-sheeted envelope of holomorphy

Let M be a smooth CR-manifold of dimension 2n – 2 contained in the unit sphere We prove that if M is the finite union of boundaries of (n–1)-dimensional analytic varieties and M is globally minimal, then the envelope of holomorphy of is multi-sheeted. In some cases we prove that the number of sheets is exactly two. It is also proved (for 4-dimensional CR-manifolds contained in that the property of being globally minimal (even being of finite type at each point) is generic.Mathematics Subject Classification (2000): 32D10, 32V10, 32V25     

Newton methods for nonsmooth convex minimization: connections among -Lagrangian, Riemannian Newton and SQP methods

This paper studies Newton-type methods for minimization of partly smooth convex functions. Sequential Newton methods are provided using local parameterizations obtained from -Lagrangian theory and from Riemannian geometry. The Hessian based on the -Lagrangian depends on the selection of a dual parameter g; by revealing the connection to Riemannian geometry, a natural choice of g emerges for which the two Newton directions coincide. This choice of g is also shown to be related to the least-squares multiplier estimate from a sequential quadratic programming (SQP) approach, and with this multiplier, SQP gives the same search direction as the Newton methods. This paper is dedicated to R.T. Rockafellar, on the occasion of his 70th birthday.     

Global optimization of rational functions: a semidefinite programming approach

We consider the problem of global minimization of rational functions on (unconstrained case), and on an open, connected, semi-algebraic subset of , or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [16]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].     

The space of complete embedded maximal surfaces with isolated singularities in the 3-dimensional Lorentz-Minkowski space

We prove that a complete embedded maximal surface in = (³, dx₁² + dx₂²-dx₃²) with a finite number of singularities is an entire maximal graph with conelike singularities over any spacelike plane, and so, it is asymptotic to a spacelike plane or a half catenoid. We show that the moduli space of entire maximal graphs over {x₃=0} in with n+12 singular points and vertical limit normal vector at infinity is a 3n+4-dimensional differentiable manifold. The convergence in means the one of conformal structures and Weierstrass data, and it is equivalent to the uniform convergence of graphs on compact subsets of {x₃=0}. Moreover, the position of the singular points in ³ and the logarithmic growth at infinity can be used as global analytical coordinates with the same underlying topology. We also introduce the moduli space of marked graphs with n+1 singular points (a mark in a graph is an ordering of its singularities), which is a (n+1)-sheeted covering of . We prove that identifying marked graphs differing by translations, rotations about a vertical axis, homotheties or symmetries about a horizontal plane, the corresponding quotient space is an analytic manifold of dimension 3n–1. This manifold can be identified with a spinorial bundle associated to the moduli space of Weierstrass data of graphs in .Mathematics Subject Classification (2000): 53C50, 58D10, 53C42First and second authors research partially supported by MEC-FEDER grant number MTM2004-00160Second and third authors research partially supported by Consejería de Educación y Ciencia de la Junta de Andalucía and the European Union.     

The Rees algebra of a positive normal affine semigroup ring

Let R be a positive normal affine semigroup ring of dimension d and let be the maximal homogeneous ideal of R. We show that the integral closure of is equal to for all n ∈ℕ with n ≥ d − 2. From this we derive that the Rees algebra R[t] is normal in case that d ≤ 3. If emb dim(R) = d + 1, we can give a necessary and sufficient condition for R[t] to be normal.     

Topologically transitive extensions of bounded operators

Let X be any Banach space and T a bounded operator on X. An extension of the pair (X,T) consists of a Banach space in which X embeds isometrically through an isometry i and a bounded operator on such that When X is separable, it is additionally required that be separable. We say that is a topologically transitive extension of (X, T) when is topologically transitive on , i.e. for every pair of non-empty open subsets of there exists an integer n such that is non-empty. We show that any such pair (X,T) admits a topologically transitive extension , and that when H is a Hilbert space, (H,T) admits a topologically transitive extension where is also a Hilbert space. We show that these extensions are indeed chaotic.Mathematics Subject Classification (2000): 47 A 16     

Proper forcing extensions and Solovay models

We study the preservation of the property of being a Solovay model under proper projective forcing extensions. We show that every strongly-proper forcing notion preserves this property. This yields that the consistency strength of the absoluteness of under strongly-proper forcing notions is that of the existence of an inaccessible cardinal. Further, the absoluteness of under projective strongly-proper forcing notions is consistent relative to the existence of a -Mahlo cardinal. We also show that the consistency strength of the absoluteness of under forcing extensions with -linked forcing notions is exactly that of the existence of a Mahlo cardinal, in contrast with the general ccc case, which requires a weakly-compact cardinal.Research partially supported by the research projects BFM2002-03236 of the Spanish Ministry of Science and Technology, and 2002SGR 00126 of the Generalitat de Catalunya. The second author was also partially supported by the research project GE01/HUM10, Grupos de excelencia, Principado de Asturias.Mathematics Subject Classification (2000): 03E15, 03E35