On Global Optimality Conditions and Cutting Plane Algorithms

We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems.     

Generalized convexity for non-regular optimization problems with conic constraints

In non-regular problems the classical optimality conditions are totally inapplicable. Meaningful results were obtained for problems with conic constraints by Izmailov and Solodov (SIAM J Control Optim 40(4):1280–1295, 2001). They are based on the so-called 2-regularity condition of the constraints at a feasible point. It is well known that generalized convexity notions play a very important role in optimization for establishing optimality conditions. In this paper we give the concept of Karush–Kuhn–Tucker point to rewrite the necessary optimality condition given in Izmailov and Solodov (SIAM J Control Optim 40(4):1280–1295, 2001) and the appropriate generalized convexity notions to show that the optimality condition is both necessary and sufficient to characterize optimal solutions set for non-regular problems with conic constraints. The results that exist in the literature up to now, even for the regular case, are particular instances of the ones presented here.     

Global optimization and multi knapsack: A percolation algorithm

Since the standard multi knapsack problem, may be rewritten as a reverse convex problem, we present a global optimization approach. It is known from solving high dimensional nonconvex problems that pure cutting plane methods may fail and branch-and-bound is impractical, due to a large duality gap. On the other hand, a strategy based on some sufficient optimality condition does not help much because it requires generating all level set points, an intractable problem. Therefore, we propose to combine both a cutting plane method and a sufficient optimality condition together with a random generation of level set points where the number of points is limited by a tabu list to prevent re-examination of the same level set area. Experiments show that we end up with a small duality gap allowing a subsequent branch-and-bound approach to prove optimality.     

Saddle Points Theory of Two Classes of Augmented Lagrangians and Its Applications to Generalized Semi-infinite Programming

In this paper, we develop the sufficient conditions for the existence of local and global saddle points of two classes of augmented Lagrangian functions for nonconvex optimization problem with both equality and inequality constraints, which improve the corresponding results in available papers. The main feature of our sufficient condition for the existence of global saddle points is that we do not need the uniqueness of the optimal solution. Furthermore, we show that the existence of global saddle points is a necessary and sufficient condition for the exact penalty representation in the framework of augmented Lagrangians. Based on these, we convert a class of generalized semi-infinite programming problems into standard semi-infinite programming problems via augmented Lagrangians. Some new first-order optimality conditions are also discussed. This research was supported by the National Natural Science Foundation of P.R. China (Grant No. 10571106 and No. 10701047).     

Generalized convexity in non-regular programming problems with inequality-type constraints

Convexity plays a very important role in optimization for establishing optimality conditions. Different works have shown that the convexity property can be replaced by a weaker notion, the invexity. In particular, for problems with inequality-type constraints, Martin defined a weaker notion of invexity, the Karush-Kuhn-Tucker-invexity (hereafter KKT-invexity), that is both necessary and sufficient to obtain Karush-Kuhn-Tucker-type optimality conditions. It is well known that for this result to hold the problem has to verify a constraint qualification, i.e., it must be regular or non-degenerate. In non-regular problems, the classical optimality conditions are totally inapplicable. Meaningful results were obtained for problems with inequality-type constraints by Izmailov. They are based on the 2-regularity condition of the constraints at a feasible point. In this work, we generalize Martin's result to non-regular problems by defining an analogous concept, the 2-KKT-invexity, and using the characterization of the tangent cone in the 2-regular case and the necessary optimality condition given by Izmailov.     

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.     

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.     

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.     

Beyond Canonical DC-Optimization: The Single Reverse Polar Problem

We propose a novel generalization of the Canonical Difference of Convex problem (CDC), and we study the convergence of outer approximation algorithms for its solution, which use an approximated oracle for checking the global optimality conditions. Although the approximated optimality conditions are similar to those of CDC, this new class of problems is shown to significantly differ from its special case. Indeed, outer approximation approaches for CDC need be substantially modified in order to cope with the more general problem, bringing to new algorithms. We develop a hierarchy of conditions that guarantee global convergence, and we build three different cutting plane algorithms relying on them.     

