CONORBIT: constrained optimization by radial basis function interpolation in trust regions†

This paper presents CONORBIT (CONstrained Optimization by Radial Basis function Interpolation in Trust regions), a derivative-free algorithm for constrained black-box optimization where the objective and constraint functions are computationally expensive. CONORBIT employs a trust-region framework that uses interpolating radial basis function (RBF) models for the objective and constraint functions, and is an extension of the ORBIT algorithm [S.M. Wild, R.G. Regis and C.A. Shoemaker, ORBIT: optimization by radial basis function interpolation in trust-regions, SIAM J. Sci. Comput. 30 (2008), pp. 3197–3219]. It uses a small margin for the RBF constraint models to facilitate the generation of feasible iterates, and extensive numerical tests confirm that such a margin is helpful in improving performance. CONORBIT is compared with other algorithms on 27 test problems, a chemical process optimization problem, and an automotive application. Numerical results show that CONORBIT performs better than COBYLA (Powell 1994), a sequential penalty derivative-free method, an augmented Lagrangian method, a direct search method, and another RBF-based algorithm on the test problems and on the automotive application.     

Kernelized LARS–LASSO for constructing radial basis function neural networks

Model structure selection is of crucial importance in radial basis function (RBF) neural networks. Existing model structure selection algorithms are essentially forward selection or backward elimination methods that may lead to sub-optimal models. This paper proposes an alternative selection procedure based on the kernelized least angle regression (LARS)–least absolute shrinkage and selection operator (LASSO) method. By formulating the RBF neural network as a linear-in-the-parameters model, we derive a l ₁-constrained objective function for training the network. The proposed algorithm makes it possible to dynamically drop a previously selected regressor term that is insignificant. Furthermore, inspired by the idea of LARS, the computing of output weights in our algorithm is greatly simplified. Since our proposed algorithm can simultaneously conduct model structure selection and parameter optimization, a network with better generalization performance is built. Computational experiments with artificial and real world data confirm the efficacy of the proposed algorithm.     

A parallel O(log n) algorithm for the drawing of algebraic curves in an n × n square

