On characterizing the set of possible effective tensors of composites: The variational method and the translation method

A general algebraic framework is developed for characterizing the set of possible effective tensors of composites. A transformation to the polarization-problem simplifies the derivation of the Hashin-Shtrikman variational principles and simplifies the calculation of the effective tensors of laminate materials. A general connection is established between two methods for bounding effective tensors of composites. The first method is based on the variational principles of Hashin and Shtrikman. The second method, due to Tartar, Murat, Lurie, and Cherkaev, uses translation operators or, equivalently, quadratic quasiconvex functions. A correspondence is established between these translation operators and bounding operators on the relevant non-local projection operator, T₁. An important class of bounds, namely trace bounds on the effective tensors of two-component media, are given a geometrical interpretation: after a suitable fractional linear transformation of the tensor space each bound corresponds to a tangent plane to the set of possible tensors. A wide class of translation operators that generate these bounds is found. The extremal translation operators in this class incorporate projections onto spaces of antisymmetric tensors. These extremal translations generate attainable trace bounds even when the tensors of the two-components are not well ordered. In particular, they generate the bounds of Walpole on the effective bulk modulus. The variational principles of Gibiansky and Cherkaev for bounding complex effective tensors are reviewed and used to derive some rigorous bounds that generalize the bounds conjectured by Golden and Papanicolaou. An isomorphism is shown to underlie their variational principles. This isomorphism is used to obtain Dirichlet-type variational principles and bounds for the effective tensors of general non-selfadjoint problems. It is anticipated that these variational principles, which stem from the work of Gibiansky and Cherkaev, will have applications in many fields of science.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

On the Optimal Design of Wall-to-Wall Heat Transport

We consider the problem of optimizing heat transport through an incompressible fluid layer. Modeling passive scalar transport by advection-diffusion, we maximize the mean rate of total transport by a divergence-free velocity field. Subject to various boundary conditions and intensity constraints, we prove that the maximal rate of transport scales linearly in the r.m.s. kinetic energy and, up to possible logarithmic corrections, as the one-third power of the mean enstrophy in the advective regime. This makes rigorous a previous prediction on the near optimality of convection rolls for energy-constrained transport. On the other hand, optimal designs for enstrophy-constrained transport are significantly more difficult to describe: we introduce a “branching” flow design with an unbounded number of degrees of freedom and prove it achieves nearly optimal transport. The main technical tool behind these results is a variational principle for evaluating the transport of candidate designs. The principle admits dual formulations for bounding transport from above and below. While the upper bound is closely related to the “background method,” the lower bound reveals a connection between the optimal design problems considered herein and other apparently related model problems from mathematical materials science. These connections serve to motivate designs. © 2019 Wiley Periodicals, Inc.     

Semidefinite relaxations for non-convex quadratic mixed-integer programming

We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this approach as a bounding routine in an SDP-based branch-and-bound framework. In case of a convex objective function, the new SDP bound improves the bound given by the continuous relaxation of the problem. Numerical experiments show that our algorithm performs well on various types of non-convex instances.     

On singular stochastic control and optimal stopping of spectrally negative jump diffusions

We consider a broad class of singular stochastic control problems of spectrally negative jump diffusions in the presence of potentially nonlinear state-dependent exercise payoffs. We analyse these problems by relying on associated variational inequalities and state a set of sufficient conditions under which the value of the considered problems can be explicitly derived in terms of the increasing minimal r-harmonic map. We also present a set of inequalities bounding the value of the optimal policy and prove that increased policy flexibility increases both the value of the optimal strategy as well as the rate at which this value grows.     

Enhancing RLT relaxations via a new class of semidefinite cuts

