Parallel bundle-based decomposition for large-scale structured mathematical programming problems

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.     

Homogeneous Self-dual Algorithms for Stochastic Semidefinite Programming

Ariyawansa and Zhu have proposed a new class of optimization problems termed stochastic semidefinite programs to handle data uncertainty in applications leading to (deterministic) semidefinite programs. For stochastic semidefinite programs with finite event space, they have also derived a class of volumetric barrier decomposition algorithms, and proved polynomial complexity of certain members of the class. In this paper, we consider homogeneous self-dual algorithms for stochastic semidefinite programs with finite event space. We show how the structure in such problems may be exploited so that the algorithms developed in this paper have complexity similar to those of the decomposition algorithms mentioned above.     

Boosting local search with Lagrangian relaxation

Local search algorithms play an essential role in solving large-scale combinatorial optimization problems. Traditionally, the local search procedure is guided mainly by the objective function of the problem. Hence, the greedy improvement paradigm poses the potential threat of prematurely getting trapped in low quality attraction basins. In this study, we intend to utilize the information extracted from the relaxed problem, to enhance the performance of the local search process. Considering the Lin-Kernighan-based local search (LK-search) for the p-median problem as a case study, we propose the Lagrangian relaxation Assisted Neighborhood Search (LANS). In the proposed algorithm, two new mechanisms, namely the neighborhood reduction and the redundancy detection, are developed. The two mechanisms exploit the information gathered from the relaxed problem, to avoid the search from prematurely targeting low quality directions, and to cut off the non-promising searching procedure, respectively. Extensive numerical results over the benchmark instances demonstrate that LANS performs favorably to LK-search, which is among the state-of-the-art local search algorithms for the p-median problem. Furthermore, by embedding LANS into other heuristics, the best known upper bounds over several benchmark instances could be updated. Besides, run-time distribution analysis is also employed to investigate the reason why LANS works. The findings of this study confirm that the idea of improving local search by leveraging the information induced from relaxed problem is feasible and practical, and might be generalized to a broad class of combinatorial optimization problems.     

On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems

This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.     

Probabilistic asymptotic properties of some combinatorial optimization problems

A class of combinatorial optimization problems with sum- and bottleneck objective function is described, having the following probabilistic asymptotic behaviour: With probability tending to one the ratio between worst and optimal objective function value approaches one as the size of the problem tends to infinity.Problems belonging to this class are among others quadratic assignment problems, as well as certain combinatorial and graph theoretical optimization problems.The obtained results suggest that even very simple heuristic algorithms incline to yield good solutions for high dimensional problems of this class.     

Characterization of local solutions for a class of nonconvex programs

A nonconvex programming problem, which arises in the context of application of Benders' decomposition procedure to a class of network optimization problems, is considered. Conditions which are both necessary and sufficient for a local maximum are derived. The concept of a basic local maximum is introduced, and it is shown that there is a finite number of basic local maxima and at least one such local maximum is optimal.     

Derivative-free optimization: a review of algorithms and comparison of software implementations

This paper addresses the solution of bound-constrained optimization problems using algorithms that require only the availability of objective function values but no derivative information. We refer to these algorithms as derivative-free algorithms. Fueled by a growing number of applications in science and engineering, the development of derivative-free optimization algorithms has long been studied, and it has found renewed interest in recent time. Along with many derivative-free algorithms, many software implementations have also appeared. The paper presents a review of derivative-free algorithms, followed by a systematic comparison of 22 related implementations using a test set of 502 problems. The test bed includes convex and nonconvex problems, smooth as well as nonsmooth problems. The algorithms were tested under the same conditions and ranked under several criteria, including their ability to find near-global solutions for nonconvex problems, improve a given starting point, and refine a near-optimal solution. A total of 112,448 problem instances were solved. We find that the ability of all these solvers to obtain good solutions diminishes with increasing problem size. For the problems used in this study, TOMLAB/MULTIMIN, TOMLAB/GLCCLUSTER, MCS and TOMLAB/LGO are better, on average, than other derivative-free solvers in terms of solution quality within 2,500 function evaluations. These global solvers outperform local solvers even for convex problems. Finally, TOMLAB/OQNLP, NEWUOA, and TOMLAB/MULTIMIN show superior performance in terms of refining a near-optimal solution.     

Structural learning of Bayesian networks by bacterial foraging optimization

Algorithms inspired by swarm intelligence have been used for many optimization problems and their effectiveness has been proven in many fields. We propose a new swarm intelligence algorithm for structural learning of Bayesian networks, BFO-B, based on bacterial foraging optimization. In the BFO-B algorithm, each bacterium corresponds to a candidate solution that represents a Bayesian network structure, and the algorithm operates under three principal mechanisms: chemotaxis, reproduction, and elimination and dispersal. The chemotaxis mechanism uses four operators to randomly and greedily optimize each solution in a bacterial population, then the reproduction mechanism simulates survival of the fittest to exploit superior solutions and speed convergence of the optimization. Finally, an elimination and dispersal mechanism controls the exploration processes and jumps out of a local optima with a certain probability. We tested the individual contributions of four algorithm operators and compared with two state of the art swarm intelligence based algorithms and seven other well-known algorithms on many benchmark networks. The experimental results verify that the proposed BFO-B algorithm is a viable alternative to learn the structures of Bayesian networks, and is also highly competitive compared to state of the art algorithms.     