A parallel O(log n) algorithm for the drawing of algebraic curves in the digital plane is described. The algorithm contains a systolic subroutine and is implemented in a parallel computer structure called pyramid cellular automaton (PCA). The constructibility of conics and especially of circles (Sakoda's (1981) circle problem) in O(log n) time follows as a special case.     

A stable Gaussian radial basis function method for solving nonlinear unsteady convection–diffusion–reaction equations

We investigate a novel method for the numerical solution of two-dimensional time-dependent convection–diffusion–reaction equations with nonhomogeneous boundary conditions. We first approximate the equation in space by a stable Gaussian radial basis function (RBF) method and obtain a matrix system of ODEs. The advantage of our method is that, by avoiding Kronecker products, this system can be solved using one of the standard methods for ODEs. For the linear case, we show that the matrix system of ODEs becomes a Sylvester-type equation, and for the nonlinear case we solve it using predictor–corrector schemes such as Adams–Bashforth and implicit–explicit (IMEX) methods. This work is based on the idea proposed in our previous paper (2016), in which we enhanced the expansion approach based on Hermite polynomials for evaluating Gaussian radial basis function interpolants. In the present paper the eigenfunction expansions are rebuilt based on Chebyshev polynomials which are more suitable in numerical computations. The accuracy, robustness and computational efficiency of the method are presented by numerically solving several problems.     

Multivariate quasi-interpolation in L p (ℝ d ) with radial basis functions for scattered data

In this paper, quasi-interpolation for scattered data was studied. On the basis of generalized quasi-interpolation for scattered data proposed in [Z.M. Wu and J.P. Liu, Generalized strang-fix condition for scattered data quasi-interpolation, Adv. Comput. Math. 23 (2005), pp. 201–214.], we have developed a new method to construct the kernel in the scheme by the linear combination of the scales, instead of the gridded shifts of the radial basis function. Compared with the kernel proposed in [Z.M. Wu and J.P. Liu, Generalized strang-fix condition for scattered data quasi-interpolation, Adv. Comput. Math. 23 (2005), pp. 201–214.], the new kernel, which is still a radial function, possesses the feature of polynomial reproducing property. This opens a possibility for us to propose a different technique by obtaining a higher approximation order of the convergence.     

Numerical investigation based on radial basis function–finite-difference (RBF–FD) method for solving the Stokes–Darcy equations

A meshless method is presented to numerically study an interface problem between a flow in a porous medium governed by Darcy equations and a fluid flow, governed by Stokes equations. In fact, the domain of the problem has two parts, one governed by Stokes equations and the another governed by Darcy law. Governing equations on these two parts are mutually coupled by interface conditions. The approximation solution is based on local radial basis function–finite-difference (RBF–FD) which is carried out within a small influence domain instead of a global one. By this strategy, the final linear system is more sparse and well posed than the global one. Several numerical results are provided to illustrate the good performance of the proposed scheme.

     

A fast learning algorithm of neural network with tunable activation function

This paper presents a modified structure of a neural network with tunable activation function and provides a new learning algorithm for the neural network training. Simulation results of XOR problem, Feigenbaum function, and Henon map show that the new algorithm has better performance than BP (back propagation) algorithm in terms of shorter convergence time and higher convergence accuracy. Further modifications of the structure of the neural network with the faster learning algorithm demonstrate simpler structure with even faster convergence speed and better convergence accuracy.     

A note on the potential function algorithm for pattern classification†

A system design engineer often resorts to redundancies while maximizing the probability of success of a system designed to perform a certain job over a period, This will have to be done within the resources available. The problem of maximizing system reliability, subject to some linear constraints such as cost, weight or volume, is considered in this paper- The usual problem is transformed to a suitable form and the least square concept is used to develop a solution technique. This type of approach is found to be very simple and faster than earlier methods although the solution is an approximate one.     

StitchingPHm—A new algorithm for panoramic images

In this paper it is presented a new algorithm for the construction of panoramic images (including 360 panoramas), which has as main characteristic to avoid the distortion that occurs by joining of several successive images in a sequence. We used the SIFT and RANSAC algorithms to find overlap areas between pairs of images, as well as a Blend algorithm for smoothing the joints. As the proposed algorithm doesn’t cause distortions, the subsequent correction is not necessary, contributing to a better performance. The results of experiments using commercial software and also the proposed algorithm were compared through a visual analysis. In addition, a quantitative analysis was done using numeric measures calculated on a panoramic image, generated from an image sequence of a region mapped and georeferenced by Google Earth.     

Decomposition based hybrid VNS–TS algorithm for distributed parallel factories scheduling with virtual corporation

The main purpose of this paper is to develop a decomposition based hybrid variable neighborhood search/tabu search (DVT) algorithm for multi-factory production network scheduling problem where a number of different individual factories collaborate despite their different objectives. It is assumed some of the network's factories are interested in total processing cost minimization whereas the remaining factories are interested in the production profits maximization. It is also assumed that jobs can migrate from their original factory to other factories but a transportation time is incurred. Our proposed algorithm comprises of a tabu search and a variable neighborhood search with several local search algorithms. In this hybridization, to improve the search ability of the algorithm, we make use of guiding principles with ordering of neighborhood structures by mixed integer linear programming relaxation. In the proposed algorithm, the parallel search strategy is designed for a scalar bi-objective. Multiple objectives are combined with L₁-metric technique then each sub-search procedure evolves separately until a good approximation of the Pareto-front is obtained. The non-dominated sets obtained from our algorithm and original heuristic (algorithm without ordering concept) are compared using three different indices. Furthermore, the problem is modeled as a mixed integer linear programming and solved by improved ϵ-constraint approach (IEA) with CPLEX solver. The results of comparisons between IEA and DVT algorithm showed the proposed algorithm yielded most of the solutions in the net non-dominated front.     

PAPS — A testbed for performance prediction of parallel applications

The PAPS (Performance Analysis of Parallel Systems) toolset is a testbed for the model based performance prediction of message passing parallel applications executed on private memory multiprocessor computer systems. PAPS allows to describe the execution behavior of the computer hardware and operating system software resources up to a very detailed level. This enables very accurate performance prediction of parallel applications even in the case of substantial performance degradation due to contention for shared resources. In this paper the fundamental design principles and implementation methodologies for the development of the PAPS toolset are presented and the PAPS parallel system specification formalisms are described. A simplified performance study of a parallel Gaussian elimination application on the nCUBE 2 multiprocessor system is used to demonstrate the usage of the tool.     

A problem evolution algorithm with linear programming for the dynamic facility layout problem—A general layout formulation

Facility layout problems (FLPs) are quite common and important in many industries. This paper presents a mixed integer linear programming (MILP) model for the dynamic facility layout problem, which is a generalization of several special cases of FLPs studied in recent years. A new evolutionary meta-heuristic framework, named as the problem evolution algorithm (PEA), is developed as a general solution approach for FLPs. Computational experiments show that the PEA combined with the linear programming (LP), called PEA-LP in short, performs well in various types of FLPs. In addition, a new polyhedral inner-approximation method is proposed based on secant lines for the linearization of the non-linear constraint for department area requirements. This new method guarantees that the actual department area is always greater than or equal to the required area within a given maximum deviation error. Furthermore, two new symmetry-breaking constraints which help to improve the computational efficiency of the MILP model are also introduced. Computational experiments on several well-known problem instances from the literature are carried out to test the DFLP-FZ and the PEA-LP with promising results.     

A new polynomial-time algorithm for the maximum weighted (χ(G) — 1)-coloring problem in comparability graphs

For a weighted graph G = (V, E), the maximum weightedk-coloring problem is to color a set of vertices of maximum weight usingk colors. In this paper we are interested in solving this problem in comparability graphs. For these graphs, as shown by Cameron, the problem can be translated into a dual transportation problem. Let (G) denote the chromatic number of a comparability graphG. We prove that whenk is equal to (G) — 1, the problem can be solved more efficiently by finding a maximum weighted stable set in a bipartite graph. Maximum matching algorithms can be used in the unweighted case.This work was supported by an NSERC International Fellowship to the University of Montréal, and by NSERC #OGP0105384.     

A new algorithm for the extraction of the surface waves for the Green''''s function in layered dielectrics

There exist the complicated waveguide modes as well as the surface waves in the electromagnetic field induced by a horizontal electric dipole in layered lossless dielectrics between two ground planes. In spectral domain, all these modes can be characterized by the rational parts with the real poles of the vector and scalar potentials. The accurate extraction of these modes plays an important role in the evaluation of the Green's function in spatial domain. In this paper, a new algorithm based on rational approximation is presented, which can accurately extract all the real poles and the residues of each pole simultaneously. Thus, we can get all the surface wave modes and waveguide modes, which is of great help to the calculation of the spatial domain Green's function. The numerical results demonstrated the accuracy and efficiency of the proposed method.     

A water-flow algorithm for flexible flow shop scheduling with intermediate buffers

We investigate the flexible flow shop scheduling problem with limited or unlimited intermediate buffers. A common objective of the problem is to find a production schedule that minimizes the completion time of jobs. Other objectives that we also consider are minimizing the total weighted flow time of jobs and minimizing the total weighted tardiness time of jobs. We propose a water-flow algorithm to solve this scheduling problem. The algorithm is inspired by the hydrological cycle in meteorology and the erosion phenomenon in nature. In the algorithm, we combine the amount of precipitation and its falling force to form a flexible erosion capability. This helps the erosion process of the algorithm to focus on exploiting promising regions strongly. To initiate the algorithm, we use a constructive procedure to obtain a seed permutation. We also use an improvement procedure for constructing a complete schedule from a permutation that represents the sequence of jobs in the first stage of the scheduling problem. To evaluate the proposed algorithm, we use benchmark instances taken from the literature and randomly generated instances of the scheduling problem. The computational results demonstrate the efficacy of the algorithm. We have also obtained several improved solutions for the benchmark instances using the proposed algorithm. We further illustrate the algorithm’s capability for solving problems in practical applications by applying it to a maltose syrup production problem.     

A polynomial-time algorithm for a flow-shop batching problem with equal-length operations

A flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set-up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B _i is the sum of processing times of operations in B _i and the earliest start of B _i on a machine is the finishing time of B _i on the previous machine plus the set-up time s. Cheng et al. (Naval Research Logistics 47:128–144, 2000) provided an O(n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161:285–291, 2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10:353–364, 2007) improved the pseudopolynomial complexity to \(O(\sqrt{n})\). In this paper, we provide a polynomial-time algorithm of time complexity O(log?³ n).     

A color-based face tracking algorithm for enhancing interaction with mobile devices

A color-based face tracking algorithm is proposed to be used as a human-computer interaction tool on mobile devices. The solution provides a natural means of interaction enabling a motion parallax effect in applications. The algorithm considers the characteristics of mobile use-constrained computational resources and varying environmental conditions. The solution is based on color comparisons and works on images gathered from the front camera of a device. In addition to color comparisons, the coherency of the facial pixels is considered in the algorithm. Several applications are also demonstrated in this work, which use the face position to determine the viewpoint in a virtual scene, or for browsing large images. The accuracy of the system is tested under different environmental conditions such as lighting and background, and the performance of the system is measured in different types of mobile devices. According to these measurements the system allows for accurate (7% RMS error) face tracking in real time (20–100 fps).     

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

A new parallel implementation of Strassen’s matrix multiplication algorithm is proposed for massively parallel supercomputers with 2D, all-port torus interconnection networks. The proposed algorithm employs a special conflict-free routing pattern for better scalability and is able to yield a performance rate very close to the theoretical bound for many practical network and matrix sizes. It effectively scales up to very large networks typically containing hundreds-of-thousands processors where petaflop or exaflop processing rates are sought.