A hybrid global optimization algorithm for non-linear least squares regression

A hybrid global optimization algorithm is proposed aimed at the class of objective functions with properties typical of the problems of non-linear least squares regression. Three components of hybridization are considered: simplicial partition of the feasible region, indicating and excluding vicinities of the main local minimizers from global search, and computing the indicated local minima by means of an efficient local descent algorithm. The performance of the algorithm is tested using a collection of non-linear least squares problems evaluated by other authors as difficult global optimization problems.     

Stability Index Method for Global Minimization

The Stability Index Method (SIM) combines stochastic and deterministic algorithms to find global minima of multidimensional functions. The functions may be nonsmooth and may have multiple local minima. The method examines the change of the diameters of the minimizing sets for its stopping criterion. At first, the algorithm uses the uniform random distribution in the admissible set. Then normal random distributions of decreasing variation are used to focus on probable global minimizers. To test the method, it is applied to seven standard test functions of several variables. The computational results show that the SIM is efficient, reliable and robust.The authors thank the referees for valuable suggestions.     

A Multivariate Global Optimization Using Linear Bounding Functions

Recently linear bounding functions (LBFs) were proposed and used to find -global minima. This paper presents an LBF-based algorithm for multivariate global optimization problems. The algorithm consists of three phases. In the global phase, big subregions not containing a solution are quickly eliminated and those which possibly contain the solution are detected. An efficient scheme for the local phase is developed using our previous local minimization algorithm, which is globally convergent with superlinear/quadratic rate and does not require evaluation of gradients and Hessian matrices. To ensure that the found minimizers are indeed the global solutions or save computation effort, a third phase called the verification phase is often needed. Under adequate conditions the algorithm finds the -global solution(s) within finite steps. Numerical testing results illustrate how the algorithm works, and demonstrate its potential and feasibility.     

The Structure of Minimizers of the Frame Potential on Fusion Frames

In this paper we study the fusion frame potential that is a generalization of the Benedetto-Fickus (vectorial) frame potential to the finite-dimensional fusion frame setting. We study the structure of local and global minimizers of this potential, when restricted to suitable sets of fusion frames. These minimizers are related to tight fusion frames as in the classical vector frame case. Still, tight fusion frames are not as frequent as tight frames; indeed we show that there are choices of parameters involved in fusion frames for which no tight fusion frame can exist. We exhibit necessary and sufficient conditions for the existence of tight fusion frames with prescribed parameters, involving the so-called Horn-Klyachko’s compatibility inequalities. The second part of the work is devoted to the study of the minimization of the fusion frame potential on a fixed sequence of subspaces, with a varying sequence of weights. We related this problem to the index of the Hadamard product by positive matrices and use it to give different characterizations of these minima.     

A unified approach to one-parametric general quadratic programming

A method is proposed for finding local minima to the parametric general quadratic programming problem where all the coefficients are linear or polynomial functions of a scalar parameter. The local minimum vector and the local minimum value are determined explicitly as rational functions of the parameter. A numerical example is given.     

Generating Sum-of-Ratios Test Problems in Global Optimization

A method is presented for the construction of test problems involving the minimization over convex sets of sums of ratios of affine functions. Given a nonempty, compact convex set, the method determines a function that is the sum of linear fractional functions and attains a global minimum over the set at a point that can be found by convex programming and univariate search. Generally, the function will have also local minima over the set that are not global minima.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

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.     

Subvexormal Functions and Subvex Functions

Subvexormal functions and subinvexormal functions are proposed, whose properties are shared commonly by most generalized convex functions and most generalized invex functions, respectively. A necessary and sufficient condition for a subvexormal function to be subinvexormal is given in the locally Lipschitz and regular case. Furthermore, subvex functions and subinvex functions are introduced. It is proved that the class of strictly subvex functions is equivalent to that of functions whose local minima are global and that, in the locally Lipschitz and regular case, both strongly subvex functions and strongly subinvex functions can be characterized as functions whose relatively stationary points (slight extension of stationary points) are global minima.     

一类不依赖于局部极小解个数的填充函数

求解无约束总体优化问题的一类单参数填充函数需要假设问题的局部极小解的个数只有有限个,而且填充函数中参数的选取与局部极小解的谷域的半径有关.本文对填充函数的定义作适当改进,而且对已有的这一类填充函数作改进,构造了一类双参数填充函数.新的填充函数不仅无须对问题的局部极小解的个数作假设,而且其中参数的选取与局部极小解的谷域的半径无关.     

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 Volume Constrained Variational Problem with Lower-Order Terms

We study a one-dimensional variational problem with two or more level set constraints. The existence of global and local minimizers turns out to be dependent on the regularity of the energy density. A complete characterization of local minimizers and the underlying energy landscape is provided. The Γ -limit when the phases exhaust the whole domain is computed.     

