Home

The OPTLSO Procedure

1. a proc fcmp outlib sasuser myfuncs mypkg function loglkh3 x sigma mu return log sigma 0 5x x mu sigma 2 endsub run proc optlso variables objective run lkhvar lkhob33 Syntax OPTLSO Procedure 21 Syntax OPTLSO Procedure The following statements are available in the OPTLSO procedure PROC OPTLSO lt options gt READARRAY SAS data set 1 lt SAS data set 2 SAS data set k gt PERFORMANCE lt options gt PROC OPTLSO Statement PROC OPTLSO lt options gt The PROC OPTLSO statement invokes the OPTLSO procedure Functional Summary Table 3 1 outlines the options available in the PROC OPTLSO statement Table 3 1 Summary of PROC OPTLSO Options Description option Input Data Set Options Specifies the input cache file CACHEIN Specifies the initial genetic algorithm population FIRSTGEN Describes the linear constraints LINCON Indicates that the description uses the mathematical MPSDATA programming system MPS data format Describes the nonlinear constraints NLINCON Describes the objective function OBJECTIVE Specifies the initial trial points PRIMALIN Indicates that the description uses the quadratic QPSDATA programming system QPS data format Describes the variables VARIABLES Output Data Set Options Specifies the output cache file CACHEOUT Specifies the local solutions and best feasible solution PRIMALOUT Specifies the members of the genetic algorithm population L
2. Testing Unconstrained Optimization Software ACM Transactions on Mathematical Software 7 1741 Plantenga T 2009 HOPSPACK 2 0 User Manual v 2 0 2 Technical report Sandia National Laboratories References 77 Schiitze O Esquivel X Lara A and Coello Coello C A 2012 Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization IEEE Transactions on Evolutionary Computation 16 504 522 Taddy M A Lee H K H Gray G A and Griffin J D 2009 Bayesian Guided Pattern Search for Robust Local Optimization Technometrics 51 389 401 Van Veldhuizen D A 1999 Multiobjective Evolutionary Algorithms Classifications Analyses and New Innovations Ph D diss Air Force Institute of Technology Subject Index Bard function 59 Branin function 16 derivative free optimization OPTLSO procedure 14 details OPTLSO procedure 27 displayed output to log OPTLSO procedure 27 40 examples OPTLSO procedure 43 FCMP basics OPTLSO procedure 27 function caching OPTLSO procedure 39 functional summary OPTLSO procedure 21 genetic algorithms 34 Intermediate functions OPTLSO procedure 29 Johnson function 65 large data OPTLSO procedure 30 linear constraints OPTLSO procedure 33 local search optimization 27 43 OROPTLSO _OROPTLSO_ 42 MPS and QPS objective functions OPTESO procedure 29 multiple objectives OPTESO
3. Example 3 10 Multiobjective Optimization The following optimization problem is discussed in Huband et al 2006 Cust dio et al 2011 This example illustrates how to use PROC FCMP to define multiple nonlinear objectives This problem minimizes Fix la 1 a x2 and fo x x1 x2 22 3 subject to 0 lt x1 x2 lt 5 The VARIABLES VARDATA option in the PROC OPTLSO statement specifies the variables and their respective bounds The objective functions are defined by using PROC FCMP and the objective function names and other properties are described in the SAS data set objdata The problem description is then passed to the OPTLSO procedure by using the options VARIABLES VARDATA and OBJECTIVE OBJDATA data vardata input _id _lb ub_ datalines x1 05 x2 05 proc fcmp outlib sasuser myfuncs mypkg function fdef1 x1 x2 return x1 1 xx2 x1 x2 2 endsub function fdef2 x1 x2 return x1 x2 2 x2 3 xx2 endsub run data objdata input _id _function_ _sense_ datalines f1 fdefl min Example 3 10 Multiobjective Optimization 73 2 fdef2 min t options cmplib sasuser myfuncs proc optlso primalout solution variables vardata objective objdata logfreq 50 a run proc transpose data solution out pareto label _sol_ name _sol_ by _sol_ var _value_ id _id run proc gplot data pareto plot 2x f1 run quit Output 3 10 1 show
4. on page 33 If you do not specify the OBJECTIVE option PROC OPTLSO optimizes m x However if you specify the OBJECTIVE option the objective 30 4 Chapter 3 The OPTLSO Procedure function m x is ignored unless you explicitly include the corresponding objective function name and specify whether the function is to be used as an intermediate or objective function See Example 3 4 Combining MPS and FCMP Function Definitions on page 51 If the objective name also matches a name in the FCMP library the FCMP function definition takes precedence Using Large Data Sets When your objective function includes the sum of a family of functions that are parameterized by the rows of a given data set PROC OPTLSO enables you to include in your objective function definition a single external data set that is specified in the _DATASET_ column of the OBJECTIVE data set Consider the following unconstrained optimization problem where k is a very large integer for example 10 A denotes ak x 5 matrix and b denotes the corresponding right hand side target vector min f x Ax bll2 lx ll xeER gt To evaluate the objective function the following operations must be performed k dai i 1 5 Y oe j l fx VAG 42 AG II f where 2 5 di bi Y ayx j 1 and aj denotes the jth entry of row i of the matrix A Assume that there is an existing SAS data set that stores numerical entries for A and b The follow
5. sasuser myfuncs proc fcmp outlib sasuser myfuncs mypkg function SmoothFunc x y x sin x x xxcos x return y endsub function DiscretizedFunc x array lookup amp N 2 nosymbols re read_array f_discrete lookup do i 1 to eval amp N 1 if x gt lookup i 1 and x lt lookup i 1 1 then do lookup value at nearest smaller discretized point y lookup i 2 i eval amp N 1 end end return y endsub run The previous statements define PROC FCMP functions for both the smooth and discretized versions of the objective function The smooth version is used as follows to generate the discrete points in the lookup table data set f_discrete for x values at 100 NV points between 0 L and 10 U The values in the following data set created are used in the discretized version of the function that will be used in PROC OPTLSO for optimization That discretized version of the function performs a simple lookup of the point data that are contained in the f_discrete data set For a specified x value the function finds the two discrete values in the data set that are closest to x Then the smaller of the two nearest points is returned as the function value Example 3 9 Discontinuous Function with a Lookup Table 69 data f_ discrete a amp L b amp U n amp N drop i a b n do i 1 to n x a i n x b a y SmoothFunc x output end run data vardata input _id _1b ub_
6. 1 03163 56 Chapter 3 The OPTLSO Procedure Example 3 6 Using Nonlinear Constraints The following optimization problem is discussed in Haverly 1978 and Liebman et al 1986 This example illustrates how to use PROC FCMP to define nonlinear constraints and use an MPS data set to define linear constraints Maximize F x 9x1 15x2 6x3 16x4 10x5 subject to X3 X4 X6 X7 X6 X8 X X7 X9 X2 Xg X9 X5 2 5x1 x10X6 2xg gt 0 1 5x2 x10x7 2x9 gt 0 3x3 x4 X10 x3 x4 0 and 0 lt x lt 100 0 lt x2 lt 200 1 lt x10 lt 3 0 lt xi fori 3 9 In the following steps the linear component of the problem definition is first described in PROC OPTMODEL and then saved as an MPS data set Because the objective is linear no FCMP objective function needs to be used In the second section of steps the nonlinear constraints are defined by using FCMP functions and their corresponding names and lower and upper bounds are stored in the data set condata The OPTLSO procedure is then called with the options NLINCON CONDATA and MPSDATA NLCEX As in Example 3 2 Using MPS Format on page 46 you can use the macro definition Isompsmod to strip brackets from the resulting data set macro lsompsmod setold setnew data amp setnew drop i set amp setold array FC _CHARACTER_ do i 1 to dim FC FC i compress FC i end run Smend proc
7. datalines x 0 10 Use the discretized function as the objective data objdata length _function_ 16 input _id _function_ _sense_ datalines f DiscretizedFunc min options cmplib sasuser myfuncs proc optlso primaluut finalsol variables vardata objective objdata readarray f _discrete run proc print data finalsol run Output 3 9 1 shows the ODS tables that are produced Output 3 9 1 Discontinuous Function ODS Tables The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 4 Data Access Information Data Engine Role Path WORK F_DISCRETE V9 Input On Client 70 Chapter 3 The OPTLSO Procedure Output 3 9 1 continued Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 1 Integer Variables 0 Continuous Variables 1 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize Solution Summary Solution Status Function convergence Objective 93 18498962 Infeasibility 0 Iterations 12 Evaluations 306 Cached Evaluations 57 Global Searches 1 Population Size 40 Seed 1 Obs _sol_ id _value_ 1 0 obj 93 1850 2 0_inf 0 0000 3 Ox 9 7087 4 Of 93 1850 The following code optimizes the smooth version of the same function to demonstrate that virtually the same result is achieved in both c
8. in seconds that is taken to set up the optimization problem and distribute data SOLUTION_COUNT indicates number of solutions that are returned in the PRIMALIN data set 1f that option was specified SOLUTION_TIME indicates the real time in seconds that is taken by the procedure to perform iterations for solving the problem Examples OPTLSO Procedure Example 3 1 Using Dense Format This example uses data from Floudas and Pardalos 1992 and illustrates how to use the VARIABLES and LINCON options in conjunction with the OBJECTIVE option The problem has nine linear constraints and a quadratic objective function Suppose you want to minimize 4 4 13 FO 5 4 59 Y xi i 5 i 1 i 1 subject to 2x1 2x2 x10 x11 lt 10 2X1 2x3 x10 x12 lt 10 2x1 2x3 x11 x12 lt 10 8x x10 lt 0 8x2 x11 lt 0 8x3 x12 lt 0 2x4 x5 X19 lt 0 2x6 x7 x11 lt 0 2xg X9 x12 lt 0 and 0 lt x lt 1 1 1 0 lt x lt 100 i 10 11 12 0O lt x13 lt 1l 44 Chapter 3 The OPTLSO Procedure The following statements use the dense format to define the linear constraints data vardata input _id _1b ub_ datalines x1 0 1 x2 0 1 x3 0 1 x4 0 1 x5 0 1 x6 0 1 x7 0 1 x8 0 1 x9 0 1 x10 0 100 x11 0 100 x12 0 100 x13 0 1 proc fcmp outlib sasuser myfuncs mypkg function quadob3 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 suml 5x x1 x2 x3 x4
9. 2 x 10 a2 2x x 1 2 x 3 x 10 a3 2 x 1 2xx 3 x 11 a4 8xx 1 x 10 lt 0 a5 8x xx 2 x 11 lt 0 a6 8xx 3 x 12 lt 0 a7 2 x 4 x 5 x 10 a8 2x x 6 x 7 x 11 a9 2 x 8 x 9 x 12 save qps qpdata quit proc optlso primalout solution qpsdata qpdata performance nthreads 2 run proc print data solution run sum i in 5 13 x i x 11 lt x 12 lt x 12 lt lt 0 lt 0 lt 0 Note that in this case the objective definition is taken directly from the QPS data set gpdata Output 3 3 1 shows the output from running these steps 50 Chapter 3 The OPTLSO Procedure Output 3 3 1 Using QPS Format The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 Problem Summary Problem Type QP QPS Data Set QPDATA Number of Variables 13 Integer Variables 0 Continuous Variables 13 Number of Constraints 9 Linear Constraints 9 Nonlinear Constraints 0 Objective Definition Source QPDATA Objective Sense Minimize Solution Summary Solution Status Function convergence Objective 15 00099275 Infeasibility 0 0009927519 Iterations 32 Evaluations 3956 Cached Evaluations 356 Global Searches 1 Population Size 160 Seed 1 Example 3 4 Combining MPS and FCMP Function Definitions 51 Output 3 3 1 continued Obs _sol_ _id_ _value_ 1 O _obj_ 15 0010 2 O_inf_ 0 0010 3
10. 32 1805 Cached Evaluations 36 Global Searches Population Size Seed Obs _sol_ 1 2 3 4 5 1 80 1 _id_ _value_ 0 _obj_ 0 39789 O _inf_ 0 00000 0 x1 9 42482 0 x2 2 47508 Of 0 39789 You can use a LINCON option to specify general linear equality or inequality constraints of the following form n Y ayx lt gt b fort Lo m J 1 18 Chapter 3 The OPTLSO Procedure For example suppose that in addition to the bound constraints on the decision variables you need to guarantee that the sum x x2 is less than or equal to 0 6 To guarantee this you can add a LINCON option to the previous data set definitions as in the following statements data lindata input id lb x1 x2 _ub datalines al 11 0 6 a proc optlso variables vardata objective objdata lincon lindata run Here the symbol A1 denotes the name of the given linear constraints that are specified in the _ID_ column The corresponding lower and upper bounds are specified in the _LB_ and _UB_ columns respectively Nonlinear Constraints on the Decision Variables You can specify general nonlinear equality or inequality constraints by using the NLINCON option and adding its definition to the existing PROC FCMP library Consider the previous problem with the following additional constraint x 2x2 gt 14 You can specify this constraint by adding a new FCMP function library and providing it a corresponding name
11. 401 4796 0 000002728 0 21375 5 444 5000 0 000000698 0 23647 6 NOTE Function convergence criteria reached NOTE There were 2 observations read from the data set WORK VARDATA NOTE There were 2 observations read from the data set WORK OBJDATA NOTE The data set WORK SOLUTION has 25000 observations and 3 variables When solving a multiobjective problem with 2 objectives it can be useful to create a plot with PROC GPLOT of the Pareto optimal set returned by PROC OPTLSO Output 3 10 3 shows a plot of the Pareto optimal set found by PROC OPTLSO References 75 Output 3 10 3 Multiobjective Plot of Pareto optimal Set f2 5 4 3 J 44 1 3 2 1 ol POA A te ia 2 fh A E l 0 1 2 3 4 f1 References Bowman K O and Shenton L R 1983 Johnson s System of Distributions in S Kotz N L Johnson Sons and C B Read eds Encyclopedia of Statistical Sciences volume 4 303 314 New York John Wiley amp Coello Coello C A and Cruz Cortes N 2005 Solving Multiobjective Optimization Problems Using an Artificial Immune System Genetic Programming and Evolvable Machines 6 163 190 Cust dio A L Madeira J F A Vaz A I E and Vicente L N 2011 Direct Multisearch for Multiobjective Optimization SIAM Journal on Optimization 21 1109 1140 Floudas C A and Pardalos P M 1992 Recent Advances in Global Optimization Princeton NJ Princeton University
12. Constraints on page 33 PROC OPTLSO Statement 23 NLINCON SAS data set names the FCMP functions to be used from the current library as nonlinear constraints along with respective bounds This data set should contain three columns _ID_ to specify the corresponding FCMP function names and _LB_ and _UB_ to specify the lower and upper bounds for the corresponding constraints respectively For more information see the section Describing Nonlinear Constraints on page 34 OBJECTIVE SAS data set names the FCMP functions to be used from the current library to form the objective At a minimum this data set should have three columns _ID_ to specify the function name to be used internally by the solver FUNCTION_ to specify the corresponding FCMP function and _SENSE_ to specify whether the objective is to be minimized or maximized PROC OPTLSO enables you to implicitly define your objective function by using an external data set and an intermediate FCMP function definition that can be used as placeholders to store temporary terms with respect to the external data set For more information see the section Describing the Objective Function on page 28 PRIMALIN SAS data set specifies an initial sample set to be evaluated Initial data sets might be useful over a sequence of runs when you want to ensure that PROC OPTLSO generates points that are at least as good as your current best solution This option is more general than the FIRSTGEN
13. Griffin Kolda and Lewis 2008 If integer variables are present the _TYPE_ column value signifies that a given variable is either c for continuous or I for integer By default all variables are assumed to be continuous 28 Chapter 3 The OPTLSO Procedure You can use the VARIABLES option to specify the SAS data set that describes the variables to be optimized For example suppose you want to specify the following set of variables where x and x2 are continuous and x3 is an integer variable 0 lt x lt 1000 0 lt x2 lt 0 001 0 lt x3 lt 4 You can specify this set of variables by using the following DATA step data vardata input _id _lb ub type _ datalines x1 01000 C x2 0 0 001 C x3 04 I r By default variables are automatically scaled PROC OPTLSO uses this scaling along with the cache tolerance when PROC OPTLSO builds the function value cache For more information about scaling see the section Function Value Caching on page 39 You can provide your own scaling by setting a _SCALE_ column in the variable data set as follows data vardata input _id _lb ub type _scale datalines x1 01000 c 1000 x2 00 001C 0 5 x3 0 4 I 2 When derivative free optimization is performed proper scaling of variables can dramatically improve performance Default scaling takes into account the lower and upper bounds so you are encouraged to provide the best estimates possible Describing the O
14. PROC OPTLSO statement 23 LINCON option PROC OPTLSO statement 22 LOGFREQ option PROC OPTLSO statement 25 LOGLEVEL option PROC OPTLSO statement 25 MAXFUNC option PROC OPTLSO statement 24 MAXGEN option PROC OPTLSO statement 24 MAXTIME option PROC OPTLSO statement 24 MPSDATA option PROC OPTLSO statement 22 NGLOBAL option PROC OPTLSO statement 24 NLINCONZ option PROC OPTLSO statement 23 NLOCAL option PROC OPTLSO statement 24 OBJECTIVE option PROC OPTLSO statement 23 OPTLSO procedure PROC OPTLSO statement 21 PARETOMAX option PROC OPTLSO statement 25 PERFORMANCE statement OPTLSO procedure 25 POPSIZE option PROC OPTLSO statement 25 PRIMALIN option PROC OPTLSO statement 23 PRIMALOUT option PROC OPTLSO statement 24 PRINTLEVEL option PROC OPTLSO statement 25 PROC OPTLSO statement input data set options 22 optimization control options 24 output data set options 23 statement options 21 stopping condition options 24 technical options 25 QPSDATA option PROC OPTLSO statement 23 READARRAY statement OPTLSO procedure 26 SEED option PROC OPTLSO statement 25 VARIABLES option PROC OPTLSO statement 23
15. Press Goldberg D E 1989 Genetic Algorithms in Search Optimization and Machine Learning Reading MA Addison Wesley 76 Chapter 3 The OPTLSO Procedure Gray G A and Fowler K R 2011 The Effectiveness of Derivative Free Hybrid Methods for Black Box Optimization International Journal of Mathematical Modeling and Numerical Optimization 2 112 133 Gray G A Fowler K R and Griffin J D 2010 Hybrid Optimization Schemes for Simulation Based Problems Procedia Computer Science 1 1349 1357 Gray G A and Kolda T G 2006 Algorithm 856 APPSPACK 4 0 Asynchronous Parallel Pattern Search for Derivative Free Optimization ACM Transactions on Mathematical Software 32 485 507 Griffin J D Fowler K R Gray G A and Hemker T 2011 Derivative Free Optimization via Evolutionary Algorithms Guiding Local Search EAGLS for MINLP Pacific Journal of Optimization 7 425 443 Griffin J D and Kolda T G 2010a Asynchronous Parallel Hybrid Optimization Combining DIRECT and GSS Optimization Methods and Software 25 797 817 Griffin J D and Kolda T G 2010b Nonlinearly Constrained Optimization Using Heuristic Penalty Methods and Asynchronous Parallel Generating Set Search Applied Mathematics Research Express 2010 36 62 Griffin J D Kolda T G and Lewis R M 2008 Asynchronous Parallel Generating Set Search for Linearly Constrained Optimiza
16. Using External Data Sets This example illustrates the use of external data sets that are specified in the OBJECTIVE option The Bard function Mor Garbow and Hillstrom 1981 is a least squares problem that has n 3 parameters and m 15 functions fk 1 15 FO 22 fee x 1 x2 x3 where k E TE Uk X2 WKX3 with vy 16 k wz min uz vz and y 0 14 0 18 0 22 0 25 0 29 0 32 0 35 0 39 0 37 0 58 0 73 0 96 1 34 2 10 4 39 The minimum function value f x 4 107E 3 occurs at the point 0 08 1 13 2 34 In this example the additional variable bounds 1000 lt x lt 1000 fori 1 2 3 are added There are three approaches to specifying the objective function The first approach assumes that the necessary data are stored within the FCMP function In this case you can specify the objective function without using an external data set as follows 60 Chapter 3 The OPTLSO Procedure data vardata input _id _lb ub_ datalines x1 1000 1000 x2 1000 1000 x3 1000 1000 a data objdata input _id _function_ _sense_ datalines f bard min proc fcmp outlib sasuser myfuncs mypkg function bard x1 x2 x3 array y 15 nosym 0 14 0 18 0 22 0 25 0 29 0 32 0 35 0 39 0 37 0 58 0 73 0 96 1 34 2 10 4 39 fx 0 do k 1 to 15 vk 16 k wk min k vk fxk y k x1 k vk x2 wkx x3 fx fx f fxkxx2 end return 0 5xfx endsub run options
17. _ub_ datalines al 2 12 a2 2 1 1 a3 21 2 a data objdata input _id _function_ _sense_ datalines f sixhump min a proc fcmp outlib sasuser myfuncs mypkg function sixhump x1 x2 return 4 2 1xx1xx2 x1x 4 3 xx1xx2 x1xx2 4 4xx2xx2 x x2 x 2 endsub run options cmplib sasuser myfuncs proc optlso primalout solution variables xbnds objective objdata lincon lindata Example 3 5 Linear Constraints and a Nonlinear Objective 55 performance nthreads 2 run proc print data solution run Output 3 5 1 shows the output from running these steps Output 3 5 1 Linear Constraints and a Nonlinear Objective The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 Problem Summary Problem Type Linear Constraints Objective Definition Set OBJDATA NLP LINDATA Variables XBNDS Number of Variables 2 Integer Variables 0 Continuous Variables 2 Number of Constraints 3 Linear Constraints 3 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize Solution Summary Solution Status Objective Infeasibility Iterations Evaluations Function convergence 1 031628453 0 26 1474 Cached Evaluations 17 Global Searches Population Size Seed 1 80 1 Obs _sol_ _id_ _value_ O _obj_ 1 03163 1 n A WN 0 _inf_ 0 00000 0 x1 0 08983 0 x2 0 71265 Of
18. and bounds in the NLINCON option as in the following statements data condata input _id _1b ub_ datalines cl 14 proc fcmp outlib sasuser myfuncs mypkg function c1 x1 x2 return xlxx2 2xx2 endsub run proc optlso variables vardata objective objdata lincon lindata nlincon condata run By calling PROC FCMP a second time you can append the definition of C1 to your existing user library That is you do not need to redefine BRANIN after it has been added Introductory Examples 19 A Simple Maximum Likelihood Example The following is a very simple example of a maximum likelihood estimation problem that uses the log likelihood function I u 0 logto gt ELY The maximum likelihood estimates of the parameters u and o form the solution to max l 1 0 1 where o gt 0 and uo logto 5 ELY The following sets of statements demonstrate two ways to formulate this example problem data lkhvar input _id _lb datalines mu sigma 0 t data lkhobj1 input _id _function_ _sense_ datalines f loglkh1 max r In the following statements the FCMP function is stand alone because all the necessary data are defined within the function itself proc fcmp outlib sasuser myfuncs mypkg function loglkhl mu sigma array x 5 nosym 1 3 4 5 7 s 0 do j 1 to 5 s s log sigma 0 5x x 3 mu sigma x 2 end return s
19. are treated as black box constraints and can degrade performance If you have only a few variables and linear constraints you might prefer to use the dense format to describe your linear constraints by specifying both the LINCON option and the VARIABLES option Suppose a problem has the following linear constraints l lt 2x1 4x3 lt 15 1 lt 3x 7x2 lt 13 x x2 x3 11 The following DATA step formulates this information as an input data set for PROC OPTLSO data lcondata input _id_ _1b_ x1 x3 _ub_ datalines al 1 2 0 4 15 a2 1 37 013 a3 11 11 1 11 Linear constraints are handled by using tangent search directions that are defined with respect to nearby constraints The metric that is used to determine when a constraint is sufficiently near might cause the algorithm to temporarily treat range constraints as equality constraints For this reason it is preferable that you not separate a range constraint into two inequality constraints For example although both of the following range constraint formulations are equivalent the former is preferred 1 lt 2x1 4x3 lt 15 and 2x 4x3 lt 15 1 lt 2x1 4x3 Even for a moderate number of variables and constraints using the dense format to describe the linear constraints can be burdensome As an alternative you can construct a sparse formulation by using MPS format or QPS format SAS data sets and specifying the MPSDATA or QPSDATA opt
20. cmplib sasuser myfuncs proc optlso primalout solution variables vardata objective objdata performance nthreads 2 run proc print data solution run Output 3 7 1 shows the output from running these steps Output 3 7 1 Using External Data Sets The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 Example 3 7 Using External Data Sets 61 Output 3 7 1 continued Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 3 Integer Variables 0 Continuous Variables 3 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize Solution Summary Solution Status Function convergence Objective 0 0041074417 Infeasibility 0 Iterations 73 Evaluations 6261 Cached Evaluations 91 Global Searches 1 Population Size 120 Seed 1 Obs _sol_ _id_ _value_ 1 0 _obj_ 0 00411 2 0 _inf_ 0 00000 3 0x1 0 08239 4 0x2 1 13238 5 0x3 234437 6 Of 0 00411 This approach is cumbersome if the size of the required data increases A second approach for medium sized data sets is to use the READ_ARRAY statement within the FCMP function definition Because the environment might be distributed PROC OPTLSO requires a list of all data sets that are used in FCMP function definitions to ensure that the corresponding data sets are available This list s
21. ensure deterministic results MAXGEN specifies the maximum number of genetic algorithm iterations The default is 500 MAXTIME r specifies an upper limit in seconds on the real time used in the optimization process The actual running time of PROC OPTLSO optimization might be longer because the actual running time includes the remaining time needed to finish current function evaluations the time for the output of the temporary results and if required the time for saving the results to appropriate data sets By default the MAXTIMEZ option is not used Optimization Control Options You can specify the following options to tailor the solver to your specific optimization problem FEASTOL r specifies a feasibility tolerance for provided constraints Specify r gt 1E 9 The default is r 1E 3 NGLOBAL i specifies the number of genetic algorithms to create with each algorithm working on a separate population of the size specified by the POPSIZE option Specify as an integer greater than 0 NLOCAL specifies the number of local solvers to create Specify as an integer greater than 0 The default is twice the number of variables in the problem PERFORMANCE Statement 25 POPSIZE specifies the population size for the genetic algorithm to use The default is 40 x ceil log n 1 where n denotes the number of variables Technical Options You can specify the following technical options CACHEMAX specifies the maximum n
22. if you prefer that the rows of the data sets correspond to individual points you can use the following statements to transpose the returned data set where popout denotes the data set that is returned by PROC OPTLSO proc transpose data popout out poprow drop _label name_ by _sol_ var _value_ id _id run Function Value Caching To improve performance the OPTLSO procedure implements a caching system This caching system helps reduce the overall workload of the solver by eliminating duplicate function evaluations As the individual optimizers citizens submit new trial points for evaluation the points are saved in the cache along with their function evaluation values Then before beginning the potentially expensive function evaluations for a new trial point PROC OPTLSO determines whether a similar point already exists within the cache If a similar point is found in the cache its function values are immediately returned for the newly submitted point Returning function values from the cache instead of duplicating the effort of computing new function values can lead to significant performance improvements for the overall procedure The cache is implemented as a splay tree similar to that used in Gray and Kolda 2006 Hough Kolda and Patrick 2000 The splay tree rebalances itself as new points are added to the cache This rebalancing ensures that recently added or accessed points are maintained at the root of the tree and
23. option because points that are defined in this data set might or might not be used to define the initial population for the genetic algorithm GA For more information see the section Specifying and Returning Trial Points on page 38 QPSDATA SAS data set specifies a data set that can be used as a sparse alternative to the LINCON option which uses a dense format to define variables Quadratic programming system QPS is a common file format for representing linear and mixed integer mathematical programs that have quadratic terms in the objective function This option differs from the MPSDATA option in that any quadratic terms in the objective can be included in the data set Do not use this option if the problem does not have quadratic terms For an example of using PROC OPTMODEL to create the corresponding QPS file see Example 3 3 Using QPS Format on page 49 Internally binary variables are converted into integer variables with lower and upper bounds of 0 and 1 respectively VARIABLES SAS data set stores the variable names bounds type and scale These names must match corresponding names FCMP functions and related data sets For more information see the section The Variable Data Set on page 27 Output Data Set Options You can specify the following options that are related to output data sets CACHEOUT SAS data set specifies the data set to which all completed function evaluations are output For more information
24. optmodel var x 1 10 gt 0 x 10 1b 1 x 10 ub 3 x 1 ub 100 x 2 ub 200 con x 3 x 4 x 6 x 7 x 6 x 8 x 1 Example 3 6 Using Nonlinear Constraints 57 x 7 x 9 x 2 x 8 x 9 x 5 max f 9xx 1 15 x 2 6 x 3 16 x 4 10 x 5 save mps nlcexOld quit lsompsmod nlcexOld nlcex proc fcmp outlib sasuser myfuncs mypkg function nlcl x1 x6 x8 x10 return 2 5 xl x10 x6 2x x8 endsub function nlc2 x2 x7 x9 x10 return 1 5 x2 x10 x7 2x x9 endsub function nlc3 x3 x4 x10 return 3 x3 x4 x10x x3 x4 endsub run data condata input _id _lb ub_ datalines nlcl 0 nlc2 0 nlc3 0 0 a options cmplib sasuser myfuncs proc optlso primalout solution mpsdata nlcex nlincon condata logfreq 10 performance nthreads 2 run proc print data solution run Output 3 6 1 shows the ODS tables that are produced from running these steps Output 3 6 1 Using Nonlinear Constraints ODS Tables The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 58 Chapter 3 The OPTLSO Procedure Output 3 6 1 continued Problem Summary Problem Type NLP MPS Data Set NLCEX Nonlinear Constraints CONDATA Number of Variables 10 Integer Variables 0 Continuous Variables 10 Number of Constraints 7 Linear Constraints 4 Nonlinear Constraints 3 Objective Definition Sour
25. procedure in Base SAS Procedures Guide Further not all PROC FCMP functionality is currently compatible with PROC OPTLSO in particular the following FCMP functions are not supported and should not be called within your FCMP function definitions WRITE_ARRAY RUN_MACRO and RUN_SASFILE The READ_ARRAY function is supported however the corresponding data sets that are used must be listed in a separate statement of PROC OPTLSO see the section READARRAY Statement on page 26 and the second program in Example 3 7 Using External Data Sets on page 59 After you define your objective and constraint functions you must specify the libraries by using the CMPLIB system option in the OPTIONS statement For more information about the OPTIONS statement see SAS Statements Reference For more information about the CMPLIB system option see SAS System Options Reference The Variable Data Set The variable data set can have up to five columns The variable names are described in the _ID_ column These names are used to map variable values to identically named FCMP function variable arguments Lower and upper bounds on the variables are defined in columns _LB_ and _UB_ respectively You can manually enter scaling for each variable by using the _SCALE_ column Derivative free optimization performance can often be greatly improved by scaling the variables appropriately By default the scale vector is defined in a manner similar to that described in
26. see the section Specifying and Returning Trial Points on page 38 LASTGEN SAS data set specifies the data set to which the members of the current genetic algorithm population are returned on exit If more than one genetic algorithm is used the data set combines the members from each population into a single data set 24 Chapter 3 The OPTLSO Procedure PRIMALOUT SAS data set specifies the output solution set You can use this data set in future solves as the input set for the PRIMALIN option For more information see the section Specifying and Returning Trial Points on page 38 Stopping Condition Options You can specify the following options that determine when to stop optimization ABSFCONV n specifies an absolute function convergence criterion PROC OPTLSO stops when the changes in the objective function and constraint violation values in successive iterations meet the criterion IEF SQP IED OGM lt r where 0 x denotes the maximum constraint violation at point x The optional integer value n specifies the number of successive iterations for which the criterion must be satisfied before the process is terminated The default is r 1E 6 and n 10 To cause an early exit you must specify a value for n that is less than the value of the MAXGEN option MAXFUNC specifies the maximum number of function calls in the optimization process The actual number of function evaluations can exceed this number in order to
27. sum2 5x x1l 2 x2 2 x3xx2 x4xx2 sum3 x5 x6 x7 x8 x9 x10 x11 x12 x13 return suml sum2 sum3 endsub run data objdata input _id function _sense_ datalines f quadob3 min data lindata input _id_ _1b_ x1 x13 _ub_ datalines al 2 2 0 O O O 0 0 0110010 a2 2 0 2 0 O O 0 0 0101010 ad 2 0 2 0 O O O 0 0011010 a4 8 00 O O O O 0 01000 0 a5 0 8 0 0 0 O O 0 00100 0 a6 0 0 8 0 0 0 0 0 00010 0 a7 0 0 0 2 1 0 0 0 01000 0 a8 0 0 0 0 0 2 1 0 00100 0 a9 0 00 0 0 0 0 2 10010 0 options cmplib sasuser myfuncs proc optlso primalout solution objective objdata variables vardata Example 3 1 Using Dense Format 45 lincon lindata performance nthreads 2 run proc print data solution run The VARIABLES VARDATA option in the PROC OPTLSO statement specifies the variables and their respective bounds The objective function is defined by using PROC FCMP and the objective function name QUADOBJ Other properties are described in the SAS data set objdata The linear constraints are specified by using the SAS data set lindata in which each row stores the zero and nonzero coefficients of the corresponding linear constraint along with their respective lower and upper bounds The problem description is then passed to the OPTLSO procedure by using the options VARIABLES VARDATA OBJECTIVE OBJDATA and LINCON LINDATA The PERFORMANCE statement specifies the number of threads that
28. work such as when the objective function has many local The OPTLSO Algorithm 35 optima when the objective function is not differentiable or continuous or when solution elements are constrained to be integers or sequences In most cases genetic algorithms require more computation than specialized techniques that take advantage of specific problem structures or characteristics However for optimization problems for which no such techniques are available genetic algorithms provide a robust general method of solution In general genetic algorithms use some variation of the following process to search for an optimal solution initialization An initial population of solutions is randomly generated and the objective function is evaluated for each member of this initial iteration selection Individual members of the current iteration are chosen stochas tically either to parent the next iteration or to be passed on to it such that the members that are the fittest are more likely to be selected A solution s fitness is based on its objective value with better objective values reflecting greater fitness crossover Some of the selected solutions are passed to a crossover op erator The crossover operator combines two or more parents to produce new offspring solutions for the next iteration The crossover operator tends to produce new offspring that retain the common characteristics of the parent solutions while combining the other trai
29. ASTGEN on exit Stopping Condition Options Specifies the absolute function convergence criterion ABSFCONV Specifies the maximum number of function evaluations MAXFUNC Specifies the maximum number of genetic algorithm MAXGEN iterations Specifies the upper limit on real time MAXTIME 22 Chapter 3 The OPTLSO Procedure Description option Optimization Control Options Specifies the feasibility tolerance FEASTOL Specifies the number of global searches NGLOBAL Specifies the number of local searches NLOCAL Genetic algorithm population size POPSIZE Technical Options Specifies the cache tolerance CACHETOL Specifies the maximum cache size CACHEMAX Specifies the maximum size of the Pareto optimal set PARETOMAX Specifies how frequently to print the solution progress LOGFREQ Specifies how much detail of solution progress to printin LOGLEVEL the log Enables or disables the printing summary PRINTLEVEL Initializes the seed for sampling routines SEED Input Data Set Options You can specify the following options that are related to input data sets CACHEIN SAS data set names a previously computed sample set Using a previously computed sample set enables PROC OPTLSO to warm start It is crucial that the nonlinear objective and function values be identical to those that were used when the cache data set was generated For more information see the section Specifying and Returning Trial Points on page 38 FIRSTGEN SAS data
30. For example if the problem is convex a local algorithm should be sufficient and the application of the global algorithm would create unnecessary overhead If the problem instead has many local minima failing to run a global search algorithm first could result in an inferior solution Rather than attempting to guess which paradigm is best PROC OPTLSO simultaneously performs global and local searches while continuously sharing computational resources and function evaluations The resulting run time and solution quality should be similar to having automatically selected the best global and local search combination given a suitable number of threads and processors Moreover because information is shared the robustness of the hybrid approach can be increased over hybrid combinations that simply use the output of one algorithm to hot start the second Getting Started OPTLSO Procedure 15 algorithm In this chapter the term solver refers to an implementation of one or more algorithms that can be used to solve a problem The OPTLSO procedure uses different strategies to handle different types of constraints Linear constraints are handled by using both linear programming and strategies similar to those in Griffin Kolda and Lewis 2008 where tangent directions to nearby constraints are constructed and used as search directions Nonlinear constraints are handled by using smooth merit functions Griffin and Kolda 2010b Integer and categorical variab
31. OOOO GSas s SAS OR 13 2 User s Guide Local Search Optimization The OPTLSO Procedure The correct bibliographic citation for this manual is as follows SAS Institute Inc 2014 SAS OR 13 2 User s Guide Local Search Optimization Cary NC SAS Institute Inc SAS OR 13 2 User s Guide Local Search Optimization Copyright 2014 SAS Institute Inc Cary NC USA All rights reserved Produced in the United States of America For a hard copy book No part of this publication may be reproduced stored in a retrieval system or transmitted in any form or by any means electronic mechanical photocopying or otherwise without the prior written permission of the publisher SAS Institute Inc For a Web download or e book Your use of this publication shall be governed by the terms established by the vendor at the time you acquire this publication The scanning uploading and distribution of this book via the Internet or any other means without the permission of the publisher is illegal and punishable by law Please purchase only authorized electronic editions and do not participate in or encourage electronic piracy of copyrighted materials Your support of others rights is appreciated U S Government License Rights Restricted Rights The Software and its documentation is commercial computer software developed at private expense and is provided with RESTRICTED RIGHTS to the United States Government Use duplication or discl
32. OPTLSO procedure along with the statement and option specifications that are required to produce each table Table 3 4 ODS Tables Produced by PROC OPTLSO ODS Table Name Description Statement Option ProblemSummary Summary of the input optimization PROC OPTLSO PRINTLEVEL 1 problem default SolutionSummary Summary of the solution status PROC OPTLSO PRINTLEVEL 1 default Performancelnfo List of performance options and PROC OPTLSO PRINTLEVEL 1 their values default Timing Detailed solution timing PERFORMANCE DETAILS 42 Chapter 3 The OPTLSO Procedure Macro Variable OROPTLSO _ The OPTLSO procedure defines a macro variable named OROPTLSO_ This variable contains a character string that indicates the status of the procedure upon termination The contents of the macro variable are interpreted as follows STATUS indicates the procedure s status at termination It can take one of the following values OK SYNTAX_ERROR DATA_ERROR OUT_OF_MEMORY IO_ERROR SEMANTIC_ERROR ERROR SOLUTION_STATUS The procedure terminated normally The use of syntax is incorrect The input data are inconsistent Insufficient memory was allocated to the procedure A problem in reading or writing of data has occurred An evaluation error such as an invalid operand type has occurred The status cannot be classified into any of the preceding categories indicates the status of the solution at termination It can take one of the fol
33. Ox 1 1 0000 4 ox 1 0000 5 0x B3 1 0000 6 0x 4 1 0000 7 0x5 1 0000 8 0x 6 1 0000 9 0x 7 1 0000 10 0x 8 1 0000 11 0x9 1 0000 12 0x 10 3 0000 13 0x 11 3 0000 14 0 x 12 3 0010 15 0x 13 1 0000 16 Oz 15 0010 Example 3 4 Combining MPS and FCMP Function Definitions In this example the linear component of the same problem definition as in Example 3 1 is described by using the OPTMODEL procedure and is saved as an MPS data set The quadratic component of the objective is then defined by using the FCMP function QUADOBJ As in Example 3 2 Using MPS Format on page 46 you can use the macro definition Isompsmod to strip brackets from the resulting data set macro lsompsmod setold setnew data amp setnew drop i set amp setold array FC _CHARACTER_ do i 1 to dim FC FC i compress FC i end run Smend For more complicated array structures take care to ensure that the resulting transformation is well defined Next you run a PROC OPTMODEL step that outputs a MPS data set followed by the 7LSOMPSMOD macro followed by the PROC FCMP step that defines the FCMP function QUADOBJ followed by a PROC OPTLSO step that takes as input both the MPS data set that was output by PROC OPTMODEL and transformed by the LSOMPSMOD macro and the quadratic component of the objective that was defined by PROC FCMP 52 Chapter 3 The OPTLSO Procedure proc optmodel var x 1 13 gt 0 lt 1 for i
34. PROC OPTLSO can use Output 3 1 1 shows the output from running these statements Output 3 1 1 Using Dense Format The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 Problem Summary Problem Type NLP Linear Constraints LINDATA Objective Definition Set OBJDATA Variables VARDATA Number of Variables 13 Integer Variables 0 Continuous Variables 13 Number of Constraints 9 Linear Constraints 9 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize _ 46 Chapter 3 The OPTLSO Procedure Output 3 1 1 continued Solution Summary Solution Status Function convergence Objective 15 00099275 Infeasibility 0 0009927519 Iterations 32 Evaluations 3956 Cached Evaluations 356 Global Searches 1 Population Size 160 Seed 1 Obs _sol_ _id_ _value_ 1 O _obj_ 15 0010 2 0 _inf_ 0 0010 3 0x 1 0000 4 0x2 1 0000 5 0x3 1 0000 6 0x4 1 0000 7 0x5 1 0000 8 0x6 1 0000 9 0x 1 0000 10 0x8 1 0000 1 0x9 1 0000 12 0x10 3 0000 13 0x11 3 0000 14 0x12 3 0010 15 0x13 1 0000 16 Of 15 0010 Example 3 2 Using MPS Format In this example the linear component of the same problem definition as in Example 3 1 is described by using the OPTMODEL procedure and is saved as an MPS data set The quadratic objective is then defined by using the FCMP function QUADOBJ Because PROC OPTMODEL outputs an MPS data set that uses array notation you can use the fo
35. a real vector or integer sequence and by applying crossover and mutation operators that are analogous to the traditional genetic operators but are more appropriate to the natural formulation of the problem Although genetic algorithms have been demonstrated to work well for a variety of problems there is no guarantee of convergence to a global optimum Also the convergence of genetic algorithms can be 36 4 Chapter 3 The OPTLSO Procedure sensitive to the choice of genetic operators mutation probability and selection criteria so that some initial experimentation and fine tuning of these parameters are often required The OPTLSO procedure seeks to automate this process by using hybrid optimization in which several genetic algorithms can run in parallel and each algorithm is initialized with different default option settings PROC OPTLSO also adds a step to the GA this step permits generating set search GSS algorithms to be used on a selected subset of the current population GSS algorithms are designed for problems that have continuous variables and have the advantage that in practice they often require significantly fewer evaluations than GAs to converge Furthermore GSS can provide a measure of local optimality that is very useful in performing multimodal optimization The following additional growth steps are used whenever continuous variables are present local search selection A small subset of points are selected based on th
36. andled Iteration Log The iteration log provides detailed information about the progress of the OPTLSO procedure The log appears by default or if LOGLEVEL 1 The iteration log provides the following information Iteration Displays the number of completed genetic algorithm iterations Best Objective Displays the best objective found at each iteration with respect to the current setting of the FEASTOL option NOTE This column is included only for single objective optimization Nondom Displays the number of nondominated solutions in the current Pareto optimal set NOTE This column is included only for multiobjective optimization Progress Displays a numerical indication of the progress being made from one iteration to the next For a description of how this value is computed see the section Multiobjective Optimization on page 36 NOTE This column is included only for multiobjective optimization Infeasibility Displays the aggregate constraint violation of the current best point Evals Displays the cumulative number of function evaluations Time Displays the time needed to achieve current best solution Procedure Termination Messages After PROC OPTLSO terminates one of the following messages is displayed User interrupted The procedure was interrupted by the user Function convergence criteria reached The best objective value and feasibility have not sufficiently improved for the specified number of iterations This
37. are therefore available for quick retrieval This splay tree data structure lends itself nicely to the needs of a caching system When determining whether a newly submitted trial point has a similar point already in the cache PROC OPTLSO compares the new trial point to all previous trial points by using the value of the CACHETOL option in the PROC OPTLSO statement This value specifies a tolerance to use in comparing two points and determining whether the two points are similar enough In addition to the CACHETOL value the cache comparison also takes into account the _SCALE_ values that are specified as part of the variable data set that 1s specified in the VARIABLES option 40 4 Chapter 3 The OPTLSO Procedure Two points x and y are considered cache equivalent if x yil lt sje fori 1 n where s denotes the corresponding scaling vector Thus if a point x has been evaluated or is being evaluated and a point y is submitted for evaluation and satisfies the preceding criteria y is cache evaluated instead of being evaluated directly In this case y is associated with f x and c x Although the splay tree is very efficient the cache lookup time for quick evaluation might eventually dominate the evaluation process time You can use the CACHEMAX option to limit the size of the cache Even when the FCMP functions are not defined the cache system helps to avoid redundant computations when the linear constraints are explicitly h
38. ases Slet N 100 Slet L 0 Slet U 10 options cmplib sasuser myfuncs proc fcmp outlib sasuser myfuncs mypkg function SmoothFunc x y xxsin x x xxcos x return y endsub run Example 3 9 Discontinuous Function with a Lookup Table 71 data vardata input _id _1b ub_ datalines x 0 10 Use the smooth function as the objective x data objdata length _function_ 16 input _id function _sense_ datalines f SmoothFunc min options cmplib sasuser myfuncs proc optlso primaluut finalsol variables vardata objective objdata run proc print data finalsol run Output 3 9 2 shows the ODS tables that are produced Output 3 9 2 Smooth Function ODS Tables The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 4 Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 1 Integer Variables 0 Continuous Variables 1 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize 72 Chapter 3 The OPTLSO Procedure Output 3 9 2 continued Solution Summary Solution Status Function convergence Objective 93 22152602 Infeasibility 0 Iterations 19 Evaluations 475 Cached Evaluations 80 Global Searches 1 Population Size 40 Seed 1 Obs _sol_ _id_ _value_ 2 O _inf_ 0 0000 3 0 x 9 7269 4 of 93 2215
39. bjective Function PROC OPTLSO enables you to define the function explicitly by using PROC FCMP The following statements describe a PROC FCMP objective function that is used in Example 3 5 Linear Constraints and a Nonlinear Objective on page 54 proc fcmp outlib sasuser myfuncs mypkg function sixhump x1 x2 return 4 2 1xx1xx2 x1 4 3 x1 2 x1l x2 4 4xx2xx2 xx2xx2 endsub run Because PROC FCMP writes to an external library that might contain a large number of functions PROC OPTLSO needs to know which objective function in the FCMP library to use and whether to minimize or maximize the function You provide this information to PROC OPTLSO by specifying an objective Describing the Objective Function 29 description data set in the OBJECTIVE option To minimize the function sixhump you could specify the OBJECTIVE objdata option and define the following objective description data set data objdata input _id _function_ _sense_ datalines f sixhump min In the preceding DATA step the _ID_ column specifies the function name to be used internally by the solver the _FUNCTION_ column specifies the corresponding FCMP function name and the _SENSE_ column specifies whether the objective is to be minimized or maximized Intermediate Functions You can use intermediate functions to simplify the objective function definition and to improve computational efficiency You specify intermediate functions by u
40. ble you to attack multiobjective problems directly in order to evolve a set of Pareto optimal solutions in one run of the optimization process instead of solving multiple separate problems In addition local searches in neighborhoods around nondominated points can be conducted to improve objective function values and reduce crowding Because the number of nondominated points that are encountered might be greater than the total population size PROC OPTLSO stores nondominated points in an archived set M you can specify the PARETOMA X option to control the size of this set Although it is difficult to verify directly that a point lies on the true Pareto optimal frontier without using derivatives convergence can indirectly be measured by monitoring movement of the population with respect to N the current set of nondominated points A number of metrics for measuring convergence in multiobjective evolutionary algorithms have been suggested such as the generational distance by Van Veldhuizen 1999 the inverted generational distance by Coello Coello and Cruz Cortes 2005 and the averaged Hausdorff distance by Schiitze et al 2012 PROC OPTLSO uses a variation of the averaged Hausdorff distance that is extended for general constraints Distance between sets is computed in terms of the distance between a point and a set which in turn is defined in terms of the distance between two points The distance measure used by PROC OPTLSO for two points x and y
41. bservation of the data set that is generated by the following DATA step data sudata n 20000 theta 1 sigma 1 delta 3 gamma 5 rngSeed 123 do i 1 to n z rannor rngSeed a exp z gamma delta d sigma ax 2 1 2 a theta output end keep d run This generates a data set called sudata that contains n 20 000 observations You can modify n to increase or decrease the computational work per function evaluation The following call to PROC FCMP defines the corresponding FCMP function definition proc fcmp outlib sasuser myfuncs mypkg function jsu x4 x2 f1 return 20000x log x4 log x2 1 endsub function jsul x1 x2 x3 x4 d yk d x1 x2 zk yk sqrt 1 ykx x 2 return 0 5 x3 x4xlog zk 2 0 5x log 1 ykx x2 endsub run options cmplib sasuser myfuncs In the following steps the assumption for the definition of jsu and jsu1 is that jsu1 is called once for each line of data in this case 20 000 times and cumulatively summed The resulting value is then provided to the function jsu for a final calculation which is called only once per evaluation of f x data objdata input _id _function_ _sense_ _dataset_ datalines f1 jsul sudata f jsu max data vardata input id lb _ub_ datalines Example 3 8 Johnson s Systems of Distributions 67 x1 x2 le 12 x3 x4 le 12 r proc optlso primalout solution objec
42. ce NLCEX Objective Sense Maximize Solution Summary Solution Status Function convergence Objective 400 0059833 Infeasibility 0 0009972793 Iterations 34 Evaluations 4054 Cached Evaluations 435 Global Searches 1 Population Size 160 Seed 1 Obs _sol_ _id_ _value_ 1 0 _obj_ 400 006 2 O_inf 0 001 3 0x 0 000 4 0x2 200 000 5 0x3 0 000 6 0x4 99 999 7 0x5 100 001 8 0x6 0 000 9 0x7 99 999 10 0x8 0 000 11 0x9 100 001 12 0x10 1 000 13 Of 400 006 14 Onlct 0 000 15 0nlc2 0 001 16 Onlc3 0 000 Output 3 6 2 shows the iteration log from running these steps Example 3 7 Using External Data Sets 59 Output 3 6 2 Using Nonlinear Constraints Log NOTE The OPTLSO procedure is executing in single machine mode NOTE The OPTLSO algorithm is using up to 2 threads NOTE The problem has 10 variables 0 integer 10 continuous NOTE The problem has 7 constraints 4 linear 3 nonlinear NOTE The problem has 3 FCMP function definitions NOTE The deterministic parallel mode is enabled Best Iteration Objective Infeasibility Evals Time 1 0 0 170 0 11 399 9157119539 0 1299 0 21 400 004880426434 0 0008133715544 2448 o 31 400 005983302901 0 00099727927424 3685 0 34 400 005983302901 0 00099727927424 4054 o NOTE Function convergence criteria reached NOTE There were 3 observations read from the data set WORK CONDATA NOTE The data set WORK SOLUTION has 16 observations and 3 variables Example 3 7
43. criterion is a typical exit state if the global optimum is reached early in the algorithm ODS Tables 41 Maximum function evaluations reached PROC OPTLSO has attempted to exceed the maximum number of function evaluations Generations complete The maximum number of GA generations iterations has been reached At this point no new points are generated and the algorithm exits Maximum time reached PROC OPTLSO has exceeded the maximum allotted time Problem may be unbounded The objective value appears to take on arbitrarily large values at points that satisfy the feasibility tolerance Infeasible The problem is infeasible Failed The algorithm exited for any reason other than the preceding reasons For example this message is displayed if the provided FCMP function does not exist or cannot be evaluated ODS Tables PROC OPTLSO creates three Output Delivery System ODS tables by default The first table ProblemSum mary is a summary of the input problem The second table SolutionSummary is a brief summary of the solution status The third table PerformancelInfo is a summary of performance options You can use ODS table names to select tables and create output data sets For more information about ODS see SAS Output Delivery System Procedures Guide If you specify the DETAILS option in the PERFORMANCE statement then the Timing table is also produced Table 3 4 lists all the ODS tables that can be produced by the
44. data sets are available PROC OPTLSO also requires that the names of these data sets be provided as a list of names in the READARRAY statement For an example see the second program in Example 3 7 Using External Data Sets on page 59 The following example creates and reads a SAS data set into an FCMP array variable data barddata input y datalines 0 14 0 18 0 22 0 25 0 29 0 32 0 35 0 39 0 37 0 58 0 73 0 96 1 34 2 10 4 39 proc fcmp outlib sasuser myfuncs mypkg function bard x1 x2 x3 array y 15 nosym re read_array barddata y fx 0 do k 1 to 15 dk 16 k x2 min k 16 k x3 fxk y k x1 k dk fx fx f fxkxx2 end return 0 5x fx endsub run options cmplib sasuser myfuncs data _null _ bval bard 1 2 3 put bval run Here the call to READ_ARRAY in the PROC FCMP function definition of Bard populates the array Y with the rows of the BardData data set If the Bard function were subsequently used in a problem definition for PROC OPTLSO the BardData data set should be listed in the corresponding READARRAY statement of PROC OPTLSO as demonstrated in the second program in Example 3 7 Using External Data Sets on page 59 Details OPTLSO Procedure 27 Details OPTLSO Procedure The OPTLSO procedure uses a hybrid combination of genetic algorithms Goldberg 1989 Holland 1975 which optimize integer and continuous variables and generating set search Kolda Lewis and T
45. e Information Execution Mode Single Machine Number of Threads 2 48 Chapter 3 The OPTLSO Procedure Output 3 2 1 continued Problem Summary Problem Type NLP MPS Data Set LINDATA Objective Definition Set OBJDATA Number of Variables 13 Integer Variables 0 Continuous Variables 13 Number of Constraints 9 Linear Constraints 9 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize Solution Summary Solution Status Function convergence Objective 15 00099275 Infeasibility 0 0009927519 Iterations 32 Evaluations 3956 Cached Evaluations 356 Global Searches 1 Population Size 160 Seed 1 Obs _sol_ _id_ _value_ 1 0 _obj_ 15 0010 2 0 _inf_ 0 0010 3 0x 1 0000 4 0x2 1 0000 5 0x3 1 0000 6 0x4 1 0000 7 0x5 1 0000 8 0x6 1 0000 9 0x 1 0000 10 0x8 1 0000 1 0x9 1 0000 12 0x10 3 0000 13 0x11 3 0000 14 0x12 3 0010 15 0x3 1 0000 16 Of 150010 17 Oz 0 0000 Example 3 3 Using QPS Format 49 Example 3 3 Using QPS Format In this example the entire problem definition is first described in the following PROC OPTMODEL step and is then saved as a QPS data set in the subsequent PROC OPTLSO step In this case no FCMP function needs to be defined proc optmodel var x 1 13 gt 0 lt 1 for i in 10 12 x i ub 100 min con con con con con con con con con z 5xsum i in 1 4 x i 5xsum i in 1 4 x i 2 al 2x x 1 2 x
46. eir fitness score and distance to 1 other points and 2 pre existing locally optimal points local search optimization Local search optimization begins concurrently for each selected point The only modification made to the original optimization problem is that the variables lower and upper bounds are modified to temporarily fix integer variables to their current setting These additional growth steps are performed for each iteration they permit selected members of the population based on diversity and fitness to benefit from local optimization over the continuous variables If only integer variables are present this step is not used Multiobjective Optimization Many practical optimization problems involve more than one objective criterion so the decision maker needs to examine trade offs between conflicting objectives For example for a particular financial model you might want to maximize profit while minimizing risk or for a structural model you might want to minimize weight while maximizing strength The desired result for such problems is usually not a single solution but rather a range of solutions that can be used to select an acceptable compromise Ideally each point represents a necessary compromise in the sense that no single objective can be improved without worsening at least one remaining objective The goal of PROC OPTLSO in the multiobjective case is thus to return to the decision maker a set of points that represen
47. endsub run proc optlso variables lkhvar objective lkhob31 run Alternatively you can use an external data set to store the necessary observations and run PROC OPTLSO to feed each observation to an FCMP function that processes a single line of data In this case PROC OPTLSO 20 Chapter 3 The OPTLSO Procedure sums the results for you This mode is particularly useful when the data set is large and possibly distributed over a set of nodes as shown in Example 3 7 Using External Data Sets on page 59 The following statements demonstrate how to store the necessary observations in an external data set for use with PROC FCMP data logdata input x datalines 13457 a data lkhobj2 input _id _function_ _sense _dataset_ datalines loglkh2 max logdata a proc fcmp outlib sasuser myfuncs mypkg function loglkh2 mu sigma x return log sigma 0 5x x mu sigma 2 endsub run proc optlso variables objective run lkhvar lkhob32 In this case for each line of data in the data set logdata the FCMP function LOGLKH2 is called It is important that the non variable arguments of LOGLKH2 coincide with a subset of the column names in logdata in this case X However the order in which the variables and data column names appear is not important The following definition would work as well data lkhobj3 input _id function _sense _dataset_ datalines f loglkh3 max logdata
48. finition Source OBJDATA Objective Sense Minimize Objective Intermediate Functions 1 Solution Summary Solution Status Objective Infeasibility Iterations Evaluations Function convergence 15 00099275 0 0009927519 32 3956 Cached Evaluations 356 Global Searches Population Size Seed Obs _sol_ 1 0 0 O O NOUN PWN A b d 2 2 NOURA Y N 2 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 160 i id _value_ _obj_ 15 0010 _inf_ 0 0010 x1 1 0000 x2 1 0000 x3 1 0000 x4 1 0000 x5 1 0000 x6 1 0000 x7 1 0000 x8 1 0000 x9 1 0000 x10 3 0000 x11 3 0000 x12 3 0010 x13 1 0000 f 15 0010 f 4 9990 linobj 4 9990 54 4 Chapter 3 The OPTLSO Procedure Example 3 5 Linear Constraints and a Nonlinear Objective The problem in this example is to minimize the six hump camel back function Michalewicz 1996 Appendix B Minimize 4 x res 21 gt x x1x2 4 4x3 X3 subject to 2x x2 lt 2 xx gt 2 x 2x2 2 Providing derivative free algorithms with good estimates for lower and upper bounds often greatly improves performance because it prevents the algorithm from unnecessarily sampling in regions that you do not want to explore For this problem the following statements add the explicit variable bounds 2 lt x lt 2 and 2 lt x lt 2 data xbnds input _id _lb ub_ datalines xl 2 2 x2 2 2 data lindata input id lb x1 x2
49. hat AXBI and ONENORM are intermediate functions to be used as arguments of the objective function COMBINE which is of type MIN Of the three FCMP functions only F1 has requested data The entry Abdata specifies that the FCMP function AXBI should be called on each row of the data set Abdata and that the results should be summed This value is then specified as the first argument to the FCMP function COMBINE In this example Abdata is a data set that comes from the Work library However Abdata could just as easily come from a data set in a user defined library or even a data set that had been previously distributed 32 Chapter 3 The OPTLSO Procedure for example to a Teradata or Greenplum database If the data set Abdata is stored in a different library replace Abdata with libref Abdata in the data set Isqob1 The source of the data set is irrelevant to PROC OPTLSO You can omit F2 if you want to form the one norm directly in the aggregate function Thus an equivalent formulation would be as follows proc fcmp outlib sasuser myfuncs mypkg function combine2 x1 x2 x3 x4 x5 1 array x 5 f2 0 do j 1 to 5 f2 2 abs x 3 1 end return sqrt 1 2 endsub run In this case you define the objective name with a given target in a data set data lsqobj2 input _id _function_ _sense_ _dataset_ datalines f1 axbi Abdata f combine2 min r options cmplib sasuser myfuncs proc optlso variable
50. hould be specified by using the READARRAY statement 62 Chapter 3 The OPTLSO Procedure data barddata input y ee datalines 0 14 0 18 0 22 0 25 0 29 0 32 0 35 0 39 0 37 0 58 0 73 0 96 1 34 2 10 4 39 r data vardata input _id _lb ub_ datalines x1 1000 1000 x2 1000 1000 x3 1000 1000 F data objdata input _id _function_ _sense_ datalines f bard min t proc fcmp outlib sasuser myfuncs mypkg function bard x1 x2 x3 array y 15 nosym re read_array barddata y fx 0 do k 1 to 15 dk 16 k xx2 min k 16 k x3 fxk y k x1 k dk fx fx f fxkxx2 end return 0 5xfx endsub run options cmplib sasuser myfuncs proc optlso primalout solution variables vardata objective objdata readarray barddata run proc print data solution run Output 3 7 2 shows the output from running these statements Example 3 7 Using External Data Sets 63 Output 3 7 2 Using External Data Sets Il The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 4 Data Access Information Data Engine Role Path WORK BARDDATA V9 Input On Client Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 3 Integer Variables 0 Continuous Variables 3 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sen
51. in 10 12 x i ub 100 min linobj 5 sum i in 1 4 x i sum i in 5 13 x i con al 2 x 1 2 x 2 x 10 x 11 lt 10 con a2 2 x 1 2 x 3 x 10 x 12 lt 10 con a3 2 x 1 2 x 3 x 11 x 12 lt 10 lt con a4 8xx 1 x 10 lt 0 con a5 8xx 2 x 11 lt 0 con a6 8xx 3 x 12 lt 0 con a7 2xx 4 x 5 x 10 lt 0 con a8 2xx 6 x 7 x 11 lt 0 con a9 2xx 8 x 9 x 12 lt 0 save mps lindataOld quit lsompsmod lindataOld lindata proc fcmp outlib sasuser myfuncs mypkg function quadob3 x1 x2 x3 x4 f1 return f1 5x x1l 2 x2 x2 x3xx2 x4xx2 endsub run data objdata input _id function _sense_ datalines f1 linobj f quadobj min E options cmplib sasuser myfuncs proc optlso primalout solution mpsdata lindata objective objdata performance nthreads 2 run proc print data solution run Output 3 4 1 shows the output from running these steps Output 3 4 1 Using MPS Format The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 2 Example 3 4 Combining MPS and FCMP Function Definitions 53 Output 3 4 1 continued Problem Summary Problem Type NLP MPS Data Set LINDATA Objective Definition Set OBJDATA Number of Variables 13 Integer Variables 0 Continuous Variables 13 Number of Constraints Linear Constraints Nonlinear Constraints 0 Objective De
52. ing DATA step shows an example data set where k 3 data Abdata input _id al a2 a3 a4 a5 b datalines rowl 1 2 3 4 5 6 row2 7 8 9 10 11 12 row3 13 14 15 16 17 18 The following statements pass this information to PROC OPTLSO by adding the corresponding functions to the FCMP function library Sasuser Myfuncs Mypkg proc fcmp outlib sasuser myfuncs mypkg function axbi x1 x2 x3 x4 x5 a1l a2 a3 a4 a5 b array x 5 array a 5 di b do j 1 to 5 Describing the Objective Function 31 di di a j x jl end return dixdi endsub function onenorm x1 x2 x3 x4 x5 array x 5 f2 0 do j 1 to 5 f2 2 abs x Jj end return f2 endsub function combine f1 2 return sqrt 1 2 endsub run The next DATA step then defines the objective name with a given target data lsqobj1 input _id _function_ _sense_ _dataset_ datalines f1 axbi Abdata 2 onenorm f combine min a The following DATA step declares the variables data xvar input _id qe datalines x1 x2 x3 x4 x5 The following statements call the OPTLSO procedure options cmplib sasuser myfuncs proc optlso variables xvar objective lsqobjl run The contents of the OBJECTIVE data set Isqobj1 direct PROC OPTLSO to search for the three FCMP functions AXBI ONENORM and COMBINE in the library that is specified by the CMPLIB option The missing values in the SENSE_ column indicate t
53. ion in PROC OPTLSO For more information about these data sets see Chapter 17 The MPS Format SAS Data Set SAS OR User s Guide Mathematical Programming You can easily create these data sets by using the OPTMODEL procedure as demonstrated in Example 3 2 Using MPS Format on page 46 and Example 3 3 Using QPS Format on page 49 For more information about using PROC OPTMODEL to create MPS data sets see Chapter 5 The OPTMODEL Procedure SAS OR User s Guide Mathematical Programming Both MPS and QPS data sets require that you define an objective function Although the QPS standard supports a constant term the MPS standard does not thus any constant term that is defined in PROC OPTMODEL is naturally dropped and not included in the corresponding data set In particular if the MPSDATA option is used the corresponding objective will have the form m x Tx 34 4 Chapter 3 The OPTLSO Procedure However if the QPSDATA option is used the corresponding objective will have the form 1 m x cTx 5x Ox K where c Q and the constant term K are defined within the provided data sets Although multiple objectives might be listed PROC OPTLSO uses only the first objective from the MPSDATA or QPSDATA option How the corresponding objective function is used is determined by the contents of the OBJECTIVE data set For more information see Incorporating MPS and QPS Objective Functions on page 29 Describing No
54. is calculated as k d x y 6 x 90 1 1460 0 i 1 where 0 x denotes the maximum constraint violation at point x Then the distance between a point x and a set A is defined as d x A mind x y yEA 38 Chapter 3 The OPTLSO Procedure Let F denote the set of all nondominated points within the current population at the start of generation j Let Nj denote the set of all nondominated points at the start of generation j At the beginning of each generation F CN is always satisfied Then progress made during iteration 1 is defined as 1 1 gt d x Nj 1 J xEFj Progress j 1 Because d x N j 1 0 whenever x F N Fj 1 the preceding sum is over the set of points in the population that move from a status of nondominated to dominated In this case the progress made is measured as the distance to the nearest dominating point Specifying and Returning Trial Points You can use the following options to initialize PROC OPTLSO with user specified points CACHEIN FIRSTGEN and PRIMALIN You can use the following options to have trial points returned to you CACHEOUT LASTGEN and PRIMALOUT Both input and output point data sets have the following columns _SOL_ specifies the point s unique solution tag _ID_ specifies the variable and function ID name _VALUE_ specifies the variable function value Input Data Sets The following DATA step generates 30 random points for the ini
55. les are handled by using strategies and concepts similar to those in Griffin et al 2011 This approach can be viewed as a genetic algorithm that includes an additional growth step in which selected points from the population are allotted a small fraction of the total evaluation budget to improve their fitness score that is the objective function value by using local optimization over the continuous variables Because the OPTLSO procedure is a high performance analytical procedure it also does the following e enables you to run in distributed mode on a cluster of machines that distribute the data and the computations e enables you to run in single machine mode on the server where SAS is installed e exploits all the available cores and concurrent threads regardless of execution mode For more information see Chapter 4 Shared Concepts and Topics SAS OR User s Guide Mathemat ical Programming and Chapter 3 Shared Concepts and Topics Base SAS Procedures Guide High Performance Procedures for more information about the options available for the PERFORMANCE statement Getting Started OPTLSO Procedure All nonlinear objective and constraint functions should be defined by using the FCMP procedure In PROC FCMP you specify the objective and constraint functions by using SAS statements that are similar to syntax that is used in the SAS DATA step these functions are then compiled into function libraries for subsequent u
56. llowing macro definition to strip brackets from the resulting data set macro lsompsmod setold setnew data amp setnew drop i set amp setold array FC _CHARACTER_ do i 1 to dim FC FC i compress FC i end run Smend Example 3 2 Using MPS Format 47 For more complicated array structures take care to ensure that the resulting transformation is well defined Next you run a PROC OPTMODEL step that outputs a MPS data set followed by the newly defined LSOMPSMOD macro to strip brackets followed by a PROC OPTLSO step that takes as input the MPS data set that was output by PROC OPTMODEL and transformed by the 7 LSOMPSMOD macro proc optmodel var x 1 13 gt 0 lt 1 for i in 10 12 x i ub 100 min z 0 con al 2 x 1 2 x 2 x 10 x 11 lt 10 con a2 2 x 1 2 x 3 x 10 x 12 lt 10 con a3 2 x 1 2 x 3 x 11 x 12 lt 10 con a4 8xx 1 x 10 lt 0 con a5 8xx 2 x 11 lt 0 con a6 8xx 3 x 12 lt 0 con a7 2x x 4 x 5 x 10 lt 0 con a8 2x x 6 x 7 x 11 lt 0 con a9 2x x 8 x 9 x 12 lt 0 save mps lindataOld quit lsompsmod lindataOld lindata proc optlso primalout solution mpsdata lindata objective objdata performance nthreads 2 run proc print data solution run Output 3 2 1 shows the output from running these steps Output 3 2 1 Using MPS Format The OPTLSO Procedure Performanc
57. lowing values ABORTED ABSFCONV INFEASIBLE MAXFUNC MAXGEN MAXTIME UNBOUNDED FAILED OBJECTIVE The user signaled that the procedure should terminate The procedure terminated on the absolute function convergence criterion Problem is globally infeasible Only returned if all constraints are linear The procedure terminated on the maximum number of function evaluations The maximum number of genetic algorithm iterations was completed The maximum time limit was reached The problem might be unbounded The status cannot be classified into any of the preceding categories indicates the objective value that is obtained by the procedure at termination NOTE This value is included only for single objective optimization NONDOMINATED indicates the number of nondominated solutions in the Pareto optimal set NOTE This value is included only for multiobjective optimization PROGRESS indicates the progress made during the last iteration For a description of how this value is computed see the section Multiobjective Optimization on page 36 NOTE This value is included only for multiobjective optimization Examples OPTLSO Procedure 43 INFEASIBILITY indicates the level of infeasibility of the constraints at the solution EVALUATIONS indicates the total number of evaluations that were not cached ITERATIONS indicates the number of iterations that were required to solve the problem SETUP_TIME indicates the real time
58. n yl y2 10 endsub run data objdata input _id _function_ _sense_ datalines f branin min a options cmplib sasuser myfuncs proc optlso primalout solution variables vardata objective objdata performance nthreads 4 run proc print data solution run The OBJECTIVE option in the PROC OPTLSO statement refers to the OBJDATA data set which identifies BRANIN as the name of the objective function that is defined in the FCMP library sasuser myfuncs and specifies that BRANIN should be minimized The VARIABLES option in the PROC OPTLSO statement names the decision variables x1 and x2 and specifies lower and upper bounds The PERFORMANCE statement specifies the number of threads that PROC OPTLSO can use Figure 3 1 shows the ODS tables that the OPTLSO procedure produces by default Adding a Linear Constraint Introductory Examples 17 Figure 3 1 Bound Constrained Problem Output The OPTLSO Procedure Performance Information Execution Mode Number of Threads 4 Single Machine Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 2 Integer Variables 0 Continuous Variables 2 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize Solution Summary Solution Status Objective Infeasibility Iterations Evaluations Function convergence 0 3978873689 0
59. nlinear Constraints Nonlinear constraints are treated as black box functions and are described by using the FCMP procedure You should use the NLINCON option to provide PROC OPTLSO with the corresponding FCMP function names and lower and upper bounds Suppose a problem has the following nonlinear constraints l lt x1X2X3 sin x2 lt 1 X1X2 Xx1X3 Xx2x3 1 The following statements pass this information to PROC OPTLSO by adding two corresponding functions to the FCMP function library Sasuser Myfuncs Mypkg proc fcmp outlib sasuser myfuncs mypkg function conl x1 x2 x3 return x1 x2 x3 sin x2 endsub function con2 x1 x2 x3 return x1 x2 x1 x3 x3xx3 endsub run Next the following DATA step defines nonlinear constraint names and provides their corresponding bounds in the data set condata data condata input _id _lb ub_ datalines conl 1 1 con2 11 Finally you can call PROC OPTLSO and specify NLINCON CONDATA For another example with nonlinear constraints see Example 3 6 Using Nonlinear Constraints on page 56 The OPTLSO Algorithm The OPTLSO algorithm is based on a genetic algorithm GA GAs are a family of local search algorithms that seek optimal solutions to problems by applying the principles of natural selection and evolution Genetic algorithms can be applied to almost any optimization problem and are especially useful for problems for which other calculus based techniques do not
60. orezon 2003 which performs local search on the continuous variables to improve the robustness of both algorithms Both genetic algorithms GAs and the generating set search GSS have proven to be effective algorithms for many classes of derivative free optimization problems When only continuous variables are present a GA usually requires more function evaluations than a GSS to converge to a minimum This is partly due to the GA s need to simultaneously perform a global search of the solution space In a hybrid setting the requirement for the GA to find accurate local minima can be relaxed and internal parameters can be tuned toward finding promising starting points for the GSS The FCMP Procedure The FCMP procedure is part of Base SAS software and is the primary mechanism in SAS for creating user defined functions to be used in a DATA step and many SAS procedures You can use most of the SAS programming statements and SAS functions that you can use in a DATA step to define FCMP functions and subroutines The OPTLSO procedure also uses PROC FCMP to provide a general gateway for you to describe objective and constraint functions For more information see the sections Describing the Objective Function on page 28 and Describing Nonlinear Constraints on page 34 respectively However there are a few differences between the capabilities of the DATA step and the FCMP procedure For more information see the documentation about the FCMP
61. osure of the Software by the United States Government is subject to the license terms of this Agreement pursuant to as applicable FAR 12 212 DFAR 227 7202 1 a DFAR 227 7202 3 a and DFAR 227 7202 4 and to the extent required under U S federal law the minimum restricted rights as set out in FAR 52 227 19 DEC 2007 If FAR 52 227 19 is applicable this provision serves as notice under clause c thereof and no other notice is required to be affixed to the Software or documentation The Government s rights in Software and documentation shall be only those set forth in this Agreement SAS Institute Inc SAS Campus Drive Cary North Carolina 27513 August 2014 SAS provides a complete selection of books and electronic products to help customers use SAS software to its fullest potential For more information about our offerings visit support sas com bookstore or call 1 800 727 3228 SAS and all other SAS Institute Inc product or service names are registered trademarks or trademarks of SAS Institute Inc in the USA and other countries indicates USA registration Other brand and product names are trademarks of their respective companies gt a Ha Gain Greater Insight into Your SAS Software with SAS Books Discover all that you need on your journey to knowledge and empowerment CA support sas com bookstore 9sas GO for additional books and resources THE POWER TO KNOW SAS and all other SAS Institute Inc product o
62. procedure 36 nonlinear constraints OPTLSO procedure 34 objective OPTLSO procedure 28 ODS tables OPTLSO procedure 41 options classified by function see functional summary OPTLSO examples bound constrained optimization 16 introductory examples 16 19 linear constraint 17 maximum likelihood estimates 19 nonlinear constraints 18 OPTESO procedure details 27 displayed output to log 27 40 examples 43 FCMP basics 27 function caching 39 functional summary 21 Intermediate functions 29 large data 30 linear constraints 33 MPS and QPS objective functions 29 multiple objectives 36 nonlinear constraints 34 objective 28 ODS tables 41 options classified by function 21 overview 14 34 procedure termination messages 40 specifying trial points 38 table of syntax elements 21 time limit 24 overview OPTESO procedure 34 procedure termination messages OPTLSO procedure 40 random numbers seed 25 specifying trial points OPTLSO procedure 38 syntax OPTLSO procedure 21 table of syntax elements see functional summary termination criteria time limit 24 Syntax Index ABSFCONV option PROC OPTLSO statement 24 CACHEIN option PROC OPTLSO statement 22 CACHEMA X option PROC OPTLSO statement 25 CACHEOUT option PROC OPTLSO statement 23 CACHETOL option PROC OPTLSO statement 25 FEASTOL option PROC OPTLSO statement 24 FIRSTGEN option PROC OPTLSO statement 22 LASTGEN option
63. r service names are registered trademarks or trademarks of SAS Institute Inc in the USA and other countries indicates USA registration Other brand and product names are trademarks of their respective companies 2013 SAS Institute Inc All rights reserved S107969US 0613 iv Chapter 3 The OPTLSO Procedure Contents Overview OPTLSO Procedure Getting Started OPTLSO Procedure Introductory Examples Syntax OPTLSO Procedure References PROC OPTLSO Statement PERFORMANCE Statement READARRAY Statement Details OPTLSO Procedure The FEMP Procedure oe lt o eee ees The Variable DataSet Describing the Objective Function Describing Linear Constraints Describing Nonlinear Constraints The OPTLSO Algorithm Multiobjective Optimization Specifying and Returning Trial Points Function Value Caching Iteration LOS oca Owe Ae Procedure Termination Messages ODS Tables c e e soe ed oe ee aS Macro Variable OROPTLSO_ Examples OPTLSO Procedure Example 3 1 Using Dense Format Example 3 2 Using MPS Format Example 3 3 Using QPS Format Example 3 4 Combining MPS and FCMP Function Definitions Example 3 5 Linear Constraints and a Nonlinear Objective Example 3 6 Using Nonlinear Constraints Example 3 7 Using External Data Sets Example 3 8 Johnson s Systems of Distrib
64. reated by PROC OPTLSO see the section ODS Tables on page 41 SEED specifies a nonnegative integer as a seed value for the pseudorandom number generator Pseudorandom numbers are used within the genetic algorithm PERFORMANCE Statement PERFORMANCE lt options gt The PERFORMANCE statement defines performance parameters for multithreaded and distributed com puting passes variables that describe the distributed computing environment and requests detailed results 26 Chapter 3 The OPTLSO Procedure about the performance characteristics of a SAS high performance analytics procedure For more information about the options available for the PERFORMANCE statement see Chapter 4 Shared Concepts and Topics SAS OR User s Guide Mathematical Programming and Chapter 3 Shared Concepts and Topics Base SAS Procedures Guide High Performance Procedures Note that the SAS High Performance Optimization license is required to invoke PROC OPTLSO in distributed mode For examples of running in distributed mode see the third program in Example 3 7 Using External Data Sets on page 59 and Example 3 8 Johnson s Systems of Distributions on page 65 READARRAY Statement READARRAY SAS data set 1 lt SAS data set 2 SAS data set k gt PROC FCMP see The FCMP Procedure on page 27 provides the READ_ARRAY function to read data from a SAS data set into array variables In order to ensure that the referenced
65. s xvar objective lsqobj2 run Thus any of the intermediate functions that are used within the OBJECTIVE data set objdata are permitted to have arguments that form a subset of the variables listed in the VARIABLES data set xvar and the numerical columns from the data set that is specified in the DATASET_ column of the OBJECTIVE data set Only numerical values are supported from external data sets Only one function can be of type MIN or MAX This function can take as arguments any of the variables in the VARIABLES data set any of the numerical columns from an external data set for the objective if specified and any implicit variables that are listed in the _ID_ column of the OBJECTIVE data set The following rules for the objective data set are used during parsing e Only one data set can be used for a given problem definition e The objective function can take a data set as input only if no intermediate functions are being used Otherwise only the intermediate functions can be linked to the corresponding data set The data set is used in a distributed format if either the NODES option is specified in the PERFORMANCE statement or the data set is a distributed library Describing Linear Constraints 33 Describing Linear Constraints The preferred method for describing linear constraints is to use the LINCON MPSDATA or QPSDATA option You should not describe linear constraints by using the NLINCON option because they
66. s the ODS tables that are produced Output 3 10 1 Multiobjective ODS Tables The OPTLSO Procedure Performance Information Execution Mode Single Machine Number of Threads 4 Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables 2 Integer Variables 0 Continuous Variables 2 Number of Constraints 0 Linear Constraints 0 Nonlinear Constraints 0 Objective Definition Source OBJDATA Objective Sense Minimize 74 Chapter 3 The OPTLSO Procedure Output 3 10 1 continued Solution Summary Solution Status Function convergence Nondominated 5000 Progress 6 9766249E 7 Infeasibility 0 Iterations 444 Evaluations 23647 Cached Evaluations 103 Global Searches 1 Population Size 80 Seed 1 Output 3 10 2 shows the iteration log Output 3 10 2 Multiobjective Log NOTE The OPTLSO procedure is executing in single machine mode NOTE The OPTLSO algorithm is using up to 4 threads NOTE The problem has 2 variables 0 integer 2 continuous NOTE The problem has O constraints 0 linear O nonlinear NOTE The problem has 2 FCMP function definitions NOTE The deterministic parallel mode is enabled Iteration Nondom Progress Infeasibility Evals Time 1 7 0 84 o 5t 962 0 000070835 o 2885 0 101 1689 0 000017074 0 5613 1 151 2289 0 000009575 o 8249 1 201 2933 0 000004561 0 10906 2 251 3429 0 000051118 0 13573 2 301 3876 0 000001452 0 16163 3 got 4386 0 000000716 o 18757 4
67. se The SAS CMPLIB system option specifies where to look for previously compiled functions and subroutines All procedures including PROC FCMP that support the use of FCMP functions and subroutines use this system option After your objective and constraint functions have been specified in a library PROC OPTLSO requires the names and context of the functions within this library that are relevant to the current optimization problem You can provide this information to PROC OPTLSO by using SAS data sets You use additional data sets to describe variables and linear constraints in either a sparse or a dense format Introductory Examples The following introductory examples illustrate how to get started using the OPTLSO procedure 16 Chapter 3 The OPTLSO Procedure A Bound Constrained Problem Consider the simple example of minimizing the Branin function 51 5 5 7 1 fx x2 xi x 6 10 l cos x1 10 T TT 472 subject to 5 lt x lt 10 and 0 lt x2 lt 15 Jones Perttunen and Stuckman 1993 The minimum function value is f x 0 397887 at x m 12 275 x 2 275 9 42478 2 475 You can use the following statements to solve this problem data vardata input _id _lb ub_ datalines x1 5 10 x2 0 15 proc fcmp outlib sasuser myfuncs mypkg function branin x1 x2 pi constant PI yl x2 5 1 4 rpix xx2 x1x xx14 5 xx1 pi 6 x 2 y2 10x 1 1 8xpi x cos x1 retur
68. se Minimize Solution Summary Solution Status Function convergence Objective 0 0041074417 Infeasibility 0 Iterations 73 Evaluations 6261 Cached Evaluations 91 Global Searches 1 Population Size 120 Seed 1 Obs _sol_ _id_ _value_ 1 O _obj_ 0 00411 2 0 _inf_ 0 00000 3 0x1 0 08239 4 0x2 1 13238 5 0x3 234437 6 of 0 00411 64 Chapter 3 The OPTLSO Procedure The preceding approach can be prohibitive if the size of the data set is large As a third approach to specifying the objective function PROC OPTLSO provides an alternate data input gateway that is described in the OBJECTIVE data set as shown in the following statements data vardata input _id _1b ub_ datalines x1 1000 1000 x2 1000 1000 x3 1000 1000 data barddata k un input y ee datalines 14 0 18 0 22 0 25 0 29 32 0 35 0 39 0 37 0 58 73 0 96 1 34 2 10 4 39 ooo data objdata input _id function _sense _dataset_ datalines fx bard min barddata r proc fcmp outlib sasuser myfuncs mypkg function bard x1 x2 x3 k y vk 16 k wk min k vk fxk y x1 k vk x2 wkx x3 return 0 5 fxkxx2 endsub run options cmplib sasuser myfuncs proc optlso primalout solution variables vardata objective objdata performance nodes 2 nthreads 8 run proc print data solution run Output 3 7 3 shows the output from running these statements Example 3 8 Johnson s Systems of Dis
69. set specifies an initial sample set that defines a subset of the initial population The columns of this data set should coincide with the same format that is used by the PRIMALIN data set If the population size p 1s smaller than the size of this set only the first p points of this set are used For more information see the section Specifying and Returning Trial Points on page 38 LINCON SAS data set uses a dense format to describe the optimization problem s linear constraints The corresponding data set should have columns _LB_ and _UB_ to describe lower and upper bounds respectively The column _ID_ is reserved for the corresponding constraint name The remaining columns must correspond to the linear coefficients of the variables that are listed in the VARIABLES option For more information see the section Describing Linear Constraints on page 33 MPSDATA SAS data set specifies a data set that can be used as a sparse alternative to the LINCON option which uses a dense format to define variables Mathematical programming system MPS is a common file format for representing linear and mixed integer mathematical programs For an example of using the OPTMODEL procedure to create the corresponding MPS file see Example 3 2 Using MPS Format on page 46 Internally binary variables are converted into integer variables with lower and upper bounds of O and 1 respectively For more information see the section Describing Linear
70. sing a missing value entry in the SENSE_ column to denote that the new function is not an objective The _ID_ column entries for intermediate functions can then be used as arguments for the objective function The following set of programming statements demonstrates how to create an equivalent objective definition for Example 3 5 Linear Constraints and a Nonlinear Objective on page 54 by using intermediate functions data objdata length _function_ 10 input _id _function_ _sense_ datalines f1 sixhump1 f2 sixhump2 f3 sixhumpNew min proc fcmp outlib sasuser myfuncs mypkg function sixhumpl x1 x2 return 4 2 1xx1xx2 x1x 4 3 endsub function sixhump2 x1 x2 return 4 4xx2xx2 endsub function sixhumpNew x1 x2 f1 2 return f flxx1xx2 x1 x2 f2 xx2 2 endsub run In this case PROC OPTLSO first computes the values for sixhump1 and sixhump2 internally assigning the output to f1 and f2 respectively The _ID_ column entries for intermediate functions can then be used as arguments for the objective function f8 Because the intermediate functions are evaluated first before the objective function is evaluated intermediate functions should never depend on output from the objective function Incorporating MPS and QPS Objective Functions If you use the MPSDATA or QPSDATA options to define linear constraints an objective function m x is necessarily defined see Describing Linear Constraints
71. t the continuum of best case scenarios Multiobjective optimization is performed in PROC OPTLSO whenever more than one objective function of type MIN or MAX exists For an example see Example 3 10 Multiobjective Optimization on page 72 Mathematically multiobjective optimization can be defined in terms of dominance and Pareto optimality For a k objective minimizing optimization problem a point x is dominated by a point y if fi x gt fi y for alli J k and fj x gt f y for some j J k A Pareto optimal set contains only nondominated solutions In Figure 3 2 a Pareto optimal frontier is plotted with respect to minimization objectives f x and f2 x along with a corresponding population of 10 points that are plotted in the objective space In this example point a dominates e f k b dominates e f g k c Multiobjective Optimization 37 dominates g h k and d dominates k i Although c is not dominated by any other point in the population it has not yet converged to the true Pareto optimal frontier Thus there exist points in a neighborhood of c that have smaller values of f and fo Figure 3 2 Pareto Optimal Set h x ok oe of fix In the constrained case a point x is dominated by a point y if 0 x gt e and 0 y lt 0 x where 0 x denotes the maximum constraint violation at point x and FEASTOL e thus feasibility takes precedence over objective function values Genetic algorithms ena
72. tial population if the variables x R have bounds 5 lt x lt 10 data popin low 5 0 upp 10 0 numpoints 30 dim 5 do _sol_ 1 to numpoints do i 1 to dim _id_ compress x put i 4 0 _value_ low upp low ranuni 2 output end end keep _sol id value_ run You can then use this data set as input for the OPTLSO procedure by using the FIRSTGEN option Function Value Caching 39 Output Data Sets PROC OPTLSO dynamically creates and reports on two metadata functions for you the true objective which is a combination of the FCMP objective and the linear and quadratic terms and the maximum constraint violation These functions are assigned the following function ID names therefore these names should not be used as variable constraint or function names _OBJ_ specifies the point s objective NOTE This value is omitted when solving a multiobjective problem _INF_ specifies the point s maximum constraint violation Output data sets have additional rows that correspond to the problem s FCMP functions These rows must exist for the data set specified in the CACHEIN option but they should be omitted for the data sets specified in the FIRSTGEN and PRIMALIN options When you observe the solution output it might be easier to compare points if they are listed as rows rather than as columns SAS provides a variety of ways to transform the results for your purposes For example
73. tion SIAM Journal on Scientific Computing 30 1892 1924 Haverly C A 1978 Studies of the Behavior of Recursion for the Pooling Problem SIGMAP Bulletin Association for Computing Machinery 25 19 28 Holland J H 1975 Adaptation in Natural and Artificial Systems An Introductory Analysis with Applica tions to Biology Control and Artificial Intelligence Ann Arbor University of Michigan Press Hough P D Kolda T G and Patrick H A 2000 Usage Manual for APPSPACK 2 0 Technical Report SAND2000 8843 Sandia National Laboratories Albuquerque NM and Livermore CA Huband S Hingston P Barone L and While L 2006 A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit JEEE Transactions on Evolutionary Computation 10 477 506 Jones D R Perttunen C D and Stuckman B E 1993 Lipschitzian Optimization without the Lipschitz Constant Journal of Optimization Theory and Applications 79 157 181 Kolda T G Lewis R M and Torczon V 2003 Optimization by Direct Search New Perspectives on Some Classical and Modern Methods SIAM Review 45 385 482 Liebman J Lasdon L Schrage L and Waren A 1986 Modeling and Optimization with GINO Redwood City CA Scientific Press Michalewicz Z 1996 Genetic Algorithms Data Structures Evolution Programs New York Springer Verlag Mor J J Garbow B S and Hillstrom K E 1981
74. tive objdata variables vardata logfreq 100 maxgen 1000 performance nodes 4 nthreads 8 run Output 3 8 1 shows the output from running these steps Output 3 8 1 Estimation for Johnson Sy Family of Distributions The OPTLSO Procedure Problem Summary Problem Type NLP Objective Definition Set OBJDATA Variables VARDATA Number of Variables Integer Variables 0 Continuous Variables Number of Constraints Linear Constraints Nonlinear Constraints Objective Definition Source OBJDATA Objective Sense Maximize Objective Intermediate Functions 1 Objective Data Set sudata Solution Summary Solution Status Function convergence Objective 8414 725097 Infeasibility 0 Iterations 879 Evaluations 75737 Cached Evaluations 1260 Global Searches 1 Population Size 120 Seed 1 68 Chapter 3 The OPTLSO Procedure Output 3 8 1 continued Performance Information Host Node lt lt your grid host gt gt Execution Mode Distributed Number of Compute Nodes 4 Number of Threads per Node 8 Example 3 9 Discontinuous Function with a Lookup Table This example illustrates the ability of PROC OPTLSO to optimize a discontinuous function The example generates a data set of discrete values that approximate a given smooth nonlinear function The function being optimized is simply using that data set as a lookup table to find the appropriate discretized value let N 100 let L 0 Slet U 10 options cmplib
75. tors of the lower and upper bounds respectively on the nonlinear constraint functions Equality constraints can be represented by equating the lower and upper bounds of the desired variable or constraint Because of the limited assumptions that are made on the objective function f x and constraint functions c x the OPTLSO procedure uses a parallel hybrid derivative free approach similar to approaches that are used in Taddy et al 2009 Plantenga 2009 Gray Fowler and Griffin 2010 Griffin and Kolda 2010a Derivative free methods are effective whether or not derivatives are available provided that the dimension of x is not too large Gray and Fowler 2011 As a rule of thumb derivative free algorithms are rarely applied to black box optimization problems that have more than 100 variables The term black box emphasizes that the function is used only as a mapping operator and makes no implicit assumption about or requirement on the structure of the functions themselves In contrast derivative based algorithms commonly require the nonlinear objectives and constraints to be continuous and smooth and to have an exploitable analytic representation The OPTLSO procedure solves general nonlinear problems by simultaneously applying multiple instances of global and local search algorithms in parallel This streamlines the process of needing to first apply a global algorithm in order to determine a good starting point to initialize a local algorithm
76. tributions 65 Output 3 7 3 Using External Data Sets Ill The OPTLSO Procedure Problem Summary Problem Type Objective Definition Set Variables Number of Variables Integer Variables Continuous Variables Number of Constraints Linear Constraints Nonlinear Constraints Objective Definition Source Objective Sense Objective Data Set NLP OBJDATA VARDATA Ww oo OBJDATA Minimize barddata Solution Summary Solution Status Function convergence Objective 0 0041074398 Infeasibility 0 Iterations 77 Evaluations 6438 Cached Evaluations 263 Global Searches 1 Population Size 120 Seed 1 Performance Information Host Node Execution Mode Number of Compute Nodes 2 Number of Threads per Node 8 lt lt your grid host gt gt Distributed Example 3 8 Johnson s Systems of Distributions This example further illustrates the use of external data sets that are specified in the OBJECTIVE option For this example a data set that contains n 20 000 randomly generated observations is used to estimate the parameters for the Johnson Sy family of distributions Bowman and Shenton 1983 The objective is the log likelihood for the family which involves four variables x x1 X2 X3 X4 n f x nlog x4 nlog x2 5 DI las xa log z4 log l y2 k 1 66 Chapter 3 The OPTLSO Procedure where di x Ze Ye y1 y with ye Here dx denotes the value of d in the kth o
77. ts in new ways In this way new areas of the search space are explored while attempting to retain optimal solution characteristics mutation Some of the next iteration solutions are passed to a mutation operator which introduces random variations in the solutions The purpose of the mutation operator is to ensure that the solution space is adequately searched to prevent premature convergence to a local optimum repeat The current iteration of solutions is replaced by the new iteration If the stopping criterion is not satisfied the process returns to the selection phase The crossover and mutation operators are commonly called genetic operators Selection and crossover distinguish genetic algorithms from a purely random search and direct the algorithm toward finding an optimum There are many ways to implement the general strategy just outlined and it is also possible to combine the genetic algorithm approach with other heuristic solution improvement techniques In the traditional genetic algorithm the solution space is composed of bit strings which are mapped to an objective function and the genetic operators are modeled after biological processes Although there is a theoretical foundation for the convergence of genetic algorithms that are formulated in this way in practice most problems do not fit naturally into this paradigm Modern research has shown that optimizations can be set up by using the natural solution domain for example
78. umber of points that can be cached By default PROC OPTLSO automatically calculates the maximum number of points PARETOMAX specifies the maximum number of points in the Pareto optimal set The default is 5 000 CACHETOL r specifies the cache tolerance to be used for caching and referencing previously evaluated points For more information about this tolerance see the section Function Value Caching on page 39 The value of r can be any number in the interval 0 1 The default is 1E 9 LOGFREQ i requests that the solution progress be printed to the iteration log after every iterations if the value of the LOGLEVEL option is greater than or equal to 0 The value i 0 disables the printing of the solution progress The final iteration is always printed if gt 1 and LOGLEVEL is nonzero The default is 1 LOGLEVEL 0 1 controls how much information is printed to the log file If LOGLEVEL 0 nothing is printed If LOGLEVEL 1 a short summary of the problem description and final solution status is printed If LOGLEVEL 0 this option overrides the LOGFREQ option By default LOGLEVEL 1 PRINTLEVEL 0 1 specifies whether to print a summary of the problem and solution If PRINTLEVEL 1 then the Output Delivery System ODS tables ProblemSummary SolutionSummary and Performancelnfo are produced and printed If PRINTLEVEL 0 then no ODS tables are produced By default PRINTLEVEL 1 For more information about the ODS tables that are c
79. utions Example 3 9 Discontinuous Function with a Lookup Table Example 3 10 Multiobjective Optimization 14 15 15 21 21 25 26 27 27 27 28 33 34 34 36 38 39 40 40 41 42 43 43 46 49 51 54 56 59 65 68 72 75 14 4 Chapter 3 The OPTLSO Procedure Overview OPTLSO Procedure The OPTLSO procedure performs optimization of general nonlinear functions that are defined by the FCMP procedure in Base SAS over both continuous and integer variables These functions do not need to be expressed in analytic closed form and they can be non smooth discontinuous and computationally expensive to evaluate Problem types can be single objective or multiobjective PROC OPTLSO runs in either single machine mode or distributed mode NOTE Distributed mode requires SAS High Performance Optimization The general problem formulation is given by min F x x xe lt S x lt Xu be lt A lt b subject to CS 7 ce lt S c x lt Cy xi Z el where x R is the vector of the decision variables f x R R is the objective function A is an m x n linear coefficient matrix c x R gt R is the vector of general nonlinear constraint functions that is c C1 Cp Xg and xy are the vectors of the lower and upper bounds respectively on the decision variables bg and b are the vectors of the lower and upper bounds respectively on the linear constraints and cg and cy are the vec

The OPTLSO Procedure

Contents

Download Pdf Manuals

Related Search

Related Contents