In this paper, we propose a mechanism to tighten Reformulation-Linearization Technique (RLT) based relaxations for solving nonconvex programming problems by importing concepts from semidefinite programming (SDP), leading to a new class of semidefinite cutting planes. Given an RLT relaxation, the usual nonnegativity restrictions on the matrix of RLT product variables is replaced by a suitable positive semidefinite constraint. Instead of relying on specific SDP solvers, the positive semidefinite stipulation is re-written to develop a semi-infinite linear programming representation of the problem, and an approach is developed that can be implemented using traditional optimization software. Specifically, the infinite set of constraints is relaxed, and members of this set are generated as needed via a separation routine in polynomial time. In essence, this process yields an RLT relaxation that is augmented with valid inequalities, which are themselves classes of RLT constraints that we call semidefinite cuts. These semidefinite cuts comprise a relaxation of the underlying semidefinite constraint. We illustrate this strategy by applying it to the case of optimizing a nonconvex quadratic objective function over a simplex. The algorithm has been implemented in C++, using CPLEX callable routines, and two types of semidefinite restrictions are explored along with several implementation strategies. Several of the most promising lower bounding strategies have been implemented within a branch-and-bound framework. Computational results indicate that the cutting plane algorithm provides a significant tightening of the lower bound obtained by using RLT alone. Moreover, when used within a branch-and-bound framework, the proposed lower bound significantly reduces the effort required to obtain globally optimal solutions.     

A scenario generation-based lower bounding approach for stochastic scheduling problems

In this paper, we investigate scenario generation methods to establish lower bounds on the optimal objective value for stochastic scheduling problems that contain random parameters with continuous distributions. In contrast to the Sample Average Approximation (SAA) approach, which yields probabilistic bound values, we use an alternative bounding method that relies on the ideas of discrete bounding and recursive stratified sampling. Theoretical support is provided for deriving exact lower bounds for both expectation and conditional value-at-risk objectives. We illustrate the use of our method on the single machine total weighted tardiness problem. The results of our numerical investigation demonstrate good properties of our bounding method, compared with the SAA method and an earlier discrete bounding method.     

On maintenance scheduling of production units

A typical maintenance scheduling problem is presented as a large-scale mixed integer nonlinear programming case. Several relaxations of the conditions of variables and constraints are discussed. The optimal solution of the models based on these relaxations is viewed as the lower bound of the optimal solution in the original problem. A combined implicit enumeration and branch-and-bound algorithm is used. Typical dimension of the problems for which computational experience is reported is 25 production units in the system. 19 of these are to be maintained and a planning horizon of 52 weeks with 5 types of hours per week. The corresponding dimensions of the model are about 5700 constraints, 700 binary variables and 6500 nonlinear separable variables.     

Convex relaxations of chance constrained optimization problems

In this paper we develop convex relaxations of chance constrained optimization problems in order to obtain lower bounds on the optimal value. Unlike existing statistical lower bounding techniques, our approach is designed to provide deterministic lower bounds. We show that a version of the proposed scheme leads to a tractable convex relaxation when the chance constraint function is affine with respect to the underlying random vector and the random vector has independent components. We also propose an iterative improvement scheme for refining the bounds.     

Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

The multiconstraint 0–1 knapsack problem is encountered when one has to decide how to use a knapsack with multiple resource constraints. Even though the single constraint version of this problem has received a lot of attention, the multiconstraint knapsack problem has been seldom addressed. This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxation of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.     

A hierarchy of bounds for stochastic mixed-integer programs

We consider general two-stage SMIPs with recourse, in which integer variables are allowed in both stages of the problem and randomness is allowed in the objective function, the constraint matrices (i.e., the technology matrix and the recourse matrix), and the right-hand side. We develop a hierarchy of lower and upper bounds for the optimal objective value of an SMIP by generalizing the wait-and-see solution and the expected result of using the expected value solution. These bounds become progressively stronger but generally more difficult to compute. Our numerical study indicates the bounds we develop in this paper can be strong relative to those provided by linear relaxations. Hence this new bounding approach is a complementary tool to the current bounding techniques used in solving SMIPs, particularly for large-scale and poorly formulated problems.     

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.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.     

Design of planar articulated mechanisms using branch and bound

This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements elastic stability is of major concern. We derive conditions, modeled by nonlinear matrix inequalities, which guarantee that a stable equilibrium is found and that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities.To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve mechanism design problems of realistic size to global optimality.     

Generalized roof duality

