On the complexity of the exchange algorithm for minimax optimization problems

We present an exchange algorithm for the solution of minimax optimization problems involving convex functions. For a certain class of functions, the complexity of this algorithm is shown to be either linear in the number of functions, or at least squared in that number.     

On upper semicontinuity of global minima in constrained optimization problems

This paper studies stability properties of solutions for optimization problems subject to perturbations in constraints. For problems formulated in a complete metric space sufficient conditions for topological upper semicontinuity of the solution multifunction are derived without any compactness assumptions. When the feasible solution set is additionally assumed to be compact these conditions reduce to that of Berge (“Topological Spaces,” Macmillan Co., New York, 1963), and in that case they turn out to be also necessary.     

A survey of average case complexity for linear multivariate problems

We survey recent results on the average case complexity for linear multivariate problems. Our emphasis is on problems defined on spaces of functions of d variables with large d. We present the sharp order of the average case complexity for a number of linear multivariate problems as well as necessary and sufficient conditions for the average case complexity not to be exponential in d. Dedicated to the 50th anniversary of the journal. The text was submitted by the authors in English.     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001     

On average cost stopping time problems

Summary We consider the stopping time problems whose costs are given by time average forms, a generalization of the Gittins index. We show the existence of the optimal solutions and give their approximation to these stopping time problems.     

On global quadratic growth condition for min-max optimization problems with quadratic functions

Second-order sufficient condition and quadratic growth condition play important roles both in sensitivity and stability analysis and in numerical analysis for optimization problems. In this article, we concentrate on the global quadratic growth condition and study its relations with global second-order sufficient conditions for min-max optimization problems with quadratic functions. In general, the global second-order sufficient condition implies the global quadratic growth condition. In the case of two quadratic functions involved, we have the equivalence of the two conditions.     

Basin Hopping Networks of continuous global optimization problems

Characterization of optimization problems with respect to their solvability is one of the focal points of many research projects in the field of global optimization. Our study contributes to these efforts with the usage of the computational and mathematical tools of network science. Given an optimization problem, a network formed by all the minima found by an optimization method can be constructed. In this paper we use the Basin Hopping method on well-known benchmarking problems and investigate the resulting networks using several measures.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

Improving complexity of structured convex optimization problems using self-concordant barriers

The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using the theory of self-concordant functions developed by Nesterov and Nemirovski in SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma due to den Hertog et al. in Mathematical Programming Series B 69 (1) (1995) is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results.     

On minimax optimization problems

We give a short proof that in a convex minimax optimization problem ink dimensions there exist a subset ofk + 1 functions such that a solution to the minimax problem with thosek + 1 functions is a solution to the minimax problem with all functions. We show that convexity is necessary, and prove a similar theorem for stationary points when the functions are not necessarily convex but the gradient exists for each function.     

A distributed global optimization method for packing problems

Packing optimization problems aim to seek the best way of placing a given set of rectangular cartons within a minimum volume rectangular container. Currently, packing optimization methods either have difficulty in finding a globally optimal solution or are computationally inefficient, because models involve too many 0–1 variables and because use of just a single computer. This study proposes a distributed computation method for solving a packing problem by a set of personal computers via the Internet. First, the traditional packing optimization model is converted into an equivalent model containing many fewer 0–1 variables. Then the model is decomposed into several sub-problems by dividing the objective value into many intervals. Each of these sub-problems is a linearized logarithmic program expressed as a linear mixed 0–1 problem. The whole problem is solvable and reaches a globally optimal solution. The numerical examples demonstrate that the proposed method can obtain the global optimum of a packing problem effectively.     

Geometric branch-and-bound methods for constrained global optimization problems

Geometric branch-and-bound methods are popular solution algorithms in deterministic global optimization to solve problems in small dimensions. The aim of this paper is to formulate a geometric branch-and-bound method for constrained global optimization problems which allows the use of arbitrary bounding operations. In particular, our main goal is to prove the convergence of the suggested method using the concept of the rate of convergence in geometric branch-and-bound methods as introduced in some recent publications. Furthermore, some efficient further discarding tests using necessary conditions for optimality are derived and illustrated numerically on an obnoxious facility location problem.     

Chaotic catfish particle swarm optimization for solving global numerical optimization problems

Chaotic catfish particle swarm optimization (C-CatfishPSO) is a novel optimization algorithm proposed in this paper. C-CatfishPSO introduces chaotic maps into catfish particle swarm optimization (CatfishPSO), which increase the search capability of CatfishPSO via the chaos approach. Simple CatfishPSO relies on the incorporation of catfish particles into particle swarm optimization (PSO). The introduced catfish particles improve the performance of PSO considerably. Unlike other ordinary particles, the catfish particles initialize a new search from extreme points of the search space when the gbest fitness value (global optimum at each iteration) has not changed for a certain number of consecutive iterations. This results in further opportunities of finding better solutions for the swarm by guiding the entire swarm to promising new regions of the search space and accelerating the search. The introduced chaotic maps strengthen the solution quality of PSO and CatfishPSO significantly. The resulting improved PSO and CatfishPSO are called chaotic PSO (C-PSO) and chaotic CatfishPSO (C-CatfishPSO), respectively. PSO, C-PSO, CatfishPSO, C-CatfishPSO, as well as other advanced PSO procedures from the literature were extensively compared on several benchmark test functions. Statistical analysis of the experimental results indicate that the performance of C-CatfishPSO is better than the performance of PSO, C-PSO, CatfishPSO and that C-CatfishPSO is also superior to advanced PSO methods from the literature.     

An approximately global optimization method for assortment problems

Assortment problems occur when we want to cut a number of small rectangular pieces from a large rectangle to get the minimum area within the rectangle. Recently, Chen et al. proposed a useful model for assortment problems. Although Chen et al.'s model is quite promising to find solutions, there are two inadequacies in their model: firstly, the objective function in their model is a polynomial term, which may not lead to a globally optimal solution; secondly, too many 0–1 variables are used to formulate the non-overlapping constraints. We propose a new method to reformulate an assortment model. Our model is not only able to find the approximately global optimal solution, but involves less 0–1 variables for formulating non-overlapping constraints.     

On computation complexity problems concerning relation algebras

In this paper, we study the computation complexity of some algebraic combinatorial problems that are closely associated with the graph isomorphism problem. The key point of our considerations is a relation algebra which is a combinatorial analog of a cellular algebra. We present upper bounds on the complexity of central algorithms for relation algebras such as finding the standard basis of extensions and intersection of relation algebras. Also, an approach is described to the graph isomorphism problem involving Schurian relation algebras (these algebras arise from the centralizing rings of permutation groups). We also discuss a number of open problems and possible directions for further investigation. Bibliography: 18 titles. Translated by I. N.Ponomarenko. Translated fromZapiski Nauchnykh Seminarov POMI, Vol 202, 1992, pp. 116–134.