Benchmarking optimization software with performance profiles

We propose performance profiles — distribution functions for a performance metric — as a tool for benchmarking and comparing optimization software. We show that performance profiles combine the best features of other tools for performance evaluation. Received: February 2001 / Accepted: May 2001?Published online October 2, 2001     

Model development and optimization in interactive computing environments

Integrated computing systems—such as Maple, Mathematica, and MATLAB—enable the development of “live” electronic documents that include explanatory text, calculations, custom programming (code development), visualization, and other features. As a result, teachers and students, researchers and practitioners can develop applications in a completely interactive format. Such e-documents can be put to good use in developing textbooks, lecture notes, assignments and presentations, as well as in the context of research and development (R&D) projects. The interactive approach accelerates and enhances the process of learning and research. To illustrate this approach, we discuss a nonlinear (global and local) optimization software product and a topical electronic book that support interactive model development and optimization in Maple. We highlight the key features of the e-book and the software, present illustrative examples, and point towards a range of scientific and engineering applications.      

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Solving nonlinear integer programs with large-scale optimization software

This paper describes recent experience in tackling large nonlinear integer programming problems using the MINOS large-scale optimization software. A technique is presented for extending the constrained search approach used in MINOS to exploring integer-feasible solutions once a continuous optimal solution is obtained. Computational experience with this approach is described for two classes of problems: quadratic assignment problems and pipeline network design problems.     

Parallel computing in combinatorial optimization

This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.     

OpTiX-II: A software environment for the parallel solution of nonlinear optimization problems

The intention of the paper is to give an introduction to the OpTiX-II Software Environment, which supports the parallel and distributed solution of mathematical nonlinear programming problems. First, a brief summary of nonsequential solution concepts for nonlinear optimization on multiprocessor systems will be given. The focus of attention will be put on coarse-grained parallelization and its implementation on multi-computer clusters. The conceptual design objectives for the OpTiX-II Software Environment will be presented as well as the implementation on a workstation cluster, a transputer system and a multiprocessor workstation (shared memory). The OpTiX-II system supports the steps from the formulation of nonlinear optimization problems to their solution on networks of (parallel) computers. In order to demonstrate the use of OpTiX-II, the solution of a nonlinear optimization problem from the field of structural design is discussed and some numerical test results are supplied.     

A formal apparatus for modeling trust in computing environments

Recent research in computer systems security has evolved into trust issues, which are now becoming an important topic. The majority of approaches for trust modeling addressed trust by actually focusing on security, and some of them addressed also trust as such. This paper presents a formal apparatus that concentrates on trust as such. It is flexible enough to accommodate the driving factors behind trust and consequently different trust-focused methodologies and technologies. The basic goal of the work presented in this paper is the definition of qualitative trust modeling methodology for trust management in contemporary computing environments that efficiently complements existing quantitative methodologies. Further, an open conceptual model for trust management is presented that accommodates various qualitative and quantitative trust management methodologies. This model has also been implemented in the web services environment, and this is discussed in this paper as well.     

Multi-objective optimization in uncertain random environments

Uncertain random variables are used to describe the phenomenon of simultaneous appearance of both uncertainty and randomness in a complex system. For modeling multi-objective decision-making problems with uncertain random parameters, a class of uncertain random optimization is suggested for decision systems in this paper, called the uncertain random multi-objective programming. For solving the uncertain random programming, some notions of the Pareto solutions and the compromise solutions as well as two compromise models are defined. Subsequently, some properties of these models are investigated, and then two equivalent deterministic mathematical programming models under some particular conditions are presented. Some numerical examples are also given for illustration.     

Geodesic convexity in nonlinear optimization

The properties of geodesic convex functions defined on a connected RiemannianC ² k-manifold are investigated in order to extend some results of convex optimization problems to nonlinear ones, whose feasible region is given by equalities and by inequalities and is a subset of a nonlinear space.This research was supported in part by the Hungarian National Research Foundation, Grant No. OTKA-1044.     

Sectional curvatures in nonlinear optimization

The aim of the paper is to show how to explicitly express the function of sectional curvature with the first and second derivatives of the problem’s functions in the case of submanifolds determined by equality constraints in the n-dimensional Euclidean space endowed with the induced Riemannian metric, which is followed by the formulation of the minimization problem of sectional curvature at an arbitrary point of the given submanifold as a global minimization one on a Stiefel manifold. Based on the results, the sectional curvatures of Stiefel manifolds are analysed and the maximal and minimal sectional curvatures on an ellipsoid are determined. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA-T043276 and OTKA-K60480.     