Stationary conditions for mathematical programs with vanishing constraints using weak constraint qualifications

We consider a class of optimization problems that is called a mathematical program with vanishing constraints (MPVC for short). This class has some similarities to mathematical programs with equilibrium constraints (MPECs for short), and typically violates standard constraint qualifications, hence the well-known Karush-Kuhn-Tucker conditions do not provide necessary optimality criteria. In order to obtain reasonable first order conditions under very weak assumptions, we introduce several MPVC-tailored constraint qualifications, discuss their relation, and prove an optimality condition which may be viewed as the counterpart of what is called M-stationarity in the MPEC-field.     

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

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

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.     

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.     

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.     

Generalized convexity and efficiency for non-regular multiobjective programming problems with inequality-type constraints

For multiobjective problems with inequality-type constraints the necessary conditions for efficient solutions are presented. These conditions are applied when the constraints do not necessarily satisfy any regularity assumptions, and they are based on the concept of 2-regularity introduced by Izmailov. In general, the necessary optimality conditions are not sufficient and the efficient solution set is not the same as the Karush-Kuhn-Tucker points set. So it is necessary to introduce generalized convexity notions. In the multiobjective non-regular case we give the notion of 2-KKT-pseudoinvex-II problems. This new concept of generalized convexity is both necessary and sufficient to guarantee the characterization of all efficient solutions based on the optimality conditions.     

The p-Factor-Lagrange Methods for Degenerate Nonlinear Programming

The paper presents a new approach to solving nonlinear programming (NLP) problems for which the strict complementarity condition (SCC), a constraint qualification (CQ), and a second-order sufficient condition (SOSC) for optimality are not necessarily satisfied at a solution. Our approach is based on the construction of p-regularity and on reformulating the inequality constraints as equalities. Namely, by introducing the slack variables, we get the equality constrained problem, for which the Lagrange optimality system is singular at the solution of the NLP problem in the case of the violation of the CQs, SCC and/or SOSC. To overcome the difficulty of singularity, we propose the p-factor method for solving the Lagrange system. The method has a superlinear rate of convergence under a mild assumption. We show that our assumption is always satisfied under a standard second-order sufficient condition (SOSC) for optimality. At the same time, we give examples of the problems where the SOSC does not hold, but our assumption is satisfied. Moreover, no estimation of the set of active constraints is required. The proposed approach can be applied to a variety of problems.     

Global optimality principles for polynomial optimization over box or bivalent constraints by separable polynomial approximations

In this paper we present necessary conditions for global optimality for polynomial problems with box or bivalent constraints using separable polynomial relaxations. We achieve this by first deriving a numerically checkable characterization of global optimality for separable polynomial problems with box as well as bivalent constraints. Our necessary optimality conditions can be numerically checked by solving semi-definite programming problems. Then, by employing separable polynomial under-estimators, we establish sufficient conditions for global optimality for classes of polynomial optimization problems with box or bivalent constraints. We construct underestimators using the sum of squares convex (SOS-convex) polynomials of real algebraic geometry. An important feature of SOS-convexity that is generally not shared by the standard convexity is that whether a polynomial is SOS-convex or not can be checked by solving a semidefinite programming problem. We illustrate the versatility of our optimality conditions by simple numerical examples.     

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.     

New optimality conditions for nonsmooth control problems

This work considers nonsmooth optimal control problems and provides two new sufficient conditions of optimality. The first condition involves the Lagrange multipliers while the second does not. We show that under the first new condition all processes satisfying the Pontryagin Maximum Principle (called MP-processes) are optimal. Conversely, we prove that optimal control problems in which every MP-process is optimal necessarily obey our first optimality condition. The second condition is more natural, but it is only applicable to normal problems and the converse holds just for smooth problems. Nevertheless, it is proved that for the class of normal smooth optimal control problems the two conditions are equivalent. Some examples illustrating the features of these sufficient concepts are presented.