Robust optimization of noisy blackbox problems using the Mesh Adaptive Direct Search algorithm

Blackbox optimization problems are often contaminated with numerical noise, and direct search methods such as the Mesh Adaptive Direct Search (MADS) algorithm may get stuck at solutions artificially created by the noise. We propose a way to smooth out the objective function of an unconstrained problem using previously evaluated function evaluations, rather than resampling points. The new algorithm, called Robust-MADS is applied to a collection of noisy analytical problems from the literature and on an optimization problem to tune the parameters of a trust-region method.     

Nonsmooth optimization through Mesh Adaptive Direct Search and Variable Neighborhood Search

This paper proposes a way to combine the Mesh Adaptive Direct Search (MADS) algorithm, which extends the Generalized Pattern Search (GPS) algorithm, with the Variable Neighborhood Search (VNS) metaheuristic, for nonsmooth constrained optimization. The resulting algorithm retains the convergence properties of MADS, and allows the far reaching exploration features of VNS to move away from local solutions. The paper also proposes a generic way to use surrogate functions in the VNS search. Numerical results illustrate advantages and limitations of this method.     

A Direct Search Frame-Based Adaptive Barzilai-Borwein Method

This paper proposes a direct search frame-based adaptive Barzilai-Borwein method for unconstrained minimization. The method is based on the framework of frame-based algorithms proposed by Coope and Price, but we use the strategy of ABB method and the rotational minimal positive basis to reduce the computation work at each iteration. Under some mild assumptions, the convergence of this approach will be established. Through five hundred and twenty numerical tests using the CUTEr test problem library, we show that the proposed method is promising.     

Using QR Decomposition to Obtain a New Instance of Mesh Adaptive Direct Search with Uniformly Distributed Polling Directions

The purpose of this paper is to introduce a new instance of the Mesh Adaptive Direct Search (Mads) class of algorithms, which utilizes a more uniform distribution of poll directions than do other common instances, such as OrthoMads and LtMads. Our new implementation, called QrMads, bases its poll directions on an equal area partitioning of the n-dimensional unit sphere and the QR decomposition to obtain an orthogonal set of directions. While each instance produces directions which are dense in the limit, QrMads directions are more uniformly distributed in the unit sphere. This uniformity is the key to enhanced performance in higher dimensions and for constrained problems. The trade-off is that QrMads is no longer deterministic and at each iteration the set of polling directions is no longer orthogonal. Instead, at each iteration, the poll directions are only ‘nearly orthogonal,’ becoming increasingly closer to orthogonal as the mesh size decreases. Finally, we present a variety of test results on smooth, nonsmooth, unconstrained, and constrained problems and compare them to OrthoMads on the same set of problems.     

Adaptive multi-restart Tabu Search algorithm for the vehicle routing problem with cross-docking

This paper deals with a multi-source vehicle routing problem with a cross-docking facility, and studies open and closed network configurations as well as practically relevant dependency rules and consolidation decisions. Given a set of supplier–customer pairs with known demands, the aim is to design minimum cost routes for the transportation of products via a cross-dock. Vehicles cannot travel directly from suppliers to customers, and thus, products arriving from inbound vehicles are sorted and consolidated onto outbound vehicles. The proposed method utilizes an adaptive multi-restart local search framework. For this purpose, a Tabu Search algorithm is employed, while the execution of the re-starting mechanism is based on the information extracted from a reference set of solutions. Computational experiments illustrate the efficiency and effectiveness of the proposed method. Compared to existing results, new improved upper bounds are reported.     

A Minimal Distance Constrained Adaptive Mesh Algorithm with Application to the Dual Reciprocity Method

We present a new technique for generating error equi-distributing meshes that satisfy both local quasi-uniformity and a preset minimal mesh spacing. This is first done in the one-dimensional case by extending the Kautsky and Nichols method and then in the two-dimensional case by generalizing the tensor product methods to alternating curved line equi-distributions. With the new meshing approach, we have achieved better accuracy in approximation using interpolatory radial basis functions. Furthermore, improved accuracy in numerical results has been obtained when the interpolatory strategy is applied to the dual reciprocity boundary element method for solving a class of linear and nonhomogeneous partial differential equations.     

A fast parallel algorithm to compute the rank of a matrix over an arbitrary field

It is shown that the rank of a matrix over an arbitrary field can be computed inO(log² n) time using a polynomial number of processors. Also appeared in ACM Symposium on Theory of Computing, May 28–30, 1986 Berkeley, California. Research supported by Miller Fellowship, University of California, Berkeley.     

A Mesh Adaptive Basin Hopping Method for the Design of Circular Antenna Arrays

The design of circular antenna arrays is a challenging optimization problem, which requires ad-hoc methods to fulfill the engineering requirements. In this work, we introduce the Mesh Adaptive Basin Hopping algorithm to tackle such problem effectively; the experimental results show that the new approach proposed outperforms the state-of-the-art methods, both in terms of quality of the solutions and computational efficiency.     

