A discrete dynamic convexized method for nonlinear integer programming

In this paper, we consider the box constrained nonlinear integer programming problem. We present an auxiliary function, which has the same discrete global minimizers as the problem. The minimization of the function using a discrete local search method can escape successfully from previously converged discrete local minimizers by taking increasing values of a parameter. We propose an algorithm to find a global minimizer of the box constrained nonlinear integer programming problem. The algorithm minimizes the auxiliary function from random initial points. We prove that the algorithm can converge asymptotically with probability one. Numerical experiments on a set of test problems show that the algorithm is efficient and robust.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Local Optimization Method with Global Multidimensional Search

This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present results of numerical experiments with well-known test problems and with the so-called cluster function. These results confirm that the proposed algorithms allows one to find a global minimizer or at least a deep local minimizer of a function with a huge amount of shallow local minima.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

Stability of the Minimizers of Least Squares with a Non-Convex Regularization. Part II: Global Behavior

We address estimation problems where the sought-after solution is defined as the minimizer of an objective function composed of a quadratic data-fidelity term and a regularization term. We especially focus on non-convex and possibly non-smooth regularization terms because of their ability to yield good estimates. This work is dedicated to the stability of the minimizers of such piecewise C^m, with m ≥ 2, non-convex objective functions. It is composed of two parts. In the previous part of this work we considered general local minimizers. In this part we derive results on global minimizers. We show that the data domain contains an open, dense subset such that for every data point therein, the objective function has a finite number of local minimizers, and a unique global minimizer. It gives rise to a global minimizer function which is C^m-1 everywhere on an open and dense subset of the data domain.     

A note on functions whose local minima are global

In this note, we introduce a new class of generalized convex functions and show that a real functionf which is continuous on a compact convex subsetM of ⁿ and whose set of global minimizers onM is arcwise-connected has the property that every local minimum is global if, and only if,f belongs to that class of functions.     

Stability of the Minimizers of Least Squares with a Non-Convex Regularization. Part I: Local Behavior

Many estimation problems amount to minimizing a piecewise C^m objective function, with m ≥ 2, composed of a quadratic data-fidelity term and a general regularization term. It is widely accepted that the minimizers obtained using non-convex and possibly non-smooth regularization terms are frequently good estimates. However, few facts are known on the ways to control properties of these minimizers. This work is dedicated to the stability of the minimizers of such objective functions with respect to variations of the data. It consists of two parts: first we consider all local minimizers, whereas in a second part we derive results on global minimizers. In this part we focus on data points such that every local minimizer is isolated and results from a C^m-1 local minimizer function, defined on some neighborhood. We demonstrate that all data points for which this fails form a set whose closure is negligible.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

An informational approach to the global optimization of expensive-to-evaluate functions

In many global optimization problems motivated by engineering applications, the number of function evaluations is severely limited by time or cost. To ensure that each evaluation contributes to the localization of good candidates for the role of global minimizer, a sequential choice of evaluation points is usually carried out. In particular, when Kriging is used to interpolate past evaluations, the uncertainty associated with the lack of information on the function can be expressed and used to compute a number of criteria accounting for the interest of an additional evaluation at any given point. This paper introduces minimizers entropy as a new Kriging-based criterion for the sequential choice of points at which the function should be evaluated. Based on stepwise uncertainty reduction, it accounts for the informational gain on the minimizer expected from a new evaluation. The criterion is approximated using conditional simulations of the Gaussian process model behind Kriging, and then inserted into an algorithm similar in spirit to the Efficient Global Optimization (EGO) algorithm. An empirical comparison is carried out between our criterion and expected improvement, one of the reference criteria in the literature. Experimental results indicate major evaluation savings over EGO. Finally, the method, which we call IAGO (for Informational Approach to Global Optimization), is extended to robust optimization problems, where both the factors to be tuned and the function evaluations are corrupted by noise.     

Planelike minimizers in periodic media

We show that given an elliptic integrand ?? in ?^d that is periodic under integer translations, and given any plane in ?^d, there is at least one minimizer of ?? that remains at a bounded distance from this plane. This distance can be bounded uniformly on the planes. We also show that, when folded back to ?^d/?^d, the minimizers we construct give rise to a lamination. One particular case of these results is minimal surfaces for metrics invariant under integer translations. The same results hold for other functionals that involve volume terms (small and average zero). In such a case the minimizers satisfy the prescribed mean curvature equation. A further generalization allows the formulation and proof of similar results in manifolds other than the torus provided that their fundamental group and universal cover satisfy some hypotheses. © 2001 John Wiley & Sons, Inc.     

A new discrete filled function algorithm for discrete global optimization

A definition of the discrete filled function is given in this paper. Based on the definition, a discrete filled function is proposed. Theoretical properties of the proposed discrete filled function are investigated, and an algorithm for discrete global optimization is developed from the new discrete filled function. The implementation of the algorithms on several test problems is reported with satisfactory numerical results.     

A filled function method for constrained global optimization

