Enumerative inequalities in integer programming

For a linear integer programming problem, thelocal information contained at an optimal solution of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use ofenvironmental information (of a global nature but pertaining to the discrete vicinity of ), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept ofenumerative inequalities is introduced and it is shown how it can be obtained in the context of the convex outer-domain theory of Balas, Young, et al.Generally speaking, enumerative inequalities can be made arbitrarily strong (deep), but at the cost of an increasing amount of work (i.e. enumeration) for their construction. In particular cases, however, very little global information can produce enumerative inequalities stronger than anyvalid cut.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

Implicit functions and sensitivity of stationary points

We consider the spaceL(D) consisting of Lipschitz continuous mappings fromD to the Euclideann-space ⁿ ,D being an open bounded subset of ⁿ . LetF belong toL(D) and suppose that solves the equationF(x) = 0. In case that the generalized Jacobian ofF at is nonsingular (in the sense of Clarke, 1983), we show that forG nearF (with respect to a natural norm) the systemG(x) = 0 has a unique solution, sayx(G), in a neighborhood of Moreover, the mapping which sendsG tox(G) is shown to be Lipschitz continuous. The latter result is connected with the sensitivity of strongly stable stationary points in the sense of Kojima (1980); here, the linear independence constraint qualification is assumed to be satisfied.     

Some proximity and sensitivity results in quadratic integer programming

We show that for any optimal solution for a given separable quadratic integer programming problem there exist an optimal solution for its continuous relaxation such that wheren is the number of variables and(A) is the largest absolute subdeterminant of the integer constraint matrixA. Also for any feasible solutionz, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution having greater objective function value and with . We further prove, under some additional assumptions, that the distance between a pair of optimal solutions to an integer quadratic programming problem with right hand side vectorsb andb, respectively, depends linearly on b–b₁. Finally the validity of all the results for nonseparable mixed-integer quadratic programs is established. The proximity results obtained in this paper are extensions of some of the results described in Cook et al. (1986) for linear integer programming.This research was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998.     

Multivalued differential equations in separable Banach spaces

This paper is concerned with multivalued differential equations of the form F(t,x), whereF is a multivalued mapping taking as its values nonempty compact, but not necessarily convex, subsets in a separable Banach space. The main result is connected with the existence of solutions of these equations.     

Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Saddle points of hamiltonian systems in convex problems of Lagrange

In Lagrange problems of the calculus of variations where the LagrangianL(x ), not necessarily differentiable, is convex jointly inx and , optimal arcs can be characterized in terms of a generalized Hamiltonian differential equation, where the HamiltonianH(x, p) is concave inx and convex inp. In this paper, the Hamiltonian system is studied in a neighborhood of a minimax saddle point ofH. It is shown under a strict concavity-convexity assumption onH that the point acts much like a saddle point in the sense of differential equations. At the same time, results are obtained for problems in which the Lagrange integral is minimized over an infinite interval. These results are motivated by questions in theoretical economics.This research was supported in part by Grant No. AFOSR-71-1994.     

Win probabilities and simple majorities in probabilistic voting situations

This paper considers an election between candidatesA andB in which (1) voters may be uncertain about which candidate they will vote for, and (2) the winner is to be determined by a lottery betweenA andB that is based on their vote totals. This lottery is required to treat voters equally, to treat candidates equally, and to respond nonnegatively to increased support for a candidate. The set _n of all such lottery rules based on a total ofn voters is the convex hull of aboutn/2 basic lottery rules which include the simple majority rule. For odd values ofn 3 let , and for even values ofn 4 let . With the average of then voters probabilities of voting forA, it is shown that within _n the simple majority rule maximizes candidateA's overall win probability whenever , and that(n) is the smallest number for which this is true. Similarly, the simple majority rule maximizesB's overall win probability whenever (the average of the voters probabilities of voting forB) is as large as(n). This research was supported by the National Science Foundation, Grant SOC 75-00941.     

Computing the volume is difficult

For every polynomial time algorithm which gives an upper bound (K) and a lower boundvol(K) for the volume of a convex setKR ^d , the ratio (K)/vol(K) is at least (cd/logd) ^d for some convex setKR ^d .This paper was partly written when both authors were on leave from the Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P.O. Box 127, Hungary.     

Superlinear convergence of Broyden's boundedθ-class of methods

