Cuts for mixed 0-1 conic programming

In this we paper we study techniques for generating valid convex constraints for mixed 0-1 conic programs. We show that many of the techniques developed for generating linear cuts for mixed 0-1 linear programs, such as the Gomory cuts, the lift-and-project cuts, and cuts from other hierarchies of tighter relaxations, extend in a straightforward manner to mixed 0-1 conic programs. We also show that simple extensions of these techniques lead to methods for generating convex quadratic cuts. Gomory cuts for mixed 0-1 conic programs have interesting implications for comparing the semidefinite programming and the linear programming relaxations of combinatorial optimization problems, e.g. we show that all the subtour elimination inequalities for the traveling salesman problem are rank-1 Gomory cuts with respect to a single semidefinite constraint. We also include results from our preliminary computational experiments with these cuts.Research partially supported by NSF grants CCR-00-09972, DMS-01-04282 and ONR grant N000140310514.     

On the convergence properties of Hildreth's quadratic programming algorithm

We prove the linear convergence rate of Hildreth's method for quadratic programming, in both its sequential and simulateneous versions. We give bounds on the asymptotic error constant and compare these bounds to those given by Mandel for the cyclic relaxation method for solving linear inequalities.Research of this author was partially supported by CNPq grant No. 301280/86.On leave from the Universidade Federal do Rio de Janeiro, Instituto de Matemática, Rio de Janeiro, R.J. 21.910, Brazil. Research of this author was partially supported by NIH grant HL28438.     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

Embedding and asymptotic expansions for martingales

The paper develops a way of embedding general martingales in continuous ones in such a way that the quadratic variation of the continuous martingale has conditional cumulants (given the original martingale) that are explicitly given in terms of optional and predictable variations of the original process. Bartlett identities for the conditional cumulants are also found. A main corollary to these results is the establishment of second (and in some cases higher) order asymptotic expansions for martingales.Research supported in part by National Science Foundation grant DMS 93-05601 and Army Research Office grant DAAH04-1-0105     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Valid inequalities for mixed integer linear programs

This tutorial presents a theory of valid inequalities for mixed integer linear sets. It introduces the necessary tools from polyhedral theory and gives a geometric understanding of several classical families of valid inequalities such as lift-and-project cuts, Gomory mixed integer cuts, mixed integer rounding cuts, split cuts and intersection cuts, and it reveals the relationships between these families. The tutorial also discusses computational aspects of generating the cuts and their strength. Supported by NSF grant DMI-0352885, ONR grant N00014-03-1-0188 and ANR grant BLAN06-1-138894.     

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.     

LMI Approach to Robust Model Predictive Control

This paper introduces a new approach to robust model predictive control (MPC) based on conservative approximations to semi-infinite optimization using linear matrix inequalities (LMIs). The method applies to problems with convex quadratic costs, linear and convex quadratic constraints, and linear predictive models with bounded uncertainty. If the MPC optimization problem is feasible at the initial control step (the first application of the MPC optimization), it is shown that the MPC optimization problems will be feasible at all future time steps and that the controlled system will be closed-loop stable. The method is illustrated with a solenoid control example. The authors thank the anonymous reviewers for suggestions that improved the presentation of this work. The work was supported in part by the EPRI/DoD Complex Interactive Networks/Systems Initiative under Contract EPRI-W08333-05 and by the US Army Research Office Contract DAAD19-01-1-0485.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

A network approach for specially structured linear programs arising in 0-1 quadratic optimization

Reformulation techniques are commonly used to transform 0-1 quadratic problems into equivalent, mixed 0-1 linear programs. A classical strategy is to replace each quadratic term with a continuous variable and to enforce, for each such product, four linear inequalities that ensure the continuous variable equals the associated product. By employing a transformation of variables, we show how such inequalities give rise to a network structure, so that the continuous relaxations can be readily solved. This work unifies and extends related results for the vertex packing problem and relatives, and roof duality.     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

Models of linear logic

We engage a study of nonmodal linear logic which takes times ⊗ and the linear conditional ⊸ to be the basic connectives instead of times and linear negation ()^⊥ as in Girard's approach. This difference enables us to obtain a very large subsystem of linear logic (called positive linear logic) without an involutionary negation (if the law of double negation is removed from linear logic in Girard's formulation, the resulting subsystem is extremely limited). Our approach enables us to obtain several natural models for various subsystems of linear logic, including a generic model for the so-called minimal linear logic. In particular, it is seen that these models arise spontaneously in the transition from set theory to multiset theory. We also construct a model of full (nonmodal) linear logic that is generic relative to any model of positive linear logic. However, the problem of constructing a generic model for positive linear logic remains open. Bibliography: 2 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 23–35. Original     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Nonlinear 0–1 programming: II. Dominance relations and algorithms