In this paper, a filled function method for solving constrained global optimization problems is proposed. A filled function is proposed for escaping the current local minimizer of a constrained global optimization problem by combining the idea of filled function in unconstrained global optimization and the idea of penalty function in constrained optimization. Then a filled function method for obtaining a global minimizer or an approximate global minimizer of the constrained global optimization problem is presented. Some numerical results demonstrate the efficiency of this global optimization method for solving constrained global optimization problems.     

A filled function method with one parameter for unconstrained global optimization

The filled function method is considered as an efficient approach to solve the global optimization problems. In this paper, a new filled function method is proposed. Its main idea is as follows: a new continuously differentiable filled function with only one parameter is constructed for unconstrained global optimization when a minimizer of the objective function is found, then a minimizer of the filled function will be found in a lower basin of the objective function, thereafter, a better minimizer of the objective function will be found. The above process is repeated until the global optimal solution is found. The numerical experiments show the efficiency of the proposed filled function method.     

An algorithm for nonlinear optimization problems with binary variables

One of the challenging optimization problems is determining the minimizer of a nonlinear programming problem that has binary variables. A vexing difficulty is the rate the work to solve such problems increases as the number of discrete variables increases. Any such problem with bounded discrete variables, especially binary variables, may be transformed to that of finding a global optimum of a problem in continuous variables. However, the transformed problems usually have astronomically large numbers of local minimizers, making them harder to solve than typical global optimization problems. Despite this apparent disadvantage, we show that the approach is not futile if we use smoothing techniques. The method we advocate first convexifies the problem and then solves a sequence of subproblems, whose solutions form a trajectory that leads to the solution. To illustrate how well the algorithm performs we show the computational results of applying it to problems taken from the literature and new test problems with known optimal solutions.     

A global optimization approach for solving the convex multiplicative programming problem

We consider a convex multiplicative programming problem of the form% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaGG7bGaam% OzamaaBaaaleaacaaIXaaabeaakiaacIcacaWG4bGaaiykaiabgwSi% xlaadAgadaWgaaWcbaGaaGOmaaqabaGccaGGOaGaamiEaiaacMcaca% GG6aGaamiEaiabgIGiolaadIfacaGG9baaaa!4A08!\[\{ f_1 (x) \cdot f_2 (x):x \in X\} \]where X is a compact convex set of ⁿ and f ₁, f ₂ are convex functions which have nonnegative values over X.Using two additional variables we transform this problem into a problem with a special structure in which the objective function depends only on two of the (n+2) variables. Following a decomposition concept in global optimization we then reduce this problem to a master problem of minimizing a quasi-concave function over a convex set in ² ₂. This master problem can be solved by an outer approximation method which requires performing a sequence of simplex tableau pivoting operations. The proposed algorithm is finite when the functions f _i, (i=1, 2) are affine-linear and X is a polytope and it is convergent for the general convex case.Partly supported by the Deutsche Forschungsgemeinschaft Project CONMIN.     

Kuhn-Tucker sufficiency for global minimum of multi-extremal mathematical programming problems

The Kuhn-Tucker Sufficiency Theorem states that a feasible point that satisfies the Kuhn-Tucker conditions is a global minimizer for a convex programming problem for which a local minimizer is global. In this paper, we present new Kuhn-Tucker sufficiency conditions for possibly multi-extremal nonconvex mathematical programming problems which may have many local minimizers that are not global. We derive the sufficiency conditions by first constructing weighted sum of square underestimators of the objective function and then by characterizing the global optimality of the underestimators. As a consequence, we derive easily verifiable Kuhn-Tucker sufficient conditions for general quadratic programming problems with equality and inequality constraints. Numerical examples are given to illustrate the significance of our criteria for multi-extremal problems.     

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.     

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.     

Dynamic Globally Concavized Filled Function Method for Continuous Global Optimization

We consider a box-constrained continuous global minimization problem. A new definition of filled function, namely that of globally concavized filled function, is proposed. A new two-parameter class of globally concavized filled functions A(x,k,p) is constructed, which has the same global minimizers as the problem on the solution domain if p is large enough. The minimization of A(x,k,p) can escape successfully from a previously converged local minimizer by taking increasing values of k. A dynamic globally concavized filled function method is designed based on these functions and the convergence property is proved. Numerical experiments on a set of standard testing functions show that the resulting method is competitive with some well-known global minimization methods. This research was supported partially by the NSFC under Grants 60773126 and 10301009, the NKBRSF of China under Grant 2006CB805900, and the Natural Science Foundation of Fujian province under Grant 2006J0030.     

一个新的非线性整数规划问题的单参数填充函数算法

非线性整数规划问题是一类复杂的优化问题,填充函数算法是求解整数规划问题的一类有效方法.构造一个新的单参数填充函数,分析并证明了其填充性质;然后,基于该填充函数并结合离散最速下降法提出了一种新的填充函数算法;最后,采用新算法对6个测试函数进行数值实验,结果表明该算法具有良好的计算效果,是有效可行的.