A Sequential Convexification Method (SCM) for Continuous Global Optimization

A new method for continuous global minimization problems, acronymed SCM, is introduced. This method gives a simple transformation to convert the objective function to an auxiliary function with gradually fewer local minimizers. All Local minimizers except a prefixed one of the auxiliary function are in the region where the function value of the objective function is lower than its current minimal value. Based on this method, an algorithm is designed which uses a local optimization method to minimize the auxiliary function to find a local minimizer at which the value of the objective function is lower than its current minimal value. The algorithm converges asymptotically with probability one to a global minimizer of the objective function. Numerical experiments on a set of standard test problems with several problems' dimensions up to 50 show that the algorithm is very efficient compared with other global optimization methods.     

Parallel continuation-based global optimization for molecular conformation and protein folding

This paper presents our recent work on developing parallel algorithms and software for solving the global minimization problem for molecular conformation, especially protein folding. Global minimization problems are difficult to solve when the objective functions have many local minimizers, such as the energy functions for protein folding. In our approach, to avoid directly minimizing a difficult function, a special integral transformation is introduced to transform the function into a class of gradually deformed, but smoother or easier functions. An optimization procedure is then applied to the new functions successively, to trace their solutions back to the original function. The method can be applied to a large class of nonlinear partially separable functions including energy functions for molecular conformation and protein folding. Mathematical theory for the method, as a special continuation approach to global optimization, is established. Algorithms with different solution tracing strategies are developed. Different levels of parallelism are exploited for the implementation of the algorithms on massively parallel architectures.     

Solving the Sum-of-Ratios Problem by an Interior-Point Method

We consider the problem of minimizing the sum of a convex function and of p1 fractions subject to convex constraints. The numerators of the fractions are positive convex functions, and the denominators are positive concave functions. Thus, each fraction is quasi-convex. We give a brief discussion of the problem and prove that in spite of its special structure, the problem is -complete even when only p=1 fraction is involved. We then show how the problem can be reduced to the minimization of a function of p variables where the function values are given by the solution of certain convex subproblems. Based on this reduction, we propose an algorithm for computing the global minimum of the problem by means of an interior-point method for convex programs.     

Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization

We introduce a new method for solving box-constrained mixed-integer polynomial problems to global optimality. The approach, a specialized branch-and-bound algorithm, is based on the computation of lower bounds provided by the minimization of separable underestimators of the polynomial objective function. The underestimators are the novelty of the approach because the standard approaches in global optimization are based on convex relaxations. Thanks to the fact that only simple bound constraints are present, minimizing the separable underestimator can be done very quickly. The underestimators are computed monomial-wise after the original polynomial has been shifted. We show that such valid underestimators exist and their degree can be bounded when the degree of the polynomial objective function is bounded, too. For the quartic case, all optimal monomial underestimators are determined analytically. We implemented and tested the branch-and-bound algorithm where these underestimators are hardcoded. The comparison against standard global optimization and polynomial optimization solvers clearly shows that our method outperforms the others, the only exception being the binary case where, though, it is still competitive. Moreover, our branch-and-bound approach suffers less in case of dense polynomial objective function, i.e., in case of polynomials having a large number of monomials. This paper is an extended and revised version of the preliminary paper [4].     

A Second-Order Bundle Method Based on -Decomposition Strategy for a Special Class of Eigenvalue Optimizations

In the past decade, eigenvalue optimization has gained remarkable attention in various engineering applications. One of the main difficulties with numerical analysis of such problems is that the eigenvalues, considered as functions of a symmetric matrix, are not smooth at those points where they are multiple. We propose a new explicit nonsmooth second-order bundle algorithm based on the idea of the proximal bundle method on minimizing the arbitrary eigenvalue over an affine family of symmetric matrices, which is a special class of eigenvalue function–D.C. function. To the best of our knowledge, few methods currently exist for minimizing arbitrary eigenvalue function. In this work, we apply the -Lagrangian theory to this class of D.C. functions: the arbitrary eigenvalue function λ_i with affine matrix-valued mappings, where λ_i is usually not convex. We prove the global convergence of our method in the sense that every accumulation point of the sequence of iterates is stationary. Moreover, under mild conditions we show that, if started close enough to the minimizer x*, the proposed algorithm converges to x* quadratically. The method is tested on some constrained optimization problems, and some encouraging preliminary numerical results show the efficiency of our method.     

Convergence Analysis of Some Methods for Minimizing a Nonsmooth Convex Function