A nonlinear 0–1 program can be restated as a multilinear 0–1 program, which in turn is known to be equivalent to a linear 0–1 program with generalized covering (g.c.) inequalities. In a companion paper [6] we have defined a family of linear inequalities that contains more compact (smaller cardinality) linearizations of a multilinear 0–1 program than the one based on the g.c. inequalities. In this paper we analyze the dominance relations between inequalities of the above family. In particular, we give a criterion that can be checked in linear time, for deciding whether a g.c. inequality can be strengthened by extending the cover from which it was derived. We then describe a class of algorithms based on these results and discuss our computational experience. We conclude that the g.c. inequalities can be strengthened most of the time to an extent that increases with problem density. In particular, the algorithm using the strengthening procedure outperforms the one using only g.c. inequalities whenever the number of nonlinear terms per constraint exceeds about 12–15, and the difference in their performance grows with the number of such terms. Research supported by the National Science Foundation under grant ECS 7902506 and by the Office of Naval Research under contract N00014-75-C-0621 NR 047-048.     

Linear programming via a quadratic penalty function

We use quadratic penalty functions along with some recent ideas from linearl ₁ estimation to arrive at a new characterization of primal optimal solutions in linear programs. The algorithmic implications of this analysis are studied, and a new, finite penalty algorithm for linear programming is designed. Preliminary computational results are presented.Research supported by grant No. 11-0505 from the Danish Natural Science Research Council SNF.     

Penetrative convection in a fluid layer with throughflow

Linear and nonlinear stability analyses of vertical throughflow in a fluid layer, where the density is quadratic in temperature, are studied. To avoid the loss of key terms a weighted functional is used in the energy analysis. Both conditional and unconditional thresholds are derived. When the throughflow is ascending the linear and nonlinear boundaries show substantial agreement. The linear boundary remains close to the conditional nonlinear boundary for descending throughflow, whilst the unconditional threshold begins to diverge. Grant sponsors: Leverhulme Trust: grant number F/00128/AK, EPSRC: grant number GR/S34601/01. This work has been performed under the auspicies of the G.N.F.M. of I.N.D.A.M. and M.I.U.R. (P.R.I.N. 2005): Propagazione non lineare e stabilita’ nei processi termodinamici del continuo.     

0-1 reformulations of the multicommodity capacitated network design problem

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.     

Fuzzy guaranteed cost controller for trajectory tracking in nonlinear systems

In this paper, we propose a fuzzy logic based guaranteed cost controller for trajectory tracking in nonlinear systems. Takagi–Sugeno (T–S) fuzzy model is used to represent the dynamics of a nonlinear system and the controller design is carried out using this fuzzy model. State feedback law is used for building the fuzzy controller whose performance is evaluated using a quadratic cost function. For designing the fuzzy logic based controller which satisfies guaranteed performance, linear matrix inequality (LMI) approach is used. Sufficient conditions are derived in terms of matrix inequalities for minimizing the performance function of the controller. The performance function minimization problem with polynomial matrix inequalities is then transformed into a problem of minimizing a convex performance function involving standard LMIs. This minimization problem can be solved easily and efficiently using the LMI optimization techniques. Our controller design method also ensures that the closed-loop system is asymptotically stable. Simulation study is carried out on a two-link robotic manipulator tracking a reference trajectory. From the results of the simulation study, it is observed that our proposed controller tracks the reference trajectory closely while maintaining a guaranteed minimum cost.     

Nonlinear 0–1 programming: I. Linearization techniques

Any real-valued nonlinear function in 0–1 variables can be rewritten as a multilinear function. We discuss classes of lower and upper bounding linear expressions for multilinear functions in 0–1 variables. For any multilinear inequality in 0–1 variables, we define an equivalent family of linear inequalities. This family contains the well-known system of generalized covering inequalities, as well as other linear equivalents of the multilinear inequality that are more compact, i.e., of smaller cardinality. In a companion paper [7]. we discuss dominance relations between various linear equivalents of a multilinear inequality, and describe a class of algorithms for multilinear 0–1 programming based on these results. Research supported by the National Science Foundation under grant ECS7902506 and by the Office of Naval Research under contract N00014-75-C-0621 NR 047-048.     

Enumerative technique for an extreme point fractional program

This paper presents a technique for solving a linear fractional functionals program whose optimum is supposed to occur at one of the extreme points of a convex polyhedron. This polyhedron is defined by a system of linear inequalities with non-negative restrictions on the variables. The approach is a dual method type in the sense that feasibility is achieved only at the optimal solution.