A reformulation framework for global optimization

In this paper, we present a global optimization method for solving nonconvex mixed integer nonlinear programming (MINLP) problems. A convex overestimation of the feasible region is obtained by replacing the nonconvex constraint functions with convex underestimators. For signomial functions single-variable power and exponential transformations are used to obtain the convex underestimators. For more general nonconvex functions two versions of the so-called αBB-underestimator, valid for twice-differentiable functions, are integrated in the actual reformulation framework. However, in contrast to what is done in branch-and-bound type algorithms, no direct branching is performed in the actual algorithm. Instead a piecewise convex reformulation is used to convexify the entire problem in an extended variable-space, and the reformulated problem is then solved by a convex MINLP solver. As the piecewise linear approximations are made finer, the solution to the convexified and overestimated problem will form a converging sequence towards a global optimal solution. The result is an easily-implementable algorithm for solving a very general class of optimization problems.     

A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions

We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations.     

Convex Envelopes of Monomials of Odd Degree

Convex envelopes of nonconvex functions are widely used to calculate lower bounds to solutions of nonlinear programming problems (NLP), particularly within the context of spatial Branch-and-Bound methods for global optimization. This paper proposes a nonlinear continuous and differentiable convex envelope for monomial terms of odd degree, x ^2k+1, where k N and the range of x includes zero. We prove that this envelope is the tightest possible. We also derive a linear relaxation from the proposed envelope, and compare both the nonlinear and linear formulations with relaxations obtained using other approaches.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Whitney differentiability of optimal-value functions for bound-constrained convex programming problems

ABSTRACT

In the spirit of the Whitney Extension Theorem, consider a function on a compact subset of Euclidean space to be ‘Whitney-differentiable’ if it is a restriction of a continuously Fréchet-differentiable function with an open domain. Whitney-differentiable functions have been shown to have useful (yet possibly nonunique) derivatives and calculus properties even on the boundaries of their domains. This article shows that optimal-value functions for bound-constrained convex programmes with Whitney-differentiable objective functions are themselves Whitney-differentiable, even when the linear-independence constraint qualification is not satisfied. This result extends classic sensitivity results for convex programmes, and generalizes recent work. As an application, sufficient conditions are presented for generating continuously differentiable convex underestimators of nonconvex functions for use in methods for deterministic global optimization in the multivariate McCormick framework. In particular, the main result is applied to generate Whitney-differentiable convex underestimators for quotients of functions with known Whitney-differentiable relaxations.     

AN INTERVAL ALGORITHM FOR CONSTRAINED GLOBAL OPTIMIZATION

In order to solve the constrained global optimization problem,we use penalty functions not only on constraints but also on objective function. Then within the framework of interval analysis,an interval Branch-and-Bound algorithm is given,which does not need to solve a sequence of unconstrained problems. Global convergence is proved. Numerical examples show that this algorithm is efficient.     

An efficient DC programming approach for portfolio decision with higher moments

Portfolio selection with higher moments is a NP-hard nonconvex polynomial optimization problem. In this paper, we propose an efficient local optimization approach based on DC (Difference of Convex functions) programming—called DCA (DC Algorithm)—that consists of solving the nonconvex program by a sequence of convex ones. DCA will construct, in each iteration, a suitable convex quadratic subproblem which can be easily solved by explicit method, due to the proposed special DC decomposition. Computational results show that DCA almost always converges to global optimal solutions while comparing with the global optimization methods (Gloptipoly, Branch-and-Bound) and it outperforms several standard local optimization algorithms.     

Multi-funnel optimization using Gaussian underestimation

In several applications, underestimation of functions has proven to be a helpful tool for global optimization. In protein–ligand docking problems as well as in protein structure prediction, single convex quadratic underestimators have been used to approximate the location of the global minimum point. While this approach has been successful for basin-shaped functions, it is not suitable for energy functions with more than one distinct local minimum with a large magnitude. Such functions may contain several basin-shaped components and, thus, cannot be underfitted by a single convex underestimator. In this paper, we propose using an underestimator composed of several negative Gaussian functions. Such an underestimator can be computed by solving a nonlinear programming problem, which minimizes the error between the data points and the underestimator in the L ¹ norm. Numerical results for simulated and actual docking energy functions are presented.     

Limit vector variational inequality problems via scalarization

This paper presents a global optimization approach for solving signomial geometric programming (SGP) problems. We employ an accelerated extended cutting plane (ECP) approach integrated with piecewise linear (PWL) approximations to solve the global optimization of SGP problems. In this approach, we separate the feasible regions determined by the constraints into convex and nonconvex ones in the logarithmic domain. In the nonconvex feasible regions, the corresponding constraint functions are converted into mixed integer linear constraints using PWL approximations, while the other constraints with convex feasible regions are handled by the ECP method. We also use pre-processed initial cuts and batched cuts to accelerate the proposed algorithm. Numerical results show that the proposed approach can solve the global optimization of SGP problems efficiently and effectively.     

Rigorous convex underestimators for general twice-differentiable problems

In order to generate valid convex lower bounding problems for nonconvex twice-differentiable optimization problems, a method that is based on second-order information of general twice-differentiable functions is presented. Using interval Hessian matrices, valid lower bounds on the eigenvalues of such functions are obtained and used in constructing convex underestimators. By solving several nonlinear example problems, it is shown that the lower bounds are sufficiently tight to ensure satisfactory convergence of the BB, a branch and bound algorithm which relies on this underestimation procedure [3].     