A generalized separation for the variance contributions of input variables and their distribution parameters

For the structural system with both the uncertainties of input variables and their distribution parameters, this work investigates the generalized separation approach by transforming the original variable into the auxiliary variable with arbitrary distribution. Based on the variance based sensitivity analysis, the generalized sensitivity measures can be given, which are used to identify the influences of the auxiliary variables and distribution parameters simultaneously. For the different auxiliary variables, the variance contributions are proved to be identical, which illustrates the correctness of the generalized separation approach. Then the relationship of the variance contributions of original variables with those of the auxiliary variables and distribution parameters is investigated. Several examples are employed to demonstrate the rationality of the generalized separation approach.     

A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem

Multilevel programming is characterized as mathematical programming to solve decentralized planning problems. The models partition control over decision variables among ordered levels within a hierarchical planning structure of which the linear bilevel form is a special case of a multilevel programming problem. In a system with such a hierarchical structure, the high-level decision making situations generally require inclusion of zero-one variables representing ‘yes-no’ decisions. We provide a mixed-integer linear bilevel programming formulation in which zero-one decision variables are controlled by a high-level decision maker and real-value decision variables are controlled by a low-level decision maker. An algorithm based on the short term memory component of Tabu Search, called Simple Tabu Search, is developed to solve the problem, and two supplementary procedures are proposed that provide variations of the algorithm. Computational results disclose that our approach is effective in terms of both solution quality and efficiency.     

Backtracking Adaptive Search: Distribution of Number of Iterations to Convergence

Backtracking adaptive search is a simplified stochastic optimiza-tion procedure which permits the acceptance of worsening objective function values. It generalizes the hesitant adaptive search, which in turn is a gener-alization of the pure adaptive search. In this paper, we use ideas from the theory of stochastic processes to determine the full distribution of the number of iterations to convergence for the backtracking adaptive search.Communicated by P. M. PardalosThe authors thank theMarsden Fund of the Royal Society of New Zealand for support of this research. The fourth author was supported by a Bright Future Scholarship administered by the Foundation for Research, Science and Technology.     

A Hybrid Symbiosis Organisms Search algorithm and its application to real world problems

In this paper, a new hybrid algorithm, Hybrid Symbiosis Organisms Search (HSOS) has been proposed by combining Symbiosis Organisms Search (SOS) algorithm with Simple Quadratic Interpolation (SQI). The proposed algorithm provides more efficient behavior when dealing with real-world and large scale problems. To verify the performance of this suggested algorithm, 13 (Thirteen) well known benchmark functions, CEC2005 and CEC2010 special session on real-parameter optimization are being considered. The results obtained by the proposed method are compared with other state-of-the-art algorithms and it was observed that the suggested approach provides an effective and efficient solution in regards to the quality of the final result as well as the convergence rate. Moreover, the effect of the common controlling parameters of the algorithm, viz. population size, number of fitness evaluations (number of generations) of the algorithm are also being investigated by considering different population sizes and the number of fitness evaluations (number of generations). Finally, the method endorsed in this paper has been applied to two real life problems and it was inferred that the output of the proposed algorithm is satisfactory.     

A supplement to a regularization method for the proximal point algorithm

The purpose of this paper is to show that the iterative scheme recently studied by Xu (J Glob Optim 36(1):115–125, 2006) is the same as the one studied by Kamimura and Takahashi (J Approx Theory 106(2):226–240, 2000) and to give a supplement to these results. With the new technique proposed by Maingé (Comput Math Appl 59(1):74–79, 2010), we show that the convergence of the iterative scheme is established under another assumption. It is noted that if the computation error is zero or the approximate computation is exact, our new result is a genuine generalization of Xu’s result and Kamimura–Takahashi’s result.     

On an algorithm for dynamic reconstruction of the input

We consider the problem of dynamic reconstruction of the input in a system described by a vector differential equation and nonlinear in the state variable. We indicate an algorithm that is stable under information noises and computational errors and is aimed at infinite system operation time. The algorithm is based on the dynamic regularization method.     

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

A type of modified BFGS algorithm with any rank defects and the local Q-superlinear convergence properties

A modified BFGS algorithm for solving the unconstrained optimization, whose Hessian matrix at the minimum point of the convex function is of rank defects, is presented in this paper.The main idea of the algorithm is first to add a modified term to the convex function for obtain an equivalent model, then simply the model to get the modified BFGS algorithm. The superlinear convergence property of the algorithm is proved in this paper. To compared with the Tensor algorithms presented by R. B. Schnabel (seing [4],[5]), this method is more efficient for solving singular unconstrained optimization in computing amount and complication.     

A discrete Newton algorithm for minimizing a function of many variables

A Newton-like method is presented for minimizing a function ofn variables. It uses only function and gradient values and is a variant of the discrete Newton algorithm. This variant requires fewer operations than the standard method whenn > 39, and storage is proportional ton rather thann ².