A multiobjective evolutionary approach for linearly constrained project selection under uncertainty

In the project selection problem a decision maker is required to allocate limited resources among an available set of competing projects. These projects could arise, although not exclusively, in an R&D, information technology or capital budgeting context. We propose an evolutionary method for project selection problems with partially funded projects, multiple (stochastic) objectives, project interdependencies (in the objectives), and a linear structure for resource constraints. The method is based on posterior articulation of preferences and is able to approximate the efficient frontier composed of stochastically nondominated solutions. We compared the method with the stochastic parameter space investigation method (PSI) and illustrate it by means of an R&D portfolio problem under uncertainty based on Monte Carlo simulation.     

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices.

Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both – systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed.

A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix.     

An Adaptive Version for the Metropolis Adjusted Langevin Algorithm with a Truncated Drift

This paper extends some adaptive schemes that have been developed for the Random Walk Metropolis algorithm to more general versions of the Metropolis-Hastings (MH) algorithm, particularly to the Metropolis Adjusted Langevin algorithm of Roberts and Tweedie (1996). Our simulations show that the adaptation drastically improves the performance of such MH algorithms. We study the convergence of the algorithm. Our proves are based on a new approach to the analysis of stochastic approximation algorithms based on mixingales theory.      

Liquidity Costs: A New Numerical Methodology and an Empirical Study

We consider rate swaps which pay a fixed rate against a floating rate in the presence of bid-ask spread costs. Even for simple models of bid-ask spread costs, there is no explicit strategy optimizing an expected function of the hedging error. We here propose an efficient algorithm based on the stochastic gradient method to compute an approximate optimal strategy without solving a stochastic control problem. We validate our algorithm by numerical experiments. We also develop several variants of the algorithm and discuss their performances in terms of the numerical parameters and the liquidity cost.     

Minimization Algorithms Based on Supervisor and Searcher Cooperation

In the present work, we explore a general framework for the design of new minimization algorithms with desirable characteristics, namely, supervisor-searcher cooperation. We propose a class of algorithms within this framework and examine a gradient algorithm in the class. Global convergence is established for the deterministic case in the absence of noise and the convergence rate is studied. Both theoretical analysis and numerical tests show that the algorithm is efficient for the deterministic case. Furthermore, the fact that there is no line search procedure incorporated in the algorithm seems to strengthen its robustness so that it tackles effectively test problems with stronger stochastic noises. The numerical results for both deterministic and stochastic test problems illustrate the appealing attributes of the algorithm.     

Convexity and decomposition of mean-risk stochastic programs

Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criterion leads to computational intractability even in the simplest stochastic programs. On the other hand, a number of alternative mean-risk functions are shown to be computationally tractable using slight variants of existing stochastic programming decomposition algorithms. We propose decomposition-based parametric cutting plane algorithms to generate mean-risk efficient frontiers for two particular classes of mean-risk objectives.     

A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm

Resource portfolio planning optimization is crucial to high-tech manufacturing industries. One of the most important characteristics of such a problem is intensive investment and risk in demands. In this study, a nonlinear stochastic optimization model is developed to maximize the expected profit under demand uncertainty. For solution efficiency, a stochastic programming-based genetic algorithm (SPGA) is proposed to determine a profitable capacity planning and task allocation plan. The algorithm improves a conventional two-stage stochastic programming by integrating a genetic algorithm into a stochastic sampling procedure to solve this large-scale nonlinear stochastic optimization on a real-time basis. Finally, the tradeoff between profits and risks is evaluated under different settings of algorithmic and hedging parameters. Experimental results have shown that the proposed algorithm can solve the problem efficiently.     

Globally and superlinearly convergent trust-region algorithm for convex SC1-minimization problems and its application to stochastic programs

A function mapping from ⁿ to is called an SC¹-function if it is differentiable and its derivative is semismooth. A convex SC¹-minimization problem is a convex minimization problem with an SC¹-objective function and linear constraints. Applications of such minimization problems include stochastic quadratic programming and minimax problems. In this paper, we present a globally and superlinearly convergent trust-region algorithm for solving such a problem. Numerical examples are given on the application of this algorithm to stochastic quadratic programs.This work was supported by the Australian Research Council.We are indebted to Dr. Xiaojun Chen for help in the computation. We are grateful to two anonymous referees for their comments and suggestions, which improved the presentation of this paper.     

Herleitung eines stochastischen maximumprinzips mit variationsmethoden

Using variation techniques a stochastic maximum principle is proved for control systems, which are described by stochastic differential equations over a fixed time interval. Thereby the diffusion matrix is a function of the state of the system. The principle of optimality has the form of an inequality of the conditional expectation of a HAMILTON-function with respect to the so-called б-algebra of informations.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

A parallel version of a quasigradient methoid In stochastic control theory ∗

We solve an optimal control problem for controlled parabolic Ito equations by a stochastic quasigradient method. Because of high amounts of computation time required by numerical solution of such problems we investigate the parallelization of the algorithm. We distribute the computations of space stages over several processor nodes of a parallel computer. We obtain an efficient algorithm with low communication cost by using a ring topology     

