Bounded lower subdifferentiability optimization techniques : applications

In this article we develop a global optimization algorithm for quasiconvex programming where the objective function is a Lipschitz function which may have "flat parts". We adapt the Extended Cutting Angle method to quasiconvex functions, which reduces significantly the number of iterations and objective function evaluations, and consequently the total computing time. Applications of such an algorithm to mathematical programming problems inwhich the objective function is derived from economic systems and location problems are described. Computational results are presented.

Global and threshold-free transcriptional regulatory networks reconstruction through integrating ChIP-Chip and expression data

Inferring transcriptional regulatory networks from high-throughput biological data is a major challenge to bioinformatics today. To address this challenge, we developed TReNGO (Transcriptional Regulatory Networks reconstruction based on Global Optimization), a global and threshold-free algorithm with simulated annealing for inferring regulatory networks by the integration of ChIP-chip and expression data. Superior to existing methods, TReNGO was expected to find the optimal structure of transcriptional regulatory networks without any arbitrary thresholds or predetermined number of transcriptional modules (TMs). TReNGO was applied to both synthetic data and real yeast data in the rapamycin response. In these applications, we demonstrated an improved functional coherence of TMs and TF (transcription factor)- target predictions by TReNGO when compared to GRAM, COGRIM or to analyzing ChIP-chip data alone. We also demonstrated the ability of TReNGO to discover unexpected biological processes that TFs may be involved in and to also identify interesting novel combinations of TFs.

Derivative-free optimization and neural networks for robust regression

Large outliers break down linear and nonlinear regression models. Robust regression methods allow one to filter out the outliers when building a model. By replacing the traditional least squares criterion with the least trimmed squares (LTS) criterion, in which half of data is treated as potential outliers, one can fit accurate regression models to strongly contaminated data. High-breakdown methods have become very well established in linear regression, but have started being applied for non-linear regression only recently. In this work, we examine the problem of fitting artificial neural networks (ANNs) to contaminated data using LTS criterion. We introduce a penalized LTS criterion which prevents unnecessary removal of valid data. Training of ANNs leads to a challenging non-smooth global optimization problem. We compare the efficiency of several derivative-free optimization methods in solving it, and show that our approach identifies the outliers correctly when ANNs are used for nonlinear regression.

Predicting molecular structures: an application of the cutting angle method

The ability to predict molecular geometries has important applications in chemistry. Specific examples include the areas of protein space structure elucidation, the investigation of host–guest interactions, the understanding of properties of superconductors and of zeolites. This prediction of molecular geometries often depends on finding the global minimum or maximum of a function such as the potential energy. In this paper, we consider several well-known molecular conformation problems to which we apply a new method of deterministic global optimization called the cutting angle method. We demonstrate that this method is competitive with other global optimization techniques for these molecular conformation problems.

Geometry and combinatorics of the cutting angle method

Lower approximation of Lipschitz functions plays an important role in deterministic global optimization. This article examines in detail the lower piecewise linear approximation which arises in the cutting angle method. All its local minima can be explicitly enumerated, and a special data structure was designed to process them very efficiently, improving previous results by several orders of magnitude. Further, some geometrical properties of the lower approximation have been studied, and regions on which this function is linear have been identified explicitly. Connection to a special distance function and Voronoi diagrams was established. An application of these results is a black-box multivariate random number generator, based on acceptance-rejection approach.

Knowledge extraction from a mixed transfer function artificial neural network

One of the main problems with Artificial Neural Networks (ANNs) is that their results are not intuitively clear. For example, commonly used hidden neurons with sigmoid activation function can approximate any continuous function, including linear functions, but the coefficients (weights) of this approximation are rather meaningless. To address this problem, current paper presents a novel kind of a neural network that uses transfer functions of various complexities in contrast to mono-transfer functions used in sigmoid and hyperbolic tangent networks. The presence of transfer functions of various complexities in a Mixed Transfer Functions Artificial Neural Network (MTFANN) allow easy conversion of the full model into user-friendly equation format (similar to that of linear regression) without any pruning or simplification of the model. At the same time, MTFANN maintains similar generalization ability to mono-transfer function networks in a global optimization context. The performance and knowledge extraction of MTFANN were evaluated on a realistic simulation of the Puma 560 robot arm and compared to sigmoid, hyperbolic tangent, linear and sinusoidal networks.

Reconstruction of the refractive index profile of planar waveguides using ray tracing analysis

We propose a method for refractive index profiling based on measuring coordinates and angles of laser beams passing across the waveguide layer. Calculations are performed by solving an integral equation using new global optimization methods.

Knowledge extraction from a mixed transfer function artificial neural network

