A new necessary and sufficient global optimality condition for canonical DC problems

The paper proposes a new necessary and sufficient global optimality condition for canonical DC optimization problems. We analyze the rationale behind Tuy’s standard global optimality condition for canonical DC problems, which relies on the so-called regularity condition and thus can not deal with the widely existing non-regular instances. Then we show how to modify and generalize the standard condition to a new one that does not need regularity assumption, and prove that this new condition is equivalent to other known global optimality conditions. Finally, we show that the cutting plane method, when associated with the new optimality condition, could solve the non-regular canonical DC problems, which significantly enlarges the application of existing cutting plane (outer approximation) algorithms.     

Global optimality conditions and optimization methods for quadratic integer programming problems

In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions, local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.     

Necessary Optimality Conditions and New Optimization Methods for Cubic Polynomial Optimization Problems with Mixed Variables

Multivariate cubic polynomial optimization problems, as a special case of the general polynomial optimization, have a lot of practical applications in real world. In this paper, some necessary local optimality conditions and some necessary global optimality conditions for cubic polynomial optimization problems with mixed variables are established. Then some local optimization methods, including weakly local optimization methods for general problems with mixed variables and strongly local optimization methods for cubic polynomial optimization problems with mixed variables, are proposed by exploiting these necessary local optimality conditions and necessary global optimality conditions. A global optimization method is proposed for cubic polynomial optimization problems by combining these local optimization methods together with some auxiliary functions. Some numerical examples are also given to illustrate that these approaches are very efficient.     

Global optimality conditions and optimization methods for quadratic assignment problems

In this paper some global optimality conditions for general quadratic {0, 1} programming problems with linear equality constraints are discussed and then some global optimality conditions for quadratic assignment problems (QAP) are presented. A local optimization method for (QAP) is derived according to the necessary global optimality conditions. A global optimization method for (QAP) is presented by combining the sufficient global optimality conditions, the local optimization method and some auxiliary functions. Some numerical examples are given to illustrate the efficiency of the given optimization methods.     

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

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

DC approach to weakly convex optimization and nonconvex quadratic optimization problems

Motivated by weakly convex optimization and quadratic optimization problems, we first show that there is no duality gap between a difference of convex (DC) program over DC constraints and its associated dual problem. We then provide certificates of global optimality for a class of nonconvex optimization problems. As an application, we derive characterizations of robust solutions for uncertain general nonconvex quadratic optimization problems over nonconvex quadratic constraints.     

Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma

In this paper, we present Lagrange multiplier necessary conditions for global optimality that apply to non-convex optimization problems beyond quadratic optimization problems subject to a single quadratic constraint. In particular, we show that our optimality conditions apply to problems where the objective function is the difference of quadratic and convex functions over a quadratic constraint, and to certain class of fractional programming problems. Our necessary conditions become necessary and sufficient conditions for global optimality for quadratic minimization subject to quadratic constraint. As an application, we also obtain global optimality conditions for a class of trust-region problems. Our approach makes use of outer-estimators, and the powerful S-lemma which has played key role in control theory and semidefinite optimization. We discuss numerical examples to illustrate the significance of our optimality conditions. The authors are grateful to the referees for their useful comments which have contributed to the final preparation of the paper.     

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.     

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.     

The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems

The DC programming and its DC algorithm (DCA) address the problem of minimizing a function f=g−h (with g,h being lower semicontinuous proper convex functions on R ⁿ ) on the whole space. Based on local optimality conditions and DC duality, DCA was successfully applied to a lot of different and various nondifferentiable nonconvex optimization problems to which it quite often gave global solutions and proved to be more robust and more efficient than related standard methods, especially in the large scale setting. The computational efficiency of DCA suggests to us a deeper and more complete study on DC programming, using the special class of DC programs (when either g or h is polyhedral convex) called polyhedral DC programs. The DC duality is investigated in an easier way, which is more convenient to the study of optimality conditions. New practical results on local optimality are presented. We emphasize regularization techniques in DC programming in order to construct suitable equivalent DC programs to nondifferentiable nonconvex optimization problems and new significant questions which have to be answered. A deeper insight into DCA is introduced which really sheds new light on DCA and could partly explain its efficiency. Finally DC models of real world nonconvex optimization are reported.     