A New Class of Improved Convex Underestimators for Twice Continuously Differentiable Constrained NLPs

We present a new class of convex underestimators for arbitrarily nonconvex and twice continuously differentiable functions. The underestimators are derived by augmenting the original nonconvex function by a nonlinear relaxation function. The relaxation function is a separable convex function, that involves the sum of univariate parametric exponential functions. An efficient procedure that finds the appropriate values for those parameters is developed. This procedure uses interval arithmetic extensively in order to verify whether the new underestimator is convex. For arbitrarily nonconvex functions it is shown that these convex underestimators are tighter than those generated by the BB method. Computational studies complemented with geometrical interpretations demonstrate the potential benefits of the proposed improved convex underestimators.     

A Global Optimization Method,QBB, for Twice-Differentiable Nonconvex Optimization Problem

A global optimization method, QBB, for twice-differentiable NLPs (Non-Linear Programming) is developed to operate within a branch-and-bound framework and require the construction of a relaxed convex problem on the basis of the quadratic lower bounding functions for the generic nonconvex structures. Within an exhaustive simplicial division of the constrained region, the rigorous quadratic underestimation function is constructed for the generic nonconvex function structure by virtue of the maximal eigenvalue analysis of the interval Hessian matrix. Each valid lower bound of the NLP problem with the division progress is computed by the convex programming of the relaxed optimization problem obtained by preserving the convex or linear terms, replacing the concave term with linear convex envelope, underestimating the special terms and the generic terms by using their customized tight convex lower bounding functions or the valid quadratic lower bounding functions, respectively. The standard convergence properties of the QBB algorithm for nonconvex global optimization problems are guaranteed. The preliminary computation studies are presented in order to evaluate the algorithmic efficiency of the proposed QBB approach.     

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.     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

Convex Underestimation of Twice Continuously Differentiable Functions by Piecewise Quadratic Perturbation: Spline αBB Underestimators

This paper describes the construction of convex underestimators for twice continuously differentiable functions over box domains through piecewise quadratic perturbation functions. A refinement of the classical α BB convex underestimator, the underestimators derived through this approach may be significantly tighter than the classical αBB underestimator. The convex underestimator is the difference of the nonconvex function f and a smooth, piecewise quadratic, perturbation function, q. The convexity of the underestimator is guaranteed through an analysis of the eigenvalues of the Hessian of f over all subdomains of a partition of the original box domain. Smoothness properties of the piecewise quadratic perturbation function are derived in a manner analogous to that of spline construction.     

Finding all solutions of nonlinearly constrained systems of equations

A new approach is proposed for finding all-feasible solutions for certain classes of nonlinearly constrained systems of equations. By introducing slack variables, the initial problem is transformed into a global optimization problem (P) whose multiple global minimum solutions with a zero objective value (if any) correspond to all solutions of the initial constrained system of equalities. All-globally optimal points of (P) are then localized within a set of arbitrarily small disjoint rectangles. This is based on a branch and bound type global optimization algorithm which attains finite-convergence to each of the multiple global minima of (P) through the successive refinement of a convex relaxation of the feasible region and the subsequent solution of a series of nonlinear convex optimization problems. Based on the form of the participating functions, a number of techniques for constructing this convex relaxation are proposed. By taking advantage of the properties of products of univariate functions, customized convex lower bounding functions are introduced for a large number of expressions that are or can be transformed into products of univariate functions. Alternative convex relaxation procedures involve either the difference of two convex functions employed in BB [23] or the exponential variable transformation based underestimators employed for generalized geometric programming problems [24]. The proposed approach is illustrated with several test problems. For some of these problems additional solutions are identified that existing methods failed to locate.     

An interval branch and bound method for global Robust optimization

In this paper, we design a Branch and Bound algorithm based on interval arithmetic to address nonconvex robust optimization problems. This algorithm provides the exact global solution of such difficult problems arising in many real life applications. A code was developed in MatLab and was used to solve some robust nonconvex problems with few variables. This first numerical study shows the interest of this approach providing the global solution of such difficult robust nonconvex optimization problems.

     

Entropic proximal decomposition methods for convex programs and variational inequalities

We consider convex optimization and variational inequality problems with a given separable structure. We propose a new decomposition method for these problems which combines the recent logarithmic-quadratic proximal theory introduced by the authors with a decomposition method given by Chen-Teboulle for convex problems with particular structure. The resulting method allows to produce for the first time provably convergent decomposition schemes based on C ^∞ Lagrangians for solving convex structured problems. Under the only assumption that the primal-dual problems have nonempty solution sets, global convergence of the primal-dual sequences produced by the algorithm is established. Received: October 6, 1999 / Accepted: February 2001?Published online September 17, 2001     

Convex envelopes for edge-concave functions

Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in ³ is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equivalent to the sum of the convex envelopes of these functions.Author to whom all correspondence should be addressed.     

$${{\mathcal {D}(\mathcal {C})}}$$-optimization and robust global optimization

For solving global optimization problems with nonconvex feasible sets existing methods compute an approximate optimal solution which is not guaranteed to be close, within a given tolerance, to the actual optimal solution, nor even to be feasible. To overcome these limitations, a robust solution approach is proposed that can be applied to a wide class of problems called D(C){{\mathcal {D}(\mathcal {C})}}-optimization problems. DC optimization and monotonic optimization are particular cases of D(C){{\mathcal {D}(\mathcal {C})}}-optimization, so this class includes virtually every nonconvex global optimization problem of interest. The approach is a refinement and extension of an earlier version proposed for dc and monotonic optimization.