Home

NUOPT for S-PLUS User's Guide Version 1.4

1. lt lt SIMPLE 168 gt gt Objective can only be assigned once lt lt SIMPLE 177 gt gt No lower bound for empty constraint lt lt SIMPLE 178 gt gt No upper bound for empty constraint lt lt SIMPLE 191 gt gt No assignment is allowed to Sets having both index and superSet An attempt has been made to assign to a set which is indexed and has a super set Only implicit assignment auto assignment is allowed in such a case For example this error occurs in the following a lt Set b lt Set d lt Set index a superSet b d 1 5 I lt lt SIMPLE 193 gt gt Error in solve lt lt NUOPT xx gt gt XXXXXXX Error occurred in optimization Display an error message from NUOPT 89 Appendix I lt lt SIMPLE 194 gt gt Fatal error in solve lt lt NUOPT XX gt gt XXXXXXX Fatal error occurred in optimization Display an error message from NUOPT This case NUOPT do not return any solution lt lt SIMPLE 214 gt gt Warning constraint N reduce to xxxx always satisfied SIMPLE 215 gt gt constraint N reduce to xxxx never satisfied lt lt SIMPLE 216 gt gt Trivial and Infeasible constraint appeared Some input error may produce trivial constraints between constants These warning and error reports such a situation In the example below errsample function S lt Set empty i Element set S
2. x lt Variable index i Sum x i i always satisfied but meaning less Sum x i i gt 5 never satisfied This case S is empty then Sum x 1 1 will be zero Then the constraints reduce to trivial ones The former is always satisfied the latter never satisfied Then gt s lt System errsample will produce 3 errors as below SIMP satisfi SIMP SIMP D E 214 gt gt Warning constraint l reduce to 0 0 always ed E 215 gt gt constraint 2 reduce to 0 gt 5 never satisfied D E 216 gt gt Trivial and Infeasible constraint appeared If Error 215 is detected then NUOPT stops with error 216 otherwise it will continue calculation 90 NUOPT for S PLUS User s Guide Error Messages from NUOPT In this section we explain NUOPT s error messages Error with indication FATA L are a fatal ones that cause NUOPT to terminate without any solution the variables reported remain unchanged from the given initial values in other cases NUOPT returns non optimal values for the parameters Each error is numbered Explanations follow in order lt lt NUOPT 1 gt gt memory error in preprocessing The required memory reaches its limit in the preprocessing phase FATAL NUOPT 2 gt gt infeasibl linear constraints and variable bounds Conflicting linear constraints and variable bounds cause infeasibility lt lt NUOPT 3 gt gt no variab
3. 1 2 3 4 1 0 7927655 0 08728692 0 87694254 0 59059953 2 0 7936707 0 95924969 0 22479839 0 18035779 3 0 8916424 0 26851545 0 06113247 0 99077122 4 0 1120670 1 34384028 0 79783496 1 85060734 5 1 3711549 0 76393502 0 48544747 1 34083062 6 1 4169931 0 55847085 0 37566898 0 05630496 7 1 1665775 0 19412154 2 17067057 1 01415727 8 0 5306316 0 92741468 0 27440216 1 18712652 9 0 9211911 0 18147267 0 66076270 1 93023713 79 Chapter 6 Examples 10 0 5769609 1 577358 gt averet apply portfolio gt O lt crossprod sweep port Sysl System model Port Dr Soll lt solve sysl V 67 1 42998998 0 86538263 R 2 mean folio R 2 averet folioCor Q averet ace F Sometimes an alternative formulation of the optimization problem can lead to efficiency and or stability improvements For examp le using expression 8 for the covariance matrix and in troducing internal variable z R Rj w We have a computationally more efficient formulation of this problem Minimize 1 n 1 y z tePeriod Subject to NS w 1 je Asset Sr JW Fain jeAsset S R R Ww z 0 te Period je Asset w 2 0 je Asset With the modeling language SIMPLI gt PortfolioAlt function rmat averet rmin n lt nrow rmat numb p lt ncol rmat Period Set Asset Set E this problem is written as follows 0 0 er of
4. Chapter3 Defining Optimization Models with STMPLE v lt Parameter value index i S lt Parameter size index i obj Objective type maximize obj Sum v i x i i Objective Sum s i x i i lt Capacity Constraint We use a wrapper function KnapsackInit function value lt list 1 10 c 42 12 45 5 2 61 89 32 47 18 size list 1 10 c 39 13 66 15 10 20 31 15 41 16 Capacity 121 return Knapsack value size Capacity to create a sample instance of the problem and solve it with NUOPT Because NUOPT detect the existence of integer variables NUOPT choose the default method to be simplex capable of handling Mixed Integer Linear Programming MILP models MILP is very difficult class of problems and note that it may take hours to compute optimal solution of MILP with several hundred of integer variables sys KnapsackInit System KnapsackInit gt sol KnapsackInit lt solve sys KnapsackInit trace F gt sol KnapsackInit Svariables Svariables x 1 23 4 5 6 7 8 9 10 1 70 70 9 40 dy Te 1 40 T attr Svariables x indexes Sobjective 1 242 24 NUOPT for S PLUS User s Guide counter iters fevals vars 0 0 10 Stermination tolerance residual le 08 0 Selapsed time 1 0 02000046 3 4 Constraints and Conditions 3 4 1 Constraint Objects Constraints are mathematical relations that a solution of an optimzation
5. delete con sys LregPosAlt stack 1 1 3 sys LregPosAlt stack 1 1 B Acid Conc beta Acid Conc gt 0 lt lt lt deleted gt gt gt 1 2 B Air Flow beta Air Flow gt 0 lt lt lt deleted gt gt gt 1 3 B Water Temp beta Water Temp gt 0 lt lt lt deleted gt gt gt 2 1 R 1 80 beta Air Flow 27 beta Water Temp 2 2 R 2 80 beta Air Flow 27 beta Water Temp 2 20 R 20 56 beta Air Flow 20 beta Water Temp 2 21 R 21 70 beta Air Flow 20 beta Water Temp obj lt objective gt r 1 r 1 r 2 r 2 z 3 x 3 sol LregPosAlt stack solve sys LregPosAlt stack Now restore the bound constraints and delete all but the first 9 residuals and solve 34 NUOPT for S PLUS User s Guide restore con sys LregPosAlt stack 1 1 3 delete con sys LregPosAlt stack 2 10 21 gt sys LregPosAlt stack 1 1 B Acid Conc beta Acid Conc gt 0 1 2 B Air Flow beta Air Flow gt 0 1 3 B Water Temp beta Water Temp gt 0 2 1 R 1 80 beta Air Flow 27 beta Water Temp 2 2 R 2 80 beta Air Flow 27 beta Water Temp 2 20 R 20 56 beta Air Flow 20 beta Water Temp lt lt lt deleted gt gt gt 2 21 R 21 70 beta Air Flow 20 beta Water Temp lt lt lt deleted gt gt gt obj lt objective gt r 1 r 1 r 2 r 2 z 3 1 3 Now add a new constraint gt add co
6. Element set 1 gt x lt Variable index i mp global condition x i 1 gt i lt 0 S amp amp S i gt gt lt Objective type gt f Sum x i i gt sys lt System Evaluating ts i 3 21 x i lt 1 3 x i gt 0 4 i 3 26 condition condition 0 4 global condition removing restrictions on i maximize 5 x i gt 1 6 x i lt 0 7 i 8 x i gt 1 9 x i lt 1 10 1 lt 0 amp amp 1 gt 0 11 feSum x i i Expanding CHE Ey scene 24 ume SLT ie necks Ar Freenet SAT esas gt sys f objective x 1 x 2 x 3 x 4 x 5 maximize Local conditions occur in conjunction with subscripting gt new model gt I Set gt i Element set 1 gt x lt Parameter list 1 7 3 3 index I gt x i i gt 4 9 6 of NUOPT for S PLUS User s Guide 7 7 ok 27 Chapter3 Defining Optimization Models with STMPLE Y 23 attr indexes as well as within the Sum and Prod functions gt new model gt I Set gt i lt Element set I gt x lt Parameter list 1 7 3 3 index I gt x q 32 35425063 B2 eL 0 LL 2 3 attr indexes 1 xn gt Sum x i i i gt 4 1 6 gt Prod x i i i 4 3 4 3 Conditional Expressions In some models we may want expressions to vary according to the values of their variables The function ife cons el e2 defines an
7. The next sections provide a brief explanation of the characteristics and scope of the opti 52 NUOPT for S PLUS User s Guide mization methods within NUOPT They also explain NUOPT s actions when automatically selecting a method and give general guidelines as to when it may be appropriate to override NUOPT s choices The next sections provide a brief explanation of the characteristics and scope of the opti mization methods within NUOPT They also explain NUOPT s actions when automatically selecting a method and give general guidelines as to when it may be appropriate to override NUOPT s choices 5 2 1 Higher order interior point method for LP A higher order interior point method is available for linear programming LP It uses the higher order correction technique proposed by Mehrotra 13 and Gondzio 6 In comparison to more general interior point methods applicable to convex programming such as the line search method in NUOPT our experiments show that this method can be nearly 2 3 times faster for large scale problems This method is the default choice in NUOPT when the model is linear with no integer variables To explicitly select the higher order method type gt nuopt options method higher You can force NUOPT to apply the higher order method to integer programming models How ever in this case the integrality conditions are ignored and NUOPT will issue an error message lt lt NUOPT 14 gt gt integrali
8. attr indexes 1 i 4 3 Graph Objects A graph is used for describing special models like network problems A graph consists of two sets namely node dim 1 and arc dim 2 SIMPLE provides a number of functions for manipulating graphs see Table 4 3 We can check the behavior of these functions as follows Table 4 3 Graph functions Function Arguments Brief Description Arcs graph returns the set of arcs of graph nodes graph returns the set of nodes of graph input graph node returns all arcs of graph incoming to node output graph node returns all arcs of graph outgoing from node Orig element returns the first component of a arc Dest element returns the second component of a arc new model gt ar Set c 1 2 1 3 1 4 2 1 2 5 dim 2 gt g lt Graph arcs ar 2g 12345 orig 11122 dest 2 3 4 1 5 gt nodes g 23 415 gt nodes g 1 3 arcs 1 4 and 2 5 are removed gt arcs g from the def of graph A 3 orig 11 2 dest 2 3 1 gt ar c 1 2 1 3 2 3 3 1 38 NUOPT for S PLUS User s Guide 1234 orig 1 1 2 3 dest 23 3 1 gt i lt Element set nodes g gt input g i incoming arcs 2 1 2 3 arc to node 2 is 1 2 Lane bn 22 3 13 arcs to node 3 are 2 3 and 1 3 1 31 arc to node 1 is 3 1 indexes i output g i outgoing arcs 2 23 LE arc from node 2
9. function is minimized or a concave objective function is maximized and whose feasible region is also convex Quadratic programming models fall into this category if the Hessian of the minimized maximized objective function is positive negative definite For nonlinear models NUOPT s default choice is to use a trust region method see section 5 2 4 rather than a line search method The trust region method will work but our experiments show that the line search method is about 1 5 2 times faster than the trust region method for convex programming models NUOPT cannot detect convexity in nonlinear models but if the problem is known to be convex the line search method can be selected by typing gt nuopt options method line The line search method cannot handle integrality constraints on variables 5 2 4 trust region method for NLP The trust region method 11 is an interior point method capable of handling general nonlin ear programming NLP models By default for NLP models NUOPT chooses the trust region method since it is reliable in all cases This choice is not always the best when the model is convex in which case the line search method should be selected see section 5 2 3 To explicitly select the trust region method for solving type gt nuopt options method trust The trust region method cannot handle integrality constraint of variables 5 2 5 BFGS method for NLP 55 Chapter 5 The NUOPT Solver The BFGS meth
10. gt Fixed value out of defined range An attempt has been made to fix an element at a value out of its defined range For example a Set 1 3 i Element set a I 10 the last statement produces the error message Fixed value 10 out of defined range i lt lt SIMPLE 60 gt gt Illegal characters included in subscript lt lt SIMPLE 62 gt gt Comparison between elements of different dimension lt lt SIMPLE 64 gt gt Constraint subscript not matched lt lt SIMPLE 67 gt gt Expression subscript not matched An attempt has been made to index an object with the wrong number of subscripts e g x lt Variable index i x i j gt 1 lt lt SIMPLE 70 gt gt Unmatched or ambiguous element s There are subscripts on the right hand side of an assignment that do not occur on the left hand side For example y 3 Y p i will produce the above error lt lt SIMPLE 74 gt gt Improper use of a dependent subscript For example in j lt Element set S i x Variable index j j is defined to be dependent on i but is not used together with i lt lt SIMPLE 82 gt gt Subscript of out of range An attempt has been made to use an object with a subscript out of its defined range For example in the following definitions a lt Set 1 2 i Element set a x Variable index i x 3 1 the subscript 3 is out of x s defi
11. 0 lt Nmax j Eel leber 20 8 100 200 Eel leber Eel leber eefSteak leber VitaminB VitaminA Da dual 486 67134048 0 29284699 2413 51285573 0 06987482 NUOPT for S PLUS User s Guide 0 453 5224 Sconstraints constraints 2 current lower upper initial dual slack diet VitaminA lt 2 gt 20 007124 20 100 0 6 664946 0 007123863 diet VitaminB lt 2 gt 8 001185 8 200 0 39 994389 0 001184911 counter iters fevals vars 10 12 4 termination tolerance residual 1e 008 6 14879e 010 Selapsed time 1 0 1796875 6 3 Maximal n gon The problem is to find a planar n gon of maximal area inscribed in a circle of diameter 1 Variables p 0 iln Objective DI 2 lt isn Pi Pia sin 0 Eo O Constraints P P 2p p cos 0 0 lt 1 lsi lt j lt n Pia S Pi 2 lt i lt n Bounds O0 lt p lt 1 0 x 6 p 9 where P 0 points of polygon polar radius polar angle The following function defines a SIMPLE model for the maximal n gon problem 75 Chapter 6 Examples gt ngon function N I lt Set init 1 N i Element set I j lt Element set I n lt Element n max i points of polygon polar radius polar angle rho lt Variable index I theta lt Variable index I 0 lt rho i lt 1 0 lt theta i rho i 4 i n 1 i n 1 n 1 theta i pi i n insc
12. 1 0e 8 for LP crossover ofr POLLS Crossover switch on mipfeasout off off Show the best feasible Non solution of MIP when obtained tolx positive num 1 0e 8 primal feasibility tolerance told positive num 1 0e 6 dual feasibility tolerance epsint positive num 1 0e 4 integer feasibility tolerance maxtim integer 1 no limit Optimization time limit in seconds maxnod integer 1 no limit branch and bound node number limit 58 NUOPT for S PLUS User s Guide cutoff number 1 0e50 not branch and bound set cutoff value addToCutoff positive num 0 branch and bound cutoff value margin maxintsol Positive num 1 not set The number of maximal feasible solution of MIP before stopping scaling off oTt Scaling switch on 5 3 1 Parameters for IPM variants The parameters described in this section are valid for all of the interior point methods IPM incorporated in NUOPT including higher order method for linear programming trust region method for general nonlinear programming line search method for convex programming BFGS method for nonlinear programming small to medium scale problems and not valid for simplex method for linear and integer programming active set method for quadratic and integer quadratic programming These parameters are specific to interior point methods and are explained below 1 IPM iteration limit nuop
13. 2BI feasible sol 1 291 found at 0 1 sec piv 10 prob 6 I 51 Chapter 5 The NUOPT Solver feasible sol 2 323 found at 0 1 sec piv 13 prob 8 I feasible sol 43 366 found at 0 1 sec piv 15 prob 9 iteration end In this case the following lines appear in the summary report PARTIAL PROBLEM COUNT number DUAL SIMPLEX PIVOT COUNT number The first line gives the number of branch and bound enumeration nodes subproblems exam ined to find the optimal solution and prove its optimality The next line reports total simplex pivot count required to solve sequence of subproblems in this case we use the dual simplex method 5 2 Choosing an Optimization Method The various optimization methods included in NUOPT have been discussed in the introduction section 1 The METHOD line in the output from NUOPT reports the optimization method applied which higher order method for LP HIGHER ORDER simplex method for LP and MIP SIMPLEX trust region method for NLP TRUST REGION line search method for CP INE SEARCH BFGS method for NLP BFGS LINE SEARCH Active set method for COP ACTIVE SET QP User can specify the method through the function output options otherwise NUOPT will make a suitable default choice For example a line search method can be applied to a model by typing gt nuopt options method line explicitly choose line search method
14. 39057 15 45655 17 15298 21 11131 attr indexes Initial values of parameters variables and expressions can similarly be recovered through the function init init sys LregPos stack r 1 2 3 4 P 6 7 8 9 10 11 12 23 14 15 16 17 T8 19 20 21 42 37 37 28 18 18 19 20 15 14 14 13 1112 8 7 875407 9 5 dod 21 Chapter3 Defining Optimization Models with STMPLE attr indexes dog init sys LregPos stack beta Air Flow Water Temp Acid Conc 0 0 0 attr indexes 1 qe The default initial value of both parameters and variables is zero 3 2 1 Arithmetic Operations in SIMPLE S PLUS math functions are supported in SIMPLE with the following exceptions cummax cumprod gamma lgamma round signif all any sum prod range Functions sum and prod are replaced by Sum and Prod for which the usage is shown in Table 3 2 1 Mathematical Expression SIMPLE Expression NO Sum F i i i lt I tel Sum F i i i gt lt n i lt m NO PEE Sum G i j j i Lj J Y gi j iel jeJ Y Y gti j Su m Sum G ij jj lt D i i lt D iel jeJ SIMPLE definitions gt I lt Set J lt Set i lt Element set I j lt Element set J gt F lt Expression index I G lt Expression index I J Table 2 Sum notation in SIMPLE Prod is analogous In the SIMPLE definitions the form of the expressions for F and G remains to be specified 22 NUOPT f
15. Acid Conc gt 0 1 2 beta Air Flow gt 0 1 3 beta Water Temp gt 0 14 NUOPT for S PLUS User s Guide obj objective 42 1 80 beta Air Flow 27 beta Water Temp Finally the system sys stack can be solved by calling solve gt sol stack pos lt solve sys stack Special solve methods have been created for use with SIMPLE system objects in S PLUS Once defined variables can be selectively fixed and constraints can be added or removed from the model in an analysis see section 4 Another way to define models is to write a function containing the relevant SIMPLE commands For example the model 3 corresponds to the function LregPos defined as follows gt LregPos function X y Res lt Set Var Set i Element set Res j lt Element set Var nres length y y lt Parameter list l nres y index i X lt Parameter X index dprod i j beta lt Variable index j beta j gt 0 r lt Expression index i r i y i Sum X i j beta jl 3j obj lt Objective type minimize obj Sum r i r i i Note that LregPos does not return a value like a typical S PLUS function instead it specifies a model for use with the NUOPT solver The model function LregPos can be expanded with the stack data as follows gt sys LregPos stack lt System model LregPos stack x stack loss 15 Chapter3 Defining Optimization Models w
16. abstract models with different data SIMPLE computes information about function values as well as first and second derivatives which is made available to NUOPT in a form that can be processed efficiently by the a various solvers To compute derivatives SIMPLE uses recently developed automatic differentiation technigues executed by constructing computational graphs of the system and using the operator overloading functionality of the S PLUS language SIMPLE statements create pointers to underlying C code so that unlike S PLUS objects SIMPLE objects do not persist after an S PLUS session is terminated In addition to solving models defined by SIMPLE the NUOPT optimizer can also be directly applied to linear LP and quadratic programming QP models with the S PLUS function solveQP see section 2 When used via solveQP interface the default method becomes slightly different That is for QP problems without integer variables becomes line line search method for Convex programming 11 Starting NUOPT To start NUOPT for S PLUS in UNIX or Windows 1 Start S PLUS 2 Include the SIMPLI E system gt module nuopt first T NUOPT for S PLUS User s Guide Chapter 1 Introduction NUOPT for S PLUS User s Guide 2 solveQP for Mixed Integer Linear and Quadratic Programs The S PLUS function solveQP is designed for solving mixed integer linear and quadratic programming m
17. are too small they can cause numerical difficulties and inefficiencies Values that are too large can cause the computation to give inaccurate results The default value 10 works well for many MILP and MIQP applications 61 Chapter 5 The NUOPT Solver 4 limit on elapsed time of branch and bound calculation gt nuopt options maxtim 1 5 limit on number of branch and bound enumeration tree nodes MIP only gt nuopt options maxnod 1 In the course of the branch and bound enumeration large scale MILP MIQP instances with thousands of integer variables may produce an enumeration tree that is so large as to require a prohibitive amount of time to find a global optimal solution These parameters work as safeguards to limit the calculation time to a reasonable value maxtim sets a limit on the elapsed time in the branch and bound calculation process in seconds and maxnod sets a limit on the number of nodes in the branch and bound enumeration tree If either of these limits is reached in branch and bound enumeration NUOPT terminates the calculation and reports the best solution obtained so far For both parameters a negative value the default means no limit Related error messages are NUOPT 17 gt gt lt lt NUOPT 19 gt gt lt lt NUOPT 21 gt gt lt lt NUOPT 22 gt gt see sec tion 7 3 Note that maxtim limits the total elapsed time for optimization including data input preprocessing or solution
18. elements Value of nonzero elements All these vectors have the same length that is identical to the number of non zero elements in the 10 NUOPT for S PLUS User s Guide matrix For many applications this may be more compact representation of Hessian or Constraint matrix You can specify some of the variables are integer variables by specifying the logical vector isint whose length is identical to the number of variables The T components indicates the corresponding component of variable is integer variable The knapsack problem provides an example of the use of integer variables in solveQP A mathematical statement of the problem is maximize v x same as 5 in 3 3 1 subject to x 0 1 s x lt C x 0 1 To solve this problem with v 39 13 68 15 10 20 31 15 41 16 s 39 13 68 15 10 20 31 15 41 16 C 121 you should define the corresponding S PLUS vectors v s and scalar C and n lt length v gt solveQP objL v A matrix s 1 n cLO 0 cUP C bLO rep 0 n rbUPzrep l n typermaximize isint c rep T n The underlined arguments specify that some this time all of the variables are to be integer 11 Chapter 2 solveQP for Mixed Integer Linear and Quadratic Programs 12 NUOPT for S PLUS User s Guide 3 Defining Optimization Models with SIMPLE There are two approaches to defining an optimization model with SIMPLE They can be defined dynamically by typing the necessary definitions at
19. expression that is either el or e2 depending on the value of a constraint cons If cons holds for the current values of the variables then the function ife cons el e2 returns el otherwise e2 For example gt new model gt I lt Set gt i Element set 1 gt Abs lt Expression index i gt x lt Variable index i gt x i list letters 1 19 9 9 gt Abs i ife x i gt 0 x i x i gt Abs 28 NUOPT for S PLUS User s Guide abcdef ghijkimnopqrs 98765432101234567809 attr indexes 1 i You can write down some difficult models with discontinuous function by using ife But this do not always mean NUOPT can solve the model This is why the optimization methods implemented in NUOPT are all based on algorithms that assume the continuity of constraints and objective function and its derivatives around the local optimal solution If your model with ife violated this condition NUOPT may not give the desired result There known many workaround to express such a conditional expression by using continuous variables see for example 14 for details It is strongly recommended to examine if you can write your model before writing down the model using ife 3 5 System and Solution Objects SIMPLE models must be expanded into System objects through the function System in order to be solved by NUOPT As a simple example consider the problem of maximizing the sum of two nonneg
20. gt sys LregHuber stack System LregHuber stack x stack loss sol LregHuber stack solve sys LregHuber stack trace F summary sol LregHuber stack Svariables Svariables beta current lower upper initial dual Air Flow 0 9344302 Inf Inf 0 0 Water Temp 0 3445385 Inf Inf 0 0 Acid Conc 0 5349401 Inf Inf 0 0 Sexpressions Sexpressions r initial current 1 94992491215 oo 2271215 2 0 01777207 0 01777207 20 0 35377435 0 35377435 21 8 62133634 8 62133634 SexpressionsSrho initial current 1 0 5502712145 0 5502712145 2 0 0001579232 0 0001579232 20 0 0303774345 0 0303774345 21 0 8571336341 0 8571336341 Sobjective current 70 6 303447 counter iters fevals vars 16 418 3 Stermination tolerance residual 1 5e 06 2 24565e 15 Selapsed time 1 2 399994 Now we adjust the parameter C and solve again gt current sys LregHuber stack C 1 0 gt sol LregHuber stack lt solve sys LregHuber stack gt summary sol LregHuber stack Svariables Svariables beta current lower upper Air Flow 0 9094374 Inf Inf 0 9344302 Water Temp 0 4475915 Int Inf 0 3445385 Acid Conc 0 5426359 Inf Inf 0 5349401 Sexpressions Sexpressions r initial current 1 5 45462732 5 45462732 2 0 08800855 0 08800855 20 0 38418500 0 38418500 21 8 23258606 8 23258606 NUOPT for S PLUS User s Guide trace F initial dual 0 0 71 Chapter 6 Examples Sexpressio
21. of the first LP relaxation 6 limit on number of feasible solution of MIP before stopping gt nuopt options maxintsol 1 1 means no value is set For some large MIP case feasible solution is output in early stage of the branch and bound loop but take quite a lot of time to prove its optimality in such a case users wants the calculation terminate after pre determined number of feasible solution is obtained This specifies the maximum number of feasible solution before stopping The number of obtained solution reaches this value the calculation stops even the optimality of the best solution is not proved If the solution is not proved optimality NUOPT outputs the following error message lt lt NUOPT 37 gt gt B amp B terminated with given of int sol 7 cutoff value MIP only gt nuopt options cutoff 1 0e50 1 0e50 means no value is set 62 NUOPT for S PLUS User s Guide 8 margin to cutoff value gt nuopt options addToCutoff 0 These parameters set or modify a cutoff value used in the branch and bound enumeration By default the cutoff value is set equal to the objective function value of the best integral solution obtained so far Some branches of the enumeration tree are safely pruned and some computation is saved if the objective value of a relaxed problem on top of the branch is larger than the cutoff value hereafter the objective is assumed to be minimized Finding a small cutoff value fast is very
22. on line search for general Convex Programming CP models including convex Quadratic Programming CQP models 1ine primal dual interior point method based on trust region method for general Non Linear Programming NLP models trust primal dual interior point method based on quasi Newton method for general Non Linear Programming NLP models b gs active set method for convex Quadratic Programming CQP models and mixed integer Quadratic Programming MIQP models asqp The various methods within NUOPT have different characteristics and address different problem classes The algorithms can handle both unconstrained and constrained problems The simplex interior point methods except bfgs and active set method in NUOPT are designed to handle large scale problems Note that the interior point method based on trust region trust and quasi Newton method bfgs can deal with general Non Linear problem but the obtained solution cannot guaranteed to be a global optimal solution but a local solution That is why only the convergence to one of the local solutions is proved in theory There is no established method to obtain the global optimal for general non linear solution and problem specific technique is indispensable This is out of scope of this package But one may be able to accomplish this by writing some S PLUS script that run NUOPT many times by changing starting value or constraints By default the choice of the method is tra
23. periods t Element set Period j Element set Asset R lt Parameter rmat index dprod t j rBar lt Parameter list l p averet index Asset w lt Variable index Asset z lt Variable index Period 80 NUOPT for S PLUS User s Guide V Objective minimize V Sum z t 2 t Sum R t j rBar j w jl 3 z t 0 Sum rBar j w jl j gt rmin Sum w j j 1 To set up and solve the system for a return matrix port folio R you would issue the S PLUS commands gt averet apply portfolio R 2 mean Sys2 System model PortfolioAlt portfolio R averet gt sol2 solve sys2 V trace F Because the portfolio problem is a quadratic programming model it can directly be solved by solveQP without building a System see section 2 as follows The one correspond to PortfolioCor PortfolioCorQP function rcov averet rmin 0 0 trace F build the constraint matrix and constraint bounds A lt rbind averet 1 cLO lt c rmin 1 set the bounds on the portfolio weights bLO lt rep 0 ncol rcov arguments to solveQP multiply by 2 to correspond to PortfolioCor Sol lt solveQP objQ 2 rcov A A bLO bLO cLO cLO trace trace return sol To solve the model you would issue the S PLUS commands gt averet apply portfolio R 2 mean 81 Chapter 6 Examples gt Q lt crossprod sweep portfolio R 2
24. problem are required to obey Examples are the bound constraints 8 gt 0 in the linear regression model 3 expressed in SIMPLE as beta j gt 0 and the capacity constraint s x lt C inthe knapsack problem 5 expressed as Sum s i x i i lt Capacity in SIMPLE Constraints can also be defined with the Constraint function For the above examples alternative specifications using Constraint would be bounds lt Constraint index j bounds j beta j gt 0 and cap lt Constraint cap Sum s i x i i lt Capacity 25 Chapter3 Defining Optimization Models with STMPLE This feature is useful for analysis of model solutions and also when modifying constraints in a model that has already been compiled for NUOPT through the function System see section 4 3 4 2 Condition Objects While constraints in SIMPLE are defined by expressions and thus include variables conditions apply to set elements A condition is a logical expression for deciding whether or not to execute a model statement In a Condition object lt is used to denote set inclusion in conditions of the form Element lt Set There are two sorts of conditions global and local A global condition affects all subsequent model statements until another related global condition occurs As an example consider the a linear regression model similar to 3 gt new model gt Dow Set 1 15 gt i
25. specified in their definition even if the contents of the base set are changed Another way of defining an index set in SIMPLE is through auto assignment for example gt I Set gt i Element set 1 gt StackLoss lt Parameter index i Aw gt StackLoss list 1 1 stack loss gt TI 1dp 2 3 4 5 56 791 9 d0 11 12 123 14 151617 8 49 20 2 Assignment to StackLoss had the side effect of changing the index set I in this example The parameter StackLoss does not have to be indexed by numbers since it has length 21 it could for example be indexed by letters of the alphabet gt I lt Seti gt i lt Element set 1 18 NUOPT for S PLUS User s Guide StackLoss Parameter index i gt StackLoss list LETTERS 1 1 stack loss gt B ABCDEFGHIJKLMNOPQRS TU Unlike S PLUS objects subscripts of indexed SIMPLE objects must usually be explicitly expressed except when the object is displayed or when values are assigned to it as shown above for StackLoss For example adding 1 to the SIMPLE parameter StackLoss requires different syntax than adding 1 to the S PLUS vector stack loss gt StackLoss i 1 A B C D E E G H I J K L M NOP OR S TU 43 38 38 29 19 19 20 21 16 15 15 14 1213 9 89 9 10 16 16 attr indexes stack loss 1 1 43 38 38 29 19 19 20 20 1 6 15 15 14 12 13 9 28 9 9 210 16 16 Objects of class Set may have more than one
26. the S PLUS prompt level or else they can be defined within functions Note that for the S PLUS environment for windows prompt level means the S PLUS commands window not the script file window The definitions typed in the script window outside a function definition are ignored As an example we use a statistical model that is a linear least squares regression with positivity constraints on the regression parameters Given a matrix X and and a vector y whose length is equal to the number of rows in X the idea is to minimize the sum of squared residuals where r y Xf is the vector of residuals subject to the constraints that the coefficients P be non negative A mathematical statement of this problem would be Siete te yi T minimize r r where r y XB 3 subjectto 850 As an example let X and y bethe S PLUS datasets stack x and stack loss respectively a description is available by typing help stack at the S PLUS prompt First we show how to set up the problem with the default model approach The command gt new model clears the default model defined by SIMPLE statements typed at the prompt Now we type a sequence of SIMPLE statements that specify the model We start by setting up pointers to the necessary sets and indexes values will later be assigned to these automatically gt Res lt Set set of indexes for residuals gt Var lt Set set of indexes for variables gt i lt El
27. 0001 3 000034 4 000105 5 000166 6 000199 7 000207 8 000199 9 10 9 000184 10 00017 attr indexes EEP em gt current s1 p list 1 10 21 30 assign to the changeable Parameter gt sol2 solve sl f solve the system once more gt current s1l x the result of x is changed 1 2 3 4 5 6 7 8 36 NUOPT for S PLUS User s Guide 21 00005 22 00005 23 00004 24 00004 25 00004 26 00003 27 00003 28 00002 9 10 29 00002 30 00001 attr indexes 1 moy gt fix Variable sl x i i 5 amp amp i 1 fix a part of x gt current s1 p list 1 10 7 16 changeable Param gt current s1 p LA 5 6 Y 8 9 10 7 8 amp 10 11 12 13 14 15 16 attr indexes 1 i gt sol3 lt solve s1 f solve one more time gt current s1 x tt x 2 3 4 are not changed 1 2 3 4 5 6 7 8 7 000328 22 00005 23 00004 24 00004 11 00008 12 00003 13 14 00001 9 10 15 00006 16 00018 attr indexes gt unfix Variable sl x i i 2 unfix x 2 gt sol4 lt solve sl f gt current sl x x 2 is changed 1 2 3 4 5 6 7 8 7 000063 8 000007 23 00004 24 00004 11 00005 12 00005 13 00005 14 00005 9 10 15 00004 16 00004 attr indexes gt unfix Variable sl x tt unfix all x gt sol5 lt solve sl f gt current s1 x x 3 4 are changed 1 2 3 4 5 6 7 8 7 000122 8 000117 9 000026 10 00001 11 0001 12 0001 13 00009 14 00009 37 Chapter 4 Modifying Model Systems 9 10 15 00009 16 00008
28. 1 1 0 1 5 2 55 8 5 4 5 45 Chapter 4 Modifying Model Systems 5 0 0 0 0 0 0 O 0 attr indexes gt p3 lt Parameter matrix 1 6 2 3 index dprod a a gt p3 J i 12345 ub 3 50 0 224600 attr indexes dt array 2 7 c 2 3 dimnames list c a b c 1 2 3 gt p4 lt Parameter dt index dprod a a gt p4 i j 12345ab 10000000 a2460000 b 3 9 99 0 200 attr indexes as list p4 i j Sindexes Sindexes i 1 aw p a p a p Sindexes j 1 1 23 22 3 3 46 NUOPT for S PLUS User s Guide Svalues I 2 94 56 7 Variable and Expression have the same correspondence to S PLUS objects as Parameter 3 Interface between Parameter Variable Expression and data frames Data frames are interpreted as arrays in SIMPLE In order to assign data frame d to a SIMPLE object with only one index it must first be transformed to a vector in S PLUS unlist as vector d 47 NUOPT for S PLUS User s Guide 5 The NUOPT Solver The SIMPLE modeling language is combined with an optimizer called NUOP T which is invoked by the solve command When solve is invoked NUOPT prints a trace showing the progress and status of the calculations and the solution is accessible via SIMPLE objects Variable Expression and so on SIMPLE provides a way to control NUOPT by through the function nuopt options In this section we explain the
29. Element Condition Element Instance Error Messages from SIMPLE SIMPLE error messages have the following form lt lt SIMPLE num gt gt message where num is an identity number lt lt SIMPLE 1 gt gt Bound conflict Lower bound gt Upper Bound The lower bound and the upper bound of a variable or an expression conflict lt lt SIMPLE 4 gt gt Warning Length of a subscript exceeds 30 The length of a string name used as a subscript exceeds 30 Characters are ig nored beyond position 30 lt lt SIMPLE 6 gt gt Illegal characters and so on included in subscript lt lt SIMPLE 15 gt gt Internal Error An internal error has occurred Please contact support insightful com lt lt SIMPLE 19 gt gt Warning No auto assignment performed for constant set lt lt SIMPLE 24 gt gt Attempt to find the maximum of an empty set lt lt SIMPLE 49 gt gt A call has been made to an invalid function lt lt SIMPLE 53 gt gt Operation between elements of different dimension An attempt has been made to perform an elementary binary operation between two subscripts belonging two different dimension sets 86 NUOPT for S PLUS User s Guide lt lt SIMPLE 58 gt gt Set difference error s1 s2 in which s1 doesn t include s2 An attempt has been made to do a set difference s1 s2 in which s2 is not a subset of s1 lt lt SIMPLE 59 gt
30. NUOPT for S PLUS User s Guide Version 1 4 Mathematical Systems Inc Tokyo Japan Insightful Corporation Seattle Washington USA March 2002 NUOPT for S PLUS User s Guide How to Contact Insightful Corporation Telephone 1 206 283 8802 Fax 1 206 283 8691 WWW www insightful com Mail Insightful Corporation 1700 Westlake Avenue N Suite 500 Seattle WA 98109 USA Email info insightful com Technical Support support insightful com Bug reports bugs insightful com Proprietary Notice 2002 Mathematical Systems Inc and Insightful Corporation All rights reserved The correct bibliographical reference for this document is as follows NUOPT for S PLUS User s Guide Version 1 4 Mathematical Systems Tokyo Japan and Insightful Corp Seattle Washington USA 2002 Mathematical Systems Inc owns both this software program and its documentation Both the program and documentation are copyrighted with all rights reserved by Mathematical Systems Inc No part of this document can be photocopied or reproduced in any form without prior written consent from Insightful Corp S PLUS is a registered trademark of Insightful Corp NUOPT is a trademark of Mathematical Systems Inc Other product or brand names are trademarks or registered trademarks of their respective holders NUOPT for S PLUS User s Guide Contents HOW TO CONTACT INSIGHTFUL CORPORATION cccssssesseesssessecsecescesecesecessecsecesscsscesaeessecssessec
31. P MILP MIQP with the method simplex method for LP and MILP active set method for QP and MIQP cn The relative machine precision in S PLUS itis Machine double eps 60 NUOPT for S PLUS User s Guide These parameters are related to the simplex algorithm and are not valid for IPM methods such as higher order method for linear programming trust region method for general non linear programming line search method for convex programming BFGS method for small non linear programming The following is a list of the relevant parameters those designated MIP only are valid exclu sively for the bound enumeration scheme invoked when solving MILP or MIQP by the simplex or active set method 1 primal feasibility tolerance gt nuopt options tolx 1 0e 8 This parameter gives the allowed relative error in the feasibility of primal variables Our experiments show that the default value 10 works well for many real life LP applica tions 2 dual feasibility tolerance gt nuopt options told 1 0e 6 This parameter gives the allowed relative error in the feasibility of dual variables or reduced costs shadow prices Our experiments show the default value 107 works well for many real life LP applications 3 integer feasibility tolerance MIP only gt nuopt options epsint 1 0e 4 This parameter gives a tolerance for integrality conditions on integer variables in MILP and MIOP If these values
32. apter 4 Modifying Model Systems 1 a nj gt a3 Set index dprod i j tt set w gt az list c l 1 2 3 1 2 3 1 1is gt a3 1 1 ab 3 1 51 52 53 54 55 1 2 31 32 33 2 3 41 42 indexes i j gt as list a3 Sindexes Sindexes i fi I 3 a 2 Sindexes j TI 1 13 values Svalues 1 1 a p Svalues 2 Et 54 52 53 54 55 Svalues 3 i 34 32 33 Svalues 4 1 41 42 2 Interface between Parameter Variable ith two indexes t c a b 31 33 41 42 51 55 the same as unclass a3 new model 44 Expression and vector list array NUOPT for S PLUS User s Guide gt a lt Set 1 5 gt i lt Element set a gt j lt Element set a gt p lt Parameter 3 33 p is initialized to 3 33 1 3 33 gt pl lt Parameter list 2 3 c 2 2 3 3 index i parameter with one index gt pl tt the same as as array pl and unclass pl 1 2 3 405 0 272 3 3 0 0 attr indexes gt as list pl pl is transformed to a list corresponding to Sindexes tt pl 2 2 2 p1 3 3 3 Sindexes i where p1 1 p1 4 p1 5 0 are removed 1 2 3 Svalues LL 22 93 gt p1 i 1 toux 34b Le B82 Ase ST 1 attr indexes here indexes is to specify what 3 cg M the values depend on gt p2 lt Parameter index dprod i j parameter with two indexes gt p2 list c l 2 3 1 0c 3 2
33. as follows 16 NUOPT for S PLUS User s Guide Set Element Parameter Variable IntegerVariable Expression Objective Constraint Graph System and Condition Except for Condition all have a generator function of the same name Models in SIMPLE are lists of statements involving these objects Their formal definitions are given in the appendix and their use is described in more detail in the sections that follow In addition a total of 16 functions are provided to facilitate designing testing and solving systems models as shown in Table 3 These functions are also described in the sections that follow Table 3 Functions for system controlling Function Arguments Brief Description show model Sys list model definitions System print System delete con restore con add con solve System current init lowerB upperB dual as list fix Variable unfix Variable new model model lt args gt trace sys type obj num Sys obj mem sys obj mem Sys obj sys obj trace Sys obj sys obj sys obj sys ob sys obj obj sys X sys X make a new system by expanding constraints args arguments for function model list contents of a system remove a constraint from a system restore a deleted constraint from a system add a constraint to a system solve a system show the current value of obj of a system show the init value of obj of a system show the lower bound of Var
34. ative variables that lie inside the unit circle maximize x y 6 subject to x y lt 1 x20 y gt 0 In SIMPLII E this model can be expressed as gt new model gt IL lt gt Set 1 2 gt i Element set 1 gt x lt Variable index I gt unitcirc lt Constraint gt umitelre Sumix ui x r 1 lt 1 gt x i gt 0 f Objective maximize gt f Sum x i i gt x i 1 initial values 29 Chapter3 Defining Optimization Models with STMPLE Now we expand the model into a system for solution by NUOPT gt sys lt System Evaluating Ta unitcirc Sum x i x i i lt 1 Lia x i gt 0 3 f Sum x 1 1 4 x i 1 Expanding 1 3 2 3 3 3 ok and display the expanded model gt sys 1 1 unitcirc x 1 x 1 x 2 x 2 lt 1 f objective x 1 x 2 maximize Next we solve the expanded model gt sol lt solve sys UOPT 4 6 0 Copyright C 1991 2001 Mathematical Systems Inc UMBER OF VARIABLES 2 UMBER OF FUNCTIONS 2 PROBLEM TYPE MAXIMIZATION ETHOD TRUST REGION lt preprocess begin Xpreprocess end Xiteration begin res 1 9e 001 2 5e 008 lt iteration end gt STATUS OPTIMAL VALUE OF OBJECTIVE 1 414213548 ITERATION COUNT 5 FUNC EVAL COUNT 8 30 NUOPT for S PLUS User s Guide FACTORIZATION COUNT 8 RESIDUAL 2 459224485e 008 ELAPSED TIME sec 0 68 The solution object is a list with several
35. averet gt sol3 lt PortfolioCorQP Q averet We can also use arguments to sol veQP which correspond to the Port folioAlt version gt PortfolioAltOP function rmat averet rmin 0 0 trace F n lt nrow rmat p lt ncol rmat objective function objQ diag c rep 0 p rep 1 n build the constraint matrix and constraint bounds A lt cbind rbind sweep rmat 2 averet averet 1 rbind diag rep 1 n matrix 0 2 n cLO lt c rep 0 n rmin 1 CUP c rep 0 n Inf 1 set the bounds on the portfolio weights bLO lt c rep 0 p rep Inf n call the solver and extract the optimal weights multiply by 2 to correspond to PortfolioAlt Sol lt solveQP objO 2 objQ A A bLO bLO cLO cLO CUP CUP trace trace return sol To solve the model you would issue the S PLUS commands gt averet lt apply portfolio R 2 mean gt sol4 PortfolioAltOP portfolio R averet 82 NUOPT for S PLUS User s Guide References 1 D P Bertsekas 1991 Linear Network Optimization The MIT Press 2 D Bertsimas and J N Tsitsiklis 1997 Introduction to Linear Optimization Athena Scientific 3 I Bongartz A R Conn N I M Gould and Ph L Toint 1995 CUTE Constrained and Unconstrained Testing Environment ACM Transactions on Mathematical Software 21 123 160 4 D M Gay 1991 Automatic Differentiation of Nonlinear AMPL Models in Automati
36. bproblems that occur in the enumeration process Among other methods currently incorporated in NUOPT the simplex and active set method are capable of handling integer variables Therefore they are the default choice in NUOPT for MIP models For MILP NUOPT s default choice is simplex for LP the higher order method see section 5 2 1 To force to select the simplex method for LP type gt nuopt options method simplex The simplex method is effective when a basic feasible solution is required or the problem instance is relatively small up to hundreds of variables Our experiments show that the simplex method solves small LP instances up to hundreds of variables faster than the higher order method The simplex method cannot handle nonlinear problems If the simplex method is selected Simplex method is for Mixed integer linear programming models active set method for Mixed integer Quadratic programming models Because none of these methods can handle general nonlinear models NUOPT cannot handle nonlinear models with integer variables 54 NUOPT for S PLUS User s Guide for a nonlinear problem NUOPT will reject it with the error message NUOPT 15 gt gt simplex asqp method misapplied to NLP 5 2 3 line search method for CP The line search method 9 is an interior point method capable of handling convex programming CP models Convex programming is a class of optimization models in which a convex objective
37. c Differentiation of Algorithms theory implementation and application A Griewank and G F Corliss editors SIAM 1991 61 73 5 G H Golub and C F Van Loan 1996 Matrix Computations 3rd edition Johns Hop kins 6 J Gondzio 1994 Multiple Centrality Corrections in a Primal Dual Method for Linear Programming Technical Report 1994 20 Logilab HEC Section of Management Studies University of Geneva revised 1995 7 W Hock and K Schittkowski 1980 Lecture Notes in Economics and Mathematical Systems 187 Test Examples for Nonlinear Programming Codes M Beckmann and H P Kunzi editors Springer Verlag 8 Statistical Science 1993 S PLUS Programmer s Manual Version 3 2 Seattle StatSci a division of MathSoft Inc 9 H Yamashita 1992 A globally convergent primal dual interior point method for con strained optimization Technical Report Mathematical Systems Institute In c Tokyo Japan 10 H Yamashita and H Yabe 1993 Superlinear and quadratic convergence of primal dual interior point methods for constrained optimization Technical Report Mathematical 83 References Systems Institute Inc Tokyo Japan 11 H Yamashita and T Tanabe 1993 A primal dual interior point trust region method for large scale constrained optimization Technical Report Mathematical Systems Institute Inc Tokyo Japan 12 H M Markowitz 1959 Portfolio Selection Efficient Diversification of In
38. components sol Svariables x 1 2 0 7071068 0 7071068 attr indexes 1 xm Sobjective 1 1 414214 counter iters fevals vars 5 8 2 Stermination tolerance residual 1 7e 006 2 459224e 008 Selapsed time 1 0 6809999 SerrorCode 1 0 errorCode is the error number of returned from NUOPT if no error occurred it becomes zero This is useful when calling the solve method in some user defined program checking the result of the optimization and modify the process There are more components to the solution object corresponding to lower bounds upper 31 Chapter3 Defining Optimization Models with STMPLE bounds and dual variables all components can be viewed by applying the function unclass Separate functions 1owerB upperB and dual are provided to extract these quantities lowerB sys x 1 2 0 0 attr indexes 1 xm upperB sys x 1 2 Inf Inf attr indexes 1 xm dual sys x 1 2 4 333893e 007 4 333893e 007 attr indexes 1 xm dual sys unitcirc 1 0 7071066 Current and inital values of variables and expressions are also available through functions current and init init sys x 12 1 1 attr indexes 1 current sys Prod x i i 1 0 5000004 32 Modifyin NUOPT for S PLUS User s Guide g Model Systems NUOPT for S PLUS provides several ways of modify System objects for their analysi
39. d for optimization the dots on the right of res indicate the progress of the iteration one dot per iteration also shown are successive values of the normalized residual of the optimality condition The next line gives the status OPTIMAL means a successful termination of the optimization method If an error occurs see section 7 3 the status is indicated as NON OPTIMAL and an error message is displayed STATUS NON OPTIMAL ERROR TYPE lt lt NUOPT 15 gt gt simplex method misapplied to NLP A summary report of the interior point method follows in the next line including the optimal objective function value interior point iteration count function evaluation count factorization count and final residual of optimality condition The last line shows the over all elapsed time for the execution of NUOPT 5 1 1 Messages from the Simplex Active Set Method for LP QP When using the simplex method option for linear programming the METHOD line indicates SIMPLEX in this case the calculation progress report becomes iteration begin iteration end The dots indicate the progress of the simplex method iteration one dot per some fixed number of iterations the letter 1 and 2 indicates the end of phase I search for feasible solution and phase2 search for optimal solution respectively When the crossover switch see section 5 3 1 is activated NUOPT starts a simplex method 50 NUOPT for S PLUS User s Guide iterat
40. dimension depending on the dimensionality of the objects it is intended to define For example to define a SIMPLE parameter StackX whose value is that same as that of the S PLUS matrix stack x Observations Set Measurements Set gt j lt Element set Observations gt k lt Element set Measurements gt StackX lt Parameter index dprod Observations Measurements gt StackX stack x gt StackX Air Flow Water Temp Acid Conc 1 80 27 89 2 80 27 88 20 56 20 82 19 Chapter3 Defining Optimization Models with STMPLE 21 70 20 91 attr indexes 1 xan m W The parameter is indexed by the set dprod Observations Measurements which is the direct product of the set Observations and the set Measurements Either gt StackX lt Parameter index dprod j k or gt StackX lt Parameter index Observations Measurements could also have been used in the above definition SIMPLE provides the following operations between sets Union A B Intersection A amp B Difference A B Direct Product A B Multidimensional sets may also be defined explicitly for example if gt N Set 1 2 Ti lt Set c a no then the set gt NL Set c 1 a 1 b 2 a 2 b dim 2 is the direct product of sets N and L also denoted by N L 3 2 Parameter Variable and Expression Objects Objects of class Parameter are those values that are to b
41. e treated as constants by the NUOPT solver Objects of class Variable are those whose values are to be determined by solving the model Objects of class Expression are mathematical expressions containing at least one variable In the constrained linear regression example 3 the matrix X and vector y are parameters f isa vector of variables and r denotes an expression for the residuals Parameters variables and expressions can be evaluated in a system that has been defined 20 NUOPT for S PLUS User s Guide in SIMPLE through the function current If we solve the SIMPLE model defined by function LregPos representing 3 with the stack data sys LregPos stack System model LregPos stack x stack loss sol LregPos stack solve sys LregPos stack then the current value of the residual r can be found by current sys LregPos stack r 1 2 3 4 5 6 7 8 17 59946 12 59947 14 14511 8 886675 0 9813663 1 047346 0 1133327 0 8866673 9 10 11 12 13 14 15 2 916397 3 586491 3 586503 4 520523 6 586494 5 652488 7 324605 16 17 18 19 20 21 8 324601 7 390562 7 390571 6 456552 2 152978 6 111311 attr indexes Similarly for current value of XP gt current sys LregPos stack Sum X i j beta j j 1 2 3 4 5 6 7 8 24 40054 24 40053 22 85489 19 11332 18 98137 19 04735 19 11333 19 11333 9 10 11 T2 13 14 15 16 17 17 9164 17 58649 17 5865 17 52052 17 58649 17 65249 15 32461 15 3246 15 39056 18 19 20 21 15
42. ement set Res gt j Element set Var E Now we define the vector y and matrix X as parameters in SIMPLI gt nres lt length stack loss number of residuals gt y Parameter list l nres stack loss index i gt X lt Parameter stack x index dprod i j 13 Chapter3 Defining Optimization Models with STMPLE Sets Res and Var now have values gt Res b 42 3 4 556 7 899 0 2 T2 13 14 15 46 17 18 19 20 21 y gt Var Air Flow Water Temp Acid Conc Assignment of values to sets in SIMPLE is discussed in further detail in section 3 1 Next we define the variables together with their bounds that are the problem constraints gt beta Variable index j pointer to variables gt beta j gt 0 variable bound constraints Finally we define the objective function gt r lt Expression index 1 pointer to vector of residuals gt r i y li Sum X i j beta j j define vector of residuals gt obj lt Objective type minimize pointer to objective function gt obj Sum r i r i i define objective function The model typed so far can be displayed as follows gt show model T beta j gt 0 2 r i y i Sum X i j beta j j 3 obj Sum r i r i i In order to solve the model we use the System function to expand compile the model into a form machine code that can be directly processed by the solver gt sys stack lt System 1 1 beta
43. eseeseeeseees 2 PROPRIETARYNOTIGE Li WN Epio te d e WR De EE epe ee Pe ple WD vaet WN 2 CONTENJES 4 deu AA eode addo e Wee Qudua sk oed doe eiae HY YH HY 3 1 INTRODUCTION checa iii 5 1 1 STARTING NUOP Tora hu te eb id eolit a abite t 7 2 SOLVEOP FOR MIXED INTEGER LINEAR AND QUADRATIC PROGRAMSS 9 3 DEFINING OPTIMIZATION MODELS WITH SIMPLE sccsscsssscssccsesosssscescecsecsssecsecessecsecssseees 13 3 1 SETAND ELEMENT OBJECTS INDEXING AND AUTO ASSIGNMENT esee 17 3 2 PARAMETER VARIABLE AND EXPRESSION OBJECTS eese ennt 20 3 3 INTEGER VARIABLES xi YG rotto trash tabe i eoi ra he e Ie bet 23 3 4 CONSTRAINTS AND CONDITIONS eese eere n rennen eren t tette ere nennen enne nnn 25 3 5 SYSTEM AND SOLUTION OBJECTS ccccscccsssessccessessecsscesseesscesscssseceseeseecscesseceecenssecsecesscseeeneens 29 4 MODIFYING MODEL SYSTEMS csccssscsscccsscsscecossosccssscccssccssccssscssecussessecssccecsecussecsecessecnecssseees 33 4 1 ADDING AND DELETING CONSTRAINTS eere nennen nennen trees ee FL ntn eredi ne 33 4 2 FIXING VARIABLES AND CHANGING PARAMETERS cccccesscesssscceseccensecesscecesceceesscesseeensceeene 36 43 GRAPH OBJECTS Sanaa tie tese tite eese vd vea dia 38 4 4 INTERFACE BETWEEN SIMPLE OBJECTS AND S PLUS OBJECTS 42 5 THENUOPT SOLVER decetero tele pe cete A eee 49 5 1 OUTPUT MESSAGES FROM NUOPT T uasna nennen enne i
44. following topics output messages from NUOPT optimization methods in NUOPT parameters to control NUOPT 5 1 Output messages from NUOPT setting parameters When the solve command is invoked with the argument trace set to TRU output of NUOPT will look like the following E the default the UOPT 4 2 2 Copyright C 1991 2000 Mathematical Systems Inc UMBER OF VARIABLES 10 UMBER OF FUNCTIONS 1 PROBLEM TYPE MINIMIZATION ETHOD TRUST REGION lt preprocess begin lt preprocess end lt iteration begin res 1 0e 000 1 3e 004 2 5e 009 iteration end STATUS OPTIMAL VALUE OF OBJECTIVE 45 77846971 ITERATION COUNT 7 FUNC EVAL COUNT 9 FACTORIZATION COUNT 8 This is suppressed when the t race argument of solve is set to FALSE 49 Chapter 5 The NUOPT Solver RESIDUAL 2 494695073e 009 ELAPSED TIME sec 0 18 The first three lines indicate the version of NUOPT and the number of variables functions Both the constraints and the objective function are counted in the NUMBER OF FUNCTIONS The next two lines show the problem type minimization maximization and optimization method applied In this case NUOPT reports that a trust region method was applied TRUST REGION See Section 5 2 about the various methods available in NUOPT and their choice The next four lines show the progress of the preprocessing and optimization phases When an interior point method is use
45. iable or Constraint of a system show the upper bound of Variable or Constraint of a system show the dual bound of Variable or Constraint of a system transform to a list fix the value of a variable in a system unfix the value of a variable in a system renew the default model 3 Setand Element Objects Indexing and Auto assignment Set and Element objects are used for indexing in SIMPLI E Sets in SIMPLE are analogous to vectors 17 Chapter3 Defining Optimization Models with STMPLE of character strings in S PLUS used as names for vectors and dimnames for arrays For example to specify a parameter vector StackLoss with the values of the S PLUS dataset stack loss gt 1 length stack loss I Set 1 1 gt i Element set 1 StackLoss Parameter index i sets up pointer gt StackLoss list 1 l stack loss assigns value StackLoss 4 2 Bordo 5 o6 T 8 910 lt I2 I3 14 15 I6 l7 181920 21 42 37 37 28 18 18 19 2015 14 14 13 1112 8 7 8 8 9 15 15 attr indexes 1 woe In SIMPLE an Element is used as a subscript for objects defined to represent elements of a base set In the above example i is defined to represent elements of set I or equivalently I is the base set of the index i The contents of a Set object in SIMPLE are independent of any associated Element objects The latter once defined must always be used as subscripts for the base set
46. important for efficiency but it is generally not an easy task for a solver without some knowledge of the model structure If an approximate objective value is known beforehand it is advisable to set the cutoff value manually to save computation By default cutoff is set to a huge value 10 Any value larger than this means that there is no effective cutoff value As explained above we update the cutoff value to be the best integral solution obtained so far addToCutof f is a positive value that gives a margin to the cutoff value in updating namely cutoffvalue lt f addToCutoff Here f is the objective value of the best integral solution obtained When the objective function is maximized we update the cutoff value as follows cutoffvalue lt f addToCutoff A large value of addToCutof f causes a better cutoff value and results in saving some computational effort However the larger the value of add ToCutof f the more the opti mality of the solution is degraded it can only be guaranteed that there are is solution that gives a better optimal value within addToCutoff Parameters 4 to 8 are to limit the calculation of branch and bound loop to set these parameters you can consult the information of the feasible solution obtained by setting gt nuopt options mipfeasout on report each feasible sol each obtained By doing this you can see the optimal value of feasible solutions namely the objective value of the s
47. ing gt a lt list c 1 2 1 3 2 3 c 2 4 3 4 3 2 c 1 3 3 1 1 1 Cost gt sup lt list c 1 4 c 1 1 The supply of nodes gt s5 System MinCostFlow a sup Evaluating MinCostFlow a sup ok Expanding 1 3 2 3 3 3 ok 40 NUOPT for S PLUS User s Guide gt s5 1 1 x 2 3 x 2 4 x 3 2 x 1 2 0 1 2 x 2 4 x 3 4 1 1 3 x 2 3 x 3 2 x 3 4 x 1 3 O 1 4 x 1 2 x 1 3 1 f lt objective gt x 2 3 3 x 2 4 x 3 2 x 1 2 x 3 4 33 x 1 3 minimize sol5 solve s5 f gt sol5 solve s5 f UOPT 4 2 2 Copyright C 1991 2000 Mathematical Systems Inc UMBER_OF_VARIABLES 6 UMBER OF FUNCTIONS 5 PROBLEM TYPE MINIMIZATION ETHOD HIGHER ORDER lt preprocess begin lt preprocess end lt iteration begin res 1 9e 000 2 7e 007 1 4e 010 iteration end STATUS OPTIMAL VALUE OF OBJECTIVE 3 000000002 ITERATION COUNT 6 FUNC EVAL COUNT 8 FACTORIZATION COUNT 7 RESIDUAL 1 37376295e 010 ELAPSED TIME sec 0 18 gt sols Svariables variables x 2 3 4 41 Chapter 4 Modifying Model Systems 1 1 000000e 000 6 131224e 010 NA 2 NA 1 000000e 000 6 131224e 010 3 3 070398e 010 NA 1 000000e 000 attr Svariables x indexes 1 kw Sobjective 4 3 counter iters fevals vars 6 8 6 Stermination tolerance residual le 008 1 373763e 010 Selapsed time 1 0 18 The time for solving MinCostFlow with NUOPT i
48. ion from the result of an interior point method that finds a basic feasible solution about a basic solution see 2 for example In this case a progress report of the simplex method follows that of the interior point method lt preprocess begin lt preprocess end iteration begin res 1 7e 00 ass E06 amp 02 2490 04 8 26 07 asc 5 6e 08 7 5e 09 iteration end iteration begin iZ lt iteration end gt When the simplex method is invoked there is an additional line SIMPLEX PIVOT COUNT number to report the simplex pivot count If the model contains an integer variable a branch and bound enumeration scheme is invoked automatically In this case the calculation progress report looks like lt iteration begin xls sw BA s bomo Sears tae ts Diep DE oy lt iteration end gt The dots and letter p indicate the progress of the simplex method iteration to solve the first relaxation The letter B indicates the start of branch and bound enumeration followed by dots that indicate the progress of the enumeration process The letter I indicates the update of current best integer feasible solution When you set the option gt nuopt options mipfeasout on report each feasible sol when obtained NUOPT report the objective value of the solution each time they are obtained With obtained time and the current number of simplex pivoting piv and enumeration node prob as lt iteration begin gt 1
49. ir enei ate LLIF tes lt FN 49 5 2 CHOOSING AN OPTIMIZATION METHOD coooccocccnoncnnnononcnnnionccnnnnnnncnnncnnnonancnnne nano I FI iN 52 53 SETTING PARAMETERS ia ta et et eer E n Y YG OG YY dd 57 SA OPTIONS FORTHE SOLVER etit e tal Ms eS o a LES 64 O EXAMBLES ee Lon o he ei AE ELE 69 6 1 A SIMPLE STATISTICALLY ORIENTED OPTIMIZATION PROBLEM tete 69 6 22 HE DIET PROBLEM 3 a a as FYN Y FEN 72 6 3 3MAXIMATNSGON 29m ee aeter t tete pete noth diete ere dee 75 6 4 LARGE SCALE PORTFOLI MODEL a RE SR VISUS 78 REFERENCES Sn Mt Om a a un da ue SARA EAE YN CE OT sss 83 Table of Contents APPENDIX ais 85 FORMAL SYNTAX OESIMPEE shi as ita 85 ERROR MESSAGES FROM SIMDEE rtt iia 86 91 ERROR MESSAGES FROM NUO P Thra aE EEE anno tree etnies ennt stie elnezo ense nne nne NUOPT for S PLUS User s Guide 1 Introduction NUOPT for S PLUS is a combination of the S PLUS programming environment the NUOPT optimizer and the SIMPLE modeling language NUOPT stands for NUmerical OPTimization and SIMPLE stands for System for Interactive Modeling in a Programming Language Environment NUOPT is a collection of powerful optimization methods including primal dual interior point method with higher order correction for Linear Programming LP models higher simplex method for Linear Programming LP and mixed integer programming MILP models simplex primal dual interior point method based
50. is 2 3 3 0 137 LE arc from node 3 is 3 1 1 131 2 LES arcs from node 1 are 1 3 and 1 2 indexes i gt e lt Element set arcs g gt p lt Parameter index i gt pli i gt plorig e first component of e NA not defined 2 32 1 l X ENA 2 NA 2 NA 3 NA NA 3 attr indexes Next we give an example of a model defined on a graph 4 3 1 The Minimum Cost Flow Problem The minimum cost flow problem finds a set of arc flows of a graph minimizing a linear cost function subject to the constraints that the flows produce a given divergence vector and lie within certain bounds That is minimize b ay Xj 39 Chapter 4 Modifying Model Systems constraint Ad 2 s V eN UG e4 UDS b Sx Sey VGj e4 where a j bjand s are given scalars For simplicity we assume the bounds to be b 0 and cij oo for each i j The minimum cost flow problem is described as follows gt MinCostFlow function cost snodes g lt Graph i lt Element set nodes g e lt Element set arcs g eout lt Element set output g i ein lt Element set input g i x lt Variable index arcs g a lt Parameter cost index arcs g S lt Parameter snodes index nodes g Sum x eout eout Sum x ein ein s i x e gt 0 f Objective minimize f Sum a e x e e To obtain its solution in SIMPLI E do the follow
51. ith STMPLE giving the system we originally defined by typing at the prompt The above processes can also be packaged into a single function SolveLregPos lt function X y solve System model LregPos X y You may have noticed that an alternate formulation optimization problem having the same solution as 3 is dantis T minimize rr 4 subjectto r 2 y XB B gt 0 Here auxiliary variables 7 representing the residuals have been introduced and their definition in terms of and y added as linear constraints to the problem This formulation of the problem can expressed in SIMPLE by changing statements gt r lt Expression index i gt r i y li Sum X i j beta j j to gt r lt Variable index i gt r i y i Sum X i j beta j j constraint definition An analysis of alternative formulations for a similar model is given in section 6 4 Note also that 3 and 4 are quadratic programs so that they could be solved with solveQP In the case of 3 the Hessian matrix would be X 1X multiplied by a factor of 1 2 when calling solveQP and the vector specifying the linear part would be y X For 4 the quadratic part of the objective would be the identity matrix with dimension equal to the length of the residual vector r in S PLUS diag length r and there would be no linear part of the objective The classes of objects used in SIMPLE for defining optimization models are
52. les in this model There are no variables in the model FATAL lt lt NUOPT 5 gt gt infeasible variable bounds Variable bounds cause infeasibility consider the integrality of some variables FATAL lt lt NUOPT 6 gt gt unbounded linear constraints and variable bounds The model looks unbounded determined by linear constraints and bounds FATAL lt lt NUOPT 7 gt gt internal error internal function name An internal error has occurred Please contact support insightful com FATAL lt lt NUOPT 8 gt gt memory error in optimization phase The required memory reaches its limit in the optimization phase FATAL lt lt NUOPT 9 gt gt step reduction limit exceeded A line search failed at some iteration lt lt NUOPT 10 gt gt IPM iteration limit exceeded The IPM interior point method iteration count reaches its limit given by parameter maxitn lt lt NUOPT 11 gt gt infeasible 91 Appendix The model is determined to be infeasible lt lt NUOPT 13 gt gt unbounded The model is determined to be unbounded lt lt NUOPT 14 gt gt integrality is violated Some integer variables remain fractional at the solution If a model contains integer variables only the simplex method can guarantee integrality lt lt NUOPT 15 gt gt simplex asqp misapplied to NLP An attempt has been made to apply the simplex method to NLP the simplex method and active set method cann
53. llowed An invalid specification fixing the value of a constraint I lt lt SIMPLE 125 gt gt Remove Restore Constraint number out of range A non existent constraint number is specified in delete conor restore con I lt lt SIMPLE 140 gt gt Fixed value out of range for variable An attempt has been made to fix a variable at its current value that is out of range For example in x lt Variable 3 x gt 10 s1 lt System fix Variable sl x the current value x is 3 which is out of x s range x gt 10 so that x can not be fixed 88 NUOPT for S PLUS User s Guide to its current value i lt lt SIMPLE 142 gt gt Constraint object required in function call The constraint argument for function delete con restore con must be an object defined by the Constraint function For example delete con sl x i t y i gt 6 is not allowed lt lt SIMPLE 163 gt gt No current value for empty constraint lt lt SIMPLE 164 gt gt No initial value for empty constraint lt lt SIMPLE 165 gt gt No dual value for constraint that is empty or before the model is solved I lt lt SIMPLE 167 gt gt No val dual value exists for multiply assigned Constraint id An attempt has been made to show the current or dual values of a multiply defined constraint For example if we define co sin x lt y lt z the current dual values of co is not uniquely defined
54. ms values for the variables x whose default value is the zero vector of length 77 The argument isint is a logical vector T or F specifying which component of variables are integer variables For example suppose we want to find the minimum Euclidean norm solution to a system of underdetermined linear equations This problem can be posed as the following quadratic program minimize Q subject to XB y where X is a matrix with more columns than rows and y is a vector This can be solved with solveQP as follows gt objQ lt diag ncol X no need for factor of 1 2 since no linear term gt sol lt solveQP objQ objQ A X cLO y cUP y type minimize This problem can also be solved using the singular value decomposition e g 5 However in the large sparse case the quadratic programming formulation may be more efficient Matrices objQ and A can be specified to solveQP in a sparse format For example if X is given by and y is any vector of length 2 the QP 2 would be solved in sparse format The following is the representation of the same problem by sparse format p ncol X gt sparseQ list l p l p rep l p gt sparsex lt lIrst C l l 2 2 Q i 3 25 4 Qc Lb 4 01 35 2 2 2 4 gt solveQP objO sparseQ A sparseX cLO y cUP y type minimize The matrix is given by a list that consists ofthe three vectors as below Row number of nonzero elements Column number of nonzero
55. n sys LregPosAlt stack Sum beta j j 1 1 1 B Acid Conc beta Acid Conc gt 0 1 2 B Air Flow beta Air Flow gt 0 1 3 B Water Temp beta Water Temp gt 0 2 1 R 1 80 beta Air Flow 27 beta Water Temp 2 2 R 2 80 beta Air Flow 27 beta Water Temp 2 20 R 20 56 beta Air Flow 20 beta Water Temp lt lt lt deleted gt gt gt 2 21 R 21 70 beta Air Flow 20 beta Water Temp lt lt lt deleted gt gt gt 3 1 beta Air Flow beta Water Temp beta Acid Conc 1 obj lt objective gt r 1 r 1 r 2 r 2 z 3 x 3 35 Chapter 4 Modifying Model Systems solve sys LregPosAlt stack 4 2 Fixing Variables and Changing Parameters Current values of Variables of the system can be changed and the system can be resolved with these new values We can also change some Parameters of a system may be modified by specifying them as changeable Another useful tool is to fix variables at specific values For example gt initVal a sample model function a lt Set 1 10 i lt Element set a p lt Parameter list 1 10 1 10 index i changeable T x lt Variable list 1 10 rep 30 10 index i x i gt p i f lt Objective minimize f Sum 1 x i 50 i gt sl System initVal making a System gt soll solve sl f solve the System gt current s1 x result of variable x 1 2 3 4 5 6 7 8 1 000116 2 00
56. ned range lt lt SIMPLE 91 gt gt Operation between sets of different dimension For example the error message occurs on the following case a Set 1 5 b Element 1 6 dim 2 a amp b 87 Appendix lt lt SIMPLE 92 gt gt Warning No auto assignment performed for For example ina lt Set 1 2 b lt Set 3 4 d lt Set superSet a b the last statement produces the warning No auto assignment performed for Union a b I lt lt SIMPLE 102 gt gt Set assignment dimension conflict An attempt is made to assign one set to another having different dimension I lt lt SIMPLE 103 gt gt superSet not defined for sets having different dimensions I lt lt SIMPLE 104 gt gt can not be a superset of t The first object can not be a super set of the second one lt lt SIMPLE 106 gt gt Argument arcs must be a 2 dimensional set lt lt SIMPLE 107 gt gt Argument nodes must be a 1 dimensional set The argument nodes for function Graph must be a 1 dimensional dim 1 set I lt lt SIMPLE 111 gt gt Assignment rhs includes free subscript A free subscript occurs on the right hand side of an assignment lt lt SIMPLE 113 gt gt Invalid assignment Any error in assignment not covered by other messages I lt lt SIMPLE 121 gt gt Invalid constraint specification parameter lt expr gt parameter is not a
57. nsSrho initial current 1 4 954627315 4 954627315 2 0 003872753 0 003872753 20 0 073799056 0 073799056 21 7 732586064 7 732586064 Sobjective current 55 08804 Scounter iters fevals vars 2 4 3 Stermination tolerance residual 1 5e 06 8 337337e 14 Selapsed time 1 0 1399536 6 2 The Diet Problem The Diet problem e g 2 is a well known optimization problem Its basic form is to minimize the cost of the menu subject to the nutrition and serving requirements Variables x i Food 1 Objective 24 icFood COST X 72 where NUOPT for S PLUS User s Guide Constraints Nmin lt gt ier Aj X SN max j Nutrition Bounds F min lt x lt F max i Food Food kind of food Nutrition kind of nutrition X amount of servings of food i cost cost of food i N min minimum amount of nutrition N max maximum amount of nutrition F min minimum number of servings F max maximum number of servings a amount of nutrition in one serving of a certain kind of food In SIMPLE it can be defined by gt Diet function Dcost DNmin DNmax DFmin DFmax Da Food lt Set Kind of food Nutrition lt Set Kind of nutrition i Element set Food j lt Element set Nutrition cost lt Parameter Dcost index Food cost per serving Fmin lt Parameter DFmin index Food minimum number of servings Fmax lt Parameter DFma
58. nsparent to users because NUOPT automatically selects an appropriate method based on information from SIMPLE see Table 1 Users can also specify the optimization method explicitly 1f they wish to do so Chapter1 Introduction LP MILP CP CQP NLP MIQP simplex e higher e line trust e bfgs asap o Table 1 Optimizations methods in NUOPT The presence of a symbol either or indicates that a method row is applicable to a model column The symbol indicates NUOPT s default used via modeling language SIMPLE Optimization problems are communicated to NUOPT through the modeling language SIMPLE which is designed to describe mathematical systems Such systems are characterized by mathematical relations between various guantities of interest In the case of optimization problems these relations are eguality constraints and ineguality constraints involving independent unknown variables together with an objective function to be optimized The syntax of SIMPLE is intended to be close that of familiar mathematical expressions In SIMPLE mathematical relations that contain indexed guantities are written literally allowing users to describe large scale systems in a compact way Because the models are described as sets and elements whose values are specified separately users can solve many different systems using the same
59. od uble Smaxtim uble uble uble sol uble NUOPT for S PLUS User s Guide 67 NUOPT for S PLUS User s Guide 6 Examples In this section we define and solve several well known models by SIMPLE 61 A Simple Statistically Oriented Optimization Problem The first example is a modification of the constrained linear regression model of section 3 without constraints on f and with the sum of squared residuals replaced with the sum of the Huber loss function p applied to each of the residuals prli 5 rir Ills c 7 c r i 5 c otherwise so tht r i d dt pr i is linear with slope 1 for r i lt C and eri sgn r j c for br jl C In SIMPLE this model can be defined as follows LregHuber function X y Res lt Set Var lt Set i lt Element set Res j lt Element set Var nres lt length y y lt Parameter list l nres y index i X lt Parameter X index dprod i j beta lt Variable index j r Expression index i r i yli Sum X i j beta j j C Parameter 0 1 changeable T Changeable parameter rho Expression index i Huber loss function rho i ife abs r i lt C 0 5 r i 2 C abs r i 0 5 C 2 obj lt Objective type minimize 69 Chapter 6 Examples obj Sum rho i i Here C is defined to be a changeable parameter in order to analyze several different cases
60. od is an interior point method capable of handling general NLP models The solution framework is the same as that of the line search method see section 5 2 3 for con vex programming but general NLP models can be solved by incorporating a quasi Newton method BFGS formula that provides a positive definite approximation to the Hessian of the Lagrangian function This method is not efficient for large scale problems because the Hessian matrix in the quasi Newton method is dense and has memory requirements of the order of the square of the number of variables We recommend the trust region method for large scale NLP m odels Our experiments show that the BFGS method can solve small and difficult NLP models in a more stable manner than the trust region method For small NLP models up to 50 to 100 variables in which the trust region method NUOPT s default choice takes too many iterations or fails try the BFGS method by typing gt nuopt options method bfgs The BFGS method cannot handle integrality constraints on variables 5 2 6 Active Set method for CQP and MIQP Active Set method is a classical method to solve convex QP models that is akin to the simplex method This is much faster than line IPM based on line search for special type of problems This method shows clear advantage over line for problems such that its hessian matrix is dense almost all of the element is non zero and has small number of constraints One
61. odels with NUOPT without using the SIMPLE interface The general form of a quadratic program is minimize x Qx q x subject to 1 IA Ax lt Cip bup x Integer ie I Cro Dio IA gt IA x Continuous igI where O isan nxnsymmetric matrix specifying the Hessian matrix quadratic part of the objective function and q isan n vector specifying the linear part of the objective function When Q vanishes the system 1 reduces to the general form of a linear program The factor 1 appears in the standard form of the model in order to avoid a factor of 2 in the derivatives gradient vector and Hessian matrix An important application of quadratic programming is the solution of linearly constrained linear least squares problems including portfolio optimization problems see section 6 4 Some of the variables with indices that belongs to index set I may be restricted to be integer In such a case this becomes mixed integer Linear Quadratic problem The S PLUS function solveQP for solving linear and quadratic programs has the following argument list gt args solveQP function objQ objL A cLO cUP bLO bUP x0 isint type minimize trace T NULL where objQ corresponds to the Hessian matrix O of 1 and obj L corresponds to the vector q specifying the linear part of the objective in 1 The argument x0 is a vector specifying initial Chapter 2 solveQP for Mixed Integer Linear and Quadratic Progra
62. of the examples is a portfolio optimization problem Markowitz model with relatively small investment constraints Table 5 2 comparison of line and asqp for portfolio optimization models Machine Pentium400MHz 256Mbytes of memory of assets Line search line Active set method asgp 100 0 4sec 0 1sec 200 2 0sec 0 2sec 300 6 0sec 0 5sec 400 14 4sec 0 9sec 500 24 0sec 1 4sec 600 42 6sec 2 1sec Table 5 2 shows the comparison of line and asqp for a plane markowitz type of portfolio 56 NUOPT for S PLUS User s Guide optimization model as below minimize E Q x x i jeBrand s t x 1 jeBrand 2 5x 2 Pain jeBrand x 20 j e Asset O co variance matrix a dense matrix x allocation for asset j r amean return of asset j But for the problems with large number of constraints as many as variables active set QP loses its advantage and interior point method line is generally faster Active set method is exclusively for convex QP problems It cannot treat general nonlinear problems If the active set method is selected for a nonlinear problem NUOPT will reject it with the error message NUOPT 15 gt gt simplex asqp method misapplied to NLP Among other methods currently incorporated in NUOPT the simplex and active set method are capable of handling integer variables Therefore they are the default choice in NUOPT for MIP models Fo
63. olution and time and the current number of simplex pivoting piv and enumeration node prob as below 63 Chapter 5 The NUOPT Solver lt iteration begin 1 2BI feasible sol 1 I feasible sol 2 I feasible sol 3 iteration end 291 323 366 found at found at found at 0 1 sec 0 1 sec 0 1 sec piv 10 piv 13 piv 15 prob 6 prob 8 prob 9 These information is useful for setting proper parameter value to limit the branch and bound calculation 5 3 3 General parameters The following parameters are relevant to all methods 1 scaling flag gt nuopt options scaling on This parameter can take a string value on or of f With this parameter set to on NUOPT performs scaling to balance the magnitude of objective value and constraints values in the model Numerical experiments show that scaling may help reduce numerical difficulties and make the calculation process more stable However for some numerically difficult problems the scaling process may cause undesirable results such as premature termination an inexact solution or failure to converge 5 4 Options for the Solver SIMPLE can be combined with various solvers In this version of NUOPT for S PLUS we use a solver called NUOPT Options for NUOPT are shown in Table 5 3 Details of the NUOPT options are described in Section 5 3 To show the cu
64. or S PLUS User s Guide 3 3 Integer Variables For mixed integer programming problems users can specify integer variables in their model definitions An integer variable is defined in SIMPLE by the function IntegerVarible The class of objects IntegerVariable created by this function is a subclass of class Variable The following types of integer variables may be specified binary takes on only either 0 or 1 as values semicontinuous either the integer 0 or any real number 2 1 partial takes on nonnegative integer values in a prespecified range that includes 0 and real values outside that range The following functions are provided for defining models with integer variables in SIMPLI Ld priority branch priority of an integer variable upPC downPC round up down pseudo cost of an integer variable direction branch direction of an integer variable 3 3 1 The Knapsack Problem The knapsack problem provides an example of the use of integer variables in SIMPLE In this problem we are given a knapsack of fixed capacity C and a set of objects x each with a fixed size Ss and value v A mathematical statement of the problem is minimize v x 5 subject to x 0 1 s x lt C The following function contains SIMPLE statements defining the knapsack model gt Knapsack function value size Capacity I lt Set i lt Element set I x lt IntegerVariable index i type binary 23
65. ot handle NLP FATAL lt lt NUOPT 16 gt gt Infeasible MIP This MIP mixed integer LP QP programming model has been determined to be infeasible The LP QP relaxation solution is output lt lt NUOPT 17 gt gt B amp B node limit reached with int sol Number of nodes in branch and bound enumeration reaches its limit given by pa rameter maxnod An integer feasible solution not guaranteed to be optimal is reported lt lt NUOPT 18 gt gt MIP iteration failed with int sol The branch and bound enumeration scheme failed due to numerical problems An integer feasible solution not guaranteed to be optimal is reported lt lt NUOPT 19 gt gt B amp B node limit reached no int sol Number of nodes in branch and bound enumeration reaches its limit given by pa rameter maxnod No integer feasible solution is obtained so far The LP relaxation solution is output lt lt NUOPT 20 gt gt MIP iteration failed no int sol The branch and bound enumeration scheme failed due to numerical problems No integer feasible solution is obtained The LP relaxation solution is output lt lt NUOPT 21 gt gt B amp B iter timeout with int sol 92 NUOPT for S PLUS User s Guide The elapsed time for the branch and bound calculation exceeds its limit given by parameter maxt im An integer feasible solution not guaranteed to be optimal is reported NUOPT 22 gt gt B amp B iter timeout no in
66. r MIQP NUOPT s default choice is active set method for QP the trust region method see section 5 2 4 5 3 Setting parameters Simplex method is for Mixed integer linear programming models active set method for Mixed integer Quadratic programming models Because none of these method can handle general nonlinear models NUOPT cannot handle nonlinear models with integer variables When you are using NUOPT through solveQP interface line search method see section 5 2 3 is the default choice 57 Chapter 5 The NUOPT Solver It is possible to specify parameters to control the solution process of NUOPT Although the default values are carefully chosen so that they will work in many cases some manual tuning may be helpful Table 5 3 lists the tuning parameters Some parameters are optimization method specific They fall into three categories Parameters for interior point method IPM variants 2 Parameters for the simplex method and branch and bound enumeration 3 General parameters valid for all methods The various parameters in each category are explained in the following sections Table 5 3 Options for the solver NUOPT Name Options Default Meaning method auto auto default optimization method line choice trust pfgs simplex asqp maxitn Integer 150 IPM iteration limit eps positive num 1 4e 6 for NLP IPM convergence criteria
67. rge Scale Portfolio Model An investor wants to build a portfolio whose risk is as small as possible but subject to the predetermined minimum accepted return This problem can be formulated as an optimization problem called mean variance MV model Minimize 2 O W W i jeAsset Subject to w 1 je Asset Sr JW ZF min jeAsset w 2 0 je Asset where w r and Q correspond to an allocation for asset variable a mean return of asset j and an element of a co variance matrix respectively in isa pre determined minimum 78 NUOPT for S PLUS User s Guide accecpted return The co variance matrix Q is expressed as O L n DR R R R 8 where R isa return matrix whose f j element is a return for asset j observed in period te Period R is a matrix whose rows are identical to r and n is the number of periods With SIMPLE the problem is written as follows gt PortfolioCor function rcov Asset lt Set averet rmin 0 0 i lt Element set Asset j lt Element set Asset O lt Parameter rcov index dprod Asset Asset rBar Parameter list 1 ncol rcov averet index Asset w lt Variable index Asset V Objective minimize V Sum w i Sum Q i j w j j i Sum rBar j w j j gt rmin Sum w j j To set up and solve the system for a return matrix portfolio R you would issue the S PLUS commands portfolio R
68. ribe Constraint index dprod I I inscribe i j i lt j rho i rho i rho j rho j 2 rho i rho j cos theta j theta i lt 1 increasing lt Constraint index I increasing i i gt 2 theta i gt theta i 1 theta n pi rho n 0 area lt Objective maximize area 0 5 Sum rho i rho i 1 sin theta i theta i 1 i i 2 The model can be solved as follows gt s4 System model ngon 6 polygon of 6 sides gt sol4 lt solve s4 area gt sol4 Svariables Svariables rho 1 2 3 4 5 6 0 558964 0 7792118 0 9999933 0 9999907 0 6417768 0 attr Svariables rho indexes 1 m 76 NUOPT for S PLUS User s Guide variablesS theta 1 2 3 4 5 6 0 6599817 1 073387 1 38101 1 947531 2 625132 3 141593 attr Svariables theta indexes Eh Sobjective 1 0 6749733 counter iters fevals vars 7 9 12 Stermination tolerance residual 1 5e 006 1 031837e 006 Selapsed time 1 0 2617188 The above results can be further be shown by using polygon S PLUSfunction as follows gt x lt as array current s4 rho i cos theta i x axis gt y lt as array current s4 rho i sin theta i HH y axis gt plot c 1 1 c 0 5 1 5 type n gt polygon x y density 0 see Figure 6 3 TT Chapter 6 Examples 1 0 1 5 c 0 5 1 5 05 0 0 0 5 10 05 0 0 0 5 10 c 1 1 Figure 6 3 Solutions for polygon of 6 sides 6 4 La
69. rrent options we type gt nuopt options 64 NUOPT for S PLUS User s Guide method 1 auto crossover l oft scaling 1 on Smipfeasout L ote SaddToCutoff 1 O cutoff 1 1e 050 Seps 1 10 Sepsint 1 0 0001 Smaxitn 1 150 Smaxnod told 1 1e 006 tolx 1 1e 008 Smaxintsol AJ 1 To set some options we type gt options save lt nuopt options save options gt nuopt options eps 1 7 10 6 scaling on gt nuopt options Smethod 1 auto 65 Chapter 5 The NUOPT Solver crossover l1 Tate scaling 1 on Smipfeasout 1 off SaddToCutoff 1 0 Scutoff 1 1e 050 Seps 1 1 7e 006 Sepsint 1 0 0001 Smaxitn told 1 1e 006 tolx 1 1e 008 Smaxintsol dts gt nuopt options options save restore options To see the possible values for the options we type gt nuopt options NULL Smethod 1 line trust bfgs simplex higher auto asqp crossover 7 Mumeric value integer or double is not distinguished Both integer and double value is displayed double 66 Smipfea SaddToC l do Scutoff 1 do Seps 1 do Sepsint 1 do maxitn 1 do 1 do 1 do told 1 do tolx 1 do Smaxint 1 do Ff on ff on L etr g sout on utoff uble uble uble uble uble Smaxn
70. s 4 1 Adding and Deleting Constraints It is possible to add and delete constraints in an existing system through functions add con delete con and restore con linear regression problem with positivity constraints 4 LregPosAlt function X y Res lt Set Var lt Set i lt Element set Res j lt Element set Var nres length y nvar ncol X y lt Parameter list 1 nres y index i X lt Parameter X index dprod i j beta lt Variable index j B lt Constraint index j B j beta j gt 0 r lt Variable index i R lt Constraint index i R i r i yli Sum X i j beta j j obj lt Objective type minimize obj Sum r i El il 1 First we form the system using the stack data gt sys LregPosAlt stack lt System LregPosAlt stack x We give an example using the following formulation of the stack loss 33 Chapter 4 Modifying Model Systems 1 1 B Acid Conc beta Acid Conc gt 0 1 2 B Air Flow beta Air Flow gt 0 1 3 B Water Temp beta Water Temp gt 0 2 1 R 1 80 beta Air Flow 27 beta Water Temp 2 2 R 2 80 beta Air Flow 27 beta Water Temp 2 20 R 20 56 beta Air Flow 20 beta Water Temp 2 21 R 21 70 beta Air Flow 20 beta Water Temp obj lt objective gt r 1 r 1 r 2 r 2 z 3 x 3 Now the bound constraints
71. s shown in Table 4 3 1 64Mbyte memory SunOS4 1 4 S PLUS version 3 3 Table 4 3 1 Time foe Solving MinCostFlow Data Size Number of Variables Number of Eqs Time sec 10x10 360 101 8 7E 01 20x20 1520 401 5 4E 00 30x30 3480 901 1 7E 01 50x50 9800 2501 9 5E 01 4 4 Interface Between SIMPLE Objects and S PLUS Objects S PLUS objects list or array can be assigned to SIMPLI Parameter and Expression Also as array and as list functions can be applied to almost all SIMPLE objects to convert them to S PLUS objects 42 Sparc station 20 E objects Set Variable NUOPT for S PLUS User s Guide There are basic rules governing the values of the SIMPLE objects The default initial value of Set is empty which corresponds to NULL in S The default initial value of Variable and Parameter is zero All zero valued components are omitted when transforming to S PLUS objects 1 Interface between Set and vector and list new model al Set 1 5 al is initialized to be 1 2 3 4 5 Du ww 5 as list al 4 1 2 3 4 5 gt i lt Element set al gt j lt Element set al gt a2 Set list 2 3 1ist 10 15 c a 1 index i tt set with one index gt a2 2 10 11 12 13 14 15 3 al indexes I gt as list a2 Sindexes Sindexes i tb 2A 3 Svalues Svalues 1 1 10 11 12 13 14 15 Svalues 2 43 Ch
72. t options maxitn 150 This parameter gives an upper limit on the number of IPM iterations If this limit is reached before convergence is achieved NUOPT terminates with the message lt lt NUOPT 10 gt gt IPM iteration limit exceeded 59 Chapter 5 The NUOPT Solver The default value is 150 In our experience from numerical tests interior point iterations can usually be regarded as stalled after more than 100 iterations 2 IPM convergence tolerance nuopt options eps 1 4e 6 This parameter gives the convergence tolerance for interior point methods Interior point methods are terminated successfully when the normalized optimality condition residual Yamashita 9 drops below this value As shown in Table 2 each default value depends on the problem type Table 2 Default values of convergence tolerance model type default value LP 1 0x10 NLP 7 14x10 seu 3 Crossover switch gt nuopt options crossover off This parameter can take string value on or o With this parameter set to on NUOPT starts the simplex method from the solution of the IPM iteration to construct a basic feasible solution This parameter can only be used for LP Setting this switch to on for solving NLP models will result in the following error message lt lt NUOPT 15 gt gt simplex method misapplied to NLP 5 3 2 Parameters for the simplex and active set method This section deals with the parameters for solving LP Q
73. t sol The elapsed time for the branch and bound calculation exceeds its limit given by pa rameter maxt im No integer feasible solution is obtained so far The LP relaxation solution is output lt lt NUOPT 28 gt gt higher order method is only for LP Try to use LP specific interior point method higher for NLP problems FATAL NUOPT 33 gt gt Bound violated lt lt NUOPT 34 gt gt Bound and Constraints violated NUOPT 35 gt gt Constraint violated lt lt NUOPT 36 gt gt Equality constraints violated After interior point method iteration variable bounds or constraints or equality constraints looks violated This happens when you are solving numerically difficult problem with interior point method higher line trust bfgs Try out with tighter eps by nuopt options eps 1 0e 10 or switch the scaling option by nuopt options scaling on off lt lt NUOPT 37 gt gt B amp B terminated with given ff of int sol Calculation terminated with feasible solution of MIP Mixed integer LP QP problem without proving its optimality because the number of the feasible solution reaches predetermined tolerance set by maxintsol 93 NUOPT for S PLUS User s Guide 95
74. ty is violated The higher order method cannot be applied to nonlinear problems as indicated by the error message lt lt NUOPT 28 gt gt higher order method is only for LP Because it is an interior point method the solution obtained by the higher order method is not guaranteed to be a basic solution If the solution is required to be basic select the simplex method see section 5 2 2 by setting 53 Chapter 5 The NUOPT Solver gt nuopt options method simplex Another way to obtain a basic feasible solution is to activate the crossover switch by typing nuopt options crossover on With this switch on NUOPT starts the simplex method iteration from the result of an interior point in this case the higher order method to construct a basic feasible solution Our ex periments show that for large scale LP with thousands or more variables the higher order method with crossover is the most efficient strategy for obtaining a basic feasible solution 5 2 2 Simplex method for LP and MILP The simplex method is a classical method for solving linear programming LP models Sim plex method of NUOPT is linked with a branch and bound enumeration scheme and capable of handling mixed linear integer programming MIP models When this method is selected NUOPT automatically invokes the branch and bound enumeration scheme to find a globally op timal solution for MIP The dual simplex method is used to solve the su
75. vestments Wiley 13 S Mehrotra 1992 On The Implementation of a Primal Dual Interior Point Method SIAM J Optimization 2 575 601 14 George B Dantzig Mukund N Thapa Linear Programming 1 Introduction New York Springer 1997 ISBN 0 387 94833 3 84 NUOPT for S PLUS User s Guide Appendix Formal Syntax of SIMPLE Notation aop denotes binary arthmetic operators eop denotes logical operators lt gt cop denotes logical operators amp amp and or Condition Condition cop Condition pal Parameter eop Parameter Condition Element lt Set Constraint Constraint eop Expression Constraint eop Parameter Expression eop Expression Expression eop Parameter Parameter eop Expression cha Element racter string numeric value Element aop Element Expression function Expression Variable Expression aop Expression Expression aop Parameter Parameter aop Expression f Parameter unction Parameter numeric value numeric Element Parameter aop Parameter index SetOrElement dprod SetOrElement SetOrElement S Element Sum argumentList PExpression argumentList PExpression argumentList Prod argumentList ges OSEO Element 85 Appendix PExpression Parameter Expression argumentList empty CElement argumentList C
76. x index Food maximum number of servings Nmin lt Parameter DNmin index Nutrition minimum amount of nutrition Nmax Parameter DNmax index Nutrition maximum amount of nutrition a lt Parameter Da index dprod Food Nutrition amount of nutrition in one serving of a certain kind of food x lt Variable index Food amount of serving Fmin i lt x i lt Fmax i 73 Chapter 6 Examples diet lt Constraint index Nutrition diet j Nmin j lt Sum a i j x il i totalCost Objective minimize totalCost Sum cost i x i i gt DietInit function Dcost list c PotageSoup BeefSteak c 500 2000 3000 200 DNmin list c VitaminA VitaminB c DNmax list c VitaminA VitaminB c DFmin list c PotageSoup BeefSteak c 0 0 0 0 DFmax list c PotageSoup BeefSteak c 1000 2000 2500 100 Da lt list c PotageSoup Eel Eel B c VitaminA VitaminA c 2 70 3 50 30 return Diet Dcost DNmin DNmax DFmin The model can be solved as follows gt s3 lt System DietInit gt sol3 solve s3 totalCost gt summary sol3 Svariables variables x current lower upper initial PotageSoup 0 00009681232 0 1000 0 BeefSteak 0 16002252870 0 2000 0 Eel 0 00001949195 0 2500 0 leber 0 66685219339 0 100 Sobjective initial current 74 VitaminB DFmax

NUOPT for S-PLUS User's Guide Version 1.4

Contents

Download Pdf Manuals

Related Search

Related Contents