Necessary global optimality conditions for nonlinear programming problems with polynomial constraints

In this paper, we develop necessary conditions for global optimality that apply to non-linear programming problems with polynomial constraints which cover a broad range of optimization problems that arise in applications of continuous as well as discrete optimization. In particular, we show that our optimality conditions readily apply to problems where the objective function is the difference of polynomial and convex functions over polynomial constraints, and to classes of fractional programming problems. Our necessary conditions become also sufficient for global optimality for polynomial programming problems. Our approach makes use of polynomial over-estimators and, a polynomial version of a theorem of the alternative which is a variant of the Positivstellensatz in semi-algebraic geometry. We discuss numerical examples to illustrate the significance of our optimality conditions.     

Reduced RLT representations for nonconvex polynomial programming problems

This paper explores equivalent, reduced size Reformulation-Linearization Technique (RLT)-based formulations for polynomial programming problems. Utilizing a basis partitioning scheme for an embedded linear equality subsystem, we show that a strict subset of RLT defining equalities imply the remaining ones. Applying this result, we derive significantly reduced RLT representations and develop certain coherent associated branching rules that assure convergence to a global optimum, along with static as well as dynamic basis selection strategies to implement the proposed procedure. In addition, we enhance the RLT relaxations with v-semidefinite cuts, which are empirically shown to further improve the relative performance of the reduced RLT method over the usual RLT approach. We present computational results for randomly generated instances to test the different proposed reduction strategies and to demonstrate the improvement in overall computational effort when such reduced RLT mechanisms are employed.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

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.     

Necessary optimality conditions for minimax programming problems with mathematical constraints

In this paper, necessary optimality conditions in terms of upper and/or lower subdifferentials of both cost and constraint functions are derived for minimax optimization problems with inequality, equality and geometric constraints in the setting of non-differentiatiable and non-Lipschitz functions in Asplund spaces. Necessary optimality conditions in the fuzzy form are also presented. An application of the fuzzy necessary optimality condition is shown by considering minimax fractional programming problem.     

An approximate approach of global optimization for polynomial programming problems

Many methods for solving polynomial programming problems can only find locally optimal solutions. This paper proposes a method for finding the approximately globally optimal solutions of polynomial programs. Representing a bounded continuous variable x_i as the addition of a discrete variable d_i and a small variable ϵ_i, a polynomial term x_ix_i can be expanded as the sum of d_ix_j, d_jϵ_i; and ϵ_iϵ_j. A procedure is then developed to fully linearize d_ix_j and d_je_i, and to approximately linearize ϵ_iϵ_j with an error below a pre-specified tolerance. This linearization procedure can also be extended to higher order polynomial programs. Several polynomial programming examples in the literature are tested to demonstrate that the proposed method can systematically solve these examples to find the global optimum within a pre-specified error.     

Multi-parametric disaggregation technique for global optimization of polynomial programming problems

This paper discusses a power-based transformation technique that is especially useful when solving polynomial optimization problems, frequently occurring in science and engineering. The polynomial nonlinear problem is primarily transformed into a suitable reformulated problem containing new sets of discrete and continuous variables. By applying a term-wise disaggregation scheme combined with multi-parametric elements, an upper/lower bounding mixed-integer linear program can be derived for minimization/maximization problems. It can then be solved to global optimality through standard methods, with the original problem being approximated to a certain precision level, which can be as tight as desired. Furthermore, this technique can also be applied to signomial problems with rational exponents, after a few effortless algebraic transformations. Numerical examples taken from the literature are used to illustrate the effectiveness of the proposed approach.     

Using copositivity for global optimality criteria in concave quadratic programming problems

In this note we specify a necessary and sufficient condition for global optimality in concave quadratic minimization problems. Using this condition, it follows that, from the perspective of worst-case complexity of concave quadratic problems, the difference between local and global optimality conditions is not as large as in general. As an essential ingredient, we here use the-subdifferential calculus via an approach of Hiriart-Urruty and Lemarechal (1990).     

Characterizing global optimality for DC optimization problems under convex inequality constraints

Characterizations of global optimality are given for general difference convex (DC) optimization problems involving convex inequality constraints. These results are obtained in terms of -subdifferentials of the objective and constraint functions and do not require any regularity condition. An extension of Farkas' lemma is obtained for inequality systems involving convex functions and is used to establish necessary and sufficient optimality conditions. As applications, optimality conditions are also given for weakly convex programming problems, convex maximization problems and for fractional programming problems.This paper was presented at the Optimization Miniconference held at the University of Ballarat, Victoria, Australia, on July 14, 1994.     