A Volume Constrained Variational Problem with Lower-Order Terms

We study a one-dimensional variational problem with two or more level set constraints. The existence of global and local minimizers turns out to be dependent on the regularity of the energy density. A complete characterization of local minimizers and the underlying energy landscape is provided. The Γ -limit when the phases exhaust the whole domain is computed.     

GOSH: derivative-free global optimization using multi-dimensional space-filling curves

Global optimization is a field of mathematical programming dealing with finding global (absolute) minima of multi-dimensional multiextremal functions. Problems of this kind where the objective function is non-differentiable, satisfies the Lipschitz condition with an unknown Lipschitz constant, and is given as a “black-box” are very often encountered in engineering optimization applications. Due to the presence of multiple local minima and the absence of differentiability, traditional optimization techniques using gradients and working with problems having only one minimum cannot be applied in this case. These real-life applied problems are attacked here by employing one of the mostly abstract mathematical objects—space-filling curves. A practical derivative-free deterministic method reducing the dimensionality of the problem by using space-filling curves and working simultaneously with all possible estimates of Lipschitz and Hölder constants is proposed. A smart adaptive balancing of local and global information collected during the search is performed at each iteration. Conditions ensuring convergence of the new method to the global minima are established. Results of numerical experiments on 1000 randomly generated test functions show a clear superiority of the new method w.r.t. the popular method DIRECT and other competitors.     

A search technique for global optimization in a chaotic environment

We describe a new algorithm which uses the trajectories of a discrete dynamical system to sample the domain of an unconstrained objective function in search of global minima. The algorithm is unusually adept at avoiding nonoptimal local minima and successfully converging to a global minimum. Trajectories generated by the algorithm for objective functions with many local minima exhibit chaotic behavior, in the sense that they are extremely sensitive to changes in initial conditions and system parameters. In this context, chaos seems to have a beneficial effect: failure to converge to a global minimum from a given initial point can often be rectified by making arbitrarily small changes in the system parameters.     

An analysis of neighborhood functions on generic solution spaces

The effectiveness of local search algorithms on discrete optimization problems is influenced by the choice of the neighborhood function. A neighborhood function that results in all local minima being global minima is said to have zero L-locals. A polynomially sized neighborhood function with zero L-locals would ensure that at each iteration, a local search algorithm would be able to find an improving solution or conclude that the current solution is a global minimum. This paper presents a recursive relationship for computing the number of neighborhood functions over a generic solution space that results in zero L-locals. Expressions are also given for the number of tree neighborhood functions with zero L-locals. These results provide a first step towards developing expressions that are applicable to discrete optimization problems, as well as providing results that add to the collection of solved graphical enumeration problems.     

Merit functions for nonsmooth complementarity problems and related descent algorithm

Under some assumptions, the solution set of a nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. This paper uses a family of new merit functions to deal with nonlinear complementarity problem where the underlying function is assumed to be a continuous but not necessarily locally Lipschitzian map and gives a descent algorithm for solving the nonsmooth continuous complementarity problems. In addition, the global convergence of the derivative free descent algorithm is also proved.     

Growth of Nanophase Clusters and Potential Energy Minima: Hysteresis, Oscillations, and Phase Transitions

The structures of small Lennard-Jones clusters (local and global minima) in the range n = 30 - 55 atoms are investigated during growth by random atom deposition using Monte Carlo simulations. The cohesive energy, average coordination number, and bond angles are calculated at different temperatures and deposition rates. Deposition conditions which favor thermodynamically stable (global minima) and metastable (local minima) are determined. We have found that the transition from polyicosahedral to quasicrystalline structures during cluster growth exhibits hysteresis at low temperatures. A minimum critical size is required for the evolution of the quasicrystalline family, which is larger than the one predicted by thermodynamics and depends on the temperature and the deposition rate. Oscillations between polyicosahedral and quasicrystalline structures occur at high temperatures in a certain size regime. Implications for the applicability of global optimization techniques to cluster structure determination are also discussed.     

Evolutionary Operators in Global Optimization with Dynamic Search Trajectories

One of the most commonly encountered approaches for the solution of unconstrained global optimization problems is the application of multi-start algorithms. These algorithms usually combine already computed minimizers and previously selected initial points, to generate new starting points, at which, local search methods are applied to detect new minimizers. Multi-start algorithms are usually terminated once a stochastic criterion is satisfied. In this paper, the operators of the Differential Evolution algorithm are employed to generate the starting points of a global optimization method with dynamic search trajectories. Results for various well-known and widely used test functions are reported, supporting the claim that the proposed approach improves drastically the performance of the algorithm, in terms of the total number of function evaluations required to reach a global minimizer.     

Test Functions with Variable Attraction Regions for Global Optimization Problems

Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima.