Supervised box clustering

In this work we address a technique for effectively clustering points in specific convex sets, called homogeneous boxes, having sides aligned with the coordinate axes (isothetic condition). The proposed clustering approach is based on homogeneity conditions, not according to some distance measure, and, even if it was originally developed in the context of the logical analysis of data, it is now placed inside the framework of Supervised clustering. First, we introduce the basic concepts in box geometry; then, we consider a generalized clustering algorithm based on a class of graphs, called incompatibility graphs. For supervised classification problems, we consider classifiers based on box sets, and compare the overall performances to the accuracy levels of competing methods for a wide range of real data sets. The results show that the proposed method performs comparably with other supervised learning methods in terms of accuracy.     

A Nonsmooth Global Optimization Technique Using Slopes: The One-Dimensional Case

In this paper we introduce a pruning technique based on slopes in the context of interval branch-and-bound methods for nonsmooth global optimization. We develop the theory for a slope pruning step which can be utilized as an accelerating device similar to the monotonicity test frequently used in interval methods for smooth problems. This pruning step offers the possibility to cut away a large part of the box currently investigated by the optimization algorithm. We underline the new technique's efficiency by comparing two variants of a global optimization model algorithm: one equipped with the monotonicity test and one equipped with the pruning step. For this reason, we compared the required CPU time, the number of function and derivative or slope evaluations, and the necessary storage space when solving several smooth global optimization problems with the two variants. The paper concludes on the test results for several nonsmooth examples.     

Certificates of infeasibility via nonsmooth optimization

An important aspect in the solution process of constraint satisfaction problems is to identify exclusion boxes which are boxes that do not contain feasible points. This paper presents a certificate of infeasibility for finding such boxes by solving a linearly constrained nonsmooth optimization problem. Furthermore, the constructed certificate can be used to enlarge an exclusion box by solving a nonlinearly constrained nonsmooth optimization problem.     

Optimal Multisections in Interval Branch-and-Bound Methods of Global Optimization

In this paper we define multisections of intervals that yield sharp lower bounds in branch-and-bound type methods for interval global optimization. A so called 'generalized kite', defined for differentiable univariate functions, is built simultaneously with linear boundary forms and suitably chosen centered forms. Proofs for existence and uniqueness of optimal cuts are given. The method described may be used either as an accelerating device or in a global optimization algorithm with an efficient pruning effect. A more general principle for decomposition of boxes is suggested.     

Analysis of a multi-category classifier

The use of boxes for pattern classification has been widespread and is a fairly natural way in which to partition data into different classes or categories. In this paper we consider multi-category classifiers which are based on unions of boxes. The classification method studied may be described as follows: find boxes such that all points in the region enclosed by each box are assumed to belong to the same category, and then classify remaining points by considering their distances to these boxes, assigning to a point the category of the nearest box. This extends the simple method of classifying by unions of boxes by incorporating a natural way (based on proximity) of classifying points outside the boxes. We analyze the generalization accuracy of such classifiers and we obtain generalization error bounds that depend on a measure of how definitive is the classification of training points.     

Particle swarm optimization with age-group topology for multimodal functions and data clustering

This paper proposes particle swarm optimization with age-group topology (PSOAG), a novel age-based particle swarm optimization (PSO). In this work, we present a new concept of age to measure the search ability of each particle in local area. To keep population diversity during searching, we separate particles to different age-groups by their age and particles in each age-group can only select the ones in younger groups or their own groups as their neighbourhoods. To allow search escape from local optima, the aging particles are regularly replaced by new and randomly generated ones. In addition, we design an age-group based parameter setting method, where particles in different age-groups have different parameters, to accelerate convergence. This algorithm is applied to nonlinear function optimization and data clustering problems for performance evaluation. In comparison against several PSO variants and other EAs, we find that the proposed algorithm provides significantly better performances on both the function optimization problems and the data clustering tasks.     

Search Heuristics for Box Decomposition Methods

In this paper we study search heuristics for box decomposition methods that solve problems such as global optimization, minimax optimization, or quantified constraint solving. For this we unify these methods under a branch-and-bound framework, and develop a model that is more convenient for studying heuristics for such algorithms than the traditional models from Artificial Intelligence. We use the result to prove various theorems about heuristics and apply the outcome to the box decomposition methods under consideration. We support the findings with timings for the method of quantified constraint solving developed by the author.     