Stochastic recursive inclusion in two timescales with an application to the Lagrangian dual problem

In this paper we present a framework to analyze the asymptotic behavior of two timescale stochastic approximation algorithms including those with set-valued mean fields. This paper builds on the works of Borkar and Perkins & Leslie. The framework presented herein is more general as compared to the synchronous two timescale framework of Perkins & Leslie, however the assumptions involved are easily verifiable. As an application, we use this framework to analyze the two timescale stochastic approximation algorithm corresponding to the Lagrangian dual problem in optimization theory.     

A stochastic steepest-descent algorithm

A stochastic steepest-descent algorithm for function minimization under noisy observations is presented. Function evaluation is done by performing a number of random experiments on a suitable probability space. The number of experiments performed at a point generated by the algorithm reflects a balance between the conflicting requirements of accuracy and computational complexity. The algorithm uses an adaptive precision scheme to determine the number of random experiments at a point; this number tends to increase whenever a stationary point is approached and to decrease otherwise. Two rules are used to determine the number of random experiments at a point; one, in the inner loop of the algorithm, uses the magnitude of the observed gradient of the function to be minimized; and the other, in the outer-loop, uses a measure of accumulated errors in function evaluations at past points generated by the algorithm. Once a stochastic approximation of the function to be minimized is obtained at a point, the algorithm proceeds to generate the next point by using the steepest-descent deterministic methods of Armijo and Polak (Refs. 3, 4). Convergence of the algorithm to stationary points is demonstrated under suitable assumptions.     

Stochastic techniques for global optimization: A survey of recent advances

In this paper stochastic algorithms for global optimization are reviewed. After a brief introduction on random-search techniques, a more detailed analysis is carried out on the application of simulated annealing to continuous global optimization. The aim of such an analysis is mainly that of presenting recent papers on the subject, which have received only scarce attention in the most recent published surveys. Finally a very brief presentation of clustering techniques is given.     

二层随机规划基于随机模拟的遗传算法

本提出了二层随机规划模型，给出了求解二层随机规划问题的基于随机模拟的遗传算法。实际算例表明算法是可行的、有效的。     

Global Optimization Requires Global Information

There are many global optimization algorithms which do not use global information. We broaden previous results, showing limitations on such algorithms, even if allowed to run forever. We show that deterministic algorithms must sample a dense set to find the global optimum value and can never be guaranteed to converge only to global optimizers. Further, analogous results show that introducing a stochastic element does not overcome these limitations. An example is simulated annealing in practice. Our results show that there are functions for which the probability of success is arbitrarily small.     

Convergence analysis of a global optimization algorithm using stochastic differential equations

We establish the convergence of a stochastic global optimization algorithm for general non-convex, smooth functions. The algorithm follows the trajectory of an appropriately defined stochastic differential equation (SDE). In order to achieve feasibility of the trajectory we introduce information from the Lagrange multipliers into the SDE. The analysis is performed in two steps. We first give a characterization of a probability measure (Π) that is defined on the set of global minima of the problem. We then study the transition density associated with the augmented diffusion process and show that its weak limit is given by Π.     

Algorithms for the solution of stochastic dynamic minimax problems

In this paper, we present algorithms for the solution of the dynamic minimax problem in stochastic programs. This dynamic minimax approach is suggested for the analysis of multi-stage stochastic decision problems when there is only partial knowledge on the joint probability distribution of the random data. The algorithms proposed in this paper are based on projected sub-gradient and bundle methods.

---

Résumé Dans cet article, nous proposons des algorithmes pour la solution du problème du minimax dynamique stochastique. Ce problème se présente par exemple lorsque, dans un problème de décision dynamique stochastique, l'information disponible au sujet des distributions de probabilité des paramètres est incomplète. Les algorithmes proposés sont fondés sur la méthode de sous-gradient projeté et la méthode des faisceaux.

     

Stochastic optimization with averaging of trajectories

A recursive stochastic optimization procedure under dependent disturbances is studied. It is based on the Polyak-Ruppert algorithm with trajectory averaging. Almost sure convergence of the algorithm is proved as well as asymptotic normality of the delivered estimates. It is shown that the presented algorithm attains the highest possible asymptotic convergence rate for stochastic approximation algorithms     

Phylogenetic Inference for Binary Data on Dendograms Using Markov Chain Monte Carlo

Abstract

Using a stochastic model for the evolution of discrete characters among a group of organisms, we derive a Markov chain that simulates a Bayesian posterior distribution on the space of dendograms. A transformation of the tree into a canonical cophenetic matrix form, with distinct entries along its superdiagonal, suggests a simple proposal distribution for selecting candidate trees “close” to the current tree in the chain. We apply the consequent Metropolis algorithm to published restriction site data on nine species of plants. The Markov chain mixes well from random starting trees, generating reproducible estimates and confidence sets for the path of evolution.