Convex and Concave Relaxations for the Parametric Solutions of Semi-explicit Index-One Differential-Algebraic Equations

A method is presented for computing convex and concave relaxations of the parametric solutions of nonlinear, semi-explicit, index-one differential-algebraic equations (DAEs). These relaxations are central to the development of a deterministic global optimization algorithm for problems with DAEs embedded. The proposed method uses relaxations of the DAE equations to derive an auxiliary system of DAEs, the solutions of which are proven to provide the desired relaxations. The entire procedure is fully automatable.     

Improved relaxations for the parametric solutions of ODEs using differential inequalities

A new method is described for computing nonlinear convex and concave relaxations of the solutions of parametric ordinary differential equations (ODEs). Such relaxations enable deterministic global optimization algorithms to be applied to problems with ODEs embedded, which arise in a wide variety of engineering applications. The proposed method computes relaxations as the solutions of an auxiliary system of ODEs, and a method for automatically constructing and numerically solving appropriate auxiliary ODEs is presented. This approach is similar to two existing methods, which are analyzed and shown to have undesirable properties that are avoided by the new method. Two numerical examples demonstrate that these improvements lead to significantly tighter relaxations than previous methods.     

Differentiable McCormick relaxations

McCormick’s classical relaxation technique constructs closed-form convex and concave relaxations of compositions of simple intrinsic functions. These relaxations have several properties which make them useful for lower bounding problems in global optimization: they can be evaluated automatically, accurately, and computationally inexpensively, and they converge rapidly to the relaxed function as the underlying domain is reduced in size. They may also be adapted to yield relaxations of certain implicit functions and differential equation solutions. However, McCormick’s relaxations may be nonsmooth, and this nonsmoothness can create theoretical and computational obstacles when relaxations are to be deployed. This article presents a continuously differentiable variant of McCormick’s original relaxations in the multivariate McCormick framework of Tsoukalas and Mitsos. Gradients of the new differentiable relaxations may be computed efficiently using the standard forward or reverse modes of automatic differentiation. Extensions to differentiable relaxations of implicit functions and solutions of parametric ordinary differential equations are discussed. A C++ implementation based on the library MC++ is described and applied to a case study in nonsmooth nonconvex optimization.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.     

Global Optimization with Nonlinear Ordinary Differential Equations

This paper examines global optimization of an integral objective function subject to nonlinear ordinary differential equations. Theory is developed for deriving a convex relaxation for an integral by utilizing the composition result defined by McCormick (Mathematical Programming 10, 147–175, 1976) in conjunction with a technique for constructing convex and concave relaxations for the solution of a system of nonquasimonotone ordinary differential equations defined by Singer and Barton (SIAM Journal on Scientific Computing, Submitted). A fully automated implementation of the theory is briefly discussed, and several literature case study problems are examined illustrating the utility of the branch-and-bound algorithm based on these relaxations.     

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.     

Solutions to quadratic minimization problems with box and integer constraints

This paper presents a canonical duality theory for solving quadratic minimization problems subjected to either box or integer constraints. Results show that under Gao and Strang’s general global optimality condition, these well-known nonconvex and discrete problems can be converted into smooth concave maximization dual problems over closed convex feasible spaces without duality gap, and can be solved by well-developed optimization methods. Both existence and uniqueness of these canonical dual solutions are presented. Based on a second-order canonical dual perturbation, the discrete integer programming problem is equivalent to a continuous unconstrained Lipschitzian optimization problem, which can be solved by certain deterministic technique. Particularly, an analytical solution is obtained under certain condition. A fourth-order canonical dual perturbation algorithm is presented and applications are illustrated. Finally, implication of the canonical duality theory for the popular semi-definite programming method is revealed.     

On Approximate Solutions in Vector Optimization Problems Via Scalarization

This work deals with approximate solutions in vector optimization problems. These solutions frequently appear when an iterative algorithm is used to solve a vector optimization problem. We consider a concept of approximate efficiency introduced by Kutateladze and widely used in the literature to study this kind of solutions. Necessary and sufficient conditions for Kutateladze’s approximate solutions are given through scalarization, in such a way that these points are approximate solutions for a scalar optimization problem. Necessary conditions are obtained by using gauge functionals while monotone functionals are considered to attain sufficient conditions. Two properties are then introduced to describe the idea of parametric representation of the approximate efficient set. Finally, through scalarization, characterizations and parametric representations for the set of approximate solutions in convex and nonconvex vector optimization problems are proved and the obtained results are applied to Pareto problems. AMS Classification:90C29, 49M37 This research was partially supported by Ministerio de Ciencia y Tecnología (Spain), project BFM2003-02194.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

