Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of sets of disjunctions in the continuous space, and logic propositions in terms of Boolean variables. In this paper we consider GDP problems involving convex nonlinear inequalities in the disjunctions. Based on the work by Stubbs and Mehrotra [21] and Ceria and Soares [6], we propose a convex nonlinear relaxation of the nonlinear convex GDP problem that relies on the convex hull of each of the disjunctions that is obtained by variable disaggregation and reformulation of the inequalities. The proposed nonlinear relaxation is used to formulate the GDP problem as a Mixed-Integer Nonlinear Programming (MINLP) problem that is shown to be tighter than the conventional big-M formulation. A disjunctive branch and bound method is also presented, and numerical results are given for a set of test problems.     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

A sequential parametric convex approximation method with applications to nonconvex truss topology design problems

We describe a general scheme for solving nonconvex optimization problems, where in each iteration the nonconvex feasible set is approximated by an inner convex approximation. The latter is defined using an upper bound on the nonconvex constraint functions. Under appropriate conditions, a monotone convergence to a KKT point is established. The scheme is applied to truss topology design (TTD) problems, where the nonconvex constraints are associated with bounds on displacements and stresses. It is shown that the approximate convex problem solved at each inner iteration can be cast as a conic quadratic programming problem, hence large scale TTD problems can be efficiently solved by the proposed method.     

Transportation problem with nonlinear side constraints a branch and bound approach

In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

Output Feedback Model Predictive Tracking Control Using a Slope Bounded Nonlinear Model

In this paper, an output feedback model predictive tracking control method is proposed for constrained nonlinear systems, which are described by a slope bounded model. In order to solve the problem, we consider the finite horizon cost function for an off-set free tracking control of the system. For reference tracking, the steady state is calculated by solving by quadratic programming and a nonlinear estimator is designed to predict the state from output measurements. The optimized control input sequences are obtained by minimizing the upper bound of the cost function with a terminal weighting matrix. The cost monotonicity guarantees that tracking and estimation errors go to zero. The proposed control law can easily be obtained by solving a convex optimization problem satisfying several linear matrix inequalities. In order to show the effectiveness of the proposed method, a novel slope bounded nonlinear model-based predictive control method is applied to the set-point tracking problem of solid oxide fuel cell systems. Simulations are also given to demonstrate the tracking performance of the proposed method.     

An algorithm for the min concave cost flow problem

A method is presented to solve that class of network flow problems, which may be formulated as one source - multiple destination minimum cost flow problems with concave costs. The global optimum is searched using a branch and bound procedure, in which the enumeration scheme is based on a characterization of the optimal solution set, while linear relaxations of the original problem provide lower bounds.     

Optimal use of the translation method and relaxations of variational problems

The translation method has been used with great success in bounding the effective moduli of composite materials. We consider here the analogous method for bounding the relaxations of variational problems. We optimize the bound over the set of all available translations. Our method is to cast this in the form of a minmax problem. Using techniques of nonsmooth analysis, we are able to identify the optimal translation bound, meanwhile proving the existence of at least one optimal combination rank-one convex quadratic and null-Lagrangian translation. The optimal translation bound proves to be a better general lower bound on relaxations of variational problems than is the polyconvexification in three dimensions. In two dimensions, we discuss the negative result that the optimal translation bound is exactly the polyconvexification. Several examples of optimal applications of translation bounds to non-convex nonlinear variational problems are given.     

Barrier subgradient method

In this paper we develop a new affine-invariant primal–dual subgradient method for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization. For all these problems, the rate of convergence of our method does not depend on the problem’s data.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

多项式分裂可行问题

本文研究多项式分裂可行问题,即由多项式不等式定义的分裂可行问题,包括凸与非凸、可行与不可行的问题;给出多项式分裂可行问题解集的半定松弛表示;研究其半定松弛化问题的性质;并基于这些性质建立求解多项式分裂可行问题的半定松弛算法.本文在较为一般的条件下证明了,如果分裂可行问题有解,则可通过本文建立的算法求得一个解点;如果问题...     

Polyhedral annexation in mixed integer and combinatorial programming

Polyhedral annexation is a new approach for generating all valid inequalities in mixed integer and combinatorial programming. These include the facets of the convex hull of feasible integer solutions. The approach is capable of exploiting the characteristics of the feasible solution space in regions both “adjacent to” and “distant from” the linear programming vertex without resorting to specialized notions of group theory, convex analysis or projective geometry. The approach also provides new ways for exploiting the “branching inequalities” of branch and bound.     

A Lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures

In this work we present a global optimization algorithm for solving a class of large-scale nonconvex optimization models that have a decomposable structure. Such models, which are very expensive to solve to global optimality, are frequently encountered in two-stage stochastic programming problems, engineering design, and also in planning and scheduling. A generic formulation and reformulation of the decomposable models is given. We propose a specialized deterministic branch-and-cut algorithm to solve these models to global optimality, wherein bounds on the global optimum are obtained by solving convex relaxations of these models with certain cuts added to them in order to tighten the relaxations. These cuts are based on the solutions of the sub-problems obtained by applying Lagrangean decomposition to the original nonconvex model. Numerical examples are presented to illustrate the effectiveness of the proposed method compared to available commercial global optimization solvers that are based on branch and bound methods.     

LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. It incorporates separation algorithms for valid inequalities of the bisection cut polytope described in a recent study by the authors. While the problem specific cuts help to strengthen the linear relaxation significantly, the semidefinite bound profits much more from separating the cycle inequalities of the cut polytope on a slightly enlarged support. Extensive numerical experiments show that this semidefinite branch-and-cut approach without problem specific cuts is a superior choice to the classical simplex approach exploiting bisection specific inequalities on a clear majority of our large sparse test instances from VLSI design and numerical optimization.     

Resilient and robust finite-time H∞ control for uncertain discrete-time jump nonlinear systems

This paper studies the robust and resilient finite-time H_∞ control problem for uncertain discrete-time nonlinear systems with Markovian jump parameters. With the help of linear matrix inequalities and stochastic analysis techniques, the criteria concerning stochastic finite-time boundedness and stochastic H_∞ finite-time boundedness are initially established for the nonlinear stochastic model. We then turn to stochastic finite-time controller analysis and design to guarantee that the stochastic model is stochastically H_∞ finite-time bounded by employing matrix decomposition method. Applying resilient control schemes, the resilient and robust finite-time controllers are further designed to ensure stochastic H_∞ finite-time boundedness of the derived stochastic nonlinear systems. Moreover, the results concerning stochastic finite-time stability and stochastic finite-time boundedness are addressed. All derived criteria are expressed in terms of linear matrix inequalities, which can be solved by utilizing the available convex optimal method. Finally, the validity of obtained methods is illustrated by numerical examples.     

Finite convergence of algorithms for nonlinear programs and variational inequalities

Algorithms for nonlinear programming and variational inequality problems are, in general, only guaranteed to converge in the limit to a Karush-Kuhn-Tucker point, in the case of nonlinear programs, or to a solution in the case of variational inequalities. In this paper, we derive sufficient conditions for nonlinear programs with convex feasible sets such that any convergent algorithm can be modified, by adding a convex subproblem with a linear objective function, to guarantee finite convergence in a generalized sense. When the feasible set is polyhedral, the subproblem is a linear program and finite convergence is obtained. Similar results are also developed for variational inequalities.The research of the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173.The authors are indebted to Professors Olvi Mangasarian, Garth McCormick, Jong-Shi Pang, Hanif Sherali, and Hoang Tuy for helpful comments and suggestions and to two anonymous referees for constructive remarks and for bringing to their attention the results in Refs. 13 and 14.     

A combined relaxation method for variational inequalities with nonlinear constraints

A simple iterative method for solving variational inequalities with a set-valued, nonmonotone mapping and a convex feasible set is proposed. This set can be defined by nonlinear functions. The method is based on combining and extending ideas contained in various relaxation methods of nonsmooth optimization. Also a modification of the averaging method for the problem under consideration is proposed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research was supported in part by RFFI grant No. 95-01-00061.     

Robust guaranteed cost control for uncertain linear differential systems of neutral type

In this paper, the robust guaranteed cost control problem for a class of uncertain linear differential systems of neutral type with a given quadratic cost functions is investigated. The uncertainty is assumed to be norm-bounded and time-varying nonlinear. The problem is to design a state feedback control laws such that the closed-loop system is robustly stable and the closed-loop cost function value is not more than a specified upper bound for all admissible uncertainty and time delay. A criterion for the existence of such controllers is derived based on the matrix inequality approach combined with the Lyapunov method. A parameterized characterization of the robust guaranteed cost controllers is given in terms of the feasible solutions to the certain matrix inequalities. A numerical example is given to illustrate the proposed method.     

A global optimization algorithm for linear fractional and bilinear programs

In this paper a deterministic method is proposed for the global optimization of mathematical programs that involve the sum of linear fractional and/or bilinear terms. Linear and nonlinear convex estimator functions are developed for the linear fractional and bilinear terms. Conditions under which these functions are nonredundant are established. It is shown that additional estimators can be obtained through projections of the feasible region that can also be incorporated in a convex nonlinear underestimator problem for predicting lower bounds for the global optimum. The proposed algorithm consists of a spatial branch and bound search for which several branching rules are discussed. Illustrative examples and computational results are presented to demonstrate the efficiency of the proposed algorithm.