StochasticOptimization - Applied Physics Laboratory

1 OptimizationJames C. Problem of stochastic and Deterministic Principles of stochastic Random General Properties of Direct Random Algorithms for Random stochastic Perturbation Genetic Coding and the Basic GA Core Genetic Implementation Comments on the Theory for Concluding Springer Heidelberg viewing permitted. Printing not buy this book at your bookshop. Order information see Springer Heidelberg 2004 Handbook of Computational Statistics(J. Gentle, W. H rdle, and Y. Mori, eds.)170 James C. SpallStochastic optimization algorithms have been growing rapidly in popularity overthe last decade or two, with a number of methods now becoming industry stan-dard approaches for solving challenging optimization problems.

2 This paper pro-vides a synopsis of some of the critical issues associated with stochastic optimiza-tion and a gives a summary of several popular algorithms. Much more completediscussions are available in the indicated help constrain the scope of this article, we restrict our attention to methodsusing only measurements of the criterion (loss function). Hence, we do not coverthe many stochastic methods using information such as gradients of the lossfunction. Section discusses some general issues in stochastic discusses random search methods, which are simple and surprisinglypowerful in many applications.

3 Section discusses stochastic approximation,which is a foundational approach in stochastic optimization . Section discussesa popular method that is based on connections to natural evolution geneticalgorithms. Finally, Sect. offers some concluding optimization plays a significant role in the analysis, design, and oper-ation of modern systems. Methods for stochastic optimization provide a meansof coping with inherent system noise and coping with models or systems that arehighly nonlinear, high dimensional, or otherwise inappropriate for classical deter-ministic methods of optimization .

4 stochastic optimization algorithms have broadapplication to problems in statistics ( , design of experiments and response sur-face modeling), science, engineering, and business. Algorithms that employ someform of stochastic optimization have become widely available. For example, manymodern data mining packages include methods such as simulated annealing andgenetic algorithms as tools for extracting patterns in applications include business (making short- and long-term investmentdecisions in order to increase profit), aerospace engineering (running computersimulations to refine the design of a missile or aircraft), medicine (designinglaboratory experiments to extract the maximum information about the efficacy ofa new drug), and traffic engineering (setting the timing for the signals in a trafficnetwork).

5 There are, of course,manyother us introduce some concepts and notation. Suppose is the domain ofallowable values for a vector .Thefundamentalproblemofinterestistofind the value(s) of a vector that minimize a scalar-valuedloss functionL( ).Other common names forLareperformance measure,objective function,measure-of-effectiveness(MOE),f itness function(ornegative fitness function), this problem refers tominimizinga loss function, a maximization problem( , maximizing profit) can be trivially converted to a minimization problem byCopyright Springer Heidelberg viewing permitted.

6 Printing not buy this book at your bookshop. Order information see Springer Heidelberg 2004 Handbook of Computational Statistics(J. Gentle, W. H rdle, and Y. Mori, eds.) stochastic optimization 171changing the sign of the criterion. This paper focuses on the problem of mini-mization. In some cases ( , differentiableL), the minimization problem can beconverted to a root-finding problem of finding such thatg( )= L( )| = course, this conversion must be done with care because such a root may notcorrespond to a global minimum three remaining subsections in this section define some basic quantities,discuss some contrasts between (classical) deterministic optimization and stochas-tic optimization , and discuss some basic properties and fundamental limits.

7 Thissection provides the foundation for interpreting the algorithm presentations inSects. to There are many other references that give general reviews of vari-ous aspects of stochastic optimization . Among these are Arsham (1998), Fouskakisand Draper (2002), Fu (2002), Gosavi (2003), Michalewicz and Fogel (2000), andSpall (2003).Formal Problem problem of minimizing a loss functionL=L( )can be formally representedas finding the set: arg min L( )={ :L( ) L( )for all },( )where is thep-dimensional vector of parameters that are being adjusted and arg min statement in ( ) should be read as: is the set ofvalues = ( the argument in arg min ) that minimizeL( )subject to satisfying the constraints represented in the set.

8 The elements are equivalent solutions in the sense that they yield identical values of the lossfunction. The solution set in ( ) may be a unique point, a countable (finite orinfinite) collection of points, or a set containing an uncountable number of ease of exposition, this paper generally focuses on continuous optimizationproblems, continuous case, it is often assumed thatLis a smooth (perhaps several timesdifferentiable) function of . Continuous problems arise frequently in applicationssuch as model fitting (parameter estimation), adaptive control, neural networktraining, signal processing, and experimental design.

9 Discrete optimization (orcombinatorial optimization ) is a large subject unto itself (resource allocation, net-work routing, policy planning, etc.).A major issue in optimization is distinguishing between global and local other factors being equal, one would always want a globally optimal solution tothe optimization problem ( , at least one in the set of values ). In practice,however, it may not be feasible to find a global solution and one must be satisfiedwith obtaining alocalsolution. For example,Lmay be shaped such that there isa clearly defined minimum point over a broad region of the domain , while thereis a very narrow spike at a distant point.

10 If the trough of this spike is lower than anypoint in the broad region, the local optimal solution is better than any nearby ,butitisnotbethebestpossible .Copyright Springer Heidelberg viewing permitted. Printing not buy this book at your bookshop. Order information see Springer Heidelberg 2004 Handbook of Computational Statistics(J. Gentle, W. H rdle, and Y. Mori, eds.)172 James C. SpallIt is usually only possible to ensure that an algorithm will approach a localminimum with a finite amount of resources being put into the optimization ,itiseasytoconstructfunctionsthatwill fool anyknownalgorithm,unless the algorithm is given explicit prior information about the location of theglobal solution certainly not a case of practical interest!