In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function . Instead of the original objective function f, we employ a convex approximation f _{k + 1} at the kth iteration. Some global convergence rate estimates are obtained. We illustrate our approach by proposing (i) a new family of proximal point algorithms which possesses the global convergence rate estimate even it the iteration points are calculated approximately, where are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.     

The cluster problem in multivariate global optimization

We consider branch and bound methods for enclosing all unconstrained global minimizers of a nonconvex nonlinear twice-continuously differentiable objective function. In particular, we consider bounds obtained with interval arithmetic, with the midpoint test, but no acceleration procedures. Unless the lower bound is exact, the algorithm without acceleration procedures in general gives an undesirable cluster of boxes around each minimizer. In a previous paper, we analyzed this problem for univariate objective functions. In this paper, we generalize that analysis to multi-dimensional objective functions. As in the univariate case, the results show that the problem is highly related to the behavior of the objective function near the global minimizers and to the order of the corresponding interval extension.This work was partially funded by National Science Foundation grant # CCR-9203730.     

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

In this paper we propose a variant of the random coordinate descent method for solving linearly constrained convex optimization problems with composite objective functions. If the smooth part of the objective function has Lipschitz continuous gradient, then we prove that our method obtains an ?-optimal solution in $\mathcal{O}(n^{2}/\epsilon)$ iterations, where n is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for the rate of convergence in probability is also provided. For strongly convex functions our method converges linearly. Extensive numerical tests confirm that on very large problems, our method is much more numerically efficient than methods based on full gradient information.     

Smooth strongly convex interpolation and exact worst-case performance of first-order methods

We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which provide a finite representation for those functions. This allows us to reformulate the worst-case performance estimation problem as an equivalent finite dimension-independent semidefinite optimization problem, whose exact solution can be recovered up to numerical precision. Optimal solutions to this performance estimation problem provide both worst-case performance bounds and explicit functions matching them, as our smooth (strongly) convex interpolation procedure is constructive. Our works build on those of Drori and Teboulle (Math Program 145(1–2):451–482, 2014) who introduced and solved relaxations of the performance estimation problem for smooth convex functions. We apply our approach to different fixed-step first-order methods with several performance criteria, including objective function accuracy and gradient norm. We conjecture several numerically supported worst-case bounds on the performance of the fixed-step gradient, fast gradient and optimized gradient methods, both in the smooth convex and the smooth strongly convex cases, and deduce tight estimates of the optimal step size for the gradient method.     

On the global optimization properties of finite-difference local descent algorithms

The paper is devoted to the convergence properties of finite-difference local descent algorithms in global optimization problems with a special -convex structure. It is assumed that the objective function can be closely approximated by some smooth convex function. Stability properties of the perturbed gradient descent and coordinate descent methods are investigated. Basing on this results some global optimization properties of finite-difference local descent algorithms, in particular, coordinate descent method, are discovered. These properties are not inherent in methods using exact gradients.The paper was presented at the II. IIASA-Workshop on Global Optimization, Sopron (Hungary), December 9–14, 1990.     

Stochastic comparison algorithm for continuous optimization with estimation

The problem of stochastic optimization for arbitrary objective functions presents a dual challenge. First, one needs to repeatedly estimate the objective function; when no closed-form expression is available, this is only possible through simulation. Second, one has to face the possibility of determining local, rather than global, optima. In this paper, we show how the stochastic comparison approach recently proposed in Ref. 1 for discrete optimization can be used in continuous optimization. We prove that the continuous stochastic comparison algorithm converges to an -neighborhood of the global optimum for any >0. Several applications of this approach to problems with different features are provided and compared to simulated annealing and gradient descent algorithms.This work was supported in part by the National Science Foundation under Grants EID-92-12122 and ECS-88-01912, and by a Grant from United Technologies/Otis Elevator Company.     

Norms of Multipliers and Best Approximations of Holomorphic Functions of Many Variables

We show that the Lebesgue–Landau constants of linear methods for summation of Taylor series of functions holomorphic in a polydisk and in the unit ball from over triangular domains do not depend on the number m. On the basis of this fact, we find a relation between the complete and partial best approximations of holomorphic functions in a polydisk and in the unit ball from .     

Compositions of convex functions and fully linear models

Derivative-free optimization (DFO) is the mathematical study of the optimization algorithms that do not use derivatives. One branch of DFO focuses on model-based DFO methods, where an approximation of the objective function is used to guide the optimization algorithm. Proving convergence of such methods often applies an assumption that the approximations form fully linear models—an assumption that requires the true objective function to be smooth. However, some recent methods have loosened this assumption and instead worked with functions that are compositions of smooth functions with simple convex functions (the max-function or the \(\ell _1\) norm). In this paper, we examine the error bounds resulting from the composition of a convex lower semi-continuous function with a smooth vector-valued function when it is possible to provide fully linear models for each component of the vector-valued function. We derive error bounds for the resulting function values and subgradient vectors.     