一类特殊多项式整数规划问题的最优化算法

本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用,并且是NP难问题。对于这类问题,最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先,利用最优性必要条件,我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数,设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

Global Optimality Conditions for Some Classes of Optimization Problems

We establish new necessary and sufficient optimality conditions for global optimization problems. In particular, we establish tractable optimality conditions for the problems of minimizing a weakly convex or concave function subject to standard constraints, such as box constraints, binary constraints, and simplex constraints. We also derive some new necessary and sufficient optimality conditions for quadratic optimization. Our main theoretical tool for establishing these optimality conditions is abstract convexity.     

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.     

Global Quadratic Minimization over Bivalent Constraints: Necessary and Sufficient Global Optimality Condition

In this paper, we establish global optimality conditions for quadratic optimization problems with quadratic equality and bivalent constraints. We first present a necessary and sufficient condition for a global minimizer of quadratic optimization problems with quadratic equality and bivalent constraints. Then we examine situations where this optimality condition is equivalent to checking the positive semidefiniteness of a related matrix, and so, can be verified in polynomial time by using elementary eigenvalues decomposition techniques. As a consequence, we also present simple sufficient global optimality conditions, which can be verified by solving a linear matrix inequality problem, extending several known sufficient optimality conditions in the existing literature.     

Unified approaches for solvable and unsolvable linear complementarity problems

In this paper, general linear complementarity problems (LCPs) are studied via global optimization problems. In particular, unsolvable LCPs are reformulated as multicriteria optimization, minimax optimization and quadratic programming problems. The solvability and unsolvability of LCPs are obtained via these reformulations. Furthermore, first-order and second-order global optimality conditions of LCPs are derived. Some examples are also given to demonstrate these optimality conditions.     

Outer approximation algorithms for canonical DC problems

The paper discusses a general framework for outer approximation type algorithms for the canonical DC optimization problem. The algorithms rely on a polar reformulation of the problem and exploit an approximated oracle in order to check global optimality. Consequently, approximate optimality conditions are introduced and bounds on the quality of the approximate global optimal solution are obtained. A thorough analysis of properties which guarantee convergence is carried out; two families of conditions are introduced which lead to design six implementable algorithms, whose convergence can be proved within a unified framework.     

Bounds tightening based on optimality conditions for nonconvex box-constrained optimization

First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.     

Role of copositivity in optimality criteria for nonconvex optimization problems

Second-order necessary and sufficient conditions for local optimality in constrained optimization problems are discussed. For global optimality, a criterion recently developed by Hiriart-Urruty and Lemarechal is thoroughly examined in the case of concave quadratic problems and reformulated into copositivity conditions.     

An Optimization Problem with a Separable Non-Convex Objective Function and a Linear Constraint

For a class of global optimization (maximization) problems, with a separable non-concave objective function and a linear constraint a computationally efficient heuristic has been developed.The concave relaxation of a global optimization problem is introduced. An algorithm for solving this problem to optimality is presented. The optimal solution of the relaxation problem is shown to provide an upper bound for the optimal value of the objective function of the original global optimization problem. An easily checked sufficient optimality condition is formulated under which the optimal solution of concave relaxation problem is optimal for the corresponding non-concave problem. An heuristic algorithm for solving the considered global optimization problem is developed.The considered global optimization problem models a wide class of optimal distribution of a unidimensional resource over subsystems to provide maximum total output in a multicomponent systems.In the presented computational experiments the developed heuristic algorithm generated solutions, which either met optimality conditions or had objective function values with a negligible deviation from optimality (less than 1/10 of a percent over entire range of problems tested).