RLT-POS: Reformulation-Linearization Technique-based optimization software for solving polynomial programming problems

In this paper, we introduce a Reformulation-Linearization Technique-based open-source optimization software for solving polynomial programming problems (RLT-POS). We present algorithms and mechanisms that form the backbone of RLT-POS, including constraint filtering techniques, reduced RLT representations, and semidefinite cuts. When implemented individually, each model enhancement has been shown in previous papers to significantly improve the performance of the standard RLT procedure. However, the coordination between different model enhancement techniques becomes critical for an improved overall performance since special structures in the original formulation that work in favor of a particular technique might be lost after implementing some other model enhancement. More specifically, we discuss the coordination between (1) constraint elimination via filtering techniques and reduced RLT representations, and (2) semidefinite cuts for sparse problems. We present computational results using instances from the literature as well as randomly generated problems to demonstrate the improvement over a standard RLT implementation and to compare the performances of the software packages BARON, COUENNE, and SparsePOP with RLT-POS.     

On solving a class of fractional semi-infinite polynomial programming problems

Computational Optimization and Applications - In this paper, we study a class of fractional semi-infinite polynomial programming (FSIPP) problems, in which the objective is a fraction of a convex...     

An algorithm for solving global optimization problems with nonlinear constraints

In this paper we propose an algorithm using only the values of the objective function and constraints for solving one-dimensional global optimization problems where both the objective function and constraints are Lipschitzean and nonlinear. The constrained problem is reduced to an unconstrained one by the index scheme. To solve the reduced problem a new method with local tuning on the behavior of the objective function and constraints over different sectors of the search region is proposed. Sufficient conditions of global convergence are established. We also present results of some numerical experiments.     

A global continuation algorithm for solving binary quadratic programming problems

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately. This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province.     

An effective method for solving linear programming problems with flexible constraints

For solving linear programming problems with flexible constraints being specific piecewise linear programs a new algorithm which is based on a systematic decomposition of the feasible set into linear constrained subsets is proposed and shown to converge.     

Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization

We observe that in a simple one-dimensional polynomial optimization problem (POP), the ??optimal?? values of semidefinite programming (SDP) relaxation problems reported by the standard SDP solvers converge to the optimal value of the POP, while the true optimal values of SDP relaxation problems are strictly and significantly less than that value. Some pieces of circumstantial evidences for the strange behaviors of the SDP solvers are given. This result gives a warning to users of the SDP relaxation method for POPs to be careful in believing the results of the SDP solvers. We also demonstrate how SDPA-GMP, a multiple precision SDP solver developed by one of the authors, can deal with this situation correctly.     

A method for solving to optimality uncapacitated location problems

In this paper we develop a method for solving to optimality a general 0–1 formulation for uncapacitated location problems. This is a 3-stage method that solves large problems in reasonable computing times.The 3-stage method is composed of a primal-dual algorithm, a subgradient optimization to solve a Lagrangean dual and a branch-and-bound algorithm. It has a hierarchical structure, with a given stage being activated only if the optimal solution could not be identified in the preceding stage.The proposed method was used in the solution of three well-known uncapacitated location problems: the simple plant location problem, thep-median problem and the fixed-chargep-median problem. Computational results are given for problems of up to the size 200 customers ×200 potential facility sites.     

Non-convex quadratic minimization problems with quadratic constraints: global optimality conditions

In this paper, we first examine how global optimality of non-convex constrained optimization problems is related to Lagrange multiplier conditions. We then establish Lagrange multiplier conditions for global optimality of general quadratic minimization problems with quadratic constraints. We also obtain necessary global optimality conditions, which are different from the Lagrange multiplier conditions for special classes of quadratic optimization problems. These classes include weighted least squares with ellipsoidal constraints, and quadratic minimization with binary constraints. We discuss examples which demonstrate that our optimality conditions can effectively be used for identifying global minimizers of certain multi-extremal non-convex quadratic optimization problems. The work of Z. Y. Wu was carried out while the author was at the Department of Applied Mathematics, University of New South Wales, Sydney, Australia.     

A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique

This paper is concerned with the development of an algorithm to solve continuous polynomial programming problems for which the objective function and the constraints are specified polynomials. A linear programming relaxation is derived for the problem based on a Reformulation Linearization Technique (RLT), which generates nonlinear (polynomial) implied constraints to be included in the original problem, and subsequently linearizes the resulting problem by defining new variables, one for each distinct polynomial term. This construct is then used to obtain lower bounds in the context of a proposed branch and bound scheme, which is proven to converge to a global optimal solution. A numerical example is presented to illustrate the proposed algorithm.     

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.