New methods for calculating \alpha BB-type underestimators

Most branch-and-bound algorithms in global optimization depend on convex underestimators to calculate lower bounds of a minimization objective function. The $\alpha $ BB methodology produces such underestimators for sufficiently smooth functions by analyzing interval Hessian approximations. Several methods to rigorously determine the $\alpha $ BB parameters have been proposed, varying in tightness and computational complexity. We present new polynomial-time methods and compare their properties to existing approaches. The new methods are based on classical eigenvalue bounds from linear algebra and a more recent result on interval matrices. We show how parameters can be optimized with respect to the average underestimation error, in addition to the maximum error commonly used in $\alpha $ BB methods. Numerical comparisons are made, based on test functions and a set of randomly generated interval Hessians. The paper shows the relative strengths of the methods, and proves exact results where one method dominates another.     

Computing a global optimal solution to a design centering problem

In this paper we present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over ³ and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here we prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a pointx amounts to computing the distance, with respect to a Minkowski gauge, fromx to a finite number of planes. We propose a method for finding these planes and we report some numerical results.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

Global Optimization in Practice: An Application to Interactive Multiple Objective Linear Programming

A multiple objective linear programming problem (P) involves the simultaneous maximization of two or more conflicting linear objective functions over a nonempty polyhedron X. Many of the most popular methods for solving this type of problem, including many well-known interactive methods, involve searching the efficient set X _E of the problem. Generally, however, X _E is a complicated, nonconvex set. As a result, concepts and methods from global optimization may be useful in searching X _E. In this paper, we will explain in theory, and show via an actual application to citrus rootstock selection in Florida, how the potential usefulness of the well-known interactive method STEM for solving problem (P) in this way, can depend crucially upon how accurately certain global optimization problems involving minimizations over X _E are solved. In particular, we will show both in theory and in practice that the choice of whether to use the popular but unreliable payoff table approach or to use one of the lesser known, more accurate global optimization methods to solve these problems can determine whether STEM succeeds or fails as a decision aid. Several lessons and conclusions of transferable value derived from this research are also given.     

A Non-myopic Utility Function for Statistical Global Optimization Algorithms

The high cost of providing worst-case solutions to global optimization problems has motivated the development of average-case algorithms that rely on a statistical model of the objective function. The critical role of the statistical model is to guide the search for the optimum. The standard approach is to define a utility function u(x) that in a certain sense reflects the benefit of evaluating the function at x. A proper utility function needs to strike a balance between the immediate benefit of evaluating the function at x – a myopic consideration; and the overall effect of this choice on the performance of the algorithm – a global criterion. The utility functions currently used in this context are heuristically modified versions of some myopic utility functions. We propose using a new utility function that is provably a globally optimal utility function in a non-adaptive context (where the model of the function values remains unchanged). In the adaptive context, this utility function is not necessarily optimal, however, given its global nature, we expect that its use will lead to the improved performance of statistical global optimization algorithms. To illustrate the approach, and to test the above assertion, we apply this utility function to an existing adaptive multi-dimensional statistical global optimization algorithm and provide experimental comparisons with the original algorithm.     

On the convergence of the method of analytic centers when applied to convex quadratic programs

This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor of with iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of Newton iterations to guarantee an error reduction by a factor of in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.     

Steepest Descent Methods with Generalized Distances for Constrained Optimization

We consider the problem s.t. , where C is a closed and covex subset of with nonempty interior, and introduce a family of interior point methods for this problem, which can be seen as approximate versions of generalized proximal point methods. Each step consists of a one-dimensional search along either a curve or a segment in the interior of C. The information about the boundary of C is contained in a generalized distance which defines the segment of the curve, and whose gradient diverges at the boundary of C. The objective of the search is either f or f plus a regularizing term. When , the usual steepest descent method is a particular case of our general scheme, and we manage to extend known convergence results for the steepest descent method to our family: for nonregularized one-dimensional searches,under a level set boundedness assumption on f, the sequence is bounded, the difference between consecutive iterates converges to 0 and every cluster point of the sequence satisfies first-order optimality conditions for the problem, i.e. is a solution if f is convex. For the regularized search and convex f, no boundedness condition on f is needed and full and global convergence of the sequence to a solution of the problem is established.