Abstract This study focuses on exhaustive global optimization algorithms over a simplicial feasible set with simplicial partition sets. Bounds on the objective function value and its partial derivative are based on interval automatic differentiation over the interval hull of a simplex. A monotonicity test may be used to decide to either reject a simplicial partition set or to reduce its simplicial dimension to a relative border (at the boundary of the feasible set) facet (or face) by removing one (or more) vertices. A monotonicity test is more complicated for a simplicial sub-set than for a box, because its orientation does not coincide with the components of the gradient. However, one can focus on directional derivatives (DD). In a previous study, we focused on either basic directions, such as centroid to vertex or vertex to vertex directions, or finding the best directional derivative by solving an LP or MIP. The research question of this paper refers to using local search (LS) based sampling of directions from vertex to facet. Results show that most of the monotonic DD found by LP are also found by LS, but with much less computational cost. Notice that finding a monotone direction does not require to find the direction in which a derivative bound is the steepest.

Abstract We present a novel relaxation for general nonconvex sparse MINLP problems, called overlapping convex hull relaxation (CHR). It is defined by replacing all nonlinear constraint sets by their convex hulls. If the convex hulls are disjunctive, e.g. if the MINLP is block-separable, the CHR is equivalent to the convex hull relaxation obtained by (standard) column generation (CG). The CHR can be used for computing an initial lower bound in the root node of a branch-and-bound algorithm, or for computing a start vector for a local-search-based MINLP heuristic. We describe a dynamic block and column generation (DBCG) MINLP algorithm to generate the CHR by dynamically adding aggregated blocks. The idea of adding aggregated blocks in the CHR is similar to the well-known cutting plane approach. Numerical experiments on nonconvex MINLP instances show that the duality gap can be significantly reduced with the results of CHRs. DBCG is implemented as part of the CG-MINLP framework Decogo, see https://decogo.readthedocs.io/en/latest/index.html .

Land-cover information is of paramount importance in a wide range of environmental and socioeconomic applications. Deep learning (DL) provides a large variety of potential models for extracting useful information from raw images. However, remote sensing image (RSI) classification remains a challenging goal due to the intrinsic features of the data, such as the high sample variability and lack of labeled data. This provides a challenge to the reliability of deep classifiers. In particular, convolution-based models are greatly affected by overfitting and vanishing gradient problems. To overcome these drawbacks, this letter presents a new attention-based architecture, including attention modular blocks. These blocks divide their input feature maps into several groups and split them along the channel dimension and then combine them to create an attention mask encoding global contextual information. The mask is applied to obtain a refined feature representation, strengthening those features that affect most significantly the classification and attenuating the rest. Our new method reduces significantly the number of trainable parameters. Our results, obtained using several widely used RSIs, demonstrate that the new method exhibits higher classification performance when compared to several state-of-the-art methods.

Abstract In engineering optimization with continuous variables, the use of Stochastic Global Optimization (SGO) algorithms is popular due to the easy availability of codes. All algorithms have a global and local search character, where the global behaviour tries to avoid getting trapped in local optima and the local behaviour intends to reach the lowest objective function values. As the algorithm parameter set includes a final convergence criterion, the algorithm might be running for a while around a reached minimum point. Our question deals with the local search behaviour after the algorithm reached the final stage. How fast do practical SGO algorithms actually converge to the minimum point? To investigate this question, we run implementations of well known SGO algorithms in a final local phase stage.

Despite its great potential in a wide range of human activities, hyperspectral remote sensing imaging (HSI) exhibits several challenges that prevent full exploitation of its data. In particular, land-cover classification based on HSI data suffers significant degradation due to problematic data variability. Convolutional Neural Networks (CNNs) ability to extract spectral-spatial features has enabled the development of powerful classifiers, which achieve not yet seen accuracy results. To enhance the feature extraction procedure, this paper presents a novel HSI-CNN model (DKDCNet) which combines adaptive deforming kernels (DK) and convolutions (DC) with the aim of pinpointing the effective receptive field (ERF) on the challenging input data. Experimental results on the University of Houston benchmark show that DKDCNet is able to obtain a more accurate classification than traditional strategies with similar computational cost for HSI classification. Source code: https://github.com/mhaut/DKDCNet.

Abstract Branch and Bound (B&B) algorithms in Global Optimization are used to perform an exhaustive search over the feasible area. One choice is to use simplicial partition sets. Obtaining sharp and cheap bounds of the objective function over a simplex is very important in the construction of efficient Global Optimization B&B algorithms. Although enclosing a simplex in a box implies an overestimation, boxes are more natural when dealing with individual coordinate bounds, and bounding ranges with Interval Arithmetic (IA) is computationally cheap. This paper introduces several linear relaxations using gradient information and Affine Arithmetic and experimentally studies their efficiency compared to traditional lower bounds obtained by natural and centered IA forms and their adaption to simplices. A Global Optimization B&B algorithm with monotonicity test over a simplex is used to compare their efficiency over a set of low dimensional test problems with instances that either have a box constrained search region or where the feasible set is a simplex. Numerical results show that it is possible to obtain tight lower bounds over simplicial subsets.

Abstract This paper presents a new two-phase method for solving convex mixed-integer nonlinear programming (MINLP) problems, called Decomposition-based Outer Approximation Algorithm (DECOA). In the first phase, a sequence of linear integer relaxed sub-problems (LP phase) is solved in order to rapidly generate a good linear relaxation of the original MINLP problem. In the second phase, the algorithm solves a sequence of mixed integer linear programming sub-problems (MIP phase). In both phases the outer approximation is improved iteratively by adding new supporting hyperplanes by solving many easier sub-problems in parallel. DECOA is implemented as a part of Decogo (Decomposition-based Global Optimizer), a parallel decomposition-based MINLP solver implemented in Python and Pyomo. Preliminary numerical results based on 70 convex MINLP instances up to 2700 variables show that due to the generated cuts in the LP phase, on average only 2–3 MIP problems have to be solved in the MIP phase.