An incremental clustering algorithm based on hyperbolic smoothing

Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.     

Scatter tabu search for multiobjective clustering problems

We propose a hybrid heuristic procedure based on scatter search and tabu search for the problem of clustering objects to optimize multiple criteria. Our goal is to search for good approximations of the efficient frontier for this class of problems and provide a means for improving decision making in multiple application areas. Our procedure can be viewed as an extension of SSPMO (a scatter search application to nonlinear multiobjective optimization) to which we add new elements and strategies specially suited for combinatorial optimization problems. Clustering problems have been the subject of numerous studies; however, most of the work has focused on single-objective problems. Clustering using multiple criteria and/or multiple data sources has received limited attention in the operational research literature. Our scatter tabu search implementation is general and tackles several problems classes within this area of combinatorial data analysis. We conduct extensive experimentation to show that our method is capable of delivering good approximations of the efficient frontier for improved analysis and decision making.     

一种连续的谱聚类优化模型

聚类与图的划分问题在大数据分析中有着重要的应用.这类问题一般被描述为组合优化问题,因此较难快速求解.本文设计了一种新的连续优化模型,并提出了一种块坐标下降算法,数值实验显示我们的新方法在求解聚类与图的划分问题上很有潜力.我们还更进一步分析了我们的连续优化模型和组合优化模型的关系.     

Fast construction of constant bound functions for sparse polynomials

A new method for the representation and computation of Bernstein coefficients of multivariate polynomials is presented. It is known that the coefficients of the Bernstein expansion of a given polynomial over a specified box of interest tightly bound the range of the polynomial over the box. The traditional approach requires that all Bernstein coefficients are computed, and their number is often very large for polynomials with moderately-many variables. The new technique detailed represents the coefficients implicitly and uses lazy evaluation so as to render the approach practical for many types of non-trivial sparse polynomials typically encountered in global optimization problems; the computational complexity becomes nearly linear with respect to the number of terms in the polynomial, instead of exponential with respect to the number of variables. These range-enclosing coefficients can be employed in a branch-and-bound framework for solving constrained global optimization problems involving polynomial functions, either as constant bounds used for box selection, or to construct affine underestimating bound functions. If such functions are used to construct relaxations for a global optimization problem, then sub-problems over boxes can be reduced to linear programming problems, which are easier to solve. Some numerical examples are presented and the software used is briefly introduced.     

一类广义Bent型S-Box的构造

S-box是密码理论与实践中十分重要的一种装置 ,它的密码性能由其分量函数所决定 .于是 ,选择适当的分量函数来构造 S-box就成了一个重要的研究课题 .在一定意义上 ,Bent函数是最优良的密码函数 .本文通过函数序列半群和置换群来构造其任何非零线性组合为 Bent函数与线性函数之和的函数组 ,从而可由 Bent函数构造出具有高度非线性度和其他良好性状的 S-box     

Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm

We propose an algorithm for constrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed Bernstein branch and prune algorithm is based on the Bernstein polynomial approach. We introduce several new features in this proposed algorithm to make the algorithm more efficient. We first present the Bernstein box consistency and Bernstein hull consistency algorithms to prune the search regions. We then give Bernstein contraction algorithm to avoid the computation of Bernstein coefficients after the pruning operation. We also include a new Bernstein cut-off test based on the vertex property of the Bernstein coefficients. The performance of the proposed algorithm is numerically tested on 13 benchmark problems. The results of the tests show the proposed algorithm to be overall considerably superior to existing method in terms of the chosen performance metrics.     

Bucket elimination for multiobjective optimization problems

Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.     

An improved clustering method based on biological visual models