One of the big problems with Artificial Neural Networks (ANN) is that their results are not intuitively clear. For example, if we use the traditional neurons, with a sigmoid activation function, we can approximate any function, including linear functions, but the coefficients (weights) in this approximation will be rather meaningless. To resolve this problem, this paper presents a novel kind of ANN with different transfer functions mixed together. The aim of such a network is to i) obtain a better generalization than current networks ii) to obtain knowledge from the networks without a sophisticated knowledge extraction algorithm iii) to increase the understanding and acceptance of ANNs. Transfer Complexity Ratio is defined to make a sense of the weights associated with the network. The paper begins with a review of the knowledge extraction from ANNs and then presents a Mixed Transfer Function Artificial Neural Network (MTFANN). A MTFANN contains different transfer functions mixed together rather than mono-transfer functions. This mixed presence has helped to obtain high level knowledge and similar generalization comparatively to monotransfer function nets in a global optimization context.

Review of applications of the Cutting Angle methods

The theory of abstract convexity provides us with the necessary tools for building accurate one-sided approximations of functions. Cutting angle methods have recently emerged as a tool for global optimization of families of abstract convex functions. Their applicability have been subsequently extended to other problems, such as scattered data interpolation. This paper reviews three different applications of cutting angle methods, namely global optimization, generation of nonuniform random variates and multivatiate interpolation.

Introduction to evolutionary computing in system design

In this chapter, an introduction on the use of evolutionary computing techniques, which are considered as global optimization and search techniques inspired from biological evolutions, in the domain of system design is presented. A variety of evolutionary computing techniques are first explained, and the motivations of using evolutionary computing techniques in tackling system design tasks are then discussed. In addition, a number of successful applications of evolutionary computing to system design tasks are described.

Characterizing compactness of geometrical clusters using fuzzy measures

Certain tasks in image processing require the preservation of fine image details, while applying a broad operation to the image, such as image reduction, filtering, or smoothing. In such cases, the objects of interest are typically represented by small, spatially cohesive clusters of pixels which are to be preserved or removed, depending on the requirements. When images are corrupted by the noise or contain intensity variations generated by imaging sensors, identification of these clusters within the intensity space is problematic as they are corrupted by outliers. This paper presents a novel approach to accounting for spatial organization of the pixels and to measuring the compactness of pixel clusters based on the construction of fuzzy measures with specific properties: monotonicity with respect to the cluster size; invariance with respect to translation, reflection, and rotation; and discrimination between pixel sets of fixed cardinality with different spatial arrangements. We present construction methods based on Sugeno-type fuzzy measures, minimum spanning trees, and fuzzy measure decomposition. We demonstrate their application to generating fuzzy measures on real and artificial images.

CCTV scene perspective distortion estimation from low-level motion features

Our aim is to estimate the perspective-effected geometric distortion of a scene from a video feed. In contrast to most related previous work, in this task we are constrained to use low-level spatiotemporally local motion features only. This particular challenge arises in many semiautomatic surveillance systems that alert a human operator to potential abnormalities in the scene. Low-level spatiotemporally local motion features are sparse (and thus require comparatively little storage space) and sufficiently powerful in the context of video abnormality detection to reduce the need for human intervention by more than 100-fold. This paper introduces three significant contributions. First, we describe a dense algorithm for perspective estimation, which uses motion features to estimate the perspective distortion at each image locus and then polls all such local estimates to arrive at the globally best estimate. Second, we also present an alternative coarse algorithm that subdivides the image frame into blocks and uses motion features to derive block-specific motion characteristics and constrain the relationships between these characteristics, with the perspective estimate emerging as a result of a global optimization scheme. Third, we report the results of an evaluation using nine large sets acquired using existing closed-circuit television cameras, not installed specifically for the purposes of this paper. Our findings demonstrate that both proposed methods are successful, their accuracy matching that of human labeling using complete visual data (by the constraints of the setup unavailable to our algorithms).

Towards optimization of a real-world robotic-sensor system of systems

The problem of threat detection in an unstructured environment is considered. Three systems, comprising of robots and sensors, are proposed to form a system of systems (SoS) to find a solution to the problem. System interactions are defined to provide a framework for formulation as an SoS optimization problem. Different cost and objective functions are introduced for optimization of local criteria. Using different weights, a linear combination of the local cost and objective functions is obtained to propose a global objective function. An algorithm is suggested to find an optimum value for the global objective function leading towards optimization of the SoS.

A GA-PSO layered encoding evolutionary approach to 0/1 knapsack optimization

This paper presents a layered encoding cascade evolutionary approach to solve a 0/1 knapsack optimization problem. A layered encoding structure is proposed and developed based on the schema theorem and the concepts of cascade correlation and multi-population evolutionary algorithms. Genetic algorithm (GA) and particle swarm optimization (PSO) are combined with the proposed layered encoding structure to form a generic optimization model denoted as LGAPSO. In order to enhance the finding of both local and global optimum in the evolutionary search, the model adopts hill climbing evaluation criteria, feature of strength Pareto evolutionary approach (SPEA) as well as nondominated spread lengthen criteria. Four different sizes benchmark knapsack problems are studied using the proposed LGAPSO model. The performance of LGAPSO is compared to that of the ordinary multi-objective optimizers such as VEGA, NSGA, NPGA and SPEA. The proposed LGAPSO model is shown to be efficient in improving the search of knapsack’s optimum, capable of gaining better Pareto trade-off front.