Dynamic programming (DP) approaches, in particular value iteration, is often seen as a method to derive optimal policies in inventory management. The challenge in this approach is to deal with an increasing state space when handling realistic problems. As a large part of world food production is thrown out due to its perishable character, a motivation exists to have a good look at order policies in retail. Recently, investigation has been introduced to consider substitution of one product by another, when one is out of stock. Taking this tendency into account in a policy requires an increasing state space. Therefore, we investigate the potential of using GPU platforms in order to derive optimal policies when the number of products taken into account simultaneously is increasing. First results show the potential of the GPU approach to accelerate computation in value iteration for DP.

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.

Interval branch-and-bound (B&B) algorithms are powerful methods which look for guaranteed solutions of global optimisation problems. The computational effort needed to reach this aim, increases exponentially with the problem dimension in the worst case. For separable functions this effort is less, as lower dimensional sub-problems can be solved individually. The question is how to design specific methods for cases where the objective function can be considered separable, but common variables occur in the sub-problems. This paper is devoted to establish the bases of B&B algorithms for separable problems. New B&B rules are presented based on derived properties to compute bounds. A numerical illustration is elaborated with a test-bed of problems mostly generated by combining traditional box constrained global optimisation problems, to show the potential of using the derived theoretical basis.

We describe the minimum volume simplex enclosure problem (MVSEP), which is known to be a global optimization problem, and further investigate its multimodality. The problem is a basis for several (unmixing) methods that estimate so-called endmembers and fractional values in a linear mixing model. We describe one of the estimation methods based on MVSEP. We show numerically that using nonlinear optimization local search leads to the estimation results aimed at. This is done using examples, designing instances and comparing the outcomes with a maximum volume enclosing simplex approach which is used frequently in unmixing data.

Blending algorithms aim for solving the problem of determining the mixture of raw materials in order to obtain a cheap and feasible recipe with the smallest number of raw materials. An algorithm that solves this problem for two products, where available raw material is limited, has two phases. The first phase is a simplicial branch-and-bound algorithm which determines, for a given precision, a Pareto set of solutions of the bi-blending problem as well as a subspace of the initial space where better feasible solutions (with more precision) can be found. The second phase basically consists in an exhaustive reduction of the mentioned subspace by deleting simplicial subsets that do not contain solutions. This second phase is useful for future refinement of the solutions. Previous work only focused on the first phase neglecting the second phase due to computational burden. With this in mind, we study the parallelization of the different phases of the sequential bi-blending algorithm and focus on the most time consuming phase, analyzing the performance of several strategies.

Spectral unmixing is an important technique for hyperspectral data exploitation, in which a mixed spectral signature is decomposed into a collection of spectrally pure constituent spectra, called endmembers, and a set of correspondent fractions, or abundances, that indicate the proportion of each endmember present in the mixture. Over the last years, several algorithms have been developed for automatic or semiautomatic endmember extraction. Some available approaches assume that the input data set contains at least one pure spectral signature for each distinct material and further conduct a search for the most spectrally pure signatures in the high-dimensional space spanned by the hyperspectral data. Among these approaches, those aimed at maximizing the volume of the simplex that can be formed using available spectral signatures have found wide acceptance. However, the presence of spectrally pure constituents is unlikely in remotely sensed hyperspectral scenes due to spatial resolution, mixing phenomena, and other considerations. In order to address this issue, other available algorithms have been developed to generate virtual endmembers (not necessarily present among the input data samples) by finding the simplex with minimum volume that encloses all available observations. In this paper, we discuss maximum-volume versus minimum-volume enclosing solutions and further develop a novel algorithm in the latter category which incorporates the fractional abundance estimation as an internal step of the endmember searching process (i.e., it does not require an external method to produce endmember fractional abundances). The method is based on iteratively enclosing the observations in a lower dimensional space and removing observations that are most likely not to be enclosed by the simplex of the endmembers to be estimated. The performance of the algorithm is investigated and compared to that of other algorithms (with and without the pure pixel assumption) using synthetic and real hyperspectral data sets collected by a variety of hyperspectral imaging instruments.

The aim of this work is to study the Simplex Cover (SC) problem, which is to determine whether a given simplex is covered by spheres centered at its vertices. We show that the SC problem is equivalent to a global optimization problem. We investigate its characteristics.

Spectral unmixing is an important task for remotely sensed hyperspectral data exploitation. Linear spectral unmixing relies on two main steps: 1) identification of pure spectral constituents (endmembers), and 2) end member abundance estimation in mixed pixels. One of the main problems concerning the identification of spectral endmembers is the lack of pure spectral signatures in real hyperspectral data due to spatial resolution and mixture phenomena happening at different scales. In this paper, we present a new method for endmember estimation which does not assume the presence of pure pixels in the input data. The method minimizes the volume of an enclosing simplex in the reduced space while estimating the fractional abundance of vertices in simultaneous fashion, as opposed to other volume-based approaches such as N-FINDR which inflate the simplex of maximumvolume that can be formed using available image pixels. Our experimental results and comparisons to other endmember extraction algorithms indicate promising performance of the method in the task of extracting endmembers from real hyperspectral data. In our experiments, we use laboratory-simulated forest scenes with known endmembers and fractional abundances due to their acquisition in a controlled environment using a real hyperspectral imaging instrument.