Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality

In this paper, we propose two sets of theoretically filtered bound-factor constraints for constructing reformulation-linearization technique (RLT)-based linear programming (LP) relaxations for solving polynomial programming problems. We establish related theoretical results for convergence to a global optimum for these reduced sized relaxations, and provide insights into their relative sizes and tightness. Extensive computational results are provided to demonstrate the relative effectiveness of the proposed theoretical filtering strategies in comparison to the standard RLT and a prior heuristic filtering technique using problems from the literature as well as randomly generated test cases.     

An algorithm for nonconvex programming problems

Branch and bound approaches for nonconvex programming problems had been given in [1] and [4]. Crucial for both are the use of rectangular partitions, convex envelopes and separable nonconvex portions of the objective function and constraints. We want to propose a similar algorithm which solves a sequence of problems in each of which the objective function is convex or even linear. The main difference between this approach and previous approaches is the use of general compact partitions instead of rectangular ones and a different refining rule such that the algorithm does not rely on the concept of convex envelopes and handles non-separable functions.First we describe a general algorithm and prove a convergence theorem under suitable regularity assumptions. Then we give as example an algorithm for concave minimization problems.     

A Benson type algorithm for nonconvex multiobjective programming problems

In this paper, an approximation algorithm for solving nonconvex multiobjective programming problems (NCMOPs) is presented. We modify Benson’s method using cones instead of hyperplanes. This algorithm uses an inner approximation and an outer approximation to generate (weakly) efficient solutions and (weakly \(\varepsilon \)-) nondominated points of NCMOPs. Some numerical examples are presented to clarify the proposed algorithm.     

A global optimization method for nonconvex separable programming problems

Conventional methods of solving nonconvex separable programming (NSP) problems by mixed integer programming methods requires adding numerous 0–1 variables. In this work, we present a new method of deriving the global optimum of a NSP program using less number of 0–1 variables. A separable function is initially expressed by a piecewise linear function with summation of absolute terms. Linearizing these absolute terms allows us to convert a NSP problem into a linearly mixed 0–1 program solvable for reaching a solution which is extremely close to the global optimum.     

A reformulation-convexification approach for solving nonconvex quadratic programming problems

In this paper, we consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality). It is shown that for many problems, the initial relaxation itself produces an optimal solution.     

Duality theorems for a class of nonconvex programming problems

The object of this paper is to prove duality theorems for quasiconvex programming problems. The principal tool used is the transformation introduced by Manas for reducing a nonconvex programming problem to a convex programming problem. Duality in the case of linear, quadratic, and linear-fractional programming is a particular case of this general case.The authors are grateful to the referees for their kind suggestions.     

Global optimization of nonconvex factorable programming problems

In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for two test cases, the global optimum found improves upon the solutions previously reported in the source literature. Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000     

Globally solving nonconvex quadratic programming problems via completely positive programming

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.     

Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.     

On the convergence of two branch-and-bound algorithms for nonconvex programming problems

This note presents a new convergence property for each of two branch-and-bound algorithms for nonconvex programming problems (Falk-Soland algorithms and Horst algorithms). For each algorithm, it has been shown previously that, under certain conditions, whenever the algorithm generates an infinite sequence of points, at least one accumulation point of this sequence is a global minimum. We show here that, for each algorithm, in fact, under these conditions, every accumulation point of such a sequence is a global minimum.The author would like to thank Professor R. M. Soland for his helpful comments concerning this paper.     

Global optimization of general nonconvex problems with intermediate polynomial substructures

This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations that exploit these underlying structures. These cutting plane strategies simultaneously convexify linear and nonlinear terms from multiple constraints and are highly effective at tightening standard linear programming relaxations generated by sequential factorable programming techniques. Because the number of available cutting planes increases exponentially with the number of variables, we implement cut filtering and selection strategies to prevent an exponential increase in relaxation size. We introduce algorithms for polynomial substructure detection, cutting plane identification, cut filtering, and cut selection and embed the proposed implementation in BARON at every node in the branch-and-bound tree. A computational study including randomly generated problems of varying size and complexity demonstrates that the exploitation of underlying polynomial substructures significantly reduces computational time, branch-and-bound tree size, and required memory.     

On zero duality gap in nonconvex quadratic programming problems

We present in this paper new sufficient conditions for verifying zero duality gap in nonconvex quadratically/linearly constrained quadratic programs (QP). Based on saddle point condition and conic duality theorem, we first derive a sufficient condition for the zero duality gap between a quadratically constrained QP and its Lagrangian dual or SDP relaxation. We then use a distance measure to characterize the duality gap for nonconvex QP with linear constraints. We show that this distance can be computed via cell enumeration technique in discrete geometry. Finally, we revisit two sufficient optimality conditions in the literature for two classes of nonconvex QPs and show that these conditions actually imply zero duality gap.     

Algorithms for parametric nonconvex programming

In this paper, we consider a general family of nonconvex programming problems. All of the objective functions of the problems in this family are identical, but their feasibility regions depend upon a parameter . This family of problems is called a parametric nonconvex program (PNP). Solving (PNP) means finding an optimal solution for every program in the family. A prototype branch-and-bound algorithm is presented for solving (PNP). By modifying a prototype algorithm for solving a single nonconvex program, this algorithm solves (PNP) in one branch-and-bound search. To implement the algorithm, certain compact partitions and underestimating functions must be formed in an appropriate manner. We present an algorithm for solving a particular (PNP) which implements the prototype algorithm by forming compact partitions and underestimating functions based upon rules given by Falk and Soland. The programs in this (PNP) have the same concave objective function, but their feasibility regions are described by linear constraints with differing right-hand sides. Computational experience with this algorithm is reported for various problems.The author would like to thank Professors R. M. Soland, T. L. Morin, and P. L. Yu for their helpful comments. Thanks also go to two anonymous reviewers for their useful comments concerning an earlier version of this paper.     

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.     

A note on the convergence of an algorithm for nonconvex programming problems

A strong convergence theorem is proven to hold for the general algorithm of the branch and bound type for solving nonconvex programming problems given in [1].     

Generalized Lagrangian duality for nonconvex polynomial programs with polynomial multipliers

In this paper, under the existence of a certificate of nonnegativity of the objective function over the given constraint set, we present saddle-point global optimality conditions and a generalized Lagrangian duality theorem for (not necessarily convex) polynomial optimization problems, where the Lagrange multipliers are polynomials. We show that the nonnegativity certificate together with the archimedean condition guarantees that the values of the Lasserre hierarchy of semidefinite programming (SDP) relaxations of the primal polynomial problem converge asymptotically to the common primal–dual value. We then show that the known regularity conditions that guarantee finite convergence of the Lasserre hierarchy also ensure that the nonnegativity certificate holds and the values of the SDP relaxations converge finitely to the common primal–dual value. Finally, we provide classes of nonconvex polynomial optimization problems for which the Slater condition guarantees the required nonnegativity certificate and the common primal–dual value with constant multipliers and the dual problems can be reformulated as semidefinite programs. These classes include some separable polynomial programs and quadratic optimization problems with quadratic constraints that admit certain hidden convexity. We also give several numerical examples that illustrate our results.