Bulk-Synchronous Parallel Gaussian Elimination

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We study the BSP complexity of Gaussian elimination and related problems. First, we analyze the Gaussian elimination without pivoting, which can be applied to the LU decomposition of symmetric positive-definite or diagonally dominant real matrices. Then we analyze the Gaussian elimination with Schönhage's recursive local pivoting suitable for the LU decomposition of matrices over a finite field, and for the QR decomposition of real matrices by the Givens rotations. Both versions of Gaussian elimination can be performed with an optimal amount of local computation, but optimal communication and synchronization costs cannot be achieved simultaneously. The algorithms presented in the paper allow one to trade off communication and synchronization costs in a certain range, achieving optimal or near-optimal cost values at the extremes. Bibliography: 19 titles.     

An information global minimization algorithm using the local improvement technique

In this paper, the global optimization problem with a multiextremal objective function satisfying the Lipschitz condition over a hypercube is considered. An algorithm that belongs to the class of information methods introduced by R.G. Strongin is proposed. The knowledge of the Lipschitz constant is not supposed. The local tuning on the behavior of the objective function and a new technique, named the local improvement, are used in order to accelerate the search. Two methods are presented: the first one deals with the one-dimensional problems and the second with the multidimensional ones (by using Peano-type space-filling curves for reduction of the dimension of the problem). Convergence conditions for both algorithms are given. Numerical experiments executed on more than 600 functions show quite a promising performance of the new techniques.     

Genetic and Random Search Methods in Optimal Shape Design Problems

We describe the application of two global optimization methods, namely of genetic and random search type algorithms in shape optimization. When the so-called fictitious domain approaches are used for the numerical realization of state problems, the resulting minimized function is non-differentiable and stair-wise, in general. Such complicated behaviour excludes the use of classical local methods. Specific modifications of the above-mentioned global methods for our class of problems are described. Numerical results of several model examples computed by different variants of genetic and random search type algorithms are discussed.     

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities.     

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.     

Solving some NP-complete problems using split decomposition

We show how to use the split decomposition to solve some NP-hard optimization problems on graphs. We give algorithms for clique problem and domination-type problems. Our main result is an algorithm to compute a coloration of a graph using its split decomposition. Finally we show that the clique-width of a graph is bounded if and only if the clique-width of each representative graph in its split decomposition is bounded.     

求解约束优化问题的两个微分方程算法

本文给出求解具有等式约束和不等式约束的非线性优化问题的一阶信息和二阶信息的两个微分方程系统,问题的局部最优解是这两个微分方程系统的渐近稳定的平衡点,给出了这两个微分方程系统的Euler离散迭代格式并证明了它们的收敛性定理,用龙格库塔法分别求解两个微分方程系统．我们构造了搜索方向由两个微分系统计算,步长采用Armijo线搜索的算法分别求解这个约束最优化问题,在局部Lipschitz条件下基于二阶信息的微分方程系统的迭代方法具有二阶的收敛速度。我们给出的数值结果表明龙格库塔的微分方程算法具有较好的稳定性和更高的精确度,求解二阶信息的微分方程系统的方法具有更快的收敛速度．     

A feasible method for optimization with orthogonality constraints

Minimization with orthogonality constraints (e.g., $X^\top X = I$ ) and/or spherical constraints (e.g., $\Vert x\Vert _2 = 1$ ) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. To deal with these difficulties, we apply the Cayley transform—a Crank-Nicolson-like update scheme—to preserve the constraints and based on it, develop curvilinear search algorithms with lower flops compared to those based on projections and geodesics. The efficiency of the proposed algorithms is demonstrated on a variety of test problems. In particular, for the maxcut problem, it exactly solves a decomposition formulation for the SDP relaxation. For polynomial optimization, nearest correlation matrix estimation and extreme eigenvalue problems, the proposed algorithms run very fast and return solutions no worse than those from their state-of-the-art algorithms. For the quadratic assignment problem, a gap 0.842 % to the best known solution on the largest problem “tai256c” in QAPLIB can be reached in 5 min on a typical laptop.     

Algorithmic aspects of the substitution decomposition in optimization over relations,set systems and Boolean functions

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

Two differential equation systems for equality-constrained optimization

This paper presents two differential systems, involving first and second order derivatives of problem functions, respectively, for solving equality-constrained optimization problems. Local minimizers to the optimization problems are proved to be asymptotically stable equilibrium points of the two differential systems. First, the Euler discrete schemes with constant stepsizes for the two differential systems are presented and their convergence theorems are demonstrated. Second, we construct algorithms in which directions are computed by these two systems and the stepsizes are generated by Armijo line search to solve the original equality-constrained optimization problem. The constructed algorithms and the Runge–Kutta method are employed to solve the Euler discrete schemes and the differential equation systems, respectively. We prove that the discrete scheme based on the differential equation system with the second order information has the locally quadratic convergence rate under the local Lipschitz condition. The numerical results given here show that Runge–Kutta method has better stability and higher precision and the numerical method based on the differential equation system with the second information is faster than the other one.     

Parallel Versions of the Modified Coordinate and Gradient Descent Methods and Their Application to a Class of Global Optimization Problems

We investigate the convergence of finite-difference local descent algorithms for the solution of global optimization problems with a multi-extremum objective function. Application of noise-tolerant local descent algorithms to the class of so-called -regular problems makes it possible to bypass minor extrema and thus identify the global structure of the objective function. Experimental data presented in the article confirm the efficiency of the parallel gradient and coordinate descent algorithms for the solution of some test problems.