Some results on the strength of relaxations of multilinear functions

We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yields the convex and concave envelopes if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, give insight into how to construct strong relaxations of multilinear functions.     

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.     

Bivariate Recursive Equations on Excess-of-loss Reinsurance

This paper investigates bivariate recursive equations on excess-of-loss reinsurance. For an insurance portfolio, under the assumptions that the individual claim severity distribution has bounded continuous density and the number of claims belongs to R1 （a, b） family, bivariate recursive equations for the joint distribution of the cedent＇s aggregate claims and the reinsurer＇s aggregate claims are obtained.     

Generalized Benders’ Decomposition for topology optimization problems

This article considers the non-linear mixed 0–1 optimization problems that appear in topology optimization of load carrying structures. The main objective is to present a Generalized Benders’ Decomposition (GBD) method for solving single and multiple load minimum compliance (maximum stiffness) problems with discrete design variables to global optimality. We present the theoretical aspects of the method, including a proof of finite convergence and conditions for obtaining global optimal solutions. The method is also linked to, and compared with, an Outer-Approximation approach and a mixed 0–1 semi definite programming formulation of the considered problem. Several ways to accelerate the method are suggested and an implementation is described. Finally, a set of truss topology optimization problems are numerically solved to global optimality.     

On Second-Order Optimality Conditions for Vector Optimization

In this article, two second-order constraint qualifications for the vector optimization problem are introduced, that come from first-order constraint qualifications, originally devised for the scalar case. The first is based on the classical feasible arc constraint qualification, proposed by Kuhn and Tucker (Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 481–492, University of California Press, California, 1951) together with a slight modification of McCormick’s second-order constraint qualification. The second—the constant rank constraint qualification—was introduced by Janin (Math. Program. Stud. 21:110–126, 1984). They are used to establish two second-order necessary conditions for the vector optimization problem, with general nonlinear constraints, without any convexity assumption.     

Efficient representations of Green’s functions for some elliptic equations with piecewise-constant coefficients

Convenient for immediate computer implementation equivalents of Green’s functions are obtained for boundary-contact value problems posed for two-dimensional Laplace and Klein-Gordon equations on some regions filled in with piecewise homogeneous isotropic conductive materials. Dirichlet, Neumann and Robin conditions are allowed on the outer boundary of a simply-connected region, while conditions of ideal contact are assumed on interface lines. The objective in this study is to widen the range of effective applicability for the Green’s function version of the boundary integral equation method making the latter usable for equations with piecewise-constant coefficients.     

A hybrid LP/NLP paradigm for global optimization relaxations

Polyhedral relaxations have been incorporated in a variety of solvers for the global optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.     

Complete Solutions and Extremality Criteria to Polynomial Optimization Problems

This paper presents a set of complete solutions to a class of polynomial optimization problems. By using the so-called sequential canonical dual transformation developed in the author’s recent book [Gao, D.Y. (2000), Duality Principles in Nonconvex Systems: Theory, Method and Applications, Kluwer Academic Publishers, Dordrecht/Boston/London, xviii + 454 pp], the nonconvex polynomials in can be converted into an one-dimensional canonical dual optimization problem, which can be solved completely. Therefore, a set of complete solutions to the original problem is obtained. Both global minimizer and local extrema of certain special polynomials can be indentified by Gao-Strang’s gap function and triality theory. For general nonconvex polynomial minimization problems, a sufficient condition is proposed to identify global minimizer. Applications are illustrated by several examples.     

Bringing order into the neighborhoods: relaxation guided variable neighborhood search

In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising for many other combinatorial optimization problems approached by VNS. NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.The Institute of Computer Graphics and Algorithms is supported by the European RTN ADONET under grant 504438.     

A GENERALIZED PROJECTION-SUCCESSIVE LINEAREQUATIONS ALGORITHM FOR NONLINEARLY EQUALITy AND INEQUALITY CONSTRAINED OPTIMIZATION AND ITS RATE OF CONVERGENCE

In this paper, a new superlinearly convergent algorithm is presented for optimization problems with general nonlineer equality and inequality Constraints, Comparing with other methods for these problems, the algorithm has two main advantages. First, it doesn‘t solve anyquadratic programming (QP), and its search directions are determined by the generalized projection technique and the solutions of two systems of linear equations. Second, the sequential points generated by the algoritbh satisfy all inequity constraints and its step-length is computed by the straight line search,The algorithm is proved to possesa global and auperlinear convergence.     

On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.