In this paper the so-called Broyden's bounded-class of methods is considered. It contains as a subclass Broyden's restricted-class of methods, in which the updating matrices retain symmetry and positive definiteness. These iteration methods are used for solving unconstrained minimization problems of the following form: It is assumed that the step-size coefficient _k = 1 in each iteration and the functionalf : R ⁿ R¹ satisfies the standard assumptions, viz.f is twice continuously differentiable and the Hessian matrix is uniformly positive definite and bounded (there exist constantsm, M > 0 such that my² y, for ally R ⁿ) and satisfies a Lipschitz-like condition at the optimal point , the gradient vanishes at Under these assumptions the local convergence of Broyden's methods is proved. Furthermore, the Q-superlinear convergence is shown.     

On the convergence of the method of analytic centers when applied to convex quadratic programs

This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor of with iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of Newton iterations to guarantee an error reduction by a factor of in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.     

Interior path following primal-dual algorithms. part II: Convex quadratic programming

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n ³ L).     

Translative covering by homothetic copies

We show that for any convex bodyKE ² there exists a triangleT such that , where T is a suitable homothetic copy ofT with ratio . As a corollary we show that if (K _i) are homothetic copies of a given convex bodyKE ² with areaV(K)=1, then the condition is sufficient for the existence of a translative covering ofK by (K _i).     

Moduli of continuity of selections from nonconvex maps

We consider two continuous selection problems related to the differential inclusion F(t, x). Assuming thatF is Hölder or Lipschitz continuous with compact, not necessarily convex values, we provide estimates on the modulus of continuity of these selections.     

Prime ideal decomposition inF({}^m\sqrt \mu )

LetF be an algebraic number field and F such thatx ^m– is irreducible, wherem is an integer. Let be a prime ideal inF with . The prime decomposition of in is explicitly obtained in the following cases. Case 1: , (a,m) = 1 (where means , 0 ). Case 2:m lt, wherel is a prime andl 0 . Case 3:m 0 and every prime that dividesm also dividespf–1. It is not assumed that thev ^th roots of unity are inF for anyv 2.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

On the family of translations of a tight probability measure on a topological group

Summary Let P be a tight probability measure on an Abelian normal topological group and the family of all its translations ({P(t ^–1)}). We shall investigate the closed convex hull of the set , where the closure is taken in the weak topology. Theorem 3 shows that a probability measure Q is an element of the closed convex hull of if and only if there exists a probability measure R such that Q=P*R, where P*     

Uneven distribution of ventilation—perfusion ratios in lungs estimated by a modified Newton method

The uneven distribution of ventilation—perfusion ratios ( ) in diseased lungs is the major cause of arterial hypoxemia. Farhi and Yokoyama (1967) and Yokoyama and Farhi (1967) were the first who used physiologically inert gases as indicator gases to assess the uneven distribution of Wagner and his coworkers in San Diego (1977b) extended the method and elaborated the multiple inert gas elimination technique in which blood flows in 50 compartments with different were estimated based on data for 6 indicator gases. They analyzed the indicator gas data through an enforced smoothing technique with the ridge regression. To get smooth distributions, they introduced a weighting function for compartments and an additional treatment for the non-negativity of the blood flow. The weighting function was empirically obtained. We analyzed the data without putting any weights on compartments nor any additional treatment for non-negativity of blood flow. The analytical method in the present study was a modified Newton method, which is one of the enforced smoothing method. Our method was capable of recovering all distribution patterns that were found through the method reported by Wagner et al. (1977b).     

Generating the tame and wild kernels by Dennis-Stein symbols

For many number fieldsF, it is proved that the tame kernel, K₂( ), and the wild kernel, W(F), ofF are generated by Dennis-Stein symbols. For some real quadratic number fields, generators for the tame kernel are given.     

Tensor ideals in the category of tilting modules

We study the tensor category of tilting modules over a quantum groupU _q with divided powers. The setX ₊ of dominant weights is a union of closed alcoves numbered by the elementswW ^f of a certain subset of affine Weyl groupW. G. Lusztig and N. Xi defined a partition ofW ^f into canonical right cells and the right order _R on the set of cells. For a cellAW ^f we consider a full subcategory formed by direct sums of tilting modulesQ() with highest weights . We prove that is a tensor ideal in , generalizing H. Andersen's theorem about the ideal of negligible modules which in our notations is nothing else then . The proof is an application of a recent result by W. Soergel who has computed the characters of tilting modules.This material is based upon work supported by the U.S. Civilian Research and Development Foundation under Award No. RM1-265.