A clustering methodology based on biological visual models that imitates how humans visually cluster data by spatially associating patterns has been recently proposed. The method is based on Cellular Neural Networks and some resolution adjustments. The Cellular Neural Network rebuilds low-density areas while different resolutions find the best clustering option. The algorithm has demonstrated good performance compared to other clustering techniques. However, its main drawbacks correspond to its inability to operate with more than two-dimensional data sets and the computational time required for the resolution adjustment mechanism. This paper proposes a new version of this clustering methodology to solve such flaws. In the new approach, a pre-processing stage is incorporated featuring a Self-Organization Map that maps complex high-dimensional relations into a reduced lattice yet preserving the topological organization of the initial data set. This reduced representation is employed as the two-dimensional data set for further processing. In the new version, the resolution adjustment process is also accelerated through the use of an optimization method that combines the Hill-Climbing and the Random Search techniques. By incorporating such mechanisms rather than evaluating all possible resolutions, the optimization strategy finds the best resolution for a clustering problem by using a limited number of iterations. The proposed approach has been evaluated, considering several two-dimensional and high-dimensional datasets. Experimental evidence exhibits that the proposed algorithm performs the clustering task over complex problems delivering a 46% faster on average than the original method. The approach is also compared to other popular clustering techniques reported in the literature. Computational experiments demonstrate competitive results in comparison to other algorithms in terms of accuracy and robustness.     

A new parallel method for verified global optimization

We present a new parallel method for verified global optimization, using challenge leadership for the dynamic load balancing. The new approach combines advantages of two previous models: the centralized mediator model (see [1]) and the processor farm (see [2]). It has the following properties: centralization of the process; reduction of the number of box exchanges, communications used to send boxes from one processor to another; handling of the box that most probably contains the global minimizer. Numerical results show the efficiency of this method.     

箱式约束变分不等式的一类新光滑gap函数

针对箱式约束变分不等式问题,利用一类积分型全局最优性条件,提出了一个新光滑gap函数．该光滑gap函数形式简单且具有较好的性质．利用该gap函数,箱式约束变分不等式可转化为等价光滑优化问题进行求解．进一步地,讨论了可保证等价光滑优化问题的任意聚点为箱式约束变分不等式问题解的条件．以一个简单的摩擦接触问题为例阐释了该方法的应用．最后,利用标准的变分不等式考题验证了方法的有效性．     

Testing the topographical global initialization strategy in the framework of an unconstrained optimization method

In general, classical iterative algorithms for optimization, such as Newton-type methods, perform only local search around a given starting point. Such feature is an impediment to the direct use of these methods to global optimization problems, when good starting points are not available. To overcome this problem, in this work we equipped a Newton-type method with the topographical global initialization strategy, which was employed together with a new formula for its key parameter. The used local search algorithm is a quasi-Newton method with backtracking. In this approach, users provide initial sets, instead of starting points. Then, using points sampled in such initial sets (merely boxes in \({\mathbb {R}}^{n}\)), the topographical method selects appropriate initial guesses for global optimization tasks. Computational experiments were performed using 33 test problems available in literature. Comparisons against three specialized methods (DIRECT, MCS and GLODS) have shown that the present methodology is a powerful tool for unconstrained global optimization.     

A second-order pruning step for verified global optimization

We consider pruning steps used in a branch-and-bound algorithm for verified global optimization. A first-order pruning step was given by Ratz using automatic computation of a first-order slope tuple (Ratz, Automatic Slope Computation and its Application in Nonsmooth Global Optimization. Shaker Verlag, Aachen, 1998; J. Global Optim. 14: 365–393, 1999). In this paper, we introduce a second-order pruning step which is based on automatic computation of a second-order slope tuple. We add this second-order pruning step to the algorithm of Ratz. Furthermore, we compare the new algorithm with the algorithm of Ratz by considering some test problems for verified global optimization on a floating-point computer. This paper contains some results from the author’s dissertation [29].     

Freight transportation in railway networks with automated terminals: A mathematical model and MIP heuristic approaches

In this paper we propose a planning procedure for serving freight transportation requests in a railway network with fast transfer equipment at terminals. We consider a transportation system where different customers make their requests (orders) for moving boxes, i.e., either containers or swap bodies, between different origins and destinations, with specific requirements on delivery times. The decisions to be taken concern the route (and the corresponding sequence of trains) that each box follows in the network and the assignment of boxes to train wagons, taking into account that boxes can change more than one train and that train timetables are fixed.The planning procedure includes a pre-analysis step to determine all the possible sequences of trains for serving each order, followed by the solution of a 0-1 linear programming problem to find the optimal assignment of each box to a train sequence and to a specific wagon for each train in the sequence. This latter is a generalized assignment problem which is NP-hard. Hence, in order to find good solutions in acceptable computation times, two MIP heuristic approaches are proposed and tested through an experimental analysis considering realistic problem instances.