Error estimation in nonlinear optimization

Methods are developed and analyzed for estimating the distance to a local minimizer of a nonlinear programming problem. One estimate, based on the solution of a constrained convex quadratic program, can be used when strict complementary slackness and the second-order sufficient optimality conditions hold. A second estimate, based on the solution of an unconstrained nonconvex, nonsmooth optimization problem, is valid even when strict complementary slackness is violated. Both estimates are valid in a neighborhood of a local minimizer. An active set algorithm is developed for computing a stationary point of the nonsmooth error estimator. Each iteration of the algorithm requires the solution of a symmetric, positive semidefinite linear system, followed by a line search. Convergence is achieved in a finite number of iterations. The error bounds are based on stability properties for nonlinear programs. The theory is illustrated by some numerical examples.     

Partially separable optimization and parallel computing

Parallel processors are becoming an attractive option for meeting the requirements to solve large nonlinear optimization problems and the partially separable methods are ideal candidates for parallel computing. This paper proposes implementation techniques for such methods. Computational experiments on an IBM 3090-200 and on a simulated multiprocessor are presented. The performance of both implementations is compared against a reference serial implementation.     

Evolutionary multiobjective optimization in noisy problem environments

This paper presents a multiobjective evolutionary algorithm (MOEA) capable of handling stochastic objective functions. We extend a previously developed approach to solve multiple objective optimization problems in deterministic environments by incorporating a stochastic nondomination-based solution ranking procedure. In this study, concepts of stochastic dominance and significant dominance are introduced in order to better discriminate among competing solutions. The MOEA is applied to a number of published test problems to assess its robustness and to evaluate its performance relative to NSGA-II. Moreover, a new stopping criterion is proposed, which is based on the convergence velocity of any MOEA to the true Pareto optimal front, even if the exact location of the true front is unknown. This stopping criterion is especially useful in real-world problems, where finding an appropriate point to terminate the search is crucial.     

Some software aspects of DAE simulation & optimization software

Considerable numerical software has been written for simulation and optimization of dynamical systems. From the beginning of their development, differential algebraic equations (DAEs) have often been proposed as a way to make modeling easier. The modeler need only write down equations relating the variables in the model. However, much DAE software requires at least as much user numerical and mathematical expertise as explicit methods. An important aspect of our research has been working toward helping the idea of DAEs achieve its promise in modeling and simulation by both pushing the software to handle more general problems and to also allow for less user expertise. Some recent examples are presented where this research impacts on software and their underlying algorithms. Space necessitates we assume the reader has a rough idea of what a DAE is. The examples are implicit Scicos, and optimization of DAE models. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Data parallel computing for network-structured optimization problems

Data level parallelism is a type of parallelism whereby operations are performed on many data elements concurrently, by many processors. These operations are (more or less) identical, and are executed in a synchronous, orderly fashion. This type of parallelism is used by massively parallel SIMD (i.e., Single Instruction, Multiple Data) architectures, like the Connection Machine CM-2, the AMT DAP and Masspar, and MIMD (i.e., Multiple Instruction, Multiple Data) architectures, like the Connection Machine CM-5. Data parallelism can also be described by a theoretical model of computation: the Vector-Random Access Machine (V-RAM).In this paper we discuss practical approaches to the data-parallel solution of large scale optimization problems with network—or embedded-network—structures. The following issues are addressed: (1) The concept of dataparallelism, (2) algorithmic principles that lead to data-parallel decomposition of optimization problems with network—or embedded-network—structures, (3) specific algorithms for several network problems, (4) data-structures needed for efficient implementations of the algorithms, and (5) empirical results that highlight the performance of the algorithms on a data-parallel computer, the Connection Machine CM-2.     

On optimization of continuous-time Markov networks in distributed computing

The paper presents a new stochastic model for studying the optimization of functioning rules in distributed computing. In this model a network is represented by a finite number of continuous-time homogeneous Markov processes which are connected by relations between entries of their intensity matrices. Good functioning rules are those optimizing a guide function defined according to the context. Two specific optimization problems are studied: a problem of resource allocation with conflicts between processes, and a problem of access to shared resources. The latter is a linearly constrained nonconvex problem with an objective function which is a sum of ratios of linear functions of special form.