The roof dual bound for quadratic unconstrained binary optimization is the basis for several methods for efficiently computing the solution to many hard combinatorial problems. It works by constructing the tightest possible lower-bounding submodular function, and instead of minimizing the original objective function, the relaxation is minimized. However, for higher-order problems the technique has been less successful. A standard technique is to first reduce the problem into a quadratic one by introducing auxiliary variables and then apply the quadratic roof dual bound, but this may lead to loose bounds.We generalize the roof duality technique to higher-order optimization problems. Similarly to the quadratic case, optimal relaxations are defined to be the ones that give the maximum lower bound. We show how submodular relaxations can efficiently be constructed in order to compute the generalized roof dual bound for general cubic and quartic pseudo-boolean functions. Further, we prove that important properties such as persistency still hold, which allows us to determine optimal values for some of the variables. From a practical point of view, we experimentally demonstrate that the technique outperforms the state of the art for a wide range of applications, both in terms of lower bounds and in the number of assigned variables.     

The 0–1 knapsack problem with multiple choice constraints

In this paper we consider the 0–1 knapsack problem with multiple choice constraints appended. Such a problem may arise in a capital budgeting context where only one project may be selected from a particular group of projects. Thus the problem is to choose one project from each group such that the budgetary constraint is satisfied and the maximum return is realized. We formulate two branch and bound algorithms which use two different relaxations as the primary bounding relaxations. In addition, theoretical results are given for a simple reduction in the number of variables in the problem.     

Components identification based method for box constrained variational inequality problems with almost linear functions

We present a method for solving a class of box constrained variational inequality problems. The method makes use of a procedure for identifying some components of the solution by bounding it with an interval vector. It is shown that the method computes an approximate solution of the variational inequality problem by solving at most n reduced systems of equations, where n is the dimension of the problem. Among those systems, only the one of the smallest dimension has to be solved with high accuracy. The others are solved merely to identify some components of the solution, and so the computation can be done under a very mild requirement of accuracy. Numerical results are presented for the obstacle problem, to illustrate the efficiency of the method. AMS subject classification (2000)  90C33, 65G30, 65K10     

Higher order variational integrators in optimal control theory

Higher order variational integrators are analyzed and applied to optimal control problems posed with mechanical systems. First, we derive two different kinds of high order variational integrators based on different dimensions of the underlying approximation space. While the first well-known integrator is equivalent to a symplectic partitioned Runge-Kutta method, the second integrator, denoted as symplectic Galerkin integrator, yields a method which in general, cannot be written as a standard symplectic Runge-Kutta scheme [1]. Furthermore, we use these integrators for the discretization of optimal control problems. By analyzing the adjoint systems of the optimal control problem and its discretized counterpart, we prove that for these particular integrators optimization and discretization commute [2]. This property guarantees that the accuracy is preserved for the adjoint system which is also referred to as the Covector Mapping Principle. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On a class of second order variational problems with constraints

We study the structure of optimal solutions for a class of constrained, second order variational problems on bounded intervals. We show that, for intervals of length greater than some positive constant, the optimal solutions are bounded inC ¹ by a bound independent of the length of the interval. Furthermore, for sufficiently large intervals, the ‘mass’ and ‘energy’ of optimal solutions are almost uniformly distributed.     

Optimal Fine‐Scale Structures in Compliance Minimization for a Shear Load

We return to a classic problem of structural optimization whose solution requires microstructure. It is well‐known that perimeter penalization assures the existence of an optimal design. We are interested in the regime where the perimeter penalization is weak; i.e., in the effect of perimeter as a selection mechanism in structural optimization. To explore this topic in a simple yet challenging example, we focus on a two‐dimensional elastic shape optimization problem involving the optimal removal of material from a rectangular region loaded in shear. We consider the minimization of a weighted sum of volume, perimeter, and compliance (i.e., the work done by the load), focusing on the behavior as the weight ɛ of the perimeter term tends to 0. Our main result concerns the scaling of the optimal value with respect to ɛ. Our analysis combines an upper bound and a lower bound. The upper bound is proved by finding a near‐optimal structure, which resembles a rank‐2 laminate except that the approximate interfaces are replaced by branching constructions. The lower bound, which shows that no other microstructure can be much better, uses arguments based on the Hashin‐Shtrikman variational principle. The regime being considered here is particularly difficult to explore numerically due to the intrinsic nonconvexity of structural optimization and the spatial complexity of the optimal structures. While perimeter has been considered as a selection mechanism in other problems involving microstructure, the example considered here is novel because optimality seems to require the use of two well‐separated length scales.© 2016 Wiley Periodicals, Inc.