Home

KNITRO User`s Manual Version 6.0

1. 33 48 Determining Convery ssa ataa Wa be eee Eee AA aa i 35 4 9 Calling without first derivatives ea a pa sea nun riia waa ne 36 5 User options in KNITRO 38 5 1 Description of KNITRO wer options se ce san nn sera see en ana 38 s2 The KNITRO options ile oo Ren ahnen 52 5 3 Setting options through function calle se a ee ee 53 5 4 Loading dynamic libraries sco o 4b bok a aaa a Oe ER end 53 6 KNITRO termination test and optimality 55 61 Continutus problem occiso dae ae ee daad aa Eee 55 6 2 Discrete or mixed integer problems es a carces a araa 56 7 KNITRO output and solution information 58 7 1 Understanding KNITRO output for continuous problems 58 7 2 Understanding KNITRO output for discrete problems 61 7 3 Accessing solution information 2 222 2 Cm m nn 64 8 Algorithm Options Sl Mae cola ek GC ROPES a Pee Pee at Ba Interior Diret orde Ra RA 53 Diese EG 22a eh ee EEE SOREL DEDEDE LES PA BORON eb oe ee bee een Ew we we 9 Other KNITRO special features 9 1 First derivative and gradient check options 0 92 Second derivative options oido 64 e448 ba a are Oo Feasibility options 1 4 4 4 44 cc f4 0 2 ee 44 Honor Bonds iaa p trepi Gaa RADE EAE CEOS Oe CET a a AA BG ala ae BE A a ee eS 46 Multihstat ooo ee en ESE BG AEG 9 7 Reverse communication mode for invoking KNITRO 0 5 Callback mode for invoking KNITRG a gt aa
2. Display of Final Statistics Following the termination message a summary of some final statistics on the run are printed Both relative and absolute error values are printed Final Statistics Final objective value 3 06500096351765e 02 Final feasibility error abs rel 0 00e 00 0 00e 00 Final optimality error abs rel 4 46e 07 3 06e 08 of iterations z 10 of CG iterations 5 of function evaluations 15 of gradient evaluations 11 of Hessian evaluations z 10 Total program time secs 0 00136 0 000 CPU time Time spent in evaluations sec 0 00012 Display of Solution Vector and Constraints If outlev equals 5 or 6 the values of the solution vector are printed after the final statistics If outlev equals 6 the final constraint values are also printed and the values of the Lagrange multipliers or dual variables are printed next to their corresponding constraint or bound Constraint Vector Lagrange Multipliers 1 00000006873e 00 lambda 0 7 00000062964e 02 4 50000096310e 00 lambda 1 1 07240081095e 05 a a mm PRO uo ou 60 Solution Vector x 0 4 99999972449e 01 lambda 2 7 27764067199e 01 x 1 2 00000024766e 00 lambda 3 0 00000000000e 00 KNITRO can produce additional information which may be useful in debugging or analyzing performance If outlev is positive and debug 1 then multiple files named kdbg_ 1log are created which contain detailed information on
3. OPTIMIZATION INC KNITRO 6 0 User s Manual KNITRO User s Manual Version 6 0 Richard A Waltz Todd D Plantenga Ziena Optimization Inc www ziena com March 2009 2004 2009 Ziena Optimization Inc Contents Contents a 1 Introduction 1 Tl Product Overiew 6 664244 44 800 Ee eee eed nahe 1 L2 Algorithmus Dela au ee oe oe he ee eR da eee 2 13 What s New in Verion BD oscar ad 3 14 Contact and Support Information a s sa suara ee ee 3 2 Installation 5 el WME ae a a ee ee a ae EO ROR Ee eee ee eee a 5 22 Unix hina Mae OS ce ee kad eee eee ee ee HAA eae eS 6 Zoo Limas Compatibility Issues lt ss aaoi ea ee ee RRB eo 7 3 Using KNITRO with the AMPL modeling language 9 3 1 Example Optimization Problemi o e e 9 32 ANTRO Opie tor AMPL oe oes 444444 00 ee bee er bh d Hodes eed 13 3 3 Solving with Complementarity Constraints 2 2 22 2 Con ea 17 3 4 Displaying AMPL Variables in KNITRO 000 o 18 4 The KNITRO callable library 19 4 1 KNITRO ma C application erachten eye Ba 19 42 Examples ol calling nl une a ra ee AAA RR 26 43 KNITRO ina C application 2 024 62 we eee sms RR ee es 31 44 KNITRO in Java applicatioll o aaa 5 508 SRR EEE eee REE LE Ee RO 31 45 KNITRO in a Fortran application lt ss s 2 0005 ee bebe eee we ana 32 4 6 Compiler Specifications 2 63 44 05 5 56 ee ee da EE ee 33 4 7 Specifying the Jacobian and Hessian matrices 2 2 2
4. Options hessopt 2 and hessopt 3 are only recommended for small problems n lt 1000 since they require working with a dense Hessian approximation Option hessopt 6 should be used for large problems See Section 9 2 for more information honorbnds KTR_PARAM_HONORBNDS Indicates whether or not to enforce satisfaction of simple vari able bounds throughout the optimization see Section 9 4 This option and the bar_feasible option may be useful in applications where functions are undefined outside the region defined by inequalities O no KNITRO does not require that the bounds on the variables be satisfied at intermediate iterates 1 always KNITRO enforces that the initial point and all subsequent solution estimates satisfy the bounds on the variables 2 initpt KNITRO enforces that the initial point satisfies the bounds on the variables Default value 2 Imsize KTR_PARAM_LMSIZE Specifies the number of limited memory pairs stored when approx imating the Hessian using the limited memory quasi Newton BFGS option The value must be between 1 and 100 and is only used with hessopt 6 Larger values may give a more accurate but more expensive Hessian approximation Smaller values may give a less accu rate but faster Hessian approximation When using the limited memory BFGS approach it is recommended to experiment with different values of this parameter See Section 9 2 for more details Default value 10 lpsolver KTR_PARAM_LP
5. int indexList2 is an array of length numCompConstraints specifying the variable indices for the second set of variables in the pairs of complementary variables The call to KTR_addcompcons must occur after the call to KTR_init_problem but before the first call to KTR_solve Below we provide a simple example of how to define the KNITRO data structures to specify a problem which includes complementarity constraints Example Assume we want to solve the following MPEC with KNITRO minimize f x zo 5 2x1 1 10 39a subject to Co x 2 a 1 1520 220 523 24 0 10 39b c 2 3x9 41 3 gt 0 10 39c cz 0 541 4 gt 0 10 39d l An MPEC from J F Bard Convex two level optimization Mathematical Programming 40 1 15 27 1988 ca3 x 9 41 7 gt 0 10 39e 2 gt 0 i 0 4 10 398 c z xa 0 10 398 ca 1 13 0 10 39h c3 x x4 0 10 391 It is easy to see that the last 3 constraints along with the corresponding non negativity conditions represent complementarity constraints Expressing this in compact notation we have minimize f x ap 5 2a 1 10 40a subject to co x 0 10 40b 0 lt a amp l z Lr gt 0 10 40c 0 lt co x Laz gt 0 10 40d 0 lt c3 x Lz4 gt 0 10 40e zo gt 0 71 gt 0 10 40f Since KNITRO requires that complementarity constraints be written as two variables complementary to each other we must introdu
6. let KNITRO set the number based on the problem size n maximum of n gt 0 CG iterations per minor iteration maxcrossit maximum number of allowable crossover iterations 0 maxit maximum number of iterations before terminating 0 O let KNITRO set the number based on the problem n maximum limit of n gt 0 iterations maxtime_cpu maximum CPU time in seconds before terminating 1 0e8 maxtime_real maximum real time in seconds before terminating 1 0e8 OPTION DESCRIPTION DEFAULT mip_branchrule MIP branching rule 0 O let KNITRO choose the branching rule 1 most fractional branching 2 pseudo cost branching 3 strong branching mip debug MIP debugging level 0 0 no MIP debugging output 1 print MIP debugging information mip_gub_branch Branch on GUBs 0 0 do not branch on GUB constraints 1 allow branching on GUB constraints mip_heuristic heuristic search approach 0 O let KNITRO decide whether to apply a heuristic 1 do not apply any heuristic 2 use feasibility pump heuristic 3 use MPEC heuristic mip_heuristic_maxit heuristic search iteration limit 100 mip_implications Add logical implications 1 0 do not add constraints from logical implications 1 add constraints from logical implications mip_integer_tol threshold for deciding integrality 1 0e 8 mip_integral_gap_abs absolute integrality gap stop tolerance 1 0e 6 mip_integral_gap_rel relative integrality g
7. procedure 0 auto Let KNITRO choose the heuristic to apply if any 1 mone No heuristic search applied 2 feaspump Apply feasibility pump heuristic 3 mpec Apply heuristic based on MPEC formulation Default value 0 mip_heuristic_maxit KTR_PARAM_MIP_HEURISTIC_MAXIT Specifies the maximum number of it erations to allow for MIP heuristic if one is enabled Default value 100 mip_implications KTR_PARAM_MIP_IMPLICATNS Specifies whether or not to add constraints to the MIP derived from logical implications 0 no Do not add constraints from logical implications 1 yes KNITRO adds constraints from logical implications Default value 1 mip_integer_tol KTR_PARAM_MIP_INTEGERTOL This value specifies the threshold for deciding whether or not a variable is determined to be an integer Default value 1 0e 8 mip_integral_gap_abs KTR_PARAM_MIP_INTGAPABS The absolute integrality gap stop tolerance for MIP See Section 6 2 for more information Default value 1 0e 6 46 mip_integral_gap_rel KTR_PARAM_MIP_INTGAPREL The relative integrality gap stop tolerance for MIP See Section 6 2 for more information Default value 1 0e 6 mip_knapsack KTR_PARAM_MIP_KNAPSACK Specifies rules for adding MIP knapsack cuts O none Do not add knapsack cuts 1 ineqs Add cuts derived from inequalities only 2 ineqs_eqs Add cuts derived from both inequalities and equalities Default value 1 mip_lpalg KTR_PARAM_MIP_LP
8. set xUpBnds to be KTR_INFBOUND defined in knitro h For binary variables set xUpBnds i 1 int m is a scalar specifying the number of constraints c a in 4 4 int cType is an array of length m that describes the types of the constraint functions c x in 4 4 0 ifc x is a nonlinear function or its type is unknown KTR_CONTYPE_GENERAL 1 if c is a linear function KTR_CONTYPE_LINEAR 2 if c x is a quadratic function KTR_CONTYPE_QUADRATIC int cFnType is an array of length m that describes the convexity status of the constraint functions c x in 4 4 MIP only See Section 4 8 0 if the convexity of constraint ce lt c x lt cY is unknown KTR_FNTYPE_UNCERTAIN 1 if constraint ch lt x lt cY is a convex constraint KTR_FNTYPE_CONVEX 2 if constraint cl lt c x lt cY is not a convex constraint KTR_FNTYPE_NONCONVEX double cLoBnds is an array of length m specifying the lower bounds on the constraints c x in 4 4 cLoBndsli must be set to the lower bound of the corresponding i th constraint If the constraint has no lower bound set cLoBndsli to be KTR_INFBOUND defined in knitro h If the constraint is an equality then cLoBnds should equal cUpBnds i double cUpBnds is an array of length m specifying the upper bounds on the constraints c x in 4 4 cUpBnds must be set to the upper bound of the corresponding i th constraint If the constraint has no upper bound set cUpBnds i to b
9. 373e 01 0 8 13 3 075530e 02 0 000e 00 6 888e 03 2 255e 02 0 9 14 3 065107e 02 0 000e 00 6 397e 05 2 699e 03 0 10 15 3 065001e 02 0 000e 00 4 457e 07 2 714e 05 0 The meaning of each column is described below Iter Iteration number fCount The cumulative number of function evalutions This information is only printed if outlev is greater than 3 Objective Gives the value of the objective function at the current iterate 59 FeasError Gives a measure of the feasibility violation at the current iterate see Section 6 OptError Gives a measure of the violation of the Karush Kuhn Tucker KKT first order optimality conditions not including feasibility at the current iterate see Section 6 Step The 2 norm length of the step i e the distance between the new iterate and the previous iterate CGits The number of Projected Conjugate Gradient CG iterations required to compute the step Display of Termination Status At the end of the run a termination message is printed indicating whether or not the optimal solution was found and if not why KNITRO stopped The termination message typically starts with the word EXIT If KNITRO was successful in satisfying the termination test see Section 6 the message will look as follows EXIT Locally optimal solution found See the appendix for a list of possible termination messages and a description of their meaning and the corresponding value returned by KTR_solve
10. 4 2 describes an example program that uses the reverse communications mode 9 8 Callback mode for invoking KNITRO The callback mode of KNITRO requires the user to supply several function pointers that KNITRO calls when it needs new function gradient or Hessian values or to execute a user provided newpoint routine For convenience every one of these callback routines takes the same list of arguments If your callback requires additional parameters you are encouraged to create a structure containing them and pass its address as the userParams pointer KNITRO does not modify or dereference the userParams pointer so it is safe to use for this purpose Section 4 2 describes an example program that uses the callback mode The C language prototype for the KNITRO callback function is defined in knitro h typedef int KTR_callback const int evalRequestCode const int n const int m const int nnzJ const int nnzH const double const x const double const lambda double const obj double const c double const objGrad double const jac double const hessian double const hessVector void userParans The callback functions for evaluating the functions gradients and Hessian or for performing some newpoint task are set as described below Each user callback routine should return an int value of 0 if successful or a negative value to indicate that an error occurred during execution of the user provided function Section 4 2 d
11. 5 features for example there are no generics and runs equally well on Java release 1 4 4 5 KNITRO in a Fortran application Calling KNITRO from a Fortran application follows the same outline as a C application The opti mization problem must be defined in terms of arrays and constants that follow the KNITRO API and then the Fortran version of KTR_init_problem is called Fortran integer and double precision types map directly to C int and double types Having defined the optimization problem the Fortran version of KTR_solve is called in reverse communications mode 9 7 Fortran applications require wrapper functions written in C to 1 isolate the KTR_context struc ture which has no analog in unstructured Fortran 2 convert C function names into names rec ognized by the Fortran linker and 3 renumber array indices to start from zero the C convention used by KNITRO for applications that follow the Fortran convention of starting from one The wrapper functions can be called from Fortran with exactly the same arguments as their C language counterparts except for the omission of the KTR_context argument An example Fortran program and set of C wrappers is provided in examples Fortran The code will not be reproduced here as it closely mirrors the structural form of the C reverse communications example described in Section 4 2 The example loads the matrix sparsity of the optimization problem with indices that start numbering from zer
12. KTR_INFBOUND xLoBnds 5 0 xUpBnds 5 KTR_INFBOUND xLoBnds 6 0 xUpBnds 6 KTR_INFBOUND xLoBnds 7 0 xUpBnds 7 KTR_INFBOUND indexList1 0 indexList1 1 indexList1 2 2 indexList2 0 5 3 indexList2 1 6 4 indexList2 2 T NOTE Variables which are specified as complementary through the special KTR_addcompcons functions should be specified to have a lower bound of 0 through the KNITRO lower bound array xLoBnds When using KNITRO through a particular modeling language only some modeling languages allow for the identification of complementarity constraints If a modeling language does not allow you to specifically identify and express complementarity constraints then these constraints must be formulated as regular constraints and KNITRO will not perform any specializations 10 6 Global optimization KNITRO is designed for finding locally optimal solutions of continuous optimization problems A local solution is a feasible point at which the objective function value at that point is as good or better than at any nearby feasible point A globally optimal solution is one which gives the best i e lowest if minimizing value of the objective function out of all feasible points If the problem is convez all locally optimal solutions are also globally optimal solutions The ability to guarantee convergence to the global solution on large scale nonconvez problems is a nearly impossible task on most problem
13. KTR_mip_init_problem outlev KTR_PARAM_OUTLEV Controls the level of output produced by KNITRO O none Printing of all output is suppressed 1 summary Print only summary information 2 iter_10 Print basic information every 10 iterations 3 iter Print basic information at each iteration 4 iter_verbose Print basic information and the function count at each iteration 5 iter_x Print all the above and the values of the solution vector x 6 all Print all the above and the values of the constraints c at x and the Lagrange multipliers lambda Default value 2 outmode KTR_PARAM_OUTMODE Specifies where to direct the output from KNITRO 0 screen Output is directed to standard out e g screen 1 file Output is sent to a file named knitro log 2 both Output is directed to both the screen and file knitro log Default value 0 pivot KTR_PARAM PIVOT Specifies the initial pivot threshold used in factorization routines The value should be in the range 0 0 5 with higher values resulting in more pivoting more stable factorizations Values less than 0 will be set to 0 and values larger than 0 5 will be set to 0 5 If pivot is non positive initially no pivoting will be performed Smaller values may improve the speed of the code but higher values are recommended for more stability for example if the problem appears to be very ill conditioned Default value 1 0e 8 scale KTR_PARAM_SCALE Perfor
14. aa 0040 624444450424 e wt 10 Special problem classes 10 1 Linear programming problems LPs 2 000000 10 2 Quadratic programming problems QPsS o o 10 3 Systems of Nonlinear Equations CE none 10 4 Least Squares Problems v2 22 2 222 a2 RAR Herne na ES 10 5 Complementarity constraints MPCCs 2 2 nommen 10 6 Global DB era aan inne ae 10 7 Mixed integer programming MIP 20002 References Appendix A Solution Status Codes Appendix B List of Output Files 1 Introduction This chapter gives an overview of the KNITRO optimization software package and details concerning contact and support information 1 1 Product Overview KNITRO 6 0 is an optimization software library for finding solutions of both continuous smooth optimization models with or without constraints as well as discrete optimization models with integer or binary variables i e mixed integer programs KNITRO is primarily designed for finding local solutions of large scale continuous nonlinear problems Multi start heuristics are provided for trying to locate the global solution Although primarily designed for general nonlinear optimization KNITRO is efficient at solving all of the following classes of optimization problems unconstrained bound constrained systems of nonlinear equations least squares problems both linear and nonlinear linear programming problems LPs quadratic
15. algorithm 3 NOTE The bar_feasible option see Section 9 3 is not available for use with the Active Set algorithm The method works with all Hessian options 67 9 Other KNITRO special features This section describes in more detail some of the most important features of KNITRO It provides some guidance on which features to use so that KNITRO runs most efficiently for the problem at hand 9 1 First derivative and gradient check options The default version of KNITRO assumes that the user can provide exact first derivatives to compute the objective function gradient and constraint gradients It is highly recommended that the user provide exact first derivatives if at all possible since using first derivative approximations may seri ously degrade the performance of the code and the likelihood of converging to a solution However if this is not possible the following first derivative approximation options may be used Forward finite differences This option uses a forward finite difference approximation of the objective and constraint gradients The cost of computing this approximation is n function evaluations where n is the number of variables The option is invoked by choosing user option gradopt 2 see Section 5 Centered finite differences This option uses a centered finite difference approximation of the objective and constraint gradi ents The cost of computing this approximation is 2n function evaluations where n is the number o
16. apply Active Set to provide highly accurate active set and sensitivity information see Section 9 5 For mixed integer programs MIPs KNITRO provides two variants of the branch and bound algorithm The first is a standard implementation while the second is specialized for convex mixed integer nonlinear problems For a detailed description of the algorithm implemented in Interior CG see 4 and for the global convergence theory see 1 The method implemented in Interior Direct is described in 11 The Active Set algorithm is described in 3 and the global convergence theory for this algorithm is in 2 A summary of the algorithms and techniques implemented in the KNITRO software product is given in 6 An important component of KNITRO is the HSL routine MA27 8 which is used to solve the linear systems arising at every iteration of the algorithm In addition the Active Set algorithm in KNITRO may make use of the COIN OR Clp linear programming solver module The version used in KNITRO may be downloaded from http www ziena com clp html 1 3 What s New in Version 6 0 e KNITRO 6 0 introduces new features for solving optimization models both linear and nonlin ear with binary or integer variables The KNITRO mixed integer programming MIP code offers two algorithms for mixed integer nonlinear programming MINLP The first is a non linear branch and bound method and the second implements the hybrid Quesada Grossman method for convex MIN
17. before reverting to a CG step These refactorizations are performed if negative curvature is detected in the model Rather than reverting to a CG step the Hessian matrix is modified in an attempt to make the subproblem convex and then the KKT system is refactorized Increasing this value will make the Interior Direct algorithm less likely to take CG steps If the Interior Direct algorithm is taking a large number of CG steps as indicated by a positive value for CGits in the output this may improve performance This option has no effect on the Active Set algorithm Default value 0 bar_murule KTR PARAM_BAR_MURULE Indicates which strategy to use for modifying the barrier parameter u in the barrier algorithms see Section 8 Not all strategies are available for both barrier algorithms as described below This option has no effect on the Active Set algorithm 0 auto Let KNITRO automatically choose the strategy 40 1 monotone Monotonically decrease the barrier parameter Available for both barrier algorithms N adaptive Use an adaptive rule based on the complementarity gap to determine the value of the barrier parameter Available for both barrier algorithms w probing Use a probing affine scaling step to dynamically determine the barrier pa rameter Available only for the Interior Direct algorithm gt dampmpc Use a Mehrotra predictor corrector type rule to determine the barrier pa rameter with s
18. here the number of nonzero elements in the upper triangular part of the Hessian matrix nnzH is 4 The KNITRO array hess stores the values of these elements while the arrays hessIndexRows and hessIndexCols store the row and column indices respectively The order in which these nonzero elements is stored is not important If we store them column wise the arrays hess hessIndexRows and hessIndexCols are as follows hess 0 lambda 0 cos x 0 2 lambda 1 hessIndexRows 0 0 hessIndexCols 0 0 hess 1 2 lambda 1 hessIndexRows 1 1 hessIndexCols 1 1 hess 2 3 x 2 x 2 hessIndexRows 2 1 hessIndexCols 2 2 hess 3 6 x 11 x 2 hessIndexRows 3 2 hessIndexCols 3 2 The values of hess depend on the value of x and change during the solution process The values of hessIndexRows and hessIndexCols are set in KTR_init_problem and remain constant 4 8 Determining Convexity Knowing whether or not a function is convex may be useful in methods for mixed integer program ming as linearizations derived from convex functions can be used as outer approximations of those constraints These outer approximations are useful in computing lower bounds The callable library for the mixed integer programming API allows for the user to specify whether or not the problem functions objective and constraints are convex or not If unknown they can be marked as such A function f is convex if for any two points x and
19. int This indicates an incompatibility between the libstdc library on your Linux distribution and the library that KNITRO was built with The incompatibilities may be caused by name mangling differences between versions of the gcc compiler and by differences in the Application Binary In terface of the two Linux distributions The best fix is for Ziena to rebuild the KNITRO binaries on the same Linux distribution of your target machine matching the Linux brand and release and the gcc g compiler versions If you see these errors please contact Ziena at info ziena com to correct the problem Another Linux link error sometimes seen when using the programs in examples C is the following callback1_dynamic error while loading shared libraries lib libmkl so cannot restore segment prot after reloc Permission denied This is a security enhanced Linux SELinux error message The Intel Math Kernel Library lib libmkl so shipped with KNITRO does not have the proper security identifiers for your distribution of SELinux the library is loaded with user option blasoption You could disable security enhance ments but a better fix is to change the security identifiers of the library to acceptable values On Linux Fedora Core 4 an acceptable security type is shlib_t other Linux distributions are probably similar The fix is made by changing to the KNITRO lib directory and typing chcon c v t shlib_t libmkl so 3 Using KNITRO w
20. knitro h Only hessian is modified similar implementation to callbackEvalFC Back in the main program each wrapper function is registered as a callback to KNITRO and then KTR_solve is invoked to find the solution 30 REGISTER THE CALLBACK FUNCTIONS THAT PERFORM PROBLEM EVALS THE HESSIAN CALLBACK ONLY NEEDS TO BE REGISTERED FOR SPECIFIC HESSIAN OPTIONS E G IT IS NOT REGISTERED IF THE OPTION FOR BFGS HESSIAN APPROXIMATIONS IS SELECTED if KTR_set_func_callback kc amp callbackEvalFC 0 exit 1 if KTR_set_grad_callback kc amp callbackEvalGA 0 exit 1 if nHessOpt KTR_HESSOPT_EXACT nHessOpt KTR_HESSOPT_PRODUCT if KTR_set_hess_callback kc amp callbackEvalHess 0 exit 1 SOLVE THE PROBLEM nStatus KTR_solve kc x lambda 0 amp obj NULL NULL NULL NULL NULL NULL if Status KTR_RC_OPTIMAL printf KNITRO failed to solve the problem final status d n nStatus DELETE THE KNITRO SOLVER INSTANCE KTR_free amp kc To write a driver program using reverse communications mode set up a loop that calls KTR_solve and then computes the requested problem information The loop continues until KTR_solve returns zero success or a negative error code SOLVE THE PROBLEM IN REVERSE COMMUNICATIONS MODE KNITRO RETURNS WHENEVER IT NEEDS MORE PROBLEM INFO THE CALLIN
21. lt m j 37 jacIndexCons k j jacIndexVars k i k INSTRUCT KNITRO TO COMPUTE FIRST DERIVATIVE ESTIMATES AND APPROXIMATE THE HESSIAN KTR_set_int_param kc KTR_PARAM_GRADOPT KTR_GRADOPT_CENTRAL KTR_set_int_param kc KTR_PARAM_HESSOPT KTR_HESSOPT_LBFGS INITIALIZE KNITRO WITH THE PROBLEM DEFINITION nStatus KTR_init_problem kc n objGoal objType xLoBnds xUpBnds m cType cLoBnds cUpBnds nnzJ jacIndexVars jacIndexCons O NULL NULL NULL NULL if nStatus 0 an error occurred SOLVE THE PROBLEM USING REVERSE COMMUNICATIONS MODE KNITRO RETURNS WHENEVER IT NEEDS MORE PROBLEM INFO WHICH IN THIS CASE WILL ONLY BE TO EVALUATE THE OBJECTIVE AND CONSTRAINT FUNCTIONS NO REQUESTS FOR DERIVATIVES MUST PASS objGrad AND jac BECAUSE KNITRO USES THEM TO STORE FINITE DIFFERENCE ESTIMATES while 1 nStatus KTR_solve kc x lambda evalStatus amp obj c objGrad jac NULL NULL NULL if nStatus KTR_RC_EVALFC KNITRO WANTS obj AND c EVALUATED AT THE POINT x compute obj and c at x else IN THIS EXAMPLE OTHER STATUS CODES MEAN KNITRO IS FINISHED break if nStatus KTR_RC_OPTIMAL printf KNITRO failed to solve the problem final status d n nStatus DELETE THE KNITRO SOLVER INSTANCE KTR_free amp kc 38 5 User options in KNI
22. max 1 f x7 6 32 where mip_integral_gap_abs and mip_integral_gap_rel are typically small positive numbers Since these termination conditions assume that the continuous subproblems are solved to global optimality and KNITRO only finds local solutions of nonconvex continuous optimization problems they are only reliable when solving convex mixed integer problems The integrality gap f xr f apr should be non negative although it may become slightly negative from roundoff error or if the continuous subproblems are not solved to sufficient accuracy If the integrality gap becomes largely negative this may be an indication that the model is nonconvex in which case KNITRO may not converge to the optimal solution and will be unable to verify optimality even if it claims otherwise 57 7 KNITRO output and solution information This section provides information on understanding the KNITRO output and accessing solution information 7 1 Understanding KNITRO output for continuous problems If outlev 0 then all printing of output is suppressed If outlev is positive then KNITRO prints infor mation about the solution of your optimization problem either to standard output outmode screen to a file named knitro log outmode file or to both outmode both The option outdir controls the directory where output files are created if any are and the option outappend controls whether output is appended to existing files See Section 5 fo
23. methods is that they do not always provide a clear picture of which constraints are active at the solution In general they return a less exact solution and less exact sensitivity information For this reason KNITRO offers a crossover feature in which the interior point method switches to the Active Set method at the interior point solution estimate in order to clean up the solution and provide more exact sensitivity and active set information The crossover procedure is controlled by the maxcrossit user option If this parameter is greater than 0 then KNITRO will attempt to perform maxcrossit Active Set crossover iterations after the interior point method has finished to see if it can provide a more exact solution This can be viewed as a form of post processing If maxcrossit is not positive then no crossover iterations are attempted 70 The crossover procedure will not always succeed in obtaining a more exact solution compared with the interior point solution If crossover is unable to improve the solution within maxcrossit crossover iterations then it will restore the interior point solution estimate and terminate If outlev is greater than one KNITRO will print a message indicating that it was unable to improve the solution For example if maxcrossit 3 and the crossover procedure did not succeed the message will read Crossover mode unable to improve solution within 3 iterations In this case you may want to increase the valu
24. mip_selectrule MIP node selection rule 0 0 let KNITRO choose the node select rule 1 use depth first search 2 use best bound node selection 3 use a combination of depth first and best bound mip_strong_candlim strong branching candidate limit 10 mip_strong_level strong branching level limit 10 mip_strong_maxit strong branching subproblem iteration limit 1000 mip_terminate termination condition for MIP 0 O terminate at optimal solution 1 terminate at first integer feasible solution ms_enable 0 multi start not enabled 0 1 multi start enabled ms_maxbndrange maximum range to vary unbounded x when generating start points 1 0e3 ms_maxsolves maximum number of start points to try during multi start O let KNITRO set the number based on problem size n try exactly n gt 0 start points ms_maxtime_cpu maximum CPU time for multi start in seconds 1 0e8 ms_maxtime_real maximum real time for multi start in seconds 1 0e8 ms_num_to_save number feasible points to save in knitro_mspoints log 0 ms_savetol tolerance for feasible points to be considered distinct 1 0e 6 ms_startptrange maximum range to vary all x when generating start points 1 0e20 ms_terminate termination condition for multi start 0 0 terminate after ms_maxsolves 1 terminate at first local optimum if before ms_maxsolves 2 terminate at first feasible solution if before ms_maxsolves newpoint 0 no action 0 1 save the latest new point to file knitro_newpoint log 2 appen
25. or KTR_mip_solve It returns a negative number if there is a problem with kc Continuous problems int KTR_get_number_iters const KTR_context_ptr kc This function returns the number of iterations made by KTR_solve It returns a negative number if there is a problem with kc double KTR_get_abs_feas_error const KTR_context_ptr kc This function returns the absolute feasibility error at the solution See 6 1 for a detailed definition of this quantity It returns a negative number if there is a problem with kc double KTR_get_rel_feas_error const KTR_context_ptr kc This function returns the relative feasibility error at the solution See 6 1 for a detailed definition of this quantity It returns a negative number if there is a problem with kc double KTR_get_abs_opt_error const KTR_context_ptr kc This function returns the absolute optimality error at the solution See 6 1 for a detailed definition of this quantity It returns a negative number if there is a problem with kc double KTR_get_rel_opt_error const KTR_context_ptr kc This function returns the relative optimality error at the solution See 6 1 for a detailed definition of this quantity It returns a negative number if there is a problem with kc Discrete or mixed integer problems int KTR_get_mip_num_nodes const KTR_context_ptr kc This function returns the number of nodes processed in the MIP solve made by KTR_mip_solve It returns a negative number if th
26. or the program ends The contents of the context pointer should never be modified by a calling program int KTR_free KTR_context_ptr kc_handle This function should be called last and will free the context pointer The address of the context pointer is passed so that KNITRO can set it to NULL after freeing all memory This prevents the application from mistakenly calling KNITRO functions after the context pointer has been freed 20 The C interface for KNITRO requires the application to define an optimization problem 1 1 in the following general format for complementarity constraints see Section 10 5 minimize f z 4 4a subject to cLoBnds lt c x lt cUpBnds 4 4b xLoBnds lt x lt xUpBnds 4 4c where cLoBnds and cUpBnds are vectors of length m and xLoBnds and xUpBnds are vectors of length n If constraint i is an equality constraint set cLoBnds i cUpBndsl If constraint i is unbounded from below or above set cLoBnds i or cUpBnds i to the value KTR_INFBOUND or KTR_INFBOUND respectively Similarly for xLoBnds and xUpBnds The constant KTR_INFBOUND is defined in knitro h and stands for infinity in the KNITRO code To use KNITRO the application must provide routines for evaluating the objective f x and constraint functions c x For best performance the application should also provide routines to evaluate first derivatives gradients of f x and c x and ideally the second derivatives Hessian of the Lagrangia
27. programming problems QPs both convex and nonconvex mathematical programs with complementarity constraints MPCCs general nonlinear smooth constrained problems NLP both convex and nonconvex mixed integer linear programs MILP of moderate size mixed integer convex nonlinear programs MINLP of moderate size The KNITRO package provides the following features efficient and robust solution of small or large problems solvers for both continuous and discrete problems derivative free 1st derivative and 2nd derivative options option to remain feasible throughout the optimization or not both interior point barrier and active set methods both iterative and direct approaches for computing steps support for Windows 32 bit and 64 bit Linux 32 bit and 64 bit and Mac OS X 32 bit x86 programmatic interfaces C C Fortran Java Microsoft Excel modeling language interfaces AMPL AIMMS GAMS Mathematica MATLAB MPL thread safe libraries for easy embedding into application software 1 2 Algorithms Overview The problems solved by KNITRO have the form minimize f x 1 1a subject to t lt c a lt cU 1 1b b lt eo 1 1c where x R are the unknown variables which can be specified as continuous binary or integer cl and c are lower and upper bounds possibly infinite on the general constraints and b and bY are lower and upper simple bounds possibly infinite on the variables This formulati
28. range of penalty parameter values Default value 0 blasoption KTR_PARAM_BLASOPTION Specifies the BLAS LAPACK function library to use for basic vector and matrix computations O knitro Use KNITRO built in functions 1 intel Use Intel Math Kernel Library MKL functions 41 2 dynamic Use the dynamic library specified with option blasoptionlib Default value 0 NOTE BLAS and LAPACK functions from Intel Math Kernel Library MKL 9 1 are pro vided with the KNITRO distribution The MKL is available for Windows 32 bit and 64 bit Linux 32 bit and 64 bit and Mac OS X 32 bit x86 it is not available for Solaris or Mac OS X PowerPC The MKL is not included with the free student edition of KNITRO BLAS Basic Linear Algebra Subroutines and LAPACK Linear Algebra PACKage functions are used throughout KNITRO for fundamental vector and matrix calculations The CPU time spent in these operations can be measured by setting option debug 1 and examining the output file kdbg_summ txt Some optimization problems are observed to spend less than 1 of CPU time in BLAS LAPACK operations while others spend more than 50 Be aware that the different function implementations can return slightly different answers due to roundoff errors in double precision arithmetic Thus changing the value of blasoption sometimes alters the iterates generated by KNITRO or even the final solution point The knitro option uses built in BLAS LAPACK func
29. to optimize See Section 9 3 for more details on this option bar_feasmodetol KTR_PARAM BAR FEASMODETOL Specifies the tolerance in equation 5 15 that determines whether KNITRO will force subsequent iterates to remain feasible The tolerance applies to all inequality constraints in the problem This option only has an effect if option bar_feasible stay or bar_feasible get_stay Default value 1 0e 4 bar_initpt KTR_PARAM BAR_INITPT Indicates whether an initial point strategy is used with bar rier algorithms This option has no effect on the Active Set algorithm 0 auto Let KNITRO automatically choose the strategy 1 yes Shift the initial point to improve barrier algorithm performance 2 no Do no alter the initial point supplied by the user Default value 0 bar_maxbacktrack KTR_PARAM_BAR_MAXBACKTRACK Indicates the maximum allowable number of backtracks during the linesearch of the Interior Direct algorithm before reverting to a CG step Increasing this value will make the Interior Direct algorithm less likely to take CG steps If the Interior Direct algorithm is taking a large number of CG steps as indicated by a positive value for CGits in the output this may improve performance This option has no effect on the Active Set algorithm Default value 3 bar_maxrefactor KTR_PARAM BAR MAXREFACTOR Indicates the maximum number of refactoriza tions of the KKT system per iteration of the Interior Direct algorithm
30. where feastol opttol feastol_abs and opttol_abs are constants defined by user options see Section 5 This stopping test is designed to give the user much flexibility in deciding when the solution returned by KNITRO is accurate enough One can use a scaled stopping test which is the rec ommended default option by setting feastol_abs and opttol_abs equal to 0 0e0 Likewise an absolute stopping test can be enforced by setting feastol and opttol equal to 0 0e0 Note that the stopping conditions 6 29 6 30 apply to the problem being solved internally by KNITRO If the user option scale yes see Section 5 1 then the problem objective and constraint functions may first be scaled before the problem is sent to KNITRO for the optimization In this case the stopping conditions apply to the scaled form of the problem If the accuracy achieved by KNITRO with the default settings is not satisfactory the user may either decrease the tolerances described above or try setting scale no Unbounded problems Since by default KNITRO uses a relative scaled stopping test it is possible for the optimality conditions to be satisfied within the tolerances given by 6 29 6 30 for an unbounded problem For example if 73 oo while the optimality error stays bounded condition 6 30 will eventually be satisfied for some opttol gt 0 If you suspect that your problem may be unbounded using an absolute stopping test will allow KNITRO to detect this 6 2 Di
31. 00 3 2 0 6 009759e 00 f 5 171320e 00 6 009759e 00 4 1 1 000000e 01 pr 5 171320e 00 6 009759e 00 5 0 7 092732e 00 pr 6 009759e 00 6 009759e 00 The meaning of each column is described below Node The node number If an integer feasible point was found at a given node then it is marked with a Left The current number of active nodes left in the branch and bound tree Iinf The number of integer infeasible variables at the current node solution Objective Gives the value of the objective function at the solution of the relaxed subproblem solved at the current node If the subproblem was infeasible or failed this is indi cated Additional symbols may be printed at some nodes if the node was pruned pr integer feasible f or an integer feasible point was found through rounding r Best relaxatn The value of the current best relaxation lower bound on the solution if mini mizing see Section 6 2 Best incumbent The value of the current best integer feasible point upper bound on the solu tion if minimizing see Section 6 2 Display of Termination Status At the end of the run a termination message is printed indicating whether or not the optimal solution was found and if not why KNITRO stopped The termination message typically starts with the word EXIT If KNITRO was successful in satisfying the termination test see Section 6 2 the message will look as follows EXIT Optimal solution found See the append
32. 1 if the goal is to maximize the objective function KTR_OBJGOAL_MAXIMIZE int objType is a scalar that describes the type of objective function f x in 4 4 0 if f x is a nonlinear function or its type is unknown KTR_OBJTYPE_GENERAL 1 if f x is a linear function KTR_OBJTYPE_LINEAR 22 2 if f a is a quadratic function KTR_OBJTYPE_QUADRATIC int objFnType is a scalar that describes the convexity status of the objective function f x in 4 4 MIP only See Section 4 8 0 if the convexity status of f x is unknown KTR_FNTYPE_UNCERTAIN 1 if f x is a convex function when minimizing KTR_FNTYPE_CONVEX 2 if f x is not a convex function when minimizing KTR_FNTYPE_NONCONVEX ee int xType is an array of length n that describes the types of variables x in 4 4 MIP only 0 if x is a continuous variable KTR_VARTYPE_CONTINUOUS 1 if x is an integer variable KTR_VARTYPE_INTEGER 2 if a is a binary variable KTR_VARTYPE BINARY double xLoBnds is an array of length n specifying the lower bounds on x xLoBnds i must be set to the lower bound of the corresponding i th variable z If the variable has no lower bound set xLoBnds i to be KTR_INFBOUND defined in knitro h For binary variables set xLoBnds i 0 double xUpBnds is an array of length n specifying the upper bounds on x xUpBnds must be set to the upper bound of the corresponding i th variable x If the variable has no upper bound
33. 6 0 0 z lib Tf you run a Unix bash shell then type assuming KNITRO 6 0 0 is installed at tmp gt export LD LIBRARY PATH LD LIBRARY PATH tmp knitro 6 0 0 z lib If you run a Unix csh or tcsh shell then type assuming KNITRO 6 0 0 is installed at tmp gt setenv LD_LIBRARY_PATH LD_LIBRARY PATH tmp knitro 6 0 0 z lib 54 6 KNITRO termination test and optimality 6 1 Continuous problems The first order conditions for identifying a locally optimal solution of the problem 1 1 are VeLl e r V x Y AVe x ST A 0 6 16 i 1 m j 1 n A min c a cb e Bu 0 i 6 17 A min 2 bY 07 2 0 j L n 6 18 ch lt ale lt Y i 1 m 6 19 ye ae lt o jein 6 20 AS gt 0 i T clinfinite cY finite 6 21 AM lt 0 1 Z cVinfinite c finite 6 22 A gt 0 jeB bjinfinite by finite 6 23 A lt 0 j B bj infinite b finite 6 24 Here Z and B represent the sets of indices corresponding to the general inequality constraints and non fixed variable bound constraints respectively In the conditions above A is the Lagrange multiplier corresponding to constraint c x and X is the Lagrange multiplier corresponding to the simple bounds on the variable xj There is exactly one Lagrange multiplier for each constraint and variable The Lagrange multiplier may be restricted to take on a particular sign depending on whether the corresponding constraint or variable is upper bounded o
34. ALG Specifies which algorithm to use for any linear programming LP subproblem solves that may occur in the MIP branch and bound procedure LP sub problems may arise if the problem is a mixed integer linear program MILP or if using mip_method HQG Nonlinear programming subproblems use the algorithm specified by the algorithm option O auto Let KNITRO automatically choose an algorithm based on the problem char acteristics 1 direct Use the Interior Direct barrier algorithm 2 cg Use the Interior CG barrier algorithm 3 active Use the Active Set simplex algorithm Default value 0 mip_maxnodes KTR_PARAM MIP_MAXNODES Specifies the maximum number of nodes explored 0 means no limit Default value 100000 mip_maxsolves KTR_PARAM_MIP_MAXSOLVES Specifies the maximum number of subproblem solves allowed 0 means no limit Default value 200000 mip_maxtime_cpu KTR_PARAM_MIP_MAXTIMECPU Specifies the maximum allowable CPU time in seconds for the complete MIP solution Use maxtime_cpu to additionally limit time spent per subproblem solve Default value 1 0e8 mip_maxtime_real KTR_PARAM_MIP_MAXTIMEREAL Specifies the maximum allowable real time in seconds for the complete MIP solution Use maxtime_real to additionally limit time spent per subproblem solve Default value 1 0e8 mip_method KTR_PARAM_MIP_METHOD Specifies which MIP method to use O auto Let KNITRO automatically choose the method 47 1
35. ARAM_BAR_FEASIBLE Specifies whether special emphasis is placed on getting and staying feasible in the interior point algorithms 0 no No special emphasis on feasibility 1 stay Iterates must satisfy inequality constraints once they become sufficiently fea sible 2 get Special emphasis is placed on getting feasible before trying to optimize 3 get_stay Implement both options 1 and 2 above Default value O NOTE This option can only be used with the Interior Direct and Interior CG algorithms If bar_feasible stay or bar_feasible get_stay this will activate the feasible version of KNITRO The feasible version of KNITRO will force iterates to strictly satisfy inequalities but does not require satisfaction of equality constraints at intermediate iterates see Section 9 3 This option and the honorbnds option may be useful in applications where functions are undefined outside the region defined by inequalities The initial point must satisfy inequalities to a sufficient degree if not KNITRO may generate infeasible iterates and does not switch to 39 the feasible version until a sufficiently feasible point is found Sufficient satisfaction occurs at a point x if it is true for all inequalities that cl tol lt c x lt cu tol 5 15 The constant tol is determined by the option bar_feasmodetol If bar_feasible get or bar_feasible get_stay KNITRO will place special emphasis on first trying to get feasible before trying
36. Appendix B List of Output Files knitro log This is the standard output from KNITRO The file is created if outmode file or outmode both See Section 7 for an explanation of the contents knitro_mspoints log This file contains a set of feasible points found by multi start each distinct in order of best to worst The file is created if ms_enable yes and ms_num_to_save is greater than zero See Section 9 6 for more information knitro_newpoint log This file contains a set of iterates generated by KNITRO It is created if newpoint equals saveone or saveall kdbg_barrierlP log kdbg_directIP log kdbg_normallP log kdbg_profilelP log kdbg_stepIP log kdbg_summIP log kdbg_tanglP log These files contain detailed debug information The files are created if debug problem and either barrier method Interior Direct or Interior CG executes The kdbg_directIP log file is created only for the Interior Direct method kdbg_actsetAS log kdbg_eqpAS log kdbg_IpAS log kdbg_profileAS log kdbg_stepAS log kdbg_summAS log These files contain detailed debug information The files are created if debug problem and the Active Set method executes kdbg_mip log This file contains detailed debug information The file is created if mip_debug all and one of the MIP methods executes 85
37. BB Use the standard branch and bound method 2 HQG Use the hybrid Quesada Grossman method for convex nonlinear problems only Default value 0 mip_outinterval KTR_PARAM_MIP_OUTINTERVAL Specifies node printing interval for mip_outlevel when mip_outlevel gt 0 1 Print output every node 2 Print output every 2nd node N Print output every Nth node Default value 10 mip_outlevel KTR_PARAM_MIP_OUTLEVEL Specifies how much MIP information to print O none Do not print any MIP node information 1 iters Print one line of output for every node Default value 1 mip_outsub KTR_PARAM_MIP_OUTSUB Specifies MIP subproblem solve debug output control This output is only produced if mip_debug 1 and appears in the file kdbg_mip log 0 Do not print any debug output from subproblem solves Subproblem debug output enabled controlled by option outlev 2 Subproblem debug output enabled and print problem characteristics Default value 0 mip_pseudoinit KTR_PARAM_MIP_PSEUDOINIT Specifies the method used to initialize pseudo costs corresponding to variables that have not yet been branched on in the MIP method 0 Let KNITRO automatically choose the method T Initialize using the average value of computed pseudo costs 2 Initialize using strong branching Default value 0 mip_rootalg KTR_PARAM_MIP_ROOTALG Specifies which algorithm to use for the root node solve in MIP same options as algorithm user option Defau
38. E CONSTRAINT FUNCTIONS cType 0 KTR_CONTYPE_QUADRATIC cType 1 KTR_CONTYPE_QUADRATIC cLoBnds 0 1 0 cLoBnds 1 0 0 cUpBnds 0 KTR_INFBOUND cUpBnds 1 KTR_INFBOUND PROVIDE FIRST DERIVATIVE STRUCTURAL INFORMATION jacIndexCons 0 jacIndexCons 1 0 jacIndexCons 2 I o I r 28 jacIndexCons 3 jacIndexVars 0 jacIndexVars 1 jacIndexVars 2 jacIndexVars 3 ll FOrROF PROVIDE SECOND DERIVATIVE STRUCTURAL INFORMATION hessIndexRows 0 0 hessIndexRows 1 0 hessIndexRows 2 1 hessIndexCols 0 0 hessIndexCols 1 1 hessIndexCols 2 1 CHOOSE AN INITIAL START POINT xInitial 0 2 0 xInitial 1 1 0 INITIALIZE KNITRO WITH THE PROBLEM DEFINITION nStatus KTR_init_problem kc n objGoal objType xLoBnds xUpBnds m cType cLoBnds cUpBnds nnzJ jacIndexVars jacIndexCons nnzH hessIndexRows hessIndexCols xInitial NULL if nStatus 0 an error occurred free xLoBnds xUpBnds etc Assume for simplicity that the user writes three routines for computing problem information In examples C problemHS15 c these are named computeFC computeGA and computeH To write a driver program using callback mode simply wrap each evaluation routine in a function that matches the KTR_callback prototype defined in knitro h Note that all three wrappers use the same prototype This is in case the appli
39. G PROGRAM MUST INTERPRET KNITRO S RETURN STATUS AND CONTINUE SUPPLYING PROBLEM INFORMATION UNTIL KNITRO IS COMPLETE while 1 nStatus KTR_solve kc x lambda evalStatus amp obj c objGrad jac hess hvector NULL if nStatus KTR_RC_EVALFC KNITRO WANTS obj AND c EVALUATED AT THE POINT x obj computeFC x c else if nStatus KTR_RC_EVALGA KNITRO WANTS objGrad AND jac EVALUATED AT x 31 computeGA x objGrad jac else if nStatus KTR_RC_EVALH KNITRO WANTS hess EVALUATED AT x lambda computeH x lambda hess else IN THIS EXAMPLE OTHER STATUS CODES MEAN KNITRO IS FINISHED break ASSUME THAT PROBLEM EVALUATION IS ALWAYS SUCCESSFUL IF A FUNCTION OR ITS DERIVATIVE COULD NOT BE EVALUATED AT THE GIVEN x lambda THEN SET evalStatus 1 BEFORE CALLING KTR_solve AGAIN evalStatus 0 if nStatus KTR_RC_OPTIMAL printf KNITRO failed to solve the problem final status d n nStatus DELETE THE KNITRO SOLVER INSTANCE KTR_free amp kc This completes the brief overview of creating driver programs to run KNITRO in C Again more details and options are demonstrated in the programs located in examples C including an example for a mixed integer nonlinear programming model Outputs produced when running KNITRO are discussed in Section 7 4 3 KNITRO in a C application Calling K
40. LP The KNITRO MINLP code is designed for convex mixed integer programming and is a heuristic for nonconvex problems The MIP code also handles mixed integer linear programs MILP of moderate size A MIP problem is defined and solved using the new API functions KTR_mip_init_problem and KTR_mip_solve In addition many new user options beginning with mip_ have been added to offer user control over the MIP methods See more details in Sections 4 and 5 1 and in the MINLP examples provided in the C and Java examples directories with the distribution e The multi start generation of new start points is improved in KNITRO 6 0 The user option ms_maxbndrange for generating initial points now only applies to unbounded variables while the new user option ms_startptrange establishes a maximum initial range for all variables The default value of ms_savetol was also increased See Sections 5 1 and 9 6 for more details e KNITRO 6 0 offers improved performance of the SLQP active set algorithm on simple bound constrained optimization models This will often be the most efficient algorithm for these types of problems e General performance improvements have been made for both the active set and interior point barrier solvers in KNITRO 6 0 1 4 Contact and Support Information KNITRO is licensed and supported by Ziena Optimization Inc http www ziena com General information regarding KNITRO can be found at the KNITRO website http www zien
41. NITRO from a C application follows the same outline as a C application The dis tribution provides a C general test harness in the directory examples C In the example optimization problems are coded as subclasses of an abstract interface and compiled as separate shared objects A main driver program dynamically loads a problem and sets up callback mode 9 8 so KNITRO can invoke the particular problem s evaluation methods The main driver can also use KNITRO to conveniently check partial derivatives against finite difference approximations It is easy to add more test problems to the test environment 4 4 KNITRO in a Java application Calling KNITRO from a Java application follows the same outline as a C application The optimiza tion problem must be defined in terms of arrays and constants that follow the KNITRO API and then the Java version of KTR_init_problem KTR mip_init_problem is called Java int and double types map directly to their C counterparts Having defined the optimization problem the Java version of KTR_solve KTR_mip_solve is called in reverse communications mode 9 7 32 The KNITRO distribution provides a Java Native Interface JNI wrapper for the KNITRO callable library functions defined in knitro h The Java API loads lib JNI knitro dll a JNI enabled form of the KNITRO binary on Unix the file is called lib libJNI knitro so on MacIntosh it is lib libJNI knitro jnilib In this way Java applications can crea
42. SOLVER Indicates which linear programming simplex solver the KNITRO Active Set algorithm uses when solving internal LP subproblems This option has no effect on the Interior Direct and Interior CG algorithms 1 internal KNITRO uses its default LP solver 2 cplex KNITRO uses IBM ILOG CPLEX provided the user has a valid CPLEX li cense The CPLEX library is loaded dynamically after KTR_solve is called Default value 1 If lpsolver cplex then the CPLEX shared object library or DLL must reside in the operating system s load path see Section 5 4 If this option is selected KNITRO will automatically look for in order CPLEX 11 2 CPLEX 11 1 CPLEX 11 0 CPLEX 10 2 CPLEX 10 1 CPLEX 10 0 CPLEX 9 1 CPLEX 9 0 or CPLEX 8 0 To override the automatic search and load a particular CPLEX library set its name with the character type user option cplexlibname Either supply the full path name in this option or make sure the library resides in a directory that is listed in the operating system s load path see Section 5 4 For example to specifically load the Windows CPLEX library cplex90 d11 make sure the directory containing the library is part of the PATH environment variable and call the following also be sure to check the return status of this call KTR_set_char_param_by name kc cplexlibname cplex90 d11 44 maxcgit KTR PARAM_MAXCGIT Determines the maximum allowable number of inner conjugate gradient CG itera
43. TRO KNITRO offers a number of user options for modifying behavior of the solver Each option takes a value that may be an integer double precision number or character string Options are usually identified by a string name for example algorithm but programmatic interfaces also identify options by an integer value associated with a C language macro defined in the file knitro h for example KTR_PARAM ALG This section lists all user options in alphabetical order identified by the string name and the macro definition User options beginning with bar_ apply only to the barrier interior point algorithms options beginning with mip_ apply only to the mixed integer programming MIP solvers and options specific to the multi start procedure begin with ms_ Sections 5 2 and 5 3 provide instructions on how to set and modify user options 5 1 Description of KNITRO user options algorithm KTR_PARAM ALG Indicates which algorithm to use to solve the problem see Section 8 O auto Let KNITRO automatically choose an algorithm based on the problem char acteristics 1 direct Use the Interior Direct algorithm 2 cg Use the Interior CG algorithm 3 active Use the Active Set algorithm Default value O bar_initmu KTR_PARAM BAR_INITMU Specifies the initial value for the barrier parameter u used with the barrier algorithms This option has no effect on the Active Set algorithm Default value 1 0e 1 bar_feasible KTR_P
44. Ziena supports a variety of ways to install licenses The simplest procedure is to copy each license into a file whose name begins with the characters ziena_lic please use lower case letters Then place the file in your HOME directory For more installation options and general troubleshooting read the Ziena License Manager User s Manual 2 3 Linux Compatibility Issues Linux platforms sometimes generate link errors when building the programs in examples C Simply type gmake and see if the build is successful You may see a long list of link errors similar to the following lib libknitro a text 0x28808 In function ktr_xeb4 undefined reference to std __default_alloc_template lt true 0 gt deallo cate void unsigned int lib libknitro a text 0x28837 In function ktr_xeb4 undefined reference to std __default_alloc_template lt true 0 gt deallo cate void unsigned int lib libknitro a text 0x290b0 more undefined references to std __ default_alloc_template lt true 0 gt deallocate void unsigned int follow lib libknitro a text 0x2a0ff In function ktr_x1150 undefined reference to std basic_string lt char std char_traits lt char gt gt std allocator lt char gt gt _S_empty_rep_storage lib libknitro a text 0x2a283 In function ktr_x1150 undefined reference to std __default_alloc_template lt true 0 gt deallo cate void unsigned
45. a com knitro html For technical support contact your local distributor If you purchased KNITRO directly from Ziena you may send support questions or comments to info ziena com Questions regarding licensing information or other information about KNITRO can also be sent to info ziena com 2 Installation Instructions for installing the KNITRO package on supported platforms are given below After installing view the INSTALL txt LICENSE_KNITRO txt and README txt files then test the instal lation If you purchased the KNITRO AMPL solver product then refer to Section 3 and test KNITRO as the solver for any smooth optimization model an AMPL test model is provided with the KNITRO distribution If you purchased the full KNITRO product then test KNITRO by compiling and running one or more programs in the examples directory Example problems are provided for C C Fortran and Java interfaces We recommend understanding these examples and reading Section 4 of this manual before proceeding with development of your own application interface 2 1 Windows KNITRO is supported on Windows 2003 Windows XP SP2 and Windows XP Professional x64 There are compatibility problems with Windows XP SP1 system libraries users should upgrade to Windows XP SP2 The KNITRO software package for Windows is delivered as a zipped file ending in zip or as a self extracting executable ending in exe For the zip file double click on it and extract all co
46. a complementarity constraint is a way to model a constraint which is combinatorial in nature since for example the conditions in 10 35 imply that either x or x2 must be 0 both may be 0 as well Without special care these type of constraints may cause problems for nonlinear optimization solvers because problems which contain these types of constraints fail to satisfy con straint qualifications which are often assumed in the theory and design of algorithms for nonlinear optimization For this reason we provide a special interface in KNITRO for specifying complemen tarity constraints In this way KNITRO can recognize these constraints and apply some special care to them internally Complementarity constraints can be specified in KNITRO through a call to the function KTR_addcompcons which has the following prototype and argument list Prototype int KTR_addcompcons KTR_context_ptr kc int numCompConstraints int indexListi int indexList2 Arguments KTR_context kc is a pointer to a structure which holds all the relevant information about a particular problem instance int numCompConstraints is a scalar specifying the number of complementarity constraints to be added to the problem i e the number of pairs of variables which are complementary to each other int indexList1 is an array of length numCompConstraints specifying the variable indices for the first set of variables in the pairs of complementary variables
47. ached The MIP subproblem solve limit was reached before being able to satisfy the optimality gap tol erance The subproblem solve limit can be increased through the user option mip_maxsolves See Section 5 1 406 KTR_RC_MIP_NODE_LIMIT Node limit reached The MIP node limit was reached before being able to satisfy the optimality gap tolerance The node limit can be increased through the user option mip_maxnodes See Section 5 1 500 KTR_RC_CALLBACK_ERR Callback function error This termination value indicates that an error i e negative return value occurred in a user provided callback routine 501 KTR_RC_LP_SOLVER_ERR LP solver error This termination value indicates that an unrecoverable error occurred in the LP solver used in the active set algorithm preventing the optimization from continuing 502 KTR_RC_EVAL_ERR Evaluation error This termination value indicates that an evaluation error occurred e g divide by 0 taking the square root of a negative number preventing the optimization from continuing 84 503 KTR_RC_OUT_OF_MEMORY Not enough memory available to solve problem This termination value indicates that there was not enough memory available to solve the problem 505 to 600 Termination values in this range imply some input error or other non standard failure If outlev gt 0 details of this error will be printed to standard output or the file knitro log depending on the value of outmode
48. active once an iterate x satisfies 9 33 for all inequality constraints If the initial point satisfies 9 33 then every iterate will be feasible with respect to the inequalities KNITRO can also place special emphasis on getting feasible with respect to all constraints through the option bar_feasible If bar_feasible 2 or bar_feasible 3 KNITRO will first place special emphasis on getting feasible before working on optimality This option is not always guar anteed to accelerate the finding of a feasible point However it may do a better job of obtaining feasibility on difficult problems where the default version struggles NOTE This option can only be used with the Interior Direct and Interior CG algorithms 9 4 Honor Bounds In some applications the user may want to enforce that the initial point and all subsequent iterates satisfy the simple bounds bl lt x lt bu For instance if the objective function or a nonlinear constraint function is undefined at points outside the bounds then the bounds should be enforced at all times By default KNITRO enforces bounds on the variables only for the initial start point and the final solution honorbnds 2 To enforce satisfaction at all iterates set honorbnds 1 To allow execution from an initial point that violates the bounds set honorbnds 0 9 5 Crossover Interior point or barrier methods are a powerful tool for solving large scale optimization problems However one drawback of these
49. afeguards on the corrector step Available only for the Inte rior Direct algorithm a fullmpc Use a Mehrotra predictor corrector type rule to determine the barrier pa rameter without safeguards on the corrector step Available only for the Interior Direct algorithm O quality Minimize a quality function at each iteration to determine the barrier param eter Available only for the Interior Direct algorithm Default value O bar_penaltycons KTR_PARAM_BAR_PENCONS Indicates whether a penalty approach is applied to the constraints Using a penalty approach may be helpful when the problem has degenerate or difficult constraints It may also help to more quickly identify infeasible problems or achieve feasibility in problems with difficult constraints This option has no effect on the Active Set algorithm 0 auto Let KNITRO automatically choose the strategy 1 none No constraints are penalized 2 all A penalty approach is applied to all general constraints Default value 0 bar_penaltyrule KTR_PARAM_BAR_PENRULE Indicates which penalty parameter strategy to use for determining whether or not to accept a trial iterate This option has no effect on the Active Set algorithm 0 auto Let KNITRO automatically choose the strategy 1 single Use a single penalty parameter in the merit function to weight feasibility versus optimality 2 flex Use a more tolerant and flexible step acceptance procedure based on a
50. aluations secs 0 00015 12 KNITRO 6 0 Locally optimal solution found objective 9 360000e 02 feasibility error 0 000000e 00 7 major iterations 8 function evaluations ampl For descriptions of the KNITRO output see Section 7 To display the final solution variables x and the objective value obj through AMPL use the AMPL display command as follows ampl display x x 10 2 0 3 8 ampl display obj obj 936 Upon completion KNITRO displays a message and returns an exit code to AMPL In the example above KNITRO found a solution so the message was Locally optimal solution found with exit code of zero exit code can be seen by typing ampl display solve_exitcode If a solution is not found then KNITRO returns one of the following 0 Locally optimal solution found 100 Current solution estimate cannot be improved Nearly optimal 101 Relative change in feasible solution estimate lt xtol 102 Current feasible solution estimate cannot be improved 200 Convergence to an infeasible point Problem may be locally infeasible 201 Relative change in infeasible solution estimate lt xtol 202 Current infeasible solution estimate cannot be improved 203 Multistart No primal feasible point found 300 Problem appears to be unbounded 400 Iteration limit reached 401 Time limit reached 403 MIP All nodes have been explored 404 MIP Integer feasible point found 405 MIP Subproblem solv
51. and Java interfaces are provided with the distribution in the examples directory Many user options are provided for the MIP features to tune performance including options for branching node selection rounding and heuristics for finding integer feasible points User options specific to the MIP tools begin with mip_ see Section 5 It is recommended to experiment with several of these options as they often can make a significant difference in performance In particular if finding any integer feasible point is your highest priority you should set the mip_heuristic option to search for an integer feasible point before beginning the branch and bound procedure by default no heuristics are applied The MIP features are new in KNITRO 6 0 and may not be available for every interface immedi ately References 1 R H Byrd J Ch Gilbert and J Nocedal A trust region method based on interior point techniques for nonlinear programming Mathematical Programming 89 1 149 185 2000 2 R H Byrd N I M Gould J Nocedal and R A Waltz On the convergence of successive linear quadratic programming algorithms STAM Journal on Optimization 16 2 471 489 2006 3 R H Byrd N I M Gould J Nocedal and R A Waltz An algorithm for nonlinear optimization using linear programming and equality constrained subproblems Mathematical Programming Series B 100 1 27 48 2004 4 R H Byrd M E Hribar and J Nocedal An interior poin
52. ap stop tolerance 1 0e 6 mip_knapsack add knapsack cuts 1 0 do not add knapsack cuts 1 add knapsack inequality cuts only 2 add knapsack inequality and equality cuts mip_lpalg LP subproblem algorithm 0 O let KNITRO decide the LP algorithm 1 Interior Direct barrier algorithm 2 Interior CG barrier algorithm 3 Active Set simplex algorithm mip_maxnodes maximum nodes explored 100000 mip_maxsolves maximum subproblem solves 200000 mip_maxtime_cpu maximum CPU time in seconds for MIP 1 0e8 mip_maxtime_real maximum real time in seconds for MIP 1 0e8 mip_method MIP method 0 O let KNITRO choose the method 1 branch and bound method 2 hybrid method for convex nonlinear models mip_outinterval MIP node output interval 10 mip_outlevel MIP output level 1 mip_outsub enable MIP subproblem debug output 0 mip_pseudoinit method to initialize pseudo costs 0 O let KNITRO choose the method 1 use average value 2 use strong branching 15 16 OPTION DESCRIPTION DEFAULT mip_rootalg root node relaxation algorithm 0 O let KNITRO decide the root algorithm 1 Interior Direct barrier algorithm 2 Interior CG barrier algorithm 3 Active Set algorithm mip_rounding MIP rounding rule 0 O let KNITRO choose the rounding rule 1 do not attempt rounding 2 use fast heuristic 3 apply rounding solve selectively 4 apply rounding solve always
53. ate but not the final solution double lambda is an array of length m n output by KNITRO If KTR_solve returns zero then lambda contains the multiplier values at the solution The first m components of lambda are multipliers corresponding to the constraints specified in c x while the last n components are multipliers corresponding to the bounds on z Reverse communications mode upon return lambda contains the value of multi pliers at which KNITRO needs more problem information int evalStatus is a scalar input to KNITRO used only in reverse communications mode A value of zero means the application successfully computed the problem information requested by KNITRO at x and lambda A nonzero value means the application failed to compute problem information e g if a function is undefined at the requested value double obj is a scalar holding the value of f x at the current x If KTR_solve returns KTR_RC_OPTIMAL zero then obj contains the value of the objective function f x at the solution Reverse communications mode if KTR_solve returns KTR_RC_EVALFC then obj must be filled with the value of f x computed at x before KTR_solve is called again double c is an array of length m used only in reverse communications mode If KTR_solve returns KTR_RC_EVALFC then c must be filled with the value of c x com puted at x before KTR_solve is called again double objGrad is an array of length n used only in reverse
54. ation Important solution information from KNITRO is either made available as output from the call to KTR_solve KTR_mip_solve or can be retrieved through special function calls The KTR_solve O KTR mip solve functions see Section 4 return the final value of the ob jective function in obj the final primal solution vector in the array x and the final values of the Lagrange multipliers or dual variables in the array lambda The solution status code is given by the return value from KTR_solve KTR_mip_solve In addition information related to the final statistics can be retrieved through the following function calls int KTR_get_number_FC_evals const KTR_context_ptr kc This function call returns the number of function evaluations requested by KTR_solve or KTR_mip_solve It returns a negative number if there is a problem with kc int KTR_get_number_GA_evals const KTR_context_ptr kc 64 This function call returns the number of gradient evaluations requested by KTR_solve or KTR mip_solve It returns a negative number if there is a problem with kc int KTR_get_number_H_evals const KTR_context_ptr kc This function call returns the number of Hessian evaluations requested by KTR_solve or KTR_mip_solve It returns a negative number if there is a problem with kc int KTR_get_number_HV_evals const KTR_context_ptr kc This function call returns the number of Hessian vector products requested by KTR_solve
55. bjective function becomes greater than objrange for a feasible iterate then the problem is determined to be unbounded and KNITRO proceeds no further Default value 1 0e20 opttol KTR_PARAM_OPTTOL Specifies the final relative stopping tolerance for the KKT optimal ity error Smaller values of opttol result in a higher degree of accuracy in the solution with respect to optimality See Section 6 for more information Default value 1 0e 6 opttol_abs KTR_PARAM_OPTTOLABS Specifies the final absolute stopping tolerance for the KKT optimality error Smaller values of opttol_abs result in a higher degree of accuracy in the solution with respect to optimality See Section 6 for more information Default value 0 0e0 51 outappend KTR_PARAM_OUTAPPEND Specifies whether output should be started in a new file or appended to existing files The option affects knitro log and files produced when debug 1 It does not affect knitro_newpoint log which is controlled by option newpoint 0 no Erase any existing files when opening for output 1 yes Append output to any existing files Default value 0 NOTE The option should not be changed after calling KTR_init_problem outdir KTR_PARAM_OUTDIR Specifies a single directory as the location to write all output files The option should be a full pathname to the directory and the directory must already exist NOTE The option should not be changed after calling KTR_init_problem or
56. cation finds it convenient to combine some of the evaluation steps as demonstrated in examples C callbackExample2 c FUNCTION callbackEvalFC The signature of this function matches KTR_callback in knitro h Only obj and c are modified int callbackEvalFC const int evalRequestCode const int n const int m const int nnzJ 29 const int nnzH const double const x const double const lambda double const obj double const c double const objGrad double const jac double const hessian double const hessVector void userParams 1 if evalRequestCode KTR_RC_EVALFC printf callbackEvalFC incorrectly called with eval code d n evalRequestCode return 1 IN THIS EXAMPLE CALL THE ROUTINE IN problemDef h obj computeFC x c return 0 FUNCTION callbackEvalGA PAZ The signature of this function matches KTR_callback in knitro h Only objGrad and jac are modified similar implementation to callbackEvalFC FUNCTION callbackEvalH The signature of this function matches KTR_callback in
57. ce slack variables 5 6 x7 and re write problem 10 39 as minimize f a ap 5 2a 1 10 41a subject to colz 2 a 1 1520 22 0 523 z4 0 10 41b G x 329 z 3 z5 0 10 41c a x a 0 54 4 26 0 10 41d 3 1 z0 21 7 7 0 10 41e zi gt 0 4 0 7 10 41f tol xs 10 41g 23126 10 41h 2427 10 411 Now that the problem is in a form suitable for KNITRO we define the problem for KNITRO by using c cLoBnds and cUpBnds for 10 41b 10 41e and xLoBnds xUpBnds for 10 41f to specify the normal constraints and bounds in the usual way for KNITRO We use indexList1 indexList2 and the KTR_addcompcons function call to specify the complementarity constraints 10 41g 10 415 These arrays are specified as follows for 10 41 n 8 number of variables m 4 number of regular constraints numCompConstraints 3 number of complementarity constraints c 0 2x x 1 1 1 5 x 0 x 2 0 5 x 3 x 4 c 1 3 x 0 x 1 3 x 5 c 2 x 0 0 5 x 1 4 x 6 78 c 3 x 0 x 1 7 xI7 cLoBnds 0 0 cUpBnds 0 0 cLoBnds 1 0 cUpBnds 1 0 cLoBnds 2 0 cUpBnds 2 0 cLoBnds 3 0 cUpBnds 3 0 xLoBnds 0 0 xUpBnds 0 KTR_INFBOUND xLoBnds 1 0 xUpBnds 1 KTR_INFBOUND xLoBnds 2 0 xUpBnds 2 KTR_INFBOUND xLoBnds 3 0 xUpBnds 3 KTR_INFBOUND xLoBnds 4 0 xUpBnds 4
58. ck with the modeling vendor Options are set by specifying a keyword and a corresponding value on a line in the options file Lines that begin with a character are treated as comments and blank lines are ignored For example to set the maximum allowable number of iterations to 500 you could create the following options file KNITRO Options file maxit 500 The options file is read into KNITRO by calling the following function before invoking KTR_solve or KTR mip_solve int KTR_load_param_file KTR_context kc char const filename For example if the options file is named myoptions opt status KTR_load_param_file kc myoptions opt The full set of options used by KNITRO in a given solve may be written to a text file through the function call int KTR_save_param_file KTR_context kc char const filename 53 For example status KTR_save_param_file kc knitro opt A sample options file knitro opt is provided for convenience and can be found in the examples C directory Note that this file is only read by application drivers that call KTR_load_param file such as examples C callbackExample2 c Most user options can be specified with either a numeric value or a string value The individual user options and their possible numeric values are described in Section 5 1 String values are listed in the comments of the file examples C knitro opt provided with the distribution 5 3 Setting options through functio
59. communications mode If KTR_solve returns KTR_RC_EVALGA then objGrad must be filled with the value of V f x computed at x before KTR_solve is called again double jac is an array of length nnzJ used only in reverse communications mode If KTR_solve returns KTR_RC_EVALGA then jac must be filled with the constraint Ja cobian Vc x computed at x before KTR_solve is called again Entries are stored according to the sparsity pattern defined in KTR_init_problem double hess is an array of length nnzH used only in reverse communications mode and only if option hessopt is set to KTR_HESSOPT_EXACT see Section 5 1 If KTR_solve returns KTR_RC_EVALH then hess must be filled with the Hessian of the Lagrangian computed at x and lambda before KTR_solve is called again Entries are stored according to the sparsity pattern defined in KTR_init_problem double hessVector is an array of length n used only in reverse communications mode and only if option hessopt is set to KTR HESSOPT_PRODUCT see Section 5 1 If KTR_solve returns KTR_RC_EVALHV then the Hessian of the Lagrangian at x and lambda should be 26 multiplied by hessVector and the result placed in hessVector before KTR_solve is called again void userParams is a pointer to a structure used only in callback mode The pointer is provided so the application can pass additional parameters needed for its callback routines If the application needs no additional param
60. ct unless blasoption 2 cplexlibname KTR_PARAM_CPLEXLIB See option lpsolver debug KTR_PARAM_DEBUG Controls the level of debugging output Debugging output can slow execution of KNITRO and should not be used in a production setting All debugging output is suppressed if option outlev 0 O none No debugging output 1 problem Print algorithm information to kdbg log output files 2 execution Print program execution information 42 Default value O delta KTR_PARAM_DELTA Specifies the initial trust region radius scaling factor used to determine the initial trust region size Default value 1 0e0 feastol KTR_PARAM_FEASTOL Specifies the final relative stopping tolerance for the feasibility error Smaller values of feastol result in a higher degree of accuracy in the solution with respect to feasibility See Section 6 for more information Default value 1 0e 6 feastol_abs KTR_PARAM FEASTOLABS Specifies the final absolute stopping tolerance for the fea sibility error Smaller values of feastol_abs result in a higher degree of accuracy in the solution with respect to feasibility See Section 6 for more information Default value 0 0e0 gradopt KTR_PARAM_GRADOPT Specifies how to compute the gradients of the objective and con straint functions See Section 9 1 for more information 1 exact User provides a routine for computing the exact gradients 2 forward KNITRO computes gradients by forward finite differenc
61. d all new points to file knitro_newpoint log objrange maximum allowable objective function magnitude 1 0e20 opttol optimality termination tolerance relative 1 0e 6 opttol_abs optimality termination tolerance absolute 0 0e 0 outappend append output to existing files 0 O do not append 1 do append outdir directory where output files are created 17 OPTION DESCRIPTION DEFAULT outlev printing output level 2 0 no printing just print summary information print basic information every 10 iterations print basic information at each iteration print all information at each iteration also print final primal variables also print final Lagrange multipliers sensitivies outmode direct KNITRO output to standard out e g screen 0 direct KNITRO output to the file knitro log print to both the screen and file knitro log Ne On OP WN Hr pivot initial pivot threshold for matrix factorizations 1 0e 8 presolve_dbg no debugging information 0 print the KNITRO problem with AMPL model names scale do not scale the problem 1 0 2 0 1 perform automatic scaling of functions 0 1 2 soc do not allow second order correction steps 1 selectively try second order correction steps always try second order correction steps xtol stepsize termination tolerance 1 0e 15 3 3 Solving with Complementarity Constraints KNITRO is able to solve mathematical programs with complementarit
62. d the Hessian matrix of the Lagrangian function when using exact Hessians in sparse form Below we give an example of how to do this Example Assume we want to use KNITRO to solve the following problem minimize zo 2123 4 7a subject to cos xo 0 5 4 7b 3 lt rf r lt 8 4 7c to z 2 lt 10 4 7d To 1 2 1 4 7e Rewriting in the notation of 4 4 we have f z wt a23 4 8 colz cos xp 4 9 ala 4 10 ol To z1 22 4 11 4 12 34 Computing the Sparse Jacobian Matrix The gradients first derivatives of the objective and constraint functions are given by 1 sin xo 2x0 1 Vf x a3 Vco 1 0 Vc z 221 Veo a 1 32122 0 0 1 The constraint Jacobian matrix J x is the matrix whose rows store the transposed constraint gradients i e Vco z T sin zo 0 0 Ja Vals 2x0 2x1 0 Ve2 a 7 1 1 1 In KNITRO the array objGrad stores all of the elements of V f x while the arrays jac jacIndexCons and jacIndexVars store information concerning only the nonzero elements of J x The array jac stores the nonzero values in J x evaluated at the current solution estimate x jacIndexCons stores the constraint function or row indices corresponding to these values and jacIndexVars stores the variable or column indices There is no restriction on the order in which these elements are stored however it is common to store the nonzero elements of J x in column
63. de KTR_RC_BAD_KCPTR if there is a problem with kc double KNITRO_API KTR_get_mip_lastnode_obj const KTR_context_ptr kc This function returns the objective value of the most recently solved MIP node subproblem It returns termination code KTR_RC_BAD_KCPTR if there is a problem with kc 66 8 Algorithm Options 8 1 Automatic KNITRO provides three different algorithms for solving problems See Section 1 2 for an overview of the methods By default KNITRO automatically tries to choose the best algorithm for a given problem based on problem characteristics We strongly encourage you to experiment with all the algorithms as it is difficult to predict which one will work best on any particular problem 8 2 Interior Direct This algorithm often works best and will automatically switch to Interior CG if the direct step is suspected to be of poor quality or if negative curvature is detected Interior Direct is recommended if the Hessian of the Lagrangian is ill conditioned The Interior CG method in this case will often take an excessive number of conjugate gradient iterations It may also work best when there are dependent or degenerate constraints Choose this algorithm by setting user option algorithm 1 We encourage you to experiment with different values of the bar_murule option when using the Interior Direct or Interior CG algorithm It is difficult to predict which update rule will work best on a problem NOTE Since the Interior Di
64. e KTR_INFBOUND defined in knitro h If the constraint is an equality then cLoBnds should equal cUpBnds i int nnzJ 23 is ascalar specifying the number of nonzero elements in the sparse constraint Jacobian See Section 4 7 int jacIndexVars is an array of length nnzJ specifying the variable indices of the constraint Jacobian nonzeroes If jacIndexVars i j then jac i refers to the j th variable where jac is the array of constraint Jacobian nonzero elements passed in the call KTR_solve jacIndexCons i and jacIndexVars i determine the row numbers and the column numbers respectively of the nonzero constraint Jacobian element jac i See Sec tion 4 7 NOTE C array numbering starts with index 0 Therefore the j th variable x maps to array element x j and 0 lt j lt n int jacIndexCons is an array of length nnzJ specifying the constraint indices of the con int nnzH straint Jacobian nonzeroes If jacIndexCons i k then jacli refers to the k th con straint where jac is the array of constraint Jacobian nonzero elements passed in the call KTR_solve jacIndexCons i and jacIndexVars i determine the row numbers and the column numbers respectively of the nonzero constraint Jacobian element jac i See Sec tion 4 7 NOTE C array numbering starts with index 0 Therefore the k th constraint cg maps to array element c k and 0 lt k lt m is a scalar specifying the number of nonzero elements in
65. e limit reached 406 MIP Node limit reached 501 LP solver error 502 Evaluation error 503 Not enough memory 504 Terminated by user 505 Input or other API error 506 Internal KNITRO error 507 Unknown termination 508 Illegal objno value 13 3 2 KNITRO options for AMPL KNITRO user options can be set from AMPL by typing the name of the option and a numeric value When using AMPL s interactive mode set all options in a single command for example ampl option knitro_options maxit 100 opttol 1 0e 5 When running KNITRO directly with an AMPL problem set user options on the command line with the problem name for example knitroampl testproblem nl maxit 100 opttol 1 0e 5 A complete list of available KNITRO options can always be shown by typing knitroampl These options are summarized below All options specific to the barrier interior point algorithms start with bar_ options specific to mixed integer programming begin with mip_ and options specific to the multi start procedure begin with ms_ OPTION DESCRIPTION DEFAULT alg optimization algorithm used 0 algorithm O let KNITRO choose the algorithm 1 Interior Direct barrier algorithm 2 Interior CG barrier algorithm 3 Active Set algorithm bar_feasible whether feasibility is given special emphasis 0 0 no special emphasis on feasibility 1 iterates must honor inequalities 2 emphasize first getting feasible before optimi
66. e of maxcrossit and try again If KNITRO determines that the crossover procedure will not succeed no matter how many iterations are tried then a message of the form Crossover mode unable to improve solution will be printed The extra cost of performing crossover is problem dependent In most small or medium scale problems the crossover cost is a small fraction of the total solve cost In these cases it may be worth using the crossover procedure to obtain a more exact solution On some large scale or difficult de generate problems however the cost of performing crossover may be significant It is recommended to experiment with this option to see whether improvement in the exactness of the solution is worth the additional cost 9 6 Multi start Nonlinear optimization problems 1 1 are often nonconvex due to the objective function constraint functions or both When this is true there may be many points that satisfy the local optimality conditions described in Section 6 Default KNITRO behavior is to return the first locally optimal point found KNITRO offers a simple multi start feature that searches for a better optimal point by restarting KNITRO from different initial points The feature is enabled by setting ms_enable 1 The multi start procedure generates new start points by randomly selecting components of x that satisfy lower and upper bounds on the variables KNITRO finds a local optimum from each start point using the same problem d
67. e_cpu limits how long KNITRO iterates from a single start point Therefore ms_naxtime_cpu should be greater than maxtime_cpu This option has no effect unless ms_enable yes Default value 1 0e8 ms_maxtime_real KTR_PARAM_MSMAXTIMEREAL Specifies in seconds the maximum allowable real time before termination The limit applies to the operation of KNITRO since multi start began in contrast the value of maxtime_real limits how long KNITRO iterates from a single start point Therefore ms_maxtime_real should be greater than maxtime_real This option has no effect unless ms_enable yes Default value 1 0e8 ms_num_to_save KTR_PARAM MSNUMTOSAVE Specifies the number of distinct feasible points to save in a file named knitro_mspoints log Each point results from a KNITRO solve from a different starting point and must satisfy the absolute and relative feasibility tolerances The file stores points in order from best objective to worst Points are distinct if they differ in objective value or some component by the value of ms_savetol using a relative tolerance test see Section 9 6 This option has no effect unless ms_enable yes Default value 0 ms_savetol KTR_PARAM_MSSAVETOL Specifies the tolerance for deciding if two feasible points are distinct Points are distinct if they differ in objective value or some component by the value of ms_savetol using a relative tolerance test see Section 9 6 A large value can cause the saved feasible po
68. efinition and user options The final solution returned from KTR_solve is the local optimum with the best objective function value if any local optimum have been found If no local optimum have been found KNITRO will return the best feasible solution estimate it found If no feasible solution estimate has been found KNITRO will return the least infeasible point If you wish to see details of the local optimization process for each start point then set option outlev to at least 4 The number of start points tried by multi start is specified with the option ms_maxsolves By default KNITRO will try min 200 10n where n is the number of variables in the problem Users may override the default by setting ms_maxsolves to a specific value The multi start option is convenient for conducting a simple search for a better solution point Search time is improved if the variable bounds are made as tight as possible confining the search to a region where a good solution is likely to be found The user can restrict the multi start search region without altering bounds by using the options ms_maxbndrange and ms_startptrange The first option applies to variables unbounded in at least one direction i e the upper or lower bound or both is infinite and keeps new start points within a total range equal to the value of ms_maxbndrange The second option applies to all variables and keeps new start points within a total 71 range equal to the value of ms_startp
69. ere is a problem with kc int KTR_get_mip_num_solves const KTR_context_ptr kc This function returns the number of continuous subproblems processed in the MIP solve made by KTR_mip_solve It returns a negative number if there is a problem with kc 65 double KTR_get_mip_abs_gap const KTR_context_ptr kc This function returns the final absolute integrality gap in the MIP solve made by KTR_mip_solve See 6 2 for a detailed definition of this quantity It returns KTR_INFBOUND if no incumbent i e integer feasible point was found It returns termination code KTR_RC_BAD_KCPTR if there is a problem with ke double KTR_get_mip_rel_gap const KTR_context_ptr kc This function returns the final relative integrality gap in the MIP solve made by KTR_mip_solve See 6 2 for a detailed definition of this quantity It returns KTR_INFBOUND if no incumbent i e integer feasible point was found It returns termination code KTR_RC_BAD_KCPTR if there is a problem with ke double KNITRO_API KTR_get_mip_incumbent_obj const KTR_context_ptr kc This function returns the objective value of the MIP incumbent solution It returns KTR_INFBOUND if no incumbent i e integer feasible point has been found It returns termination code KTR_RC_BAD_KCPTR if there is a problem with kc double KNITRO_API KTR_get_mip_relaxation_bnd const KTR_context_ptr kc This function returns the value of the current MIP relaxation bound It returns termination co
70. erformed before terminating Default value O maxtime_cpu KTR_PARAM_MAXTIMECPU Specifies in seconds the maximum allowable CPU time before termination Default value 1 0e8 maxtime_real KTR_PARAM_MAXTIMEREAL Specifies in seconds the maximum allowable real time before termination Default value 1 0e8 mip_branchrule KTR_PARAM_MIP_BRANCHRULE Specifies which branching rule to use for MIP branch and bound procedure O auto Let KNITRO automatically choose the branching rule 1 most_frac Use most fractional most infeasible branching 2 pseudcost Use pseudo cost branching 3 strong Use strong branching see options mip_strong_candlim mip_strong_level and mip_strong_maxit for further control of strong branching procedure 45 Default value 0 mip debug KTR_PARAM_MIP_DEBUG Specifies debugging level for MIP solution O none No MIP debugging output created 1 all Write MIP debugging output to the file kdbg_mip log Default value 0 mip_gub_branch KTR_PARAM_MIP_GUB_BRANCH Specifies whether or not to branch on generalized upper bounds GUBs O no Do not branch on GUBs 1 yes Allow branching on GUBs Default value O mip heuristic KTR_PARAM_MIP_HEURISTIC Specifies which MIP heuristic search approach to apply to try to find an initial integer feasible point If a heuristic search procedure is enabled it will run for at most mip_heuristic_maxit iterations before starting the branch and bound
71. es 3 central KNITRO computes gradients by central finite differences Default value 1 NOTE It is highly recommended to provide exact gradients if at all possible as this greatly impacts the performance of the code hessopt KTR_PARAM HESSOPT Specifies how to compute the approximate Hessian of the La grangian See Section 9 2 for more information exact User provides a routine for computing the exact Hessian bigs KNITRO computes a dense quasi Newton BFGS Hessian sr1 KNITRO computes a dense quasi Newton SR1 Hessian finite diff KNITRO computes Hessian vector products using finite differences product User provides a routine to compute the Hessian vector products oo nF UNB 1bfgs KNITRO computes a limited memory quasi Newton BFGS Hessian its size is determined by the option Imsize Default value 1 NOTE Options hessopt 4 and hessopt 5 are not available with the Interior Direct algo rithm KNITRO usually performs best when the user provides exact Hessians hessopt 1 or exact Hessian vector products hessopt 5 If neither can be provided but exact gradients are available i e gradopt 1 then hessopt 4 is recommended This option is comparable in terms of robustness to the exact Hessian option and typically not much slower in terms of time provided that gradient evaluations are not a dominant cost If exact gradients cannot 43 be provided then one of the quasi Newton options is preferred
72. escribes example program that uses the callback mode 73 This callback should modify obj and c int KTR_set_func_callback KTR_context_ptr kc KTR_callback func This callback should modify objGrad and jac int KTR_set_grad_callback KTR_context_ptr kc KTR_callback func This callback should modify hessian or hessVector depending on the value of evalRequestCode int KTR_set_hess_callback KTR_context_ptr kc KTR_callback func This callback should modify nothing int KTR_set_newpoint_callback KTR_context_ptr kc KTR_callback func NOTE To enable newpoint callbacks set newpoint user These should only be used for con tinuous problems KNITRO also provides a special callback function for output printing By default KNITRO prints to stdout or a knitro log file as determined by the outmode option Alternatively the user can define a callback function to handle all output This callback function can be set as shown below int KTR_set_puts_callback KTR_context_ptr kc KTR_puts puts_func The prototype for the KNITRO callback function used for handling output is typedef int KTR_puts char str void user 74 10 Special problem classes This section describes specializations in KNITRO to deal with particular classes of optimization problems We also provide guidance on how to best set user options and model your problem to get the best performance out of KNITRO for
73. esolve_dbg 2 outlev 0 Soo AMPL problem for KNITRO Objective name obj 0 000000e 00 lt x 0 lt 1 000000e 20 x 1 0 000000e 00 lt x 1 lt 1 000000e 20 x 2 0 000000e 00 lt x 2 lt 1 000000e 20 xL 3 2 500000e 01 lt cl 0 lt 1 000000e 20 c2 5 600000e 01 lt cl 1 lt 5 600000e 01 cl KNITRO 6 0 Locally optimal solution found objective 9 360000e 02 feasibility error 7 105427e 15 6 major iterations 7 function evaluations 19 4 The KNITRO callable library This section includes information on how to embed and call the KNITRO solver from inside a program KNITRO is written in C and C with a well documented application programming interface API defined in the file knitro h The KNITRO product contains example interfaces written in various programming languages under the directory examples These are briefly discussed in the following sections C in 4 2 C in 4 3 Java in 4 4 and Fortran in 4 5 Each example consists of a main driver program coded in the given language that defines an optimization problem and invokes KNITRO to solve it Examples also contain a makefile illustrating how to link the KNITRO library with the target language driver program In all languages KNITRO runs as a thread safe module which means that the calling program can create multiple instances of a KNITRO solver in different threads each instance solving a different problem This is useful in a multiprocessing environme
74. eters then pass a NULL pointer See Section 9 8 for more details Return Value The return value of KTR_solve KTR_mip_solve specifies the final exit code from the op timization process If the return value is zero KTR_RC_OPTIMAL or negative then KNITRO has finished solving In reverse communications mode the return value may be positive in which case it specifies a request for additional problem information after which the application should call KNITRO again A detailed description of the possible return values is given in the appendix Function KTR_restart int KTR_restart KTR_context ptr kc double x double lambda This function can be called to start another KTR_solve KTR mip_ solve sequence after mak ing small modifications The problem structure cannot be changed e g KTR init_problem KTR mip_init_problem cannot be called between KTR_solve KTRmip_solve and KTR_restart However user options can be modified and a new initial value can be passed with KTR_restart The sample program examples C restartExample c uses KTR_restart O to solve the same problem from the same start point but each time changing the interior point bar_murule option to a different value 4 2 Examples of calling in C The KNITRO distribution comes with several C language programs in the directory examples C The instructions in examples C README txt explain how to compile and run the examples This section overviews the cod
75. ever comes first newpoint KTR_PARAM_NEWPOINT Specifies additional action to take after every iteration in a solve of a continuous problem An iteration of KNITRO results in a new point that is closer to a solu tion The new point includes values of x and Lagrange multipliers lambda The newpoint fea ture in KNITRO is currently only available for continuous problems solved via KTR_solve O none 1 saveone 2 saveall 3 user Default value O KNITRO takes no additional action KNITRO writes x and lambda to the file knitro_newpoint log Previous contents of the file are overwritten KNITRO appends x and lambda to the file knitro_newpoint log Warning this option can generate a very large file All iterates including the start point crossover points and the final solution are saved Each iterate also prints the objective value at the new point except the initial start point If using callback mode see Section 9 8 and a user callback function is defined with KTR_set_newpoint_callback then KNITRO will invoke the callback function after every iteration If using reverse communications mode see Section 9 7 then KNITRO will return to the driver level after every iteration with KTR_solve returning the integer value defined by KTR_RC_NEWPOINT 6 objrange KTR_PARAM_OBJRANGE Specifies the extreme limits of the objective function for pur poses of determining unboundedness If the magnitude of the o
76. ewton method by setting algorithm 1 and will be very similar to the classical Levenberg Marquardt method when algorithm 2 For a discussion of these methods see for example 10 10 5 Complementarity constraints MPCCs A mathematical program with complementarity or equilibrium constraints also know as an MPCC or MPEC is an optimization problem which contains a particular type of constraint referred to as a complementarity constraint A complementarity constraint is a constraint which enforces that two variables are complementary to each other The variables x and x2 are complementary if the following conditions hold T X T2 0 z gt 0 LQ gt 0 10 35 The condition above is sometimes expressed more compactly as 0 lt T L T2 gt 0 One could also have more generally that a particular constraint is complementary to another con straint or a constraint is complementary to a variable However by adding slack variables a com plementarity constraint can always be expressed as two variables complementary to each other and KNITRO requires that you express complementarity constraints in this form For example if you have two constraints c 1 and c2 x which are complementary cil x e2 z 0 c gt 20 a x 2 0 you can re write this as two equality constraints and two complementary variables s and s2 as follows si 2 10 36 s2 C x 10 37 S1 X S2 0 s gt 0 S2 2 0 10 38 76 Intuitively
77. f variables The option is invoked by choosing user option gradopt 3 see Section 5 The centered finite difference approximation is often more accurate than the forward finite difference approxima tion however it is more expensive to compute if the cost of evaluating a function is high Gradient Checks If the user supplies a routine for computing exact gradients KNITRO can easily check them against finite difference gradient approximations To do this modify your application and replace the call to KTR_solve KTR_mip_solve with KTR_check_first_ders then run the application KNITRO will call the user routine for exact gradients compute finite difference approximations and print any differences that exceed a given threshold KNITRO also checks that the sparse constraint Jacobian has all nonzero elements defined The check can be made with forward or centered differences A sample driver is provided in examples C checkDersExample c Small differences between exact and finite difference approximations are to be expected see comments in examples C checkDersExample c It is best to check the gradient at different points and to avoid points where partial derivatives happen to equal zero 9 2 Second derivative options The default version of KNITRO assumes that the application can provide exact second derivatives to compute the Hessian of the Lagrangian function If the application is able to do so and the cost of computing the second deriva
78. fying optimality to 199 A feasible approximate solution was found to 299 The code terminated at an infeasible point The problem was determined to be unbounded to 499 The code terminated because it reached a pre defined limit to 599 The code terminated with an input error or some non standard error A more detailed description of individual return codes and their corresponding termination mes sages is provided below 0 100 101 102 KTR_RC_OPTIMAL Locally optimal solution found KNITRO found a locally optimal point which satisfies the stopping criterion see Section 6 for more detail on how this is defined If the problem is convex for example a linear program then this point corresponds to a globally optimal solution KTR_RC_NEAR_OPT Primal feasible solution estimate cannot be improved It appears to be optimal but desired accuracy in dual feasibility could not be achieved No more progress can be made but the stopping tests are close to being satisfied within a factor of 100 and so the current approximate solution is believed to be optimal KTR_RC_FEAS_XTOL Primal feasible solution terminate because the relative change in solution estimate lt xtol Decrease xtol to try for more accuracy The optimization terminated because the relative change in the solution estimate is less than that specified by the parameter xtol To try to get more accuracy one may decrease xtol If xtol is ver
79. imation A smaller value may give a less accurate but faster Hessian approximation When using the limited memory BFGS approach it is recommended to experiment with different values of this parameter In general the limited memory BFGS option requires more iterations to converge than the dense quasi Newton BFGS approach but will be much more efficient on large scale problems The limited memory quasi Newton option is chosen by setting user option hessopt 6 69 9 3 Feasibility options KNITRO offers an option bar_feasible that can force iterates to stay feasible with respect to in equality constraints or can place special emphasis on trying to get feasible If bar feasible 1 or bar_feasible 3 KNITRO satisfies inequalities by switching to a feasible mode of operation which alters the manner in which iterates are computed The option does not enforce feasibility with respect to equality constraints as this would impact performance too much The theory behind feasible mode is described in 5 The initial point must satisfy inequalities to a sufficient degree if not KNITRO may generate infeasible iterates and does not switch to the feasible mode until a sufficiently feasible point is found We say sufficient satisfaction occurs at a point x if it is true for all inequalities that cl tol lt c x lt cu tol 9 33 The constant tol gt 0 is determined by the option bar_feasmodetol its default value is 1 0e 4 Feasible mode becomes
80. ing language identifiers such as KTR_PARAM_ALG In AMPL parameters are set using only the lowercase text names as specified in Section 3 2 3 1 Example Optimization Problem This section provides an example AMPL model and AMPL session which calls KNITRO to solve the problem minimize 1000 x 225 23 Xa 2123 3 2a subject to 82 14xa 7x3 56 0 3 2b 27 23 23 25 gt 0 3 2c T1 T2 T3 gt 0 3 2d with initial point x x1 2 3 2 2 2 The AMPL model for the above problem is provided with KNITRO in a file called testproblem mod which is shown below 10 AMPL test program file testproblem mod Example problem formulated as an AMPL model used to demonstate using KNITRO with AMPL The problem has two local solutions the point 0 0 8 with objective 936 0 and the point 7 0 0 with objective 951 0 HH H H HH Define variables and enforce that they be non negative var x j in 1 3 gt 0 Objective function to be minimized minimize obj 1000 x 1 72 2 x 2 2 x 3 2 x 1 x 2 x 1 x x 3 Equality constraint s t c1 8 x 1 14 x 2 7 x 3 56 0 Inequality constraint s t c2 x 1 72 x 2 2 x 3 72 25 gt 0 data Define initial point let x 1 2 let x 2 let x 3 ou N N The above example displays the ease with which an optimization problem can be expressed in the AMPL modeling language Below is the AMPL session used
81. ing of driver programs but the working examples provide more complete detail Consider the following nonlinear optimization problem from the Hock and Schittkowski test set 9 minimize 100 22 2 1 1 21 4 6a subject to 1 lt 222 4 6b 0 lt ri z 4 6c z lt 0 5 4 6d This problem is coded as examples C problemHS15 c Every driver starts by allocating a new KNITRO solver instance and checking that it succeeded KTR_new might return NULL if the Ziena license check fails include knitro h 27 Include other headers define main KTR_context kc Declare other local variables CREATE A NEW KNITRO SOLVER INSTANCE kc KTR_new if ke NULL printf Failed to find a Ziena license n return 1 The next task is to load the problem definition into the solver using KTR_init_problem The problem has 2 unknowns and 2 constraints and it is easily seen that all first and second partial derivatives are generally nonzero The code below captures the problem definition and passes it to KNITRO DEFINE PROBLEM SIZES n 2 m 2 nnzJ 4 nnzH 3 allocate memory for xLoBnds xUpBnds etc DEFINE THE OBJECTIVE FUNCTION AND VARIABLE BOUNDS objType KTR_OBJTYPE_GENERAL objGoal KTR_OBJGOAL_MINIMIZE xLoBnds 0 KTR_INFBOUND xLoBnds 1 KTR_INFBOUND xUpBnds 0 0 5 xUpBnds 1 KTR_INFBOUND DEFINE TH
82. ints in the file knitro_mspoints log to cluster around more widely separated points This option has no effect unless ms_enable yes and ms_num_to_save is positive Default value 1 0e 6 ms_startptrange KTR_PARAM_MSSTARTPTRANGE Specifies the maximum range that each variable can take when determining new start points If a variable has upper and lower bounds and the difference between them is less than ms_startptrange then new start point values for the variable can be any number between its upper and lower bounds If the variable is unbounded in one or both directions or the difference between bounds is greater than the minimum of ms_startptrange and ms_maxbndrange then new start point values are restricted by the option If x is such a variable then all initial values satisfy max b z Tt lt a lt min bY x 7 T min ms_startptrange 2 ms maxbndrange 2 where x is the initial value of x provided by the user and bP and bY are the variable bounds possibly infinite on x This option has no effect unless ms_enable yes Default value 1 0e20 50 ms_terminate KTR_PARAM_MSTERMINATE Specifies the condition for terminating multi start This option has no effect unless ms_enable yes O 1 Default value O Terminate after ms_maxsolves Terminate after the first local optimal solution is found or ms_maxsolves whichever comes first Terminate after the first feasible solution estimate is found or ms_maxsolves which
83. ite difference Hessian vector product option If the problem is large and gradient evaluations are not a dominant cost then KNITRO can internally compute Hessian vector products using finite differences Each Hessian vector product in this case requires one additional gradient evaluation This option is chosen by setting user option hessopt 4 The option is only recommended if the exact gradients are provided NOTE This option may not be used when algorithm 1 Exact Hessian vector products In some cases the application may prefer to provide exact Hessian vector products but not the full Hessian for instance if the problem has a large dense Hessian The application must provide a routine which given a vector v stored in hessVector computes the Hessian vector product Hv and returns the result in hessVector This option is chosen by setting user option hessopt 5 NOTE This option may not be used when algorithm 1 Limited memory Quasi Newton BFGS The limited memory quasi Newton BFGS option is similar to the dense quasi Newton BFGS option described above However it is better suited for large scale problems since instead of storing a dense Hessian approximation it stores only a limited number of gradient vectors used to approximate the Hessian The number of gradient vectors used to approximate the Hessian is controlled by user option lmsize A larger value of Imsize may result in a more accurate but also more expensive Hessian approx
84. ith the AMPL modeling language AMPL is a popular modeling language for optimization which allows users to represent their opti mization problems in a user friendly readable intuitive format This makes the job of formulating and modeling a problem much simpler For a description of AMPL see 7 or visit the AMPL web site at http www ampl com It is straightforward to use KNITRO with the AMPL modeling language We assume in the follow ing that the user has successfully installed AMPL The KNITRO AMPL executable file knitroampl must be in the current directory where AMPL is started or in a directory included in the PATH environment variable such as a bin directory Inside of AMPL to invoke the KNITRO solver type ampl option solver knitroampl at the prompt To specify user options type for example ampl option knitro_options maxit 100 alg 2 The above command sets the maximum number of allowable iterations to 100 and chooses the Interior CG algorithm described in Section 8 When specifying multiple options all options must be set with one knitro_options command as shown in the example above If multiple knitro_options commands are specified in an AMPL session only the last one will be read See Section 3 2 for a summary of user specifiable options available in KNITRO for use with AMPL For more detail on these options see Section 5 Note that in Section 5 user parameters are defined by text names such as alg and by programm
85. ix for a list of possible termination messages and a description of their meaning and the corresponding value returned by KTR_mip_solve Display of Final Statistics Following the termination message a summary of some final statistics on the run are printed 63 Final Statistics for MIP 6 00975890892825e 00 0 00e 00 0 00e 00 0 00 Final objective value Final integrality gap abs rel of nodes processed 5 of subproblems solved 6 Total program time secs 0 09930 0 099 CPU time 0 00117 Time spent in evaluations secs Display of Solution Vector and Constraints If outlev equals 5 or 6 the values of the solution vector are printed after the final statistics Solution Vector x 0 1 30097589089e 00 x 1 0 00000000000e 00 x 2 1 00000000000e 00 x 3 0 00000000000e 00 binary variable x 4 1 00000000000e 00 binary variable x 5 0 00000000000e 00 binary variable KNITRO can produce additional information which may be useful in debugging or analyzing MIP performance If outlev is positive and mip_debug 1 then the file named kdbg_mip log is created which contains detailed information on the MIP performance In addition if mip_outsub 1 this file will contain extensive output for each subproblem solve in the MIP solution process The information produced by mip_debug is primarily intended for developers and should not be used in a production setting 7 3 Accessing solution inform
86. lt value 0 mip_rounding KTR_PARAM_MIP_ROUNDING Specifies the MIP rounding rule to apply 0 auto Let KNITRO choose the rounding rule 1 none Do not round if a node is infeasible 2 heur_only Round using a fast heuristic only 3 nlp_sometimes Round and solve a subproblem if likely to succeed 48 4 nlp_always Always round and solve a subproblem Default value 0 mip selectrule KTR_PARAM MIP_SELECTRULE Specifies the MIP select rule for choosing the next node in the branch and bound tree O auto Let KNITRO choose the node selection rule 1 depth first Search the tree using a depth first procedure 2 best_bound Select the node with the best relaxation bound 3 combo_1 Use depth first unless pruned then best bound Default value O mip_strong_candlim KTR_PARAM_MIP_STRONG_CANDLIM Specifies the maximum number of can didates to explore for MIP strong branching Default value 10 mip_strong_level KTR_PARAM_MIP_STRONG_LEVEL Specifies the maximum number of tree levels on which to perform MIP strong branching Default value 10 mip_strong_maxit KTR_PARAM_MIP_STRONG_MAXIT Specifies the maximum number of iterations to allow for MIP strong branching solves Default value 1000 mip_terminate KTR_PARAM_MIP_TERMINATE Specifies conditions for terminating the MIP algo rithm O optimal Terminate at optimum see Section 6 for more information 1 feasible Terminate at first integer feasible poin
87. lues see Section 5 for the default user option settings If nothing is listed in this section then it must be that all user options are set to their default values Lastly KNITRO prints messages that describe how it resolved user options that were set to AUTOMATIC values For example if option mip_branchrule auto then KNITRO prints the branching rule that it chooses Commercial Ziena License KNITRO 6 0 0 Ziena Optimization Inc website www ziena com email info ziena com mip_method 1 mip_outinterval 1 KNITRO changing mip_rootalg from AUTO to 1 KNITRO changing mip_lpalg from AUTO to 3 KNITRO changing mip_branchrule from AUTO to 2 61 KNITRO changing mip_selectrule from AUTO to 2 KNITRO changing mip_rounding from AUTO to 3 KNITRO changing mip_heuristic from AUTO to 1 KNITRO changing mip_pseudoinit from AUTO to 1 In the example above it is indicated that we are using mip_method 1 which is the standard branch and bound method see Section 5 and that we are printing output information at every node since mip_outinterval 1 It then determined seven other options related to the MIP method Display of Problem Characteristics KNITRO next prints a summary description of the problem characteristics including the number and type of variables and constraints and the number of nonzero elements in the Jacobian matrix and Hessian matrix if providing the exact Hessian If no initial point is provided by the user KNITRO indicate
88. m 1 1 has been solved to the desired accuracy The Interior Direct method computes new iterates by solving the primal dual KKT matrix using direct linear algebra The method may temporarily switch to the Interior CG algorithm if it encounters difficulties Interior CG algorithm This method is similar to the Interior Direct algorithm except the primal dual KKT system is solved using a projected conjugate gradient iteration This approach differs from most interior point methods proposed in the literature A projection matrix is factorized and conjugate gradient applied to approximately minimize a quadratic model of the barrier problem The use of conjugate gradient on large scale problems allows KNITRO to utilize exact second derivatives without forming the Hessian matrix Active Set algorithm Active set methods solve a sequence of subproblems based on a quadratic model of the original problem In contrast with interior point methods the algorithm seeks active inequalities and follows a more exterior path to the solution KNITRO implements a sequential linear quadratic programming SLQP algorithm similar in nature to a sequential quadratic programming method but using linear programming subproblems to estimate the active set This method may be preferable to interior point algorithms when a good initial point can be provided for example when solving a sequence of related problems KNITRO can also crossover from an interior point method and
89. model for testing KNITRO with AMPL To activate KNITRO for your computer you will need a valid Ziena license file If you purchased a floating network license then refer to the Ziena License Manager User s Manual For a stand alone license open a DOS like command window click Start Run and then type cmd Change to the directory where you unzipped the distribution and type get_machine_ID exe a program supplied with the distribution This will generate a machine ID five pairs of hexadecimal digits Email the machine ID to info ziena com Ziena will then send a license file containing the encrypted license text string Ziena supports a variety of ways to install licenses The simplest procedure is to copy each license into a file whose name begins with the characters ziena_lic Then place the file in the folder C Program Files Ziena For more installation options and general troubleshooting read the Ziena License Manager User s Manual 2 2 Unix Linux Mac OS X KNITRO is supported on Linux 32 bit and 64 bit all distributions and Mac OS X 32 bit x86 on Mac OS X 10 4 or higher The KNITRO software package for Unix is delivered as a gzipped tar file Save this file in a fresh subdirectory on your system To unpack type the commands gunzip knitro 6 x platformname tar gz tar xvf knitro 6 x platformname tar Unpacking will create a directory named knitro 6 x z or knitroampl 6 x z for the KNITRO AMPL solver product Conte
90. more details see Section 9 8 callback mode and Section 9 7 reverse communication mode Both modes use KTR_solve or KTR mip_solve for MIP solves Functions KTR_solve and KTR_mip_solve Functions KTR_solve and KTR_mip_solve have the same parameter list for convenience we just show KTR_solve below KTR_solve should be used for models where all the variables are continuous while KTR_mip_solve should be used for models with one or more binary or integer variables int KTR solvel KTR_context_ptr kc input double x output double lambda output int evalStatus input reverse comm only double obj input and output double c input reverse comm only double objGrad input reverse comm only double jac input reverse comm only double hess input reverse comm only double hessVector input output rev comm void userParams input callback only Arguments KTR_context_ptr kc is the KNITRO context pointer Do not modify its contents 25 double x is an array of length n output by KNITRO If KTR_solve returns KTR_RC_OPTIMAL zero then x contains the solution Reverse communications mode upon return x contains the value of unknowns at which KNITRO needs more problem information For continuous problems if user op tion newpoint is set to KTR_NEWPOINT_USER see Section 5 1 and KTR_solve returns KTR_RC_NEWPOINT then x contains a newly accepted iter
91. ms a scaling of the objective and constraint functions based on their values at the initial point If scaling is performed all internal computations including the stopping tests are based on the scaled values 52 0 no No scaling is performed 1 yes KNITRO is allowed to scale the objective function and constraints Default value 1 soc KTR_PARAM_SOC Specifies whether or not to try second order corrections SOC A second order correction may be beneficial for problems with highly nonlinear constraints O no No second order correction steps are attempted 1 maybe Second order correction steps may be attempted on some iterations 2 yes Second order correction steps are always attempted if the original step is rejected and there are nonlinear constraints Default value 1 xtol KTR_PARAM_XTOL The optimization process will terminate if the relative change in all com ponents of the solution point estimate is less than xtol If using the Interior Direct or Inte rior CG algorithm and the barrier parameter is still large KNITRO will first try decreasing the barrier parameter before terminating Default value 1 0e 15 5 2 The KNITRO options file The KNITRO options file allows the user to easily change user options by editing a text file instead of modifying application code Note that the AMPL interface to KNITRO cannot read such a file Other modeling environments may be able to read an options file please che
92. n First derivatives in the C language API are denoted by objGrad and jac where objGrad V f x and jac is the m x n Jacobian matrix of constraint gradients such that the i th row equals Vc x The Hessian of the Lagrangian is a matrix constructed from the individual second derivative matrices of the objective and constraint functions H z X V f x y AV c z 4 5 i 0 and is denoted by hess in the C language API Here X is the vector of Lagrange multipliers dual variables See Section 4 7 for further details on constructing the Jacobian and Hessian matrix in sparse form The ability to provide exact first derivatives is essential for efficient and reliable performance Packages like ADOL C and ADIFOR can help in generating code with derivatives If the user is unable or unwilling to provide exact first derivatives KNITRO provides an option that computes approximate first derivatives using finite differencing see Sections 4 9 and 9 1 Exact second derivatives are less important as KNITRO provides several options that substitute quasi Newton approximations for the Hessian see Section 9 2 However the ability to provide exact second derivatives often dramatically improves the performance of KNITRO Functions KTR_nit_problem and KTR_mip_init_problem int KTR_init_problem KTR_context_ptr kc int n int objGoal int objType double xLoBnds double xUpBnds int m int cType double cLoBnds double cUpBnds int
93. n calls The functions for setting user options have the form int KTR_set_int_param KTR_context kc int param_id int value for setting integer valued parameters or int KTR_set_double_param KTR_context kc int param_id double value for setting double precision valued parameters For example to specify the Interior CG algorithm and a tight optimality stop tolerance status KTR_set_int_param kc KTR_PARAM_ALG KTR_ALG_BAR_CG status KTR_set_double_param kc KTR_PARAM_OPTTOL 1 0e 8 NOTE User parameters cannot be set after beginning the optimization process i e after mak ing the first call to KTR_solve KTR mip_solve Some options cannot be set after calling KTR_init_problem KTR_mip_init_problem 5 4 Loading dynamic libraries Some user options instruct KNITRO to load dynamic libraries at runtime This will not work unless the executable can find the desired library using the operating system s load path Usually this is done by appending the path to the directory that contains the library to an environment variable For example suppose the library to be loaded is in the KNITRO lib directory The instructions below will correctly modify the load path On Windows type assuming KNITRO 6 0 0 is installed at its default location gt set PATH PATHY C Program Files Ziena knitro 6 0 0 z lib On Mac OS X type assuming KNITRO 6 0 0 is installed at tmp gt export DYLD LIBRARY PATH DYLD LIBRARY PATH tmp knitro
94. n convex QPs 10 3 Systems of Nonlinear Equations KNITRO is effective at solving systems of nonlinear equations To solve a square system of nonlinear equations using KNITRO one should specify the nonlinear equations as equality constraints i e c c in 1 1b and specify the objective function 1 1a as zero i e f x 0 If KNITRO is converging to a stationary point for which the nonlinear equations are not satisfied the multi start option described in Section 9 6 may help in finding a solution by trying different starting points 10 4 Least Squares Problems There are two ways of using KNITRO for solving problems in which the objective function is a sum of squares of the form f x 7 2 r z If the value of the objective function at the solution is not close to zero the large residual case the least squares structure of f can be ignored and the problem can be solved as any other optimization problem Any of the KNITRO options can be used 75 On the other hand if the optimal objective function value is expected to be small small residual case then KNITRO can implement the Gauss Newton or Levenberg Marquardt methods which only require first derivatives of the residual functions r 1 and yet converge rapidly To do so the user need only define the Hessian of f to be where the Gauss Newton and Levenberg Marquardt approaches consist of ignoring the last term in the Hessian KNITRO will behave like a Gauss N
95. ng any locally optimal or feasible solution estimate of a nonconvex problem and terminate as soon as one such point is found The ms_terminate option provides the user more control over when to terminate the multi start procedure If ms_terminate optimal the multi start procedure will stop as soon as the first locally optimal solution is found or after ms_maxsolves whichever comes first If ms_terminate feasible the multi start procedure will instead stop as soon as the first feasible solution estimate is found or after ms_maxsolves whichever comes first If ms_terminate maxsolves it will only terminate after ms_maxsolves In most cases the user would like to obtain the global optimum to 1 1 that is the local optimum with the very best objective function value KNITRO cannot guarantee that multi start will find the global optimum In general the global optimum can only be found with special knowledge of the objective and constraint functions for example the functions may need to be bounded by other piece wise convex functions KNITRO executes with very little information about functional form Although no guarantee can be made the probability of finding a better local solution improves if more start points are tried See Section 10 6 for more discussion 9 7 Reverse communication mode for invoking KNITRO The reverse communication mode of KNITRO returns control to the user at the driver level whenever a function gradient or Hessian eval
96. nnzJ int jacIndexVars int jacIndexCons int nnzH int hessIndexRows int hessIndexCols double xInitial double lambdalnitial 21 int KTR_mip_init_problem KTR_context_ptr kc int int int int int n objGoal objType objFnType xType double xLoBnds double xUpBnds int int int m cType cFnType double cLoBnds double cUpBnds int int int int int int nnzJ jacIndexVars jacIndexCons nnzH hessIndexRows hessIndexCols double xInitial double lambdalnitial These functions pass the optimization problem definition to KNITRO where it is copied and stored internally until KTR_free is called Once initialized the problem may be solved any number of times with different user options or initial points see the KTR_restart call below Array arguments passed to KTR_init_problem or KTR_mip_init_problem are not referenced again and may be freed or reused if desired In the description below some programming macros are mentioned as alternatives to fixed numeric constants e g KTR_OBJGOAL_MINIMIZE These macros are defined in knitro h Arguments KTR_context_ptr kc is the KNITRO context pointer Do not modify its contents int n is a scalar specifying the number of variables in the problem i e the length of x in 4 4 int objGoal is the optimization goal 0 if the goal is to minimize the objective function KTR_OBJGOAL_MINIMIZE
97. nt for instance in a web application server 4 1 KNITRO in a C application The KNITRO callable library is typically used to solve an optimization problem through a sequence of four basic function calls e KTR_new create a new KNITRO solver context pointer allocating resources e KTR_init_problem or KTR mip init problem load the problem definition into the KNI TRO solver e KTR_solve or KTR_mip solve solve the problem e KTR_free delete the KNITRO context pointer releasing allocated resources The functions KTR_init_problem and KTR_solve are used for continuous optimization models while KTRmip_init_problem and KTR_mip_solve are for optimization models with one or more integer variables The complete C language API is defined in the file knitro h provided in the installation under the include directory Functions for setting and getting user options are described in Sections 5 2 and 5 3 Functions for retrieving KNITRO results are described in Section 7 3 and illustrated in the examples C files The remainder of this section describes in detail the four basic function calls KTR_context_ptr KTR_new void This function must be called first It returns a pointer to an object the KNITRO context pointer that is used in all other calls Tf you enable KNITRO with the Ziena floating network license handler then this call also checks out a license and reserves it until KTR_free is called with the context pointer
98. ntents to a new folder For the exe file double click on it and follow the instructions The self extracting executable creates start menu shortcuts and an uninstall entry in Add Remove Programs otherwise the two install methods are identical The default installation location for KNITRO is assuming your HOMEDRIVE is C C Program Files Ziena Unpacking will create a folder named knitro 6 x z or knitroampl 6 x z for the KNITRO AMPL solver product Contents of the full product distribution are the following INSTALL txt A file containing installation instructions LICENSE_KNITRO txt A file containing the KNITRO license agreement README txt A file with instructions on how to get started using KNITRO KNITRO60 ReleaseNotes txt A file containing release notes get_machine_ID exe An executable that identifies the machine ID required for obtaining a Ziena license file doc A folder containing KNITRO documentation including this manual include A folder containing the KNITRO header file knitro h lib A folder containing the KNITRO library and object files knitro_objlib a knitro lib and knitro dll examples A folder containing examples of how to use the KNITRO API in different programming languages C C Fortran Java The examples C folder contains the most extensive set see examples C README txt for details knitroampl A folder containing knitroampl exe the KNITRO solver for AMPL in structions and an example
99. nts of the full product distribution are the following INSTALL A file containing installation instructions LICENSE_KNITRO A file containing the KNITRO license agreement README A file with instructions on how to get started using KNITRO KNITRO60 ReleaseNotes A file containing release notes get_machine_ID An executable that identifies the machine ID required for obtaining a Ziena license file doc A directory containing KNITRO documentation including this manual include A directory containing the KNITRO header file knitro h lib A directory containing the KNITRO library files libknitro a and libknitro so examples A directory containing examples of how to use the KNITRO API in dif ferent programming languages C C Fortran Java The examples C directory contains the most extensive set see examples C README txt for details knitroampl A directory containing knitroampl the KNITRO solver for AMPL instruc tions and an example model for testing KNITRO with AMPL To activate KNITRO for your computer you will need a valid Ziena license file If you purchased a floating network license then refer to the Ziena License Manager User s Manual For a stand alone license execute get_machine_ID a program supplied with the distribution This will generate a machine ID five pairs of hexadecimal digits Email the machine ID to info ziena com Ziena will then send a license file containing the encrypted license text string
100. o and therefore requires no conversion from the Fortran convention of numbering from one The C wrappers provided are sufficient for the simple example but do not implement all the functionality of the KNITRO callable library Users are free to write their own C wrapper routines or extend the example wrappers as needed 33 4 6 Compiler Specifications Listed below are the C C compilers used to build KNITRO and the Java and Fortran compilers used to test programmatic interfaces It is usually not difficult for Ziena to compile KNITRO in a different environment for example it is routinely recompiled to specific versions of gcc on Linux Contact Ziena if your application requires special compilation of KNITRO Windows 32 bit x86 C C Microsoft Visual Studio C 7 1 NET 2003 Framework 1 1 Microsoft Visual Studio C 6 0 Java 1 5 0_12 from Sun Fortran Intel Visual Fortran 9 0 Windows 64 bit x86_64 C C Microsoft Visual Studio C 8 0 NET 2005 Framework 2 0 Java 1 5 0_10 from Sun Fortran Intel Visual Fortran 9 1 Linux 32 bit x86 64 bit x86_64 C C gec g compiler version to match the Linux distribution Java 1 5 0_06 from Sun Fortran 877 895 Mac OS X 32 bit x86 C C gec g 4 0 1 XCode 2 4 1 Java 1 5 0_06 4 7 Specifying the Jacobian and Hessian matrices An important issue in using the KNITRO callable library is the ability of the application to specify the Jacobian matrix of the constraints an
101. objective function appears to be decreasing without bound while satisfying the con straints If the problem really is bounded increase the size of the parameter objrange to avoid terminating with this message KTR_RC_ITER_LIMIT Iteration limit reached The iteration limit was reached before being able to satisfy the required stopping criteria The iteration limit can be increased through the user option maxit See Section 5 1 83 401 KTR_RC_TIME_LIMIT Time limit reached The time limit was reached before being able to satisfy the required stopping criteria The time limit can be increased through the user options maxtime_cpu and maxtime_real See Section 5 1 403 KTR_RC_MIP_EXH All nodes have been explored The MIP optimality gap has not been reduced below the specified threshold but there are no more nodes to explore in the branch and bound tree If the problem is convex this could occur if the gap tolerance is difficult to meet because of bad scaling or roundoff errors or there was a failure at one or more of the subproblem nodes This might also occur if the problem is nonconvex In this case KNITRO terminates and returns the best integer feasible point found 404 KTR_RC_MIP_FEAS_TERM Terminating at first integer feasible point KNITRO has found an integer feasible point and is terminating because the user option mip_terminate feasible See Section 5 1 405 KTR_RC_MIP_SOLVE_LIMIT Subproblem solve limit re
102. on allows many types of constraints including equalities if c c fixed variables if b bY and both single and double sided inequality constraints or bounded variables Complementarity constraints may also be included see Section 10 5 KNITRO assumes that the functions f x and c x are smooth although problems with derivative discontinuities can often be solved successfully KNITRO implements three state of the art interior point and active set methods for solving con tinuous nonlinear optimization problems Each algorithm possesses strong convergence properties and is coded for maximum efficiency and robustness However the algorithms have fundamental differences that lead to different behavior on nonlinear optimization problems Together the three methods provide a suite of different ways to attack difficult problems We encourage the user to try all algorithmic options to determine which one is more suitable for the application at hand For guidance on choosing the best algorithm see Section 8 Interior Direct algorithm Interior point methods also known as barrier methods replace the nonlin ear programming problem by a series of barrier subproblems controlled by a barrier param eter u Trust regions and a merit function are used to promote convergence Interior point methods perform one or more minimization steps on each barrier subproblem then decrease the barrier parameter and repeat the process until the original proble
103. particular types of problems 10 1 Linear programming problems LPs A linear program LP is an optimization problem where the objective function and all the constraint functions are linear KNITRO has built in specializations for efficiently solving LPs However KNITRO is unable to automatically detect whether or not a problem is an LP In order for KNITRO to detect that a problem is an LP you must specify this by setting the value of objType to KTR_OBJTYPE_LINEAR and all values of the array cType to KTR_CONTYPE_LINEAR in the function call to KTR_init_problem see Section 4 If this is not done KNITRO will not apply special treatment to the LP and will typically be less efficient in solving the LP 10 2 Quadratic programming problems QPs A quadratic program QP is an optimization problem where the objective function is quadratic and all the constraint functions are linear KNITRO has built in specializations for efficiently solving QPs However KNITRO is unable to automatically detect whether or not a problem is a QP In order for KNITRO to detect that a problem is a QP you must specify this by setting the value of objType to KTR_OBJTYPE_QUADRATIC and all values of the array cType to KTR_CONTYPE_LINEAR in the function call to KTR_init_problem see Section 4 If this is not done KNITRO will not apply special treatment to the QP and will typically be less efficient in solving the QP Typically these specialization will only help o
104. performance If outlev is positive and debug 2 then KNITRO prints information useful for debugging program execution The information produced by debug is primarily intended for developers and should not be used in a production setting Users can generate a file containing iterates and or solution points with option newpoint The output file is called knitro_newpoint txt See Section 5 for details 7 2 Understanding KNITRO output for discrete problems If outlev 0 then all printing of output is suppressed If outlev is positive then KNITRO prints infor mation about the solution of your optimization problem either to standard output outmode screen to a file named knitro log outmode file or to both outmode both The option outdir con trols the directory where output files are created if any are and the option outappend controls whether output is appended to existing files When outlev is positive the options mip_outlevel mip_debug mip_outinterval and mip_outsub control the amount and type of MIP output generated as described below See Section 5 for more details This section describes KNITRO outputs at various levels for discrete or mixed integer problems We examine the output that results from running examples C callbackMINLP_static to solve prob lemMINLP c KNITRO first prints the banner displaying the Ziena license type and version of KNITRO that is installed It then lists all user options which are different from their default va
105. pplications should provide partial first derivatives whenever possible to make KNITRO more effi cient and more robust If first derivatives cannot be supplied then the application should instruct KNITRO to calculate finite difference approximations as described in Section 9 1 Even though the application does not evaluate derivatives it must still provide a sparsity pattern for the constraint Jacobian matrix that specifies which partial derivatives are nonzero KNITRO uses the sparsity pattern to speed up linear algebra computations If the sparsity pattern is unknown then the application should specify a fully dense pattern i e assume all partial derivatives are nonzero The code fragment below demonstrates how to define a problem with no derivatives and unknown sparsity pattern The code is in the C language define variables call KTR_new etc DEFINE PROBLEM SIZES NOTHING IS KNOWN ABOUT THE DERIVATIVES SD ASSUME THE JACOBIAN IS DENSE THIS EXAMPLE HAS 20 VARIABLES AND 10 CONSTRAINTS NO HESSIAN IS SUPPLIED SO SET nnzH TO ZERO n 20 m 10 nnzJ n m nnzH 0 define objType xLoBnds xUpBnds cType cLoBnds cUpBnds etc note that cType is especially useful if constraints are linear DEFINE FIRST DERIVATIVE SPARSITY PATTERN NOTHING IS KNOWN ABOUT THE DERIVATIVES SO DEFINE THE JACOBIAN MATRIX TO BE DENSE k 0 for i 0 i lt n i for j 0 j
106. r lower bounded as indicated n 6 21 6 24 If the constraint or variable has both a finite lower and upper bound then the appropriate sign of the multiplier depends on which bound if either is binding active at the solution In KNITRO we define the feasibility error FeasErr at a point x to be the maximum violation of the constraints 6 19 6 20 i e FeasErr a ae ch eslar e x c 05 _ z as _ b7 6 25 while the optimality error OptErr is defined as the maximum violation of the first three conditions 6 16 6 18 The remaining conditions on the sign of the multipliers 6 21 6 24 are enforced explicitly throughout the optimization In order to take into account problem scaling in the termi nation test the following scaling factors are defined 7 max 1 ch x e x eZ 05 _ z9 25 _ e 6 26 TZ max 1 Vf r o0 6 27 where x represents the initial point For unconstrained problems the scaling 6 27 is not effective since V f x 0 as a solution is approached Therefore for unconstrained problems only the following scaling is used in the termination test 72 max 1 min f x Vf x loo 6 28 in place of 6 27 55 KNITRO stops and declares Locally optimal solution found if the following stopping condi tions are satisfied FeasErr OptErr max 7 x feastol feastol_abs 6 29 lt lt max r2 opttol opttol_abs 6 30
107. r more details This section describes KNITRO outputs at various levels for continuous problems We examine the output that results from running examples C callback2 static to solve problemHS15 c Display of Nondefault Options KNITRO first prints the banner displaying the Ziena license type and version of KNITRO that is installed It then lists all user options which are different from their default values see Section 5 for the default user option settings If nothing is listed in this section then it must be that all user options are set to their default values Lastly KNITRO prints messages that describe how it resolved user options that were set to AUTOMATIC values For example if option algorithm auto then KNITRO prints the algorithm that it chooses Commercial Ziena License KNITRO 6 0 0 Ziena Optimization Inc website www ziena com email info ziena com outlev 6 KNITRO changing algorithm from AUTO to 1 KNITRO changing bar_murule from AUTO to 1 KNITRO changing bar_initpt from AUTO to 2 KNITRO changing bar_penaltyrule from AUTO to 1 KNITRO changing bar_penaltycons from AUTO to 1 In the example above it is indicated that we are using a more verbose output level outlev 6 instead of the default value outlev 2 KNITRO chose algorithm 1 Interior Direct and then deter mined four other options related to the algorithm Display of Problem Characteristics KNITRO next prints a summary description of the problem characteri
108. rect algorithm in KNITRO requires the explicit storage of a Hessian matrix this algorithm only works with Hessian options hessopt 1 2 3 or 6 see Section 9 2 It may not be used with Hessian options 4 or 5 which do not supply a full Hessian matrix The Interior Direct algorithm may be used with the bar_feasible option 8 3 Interior CG This algorithm is well suited to large problems because it avoids forming and factorizing the Hes sian matrix Interior CG is recommended if the Hessian is large and or dense It works with all Hessian options and with the bar_feasible option Choose this algorithm by setting user option algorithm 2 We encourage you to experiment with different values of the bar_murule option when using the Interior Direct or Interior CG algorithm It is difficult to predict which update rule will work best on a problem 8 4 Active Set This algorithm is fundamentally different from interior point methods The method is efficient and robust for small and medium scale problems but is typically less efficient than the Interior Direct and Interior CG algorithms on large scale problems many thousands of variables and constraints Active Set is recommended when warm starting i e when the user can provide a good initial solution estimate for example when solving a sequence of closely related problems This algorithm is also best at rapid detection of infeasible problems Choose this algorithm by setting user option
109. rted by KNITRO includes all complementarity constraints or switch off the AMPL presolver to be safe option presolve 0 3 4 Displaying AMPL Variables in KNITRO AMPL will often perform a reordering of the variables and constraints defined in the AMPL model The AMPL presolver may also simplify the form of the problem by eliminating certain variables or constraints The output printed by KNITRO corresponds to the reordered reformulated problem To view final variable and constraint values in the original AMPL model use the AMPL display command after KNITRO has completed solving the problem It is possible to correlate KNITRO variables and constraints with the original AMPL model You must type an extra command in the AMPL session option knitroampl_auxfiles rc and set KNITRO option presolve_dbg 2 Then the solver will print the variables and constraints that KNITRO receives with their upper and lower bounds and their AMPL model names The extra AMPL command causes the model names to be passed to the KNITRO AMPL solver The output below is obtained with the example file testproblem mod supplied with your distri bution The center column of variable and constraint names are those used by KNITRO while the names in the right hand column are from the AMPL model ampl model testproblem mod ampl option solver knitroampl ampl option knitroampl_auxfiles rc ampl option knitro_options presolve_dbg 2 outlev 0 KNITRO 6 0 pr
110. s for the constraints c x 4 4b and bounds on the variables x 4 4c The first m components of lambdalnitial are multipliers corresponding to the constraints specified in c x while the last n components are multipliers corresponding to the bounds on x If the application prefers to let KNITRO make an initial guess then pass a NULL pointer for lambdaInitial To solve the nonlinear optimization problem 4 4 KNITRO needs the application to supply information at various trial points KNITRO specifies a trial point with a new vector of variable values x and sometimes a corresponding vector of Lagrange multipliers A At a trial point KNITRO may ask the application to KTR_RC_EVALFC Evaluate f and cat x KTR_RC_EVALGA Evaluate Vf and Vc at zx KTR_RC_EVALH Evaluate the Hessian matrix of the problem at x and A KTR_RC_EVALHV Evaluate the Hessian matrix times a vector v at x and A The constants KTR_RC_ are return codes defined in knitro h The KNITRO C language API has two modes of operation for obtaining problem information callback and reverse communication With callback mode the application provides C lan guage function pointers that KNITRO may call to evaluate the functions gradients and Hessians With reverse communication the function KTR_solve or KTR mip_solve returns one of the constants listed above to tell the application what it needs and then waits to be called again with the new problem information For
111. s that it is computing one KNITRO also prints the results of any MIP preprocessing to detect special structure and indicates which MIP method it is using Problem Characteristics Objective goal Minimize Number of variables bounded below bounded above bounded below and above fixed free Number of binary variables Number of integer variables Number of constraints linear equalities nonlinear equalities linear inequalities nonlinear inequalities range Number of nonzeros in Jacobian ONPOODMDDOWODOADAODAD pa w Oo Number of nonzeros in Hessian No start point provided KNITRO computing one KNITRO detected 1 GUB constraints KNITRO derived O knapsack covers after examining 3 constraints KNITRO solving root node relaxation KNITRO MIP using Branch and Bound method Display of Node Information 62 Next if mip_outlevel 1 KNITRO prints columns of data reflecting detailed information about individual nodes during the solution process The frequency of this node information is controlled by the mip_outinterval parameter For example if mip_outinterval 100 this node information is printed only for every 100th node printing output less frequently may save significant CPU time in some cases In the example below mip_outinterval 1 so information about every node is printed Node Left Iinf Objective Best relaxatn Best incumbent 1 0 2 7 592845e 01 7 592845e 01 2 1 1 5 171320e 00 7 592845e 01 2 1 7 671320e
112. s unless the problem has some special structure or the person modeling the problem has some special knowledge about the geometry of the problem Even finding local solutions to large scale nonlinear nonconvex problems is quite challenging Although KNITRO is unable to guarantee convergence to global solutions it does provide a multi start heuristic which attempts to find multiple local solutions in the hopes of locating the global solution See Section 9 6 for information on trying to find the globally optimal solution using the KNITRO multi start feature 79 10 7 Mixed integer programming MIP KNITRO provides tools for solving optimization models both linear and nonlinear with binary or integer variables The KNITRO mixed integer programming MIP code offers two algorithms for mixed integer nonlinear programming MINLP The first is a nonlinear branch and bound method and the second implements the hybrid Quesada Grossman method for convex MINLP The KNITRO MINLP code is designed for convex mixed integer programming and is a heuristic for nonconvex problems The MIP code also handles mixed integer linear programs MILP of moderate size A MIP problem is defined and solved via the callable library interface using the API functions KTR_mip_init_problem and KTR mip_solve see Section 4 The KNITRO MIP tools do not currently handle special ordered sets SOS s or semi continuous variables Examples for solving a MINLP problem using the C
113. screte or mixed integer problems Algorithms for solving versions of 1 1 where one or more of the variables are restricted to take on only discrete values proceed by solving a sequence of continuous relaxations where the discrete variables are relaxed such that they can take on any continuous value The global solutions f xp of these relaxed problems provide a lower bound on the optimal objective value for problem 1 1 upper bound if maximizing If a feasible point is found for problem 1 1 that satisfies the discrete restrictions on the variables then this provides an upper bound on the optimal objective value of problem 1 1 lower bound if maximizing We will refer to these feasible points as incumbent points and denote the objective value at an incumbent point by f Assuming all the continuous subproblems have been solved to global optimality if the problem is convex all local solutions are global solutions an optimal solution of problem 1 1 is verified when the lower bound and upper bound are equal KNITRO declares optimality for a discrete problem when the gap between the best i e largest lower bound f xp and the best i e smallest upper bound f x7 is less than a threshold deter mined by the user options mip_integral_gap_abs and mip_integral_gap_rel Specifically KNITRO declares optimality when either f ar f xr lt mip_integral_gap_abs 6 31 56 or f xr f xp lt mip_integral_gap_abs x
114. se 0 O use KNITRO built in functions 1 use Intel Math Kernel Library functions 2 use the dynamic library specified with blasoptionlib debug enable debugging output 0 O no extra debugging 1 print info to debug solution of the problem 2 print info to debug execution of the solver delta initial trust region radius scaling 1 0e0 feastol feasibility termination tolerance relative 1 0e 6 feastol_abs feasibility termination tolerance absolute 0 0e 0 gradopt gradient computation method 1 1 use exact gradients 2 compute forward finite difference approximations 3 compute centered finite difference approximations hessopt Hessian Hessian vector computation method 1 1 use exact Hessian derivatives 2 use dense quasi Newton BFGS Hessian approximation 3 use dense quasi Newton SR1 Hessian approximation 4 compute Hessian vector products by finite diffs 5 compute exact Hessian vector products 6 use limited memory BFGS Hessian approximation honorbnds 0 allow bounds to be violated during the optimization 2 1 enforce bounds satisfaction of all iterates 2 enforce bounds satisfaction of initial point Imsize number of limited memory pairs stored in LBFGS approach 10 lpsolver 1 use internal LP solver in Active Set algorithm 1 2 use ILOG CPLEX LP solver in Active Set algorithm requires a valid CPLEX license specify library location with cplexlibname maxcgit maximum allowable conjugate gradient CG iterations 0 O
115. stics including the number and type of variables and constraints and the number of nonzero elements in the Jacobian matrix and Hessian matrix if providing the exact Hessian 58 Problem Characteristics Objective goal Minimize Number of variables bounded below bounded above bounded below and above fixed free Number of constraints linear equalities nonlinear equalities linear inequalities nonlinear inequalities range Number of nonzeros in Jacobian oPODNDOOODNDHrHOOHODMN Number of nonzeros in Hessian Display of Iteration Information Next if outlev is greater than 2 KNITRO prints columns of data reflecting detailed information about individual iterations during the solution process An iteration is defined as a step which generates a new solution estimate i e a successful step If outlev 2 summary data is printed every 10 iterations and on the final iteration If outlev 3 summary data is printed every iteration If outlev 4 the most verbose iteration information is printed every iteration Iter fCount Objective FeasError OptError Step CGits 0 1 9 090000e 02 3 000e 00 1 2 7 989784e 02 2 878e 00 9 096e 01 6 566e 02 0 2 3 4 232342e 02 2 554e 00 5 828e 01 2 356e 01 0 3 4 1 457686e 01 9 532e 01 3 088e 00 1 909e 00 0 4 9 1 235269e 02 7 860e 01 3 818e 00 7 601e 01 5 5 10 3 993788e 02 3 022e 02 1 795e 01 1 186e 00 0 6 11 3 924231e 02 2 924e 02 1 038e 01 1 856e 02 0 7 12 3 158787e 02 0 000e 00 6 905e 02 2
116. t Default value O ms_enable or multistart KTR_PARAM_MULTISTART Indicates whether KNITRO will solve from multiple start points to find a better local minimum See Section 9 6 for details 0 no KNITRO solves from a single initial point 1 yes KNITRO solves using multiple start points Default value O ms_maxbndrange KTR PARAM MSMAXBNDRANGE Specifies the maximum range that an unbounded variable can take when determining new start points If a variable is unbounded in one or both directions then new start point values are restricted by the option If x is such a variable then all initial values satisfy 0 max b z ms maxbndrange 2 lt x lt min bY x ms_maxbndrange 2 where x is the initial value of x provided by the user and b and b are the variable bounds possibly infinite on x This option has no effect unless ms_enable yes Default value 1000 0 ms_maxsolves KTR_PARAM_MSMAXSOLVES Specifies how many start points to try in multi start This option has no effect unless ms_enable yes 49 0 Let KNITRO automatically choose a value based on the problem size The value is min 200 10 N where N is the number of variables in the problem n Try n gt 0 start points Default value 0 ms_maxtime_cpu KTR_PARAM_MSMAXTIMECPU Specifies in seconds the maximum allowable CPU time before termination The limit applies to the operation of KNITRO since multi start began in contrast the value of maxtim
117. t algorithm for large scale nonlinear programming SIAM Journal on Optimization 9 4 877 900 1999 5 R H Byrd J Nocedal and R A Waltz Feasible interior methods using slacks for nonlinear optimization Computational Optimization and Applications 26 1 35 61 2003 6 R H Byrd J Nocedal and R A Waltz KNITRO An integrated package for nonlinear opti mization In G di Pillo and M Roma editors Large Scale Nonlinear Optimization pages 35 59 Springer 2006 x R Fourer D M Gay and B W Kernighan AMPL A Modeling Language for Mathematical Programming 2nd Ed Brooks Cole Thomson Learning 2003 80 8 Harwell Subroutine Library A catalogue of subroutines HSL 2002 AEA Technology Harwell Oxfordshire England 2002 9 Hock W and Schittkowski K Test Examples for Nonlinear Programming Codes volume 187 of Lecture Notes in Economics and Mathematical Systems Springer Verlag 1981 10 J Nocedal and S J Wright Numerical Optimization Springer Series in Operations Research Springer 1999 11 R A Waltz J L Morales J Nocedal and D Orban An interior algorithm for nonlinear optimization that combines line search and trust region steps Mathematical Programming A 107 3 391 408 2006 Appendix A Solution Status Codes The solution status return codes are organized as follows O 100 200 300 400 500 The final solution satisfies the termination conditions for veri
118. te a KNITRO solver instance and call Java methods that execute KNITRO functions The JNI form of KNITRO is thread safe which means that a Java application can create multiple instances of a KNITRO solver in different threads each instance solving a different problem This feature might be important in an application that is deployed on a web server To write a Java application take a look at the sample programs in examples Java The call sequence for using KNITRO is almost exactly the same as C applications that call knitro h functions with a KTR_context reference In Java an instance of the class KnitroJava takes the place of the context reference The sample programs compile by linking with the Java API class file delivered in the examples Java knitrojava jar archive This archive also contains the source code for KnitroJava Examine it directly to see the full set of methods supplied with the Java API not all methods are used in the sample programs To extract the source code type the command jar xf knitrojava jar and look for com ziena knitro KnitroJava java The sample programs closely mirror the structural form of the C reverse communications example described in Section 4 2 Refer to that section for more information See Section 4 7 for details on specifying the arrays of partial derivatives that KNITRO needs The KNITRO Java API is compiled with Java release 1 5 see Section 4 6 However the code does not make use of advanced 1
119. terminated because the relative change in the solution estimate is less than that specified by the parameter xtol To try to find a feasible point one may decrease xtol If xtol is very small already it is an indication that no more significant progress can be made It is recommended to try various initial points with the multi start feature described in Section 9 6 If this occurs for a variety of initial points it is likely the problem is infeasible KTR_RC_INFEAS_NO_IMPROVE Current infeasible solution estimate cannot be improved Problem may be badly scaled or perhaps infeasible If problem is believed to be feasible try multistart to search for feasible points No further progress can be made It is recommended to try various initial points with the multi start feature described in Section 9 6 If this occurs for a variety of initial points it is likely the problem is infeasible KTR_RC_INFEAS_MULTISTART MULTISTART No primal feasible point found The multi start feature was unable to find a feasible point If the problem is believed to be feasible then increase the number of initial points tried in the multi start feature and also perhaps increase the range from which random initial points are chosen See Section 9 6 for more details about multi start and Section 5 1 for various multi start user options KTR_RC_UNBOUNDED Problem appears to be unbounded Iterate is feasible and objective magnitude gt objrange The
120. the sparse Hessian of the La grangian Only nonzeroes in the upper triangle including diagonal nonzeroes should be counted See Section 4 7 NOTE If user option hessopt is not set to KTR_HESSOPT_EXACT then Hessian nonze roes will not be used see Section 5 1 In this case set nnzH 0 and pass NULL pointers for hessIndexRows and hessIndexCols int hessIndexRows is an array of length nnzH specifying the row number indices of the Hessian nonzeroes hessIndexRows i and hessIndexCo1s i determine the row numbers and the column numbers respectively of the nonzero Hessian element hessli where hess is the array of Hessian elements passed in the call KTR_solve See Section 4 7 NOTE Row numbers are in the range 0 n 1 int hessIndexCols is an array of length nnzH specifying the column number indices of the double Hessian nonzeroes hessIndexRows i and hessIndexCols determine the row numbers and the column numbers respectively of the nonzero Hessian element hessli where hess is the array of Hessian elements passed in the call KTR_solve See Section 4 7 NOTE Column numbers are in the range 0 n 1 xInitial is an array of length n containing an initial guess of the solution vector x If the application prefers to let KNITRO make an initial guess then pass a NULL pointer for xInitial 24 double lambdalnitial is an array of length mtn containing an initial guess of the Lagrange multiplier
121. tions based on standard netlib routines www netlib org The intel option uses MKL functions written especially for x86 and x86_64 processor architectures On a machine running an Intel processor e g Pentium 4 testing indicates that the MKL functions can reduce the CPU time in BLAS LAPACK op erations by 20 30 The dynamic option allows users to load any library that implements the functions declared in the file include blas_lapack h Specify the library name with option blasoptionlib The Intel MKL is provided in the KNITRO lib directory and is loaded at runtime by KNITRO The operating system s load path must be configured to find this directory or the MKL will fail to load See Section 5 4 for details If your machine uses security enhanced Linux SELinux you may see errors when loading the Intel MKL Refer to Section 2 3 for more information blasoptionlib KTR_PARAM BLASOPTIONLIB Specifies a dynamic library name that contains ob ject code for BLAS LAPACK functions The library must implement all the functions declared in the file include blas_lapack h The source file blasAcmlExample c in examples C provides a wrapper for the AMD Core Math Library ACML suitable for machines with an AMD pro cessor Instructions are given in the file for creating a BLAS LAPACK dynamic library from the ACML The operating system s load path must be configured to find the dynamic library as described in Section 5 4 NOTE This option has no effe
122. tions per KNITRO minor iteration O Let KNITRO automatically choose a value based on the problem size n At most n gt 0 CG iterations may be performed during one minor iteration of KNITRO Default value O maxcrossit KTR_PARAM MAXCROSSIT Specifies the maximum number of crossover iterations be fore termination If the value is positive and the algorithm in operation is Interior Direct or Interior CG then KNITRO will crossover to the Active Set algorithm near the solution The Active Set algorithm will then perform at most maxcrossit iterations to get a more exact solution If the value is 0 no Active Set crossover occurs and the interior point solution is the final result If Active Set crossover is unable to improve the approximate interior point solution then KNI TRO will restore the interior point solution In some cases especially on large scale problems or difficult degenerate problems the cost of the crossover procedure may be significant for this reason crossover is disabled by default Enabling crossover generally provides a more accurate solution than Interior Direct or Interior CG See Section 9 5 for more information Default value O maxit KTR_PARAM_MAXIT Specifies the maximum number of iterations before termination 0 Let KNITRO automatically choose a value based on the problem type Cur rently KNITRO sets this value to 10000 for LPs NLPs and 3000 for MIP problems n At most n gt 0 iterations may be p
123. tives is not overly expensive it is highly recommended to provide exact second derivatives However KNITRO also offers other options which are described in detail below Dense Quasi Newton BFGS The quasi Newton BFGS option uses gradient information to compute a symmetric positive definite 68 approximation to the Hessian matrix Typically this method requires more iterations to converge than the exact Hessian version However since it is only computing gradients rather than Hessians this approach may be more efficient in some cases This option stores a dense quasi Newton Hessian approximation so it is only recommended for small to medium problems n lt 1000 The quasi Newton BFGS option is chosen by setting user option hessopt 2 Dense Quasi Newton SR1 As with the BFGS approach the quasi Newton SR1 approach builds an approximate Hessian using gradient information However unlike the BFGS approximation the SR1 Hessian approximation is not restricted to be positive definite Therefore the quasi Newton SR1 approximation may be a better approach compared to the BFGS method if there is a lot of negative curvature in the problem since it may be able to maintain a better approximation to the true Hessian in this case The quasi Newton SR1 approximation maintains a dense Hessian approximation and so is only recommended for small to medium problems n lt 1000 The quasi Newton SR1 option is chosen by setting user option hessopt 3 Fin
124. to solve this problem with KNITRO In the example below we set alg 2 to use the Interior CG algorithm maxcrossit 2 to refine the solution using the Active Set algorithm and outlev 1 to limit output from KNITRO See Section 7 for an explanation of the KNITRO output AMPL Example ampl reset ampl option solver knitroampl ampl option knitro_options alg 2 maxcrossit 2 outlev 1 ampl model testproblem mod ampl solve KNITRO 6 0 alg 2 maxcrossit 2 outlev 1 Commercial Ziena License KNITRO 6 0 Ziena Optimization Inc website www ziena com email info ziena com algorithm 2 maxcrossit 2 outlev 1 KNITRO changing bar_murule from AUTO to 1 KNITRO changing bar_initpt from AUTO to 2 Problem Characteristics Number of variables bounded below bounded above bounded below and above fixed free Number of constraints linear equalities nonlinear equalities linear inequalities nonlinear inequalities range Number of nonzeros in Jacobian T O On OO A N OGO O O O WU W Number of nonzeros in Hessian EXIT Locally optimal solution found Final Statistics 9 36000000000000e 02 0 00e 00 0 00e 00 3 55e 15 2 22e 16 Final objective value Final feasibility error abs rel Final optimality error abs rel of iterations 7 of function evaluations 8 of gradient evaluations 8 of Hessian evaluations 7 Total program time secs 0 00321 0 001 CPU time Time spent in ev
125. trange overruling ms_maxbndrange if it is a tighter bound In general use ms_startptrange to limit the multi start search only if the initial start point supplied by the user is known to be the center of a desired search area Use ms_maxbndrange as a surrogate bound to limit the multi start search when a variable is unbounded See Section 5 1 for details The ms_num_to_save option allows a specific number of distinct feasible points to be saved in a file named knitro_mspoints log Each point results from a KNITRO solve from a different starting point and must satisfy the absolute and relative feasibility tolerances Different start points may return the same feasible point and the file contains only distinct points The option ms_savetol determines that two points are distinct if their objectives or any solution components including Lagrange multipliers are separated by more than the value of ms_savetol using a relative tolerance test More specifically two values x and y are considered distinct if z y gt max 1 x y x ms_savetol 9 34 The file stores points in order from best objective to worst If objectives are the same as defined by ms_savetol then points are ordered from smallest feasibility error to largest The file can be read manually but conforms to a fixed property value format for machine reading Instead of using multi start to search for a global solution a user may want to use multi start as a mechanism for findi
126. uation is needed making it easy to embed the KNITRO solver into an application In addition this mode allows applications to monitor or stop the progress of the KNITRO solver after each iteration based on any criteria the user desires If the return value from KTR_solve KTR mip_solve is 0 or negative the optimization is fin ished see Appendix A If the return value is positive KNITRO requires that some task be performed by the user at the driver level before re entering KTR_solve KTR_mip_solve Referring to the optimization problem formulation given in 4 4 the action to take for possible positive return values are KTR_RC_EVALFC 1 Evaluate functions f x and c x and re enter KTR_solve or KTR_mip_solve 72 KTR_RC_EVALGA 2 KTR_RC_EVALH 3 KTR_RC_EVALHV 7 KTR_RC_NEWPOINT 6 Evaluate gradient V f x and the constraint Jacobian matrix and re enter KTR_solve or KTR_mip_solve Evaluate the Hessian and re enter KTR_solve or KTR_mip_solve H x A Evaluate the Hessian H x A times a vector and re enter KTR_solve or KTR_mip_solve KNITRO has just computed a new solution estimate and the function and gradient values are up to date The user may provide routines to perform some task Then the application must re enter KTR_solve so that KNITRO can begin a new iteration KTR_RC_NEWPOINT is only returned if user option newpoint user and is only valid for continuous problems Section
127. wise fashion For the example above the number of nonzero elements nnzJ in J x is 6 and these arrays are specified as follows in column wise order jac 0 sin x 0 jacIndexCons 0 0 jacIndexVars 0 0 jac 1 2 x 0 jacIndexCons 1 1 jacIndexVars 1 0 jac 2 13 jacIndexCons 2 2 jacIndexVars 2 0 jac 3 2 x 1 jacIndexCons 3 1 jacIndexVars 3 1 jac 4 1 jacIndexCons 4 2 jacIndexVars 4 ds jac 5 ls jacIndexCons 5 2 jacIndexVars 5 2 The values of jac depend on the value of x and change during the solution process The values of jacIndexCons and jacIndexVars are set in KTR_init_problem and remain constant Computing the Sparse Hessian Matrix The Hessian of the Lagrangian matrix is defined as H z X V f x y AV c z 4 13 i 0 where A is the vector of Lagrange multipliers dual variables For the example defined by problem 4 7 The Hessians second derivatives of the objective and constraint functions are given by 0 0 0 cos zo 0 0 V f z 0 0 322 Volz 0 0 0 0 3x2 61112 0 0 0 2 0 0 000 Ve 0 2 0f V7co x 0 0 0 000 000 35 Scaling the constraint matrices by their corresponding Lagrange multipliers and summing we get Xo cos Xo 2A 0 0 H A 0 2h 322 0 322 62122 Since the Hessian matrix will always be a symmetric matrix KNITRO only stores the nonzero el ements corresponding to the upper triangular part including the diagonal In the example
128. y we have that fax 1 a y lt af x 1 a f y for all a e 0 1 4 14 In identifying the objective or constraints as convex we are assuming a problem form where the objective is being minimized and the constraints are all formulated as less than or equal to constraints If we are maximizing or looking at greater than or equal to constraints then the objective or constraint should be labeled as convex if its negation is convex 36 More specifically the objective function f x should be marked as convex if when minimizing f a satisfies condition 4 14 or if when maximizing f x satisfies condition 4 14 If we consider problem 1 1 a constraint c x should be labeled as convex if e cl is infinite c is finite and c x satisfies condition 4 14 or e cl is finite c is infinite and c x satisfies condition 4 14 or e cl is finite c is finite and c x is linear All linear functions are convex Any nonlinear equality constraint is nonconvex The MIP solvers in KNITRO are designed for convex problems problems where the objective and all the constraints are convex If one or more functions are nonconvex these solvers are only heuristics and may terminate at non optimal points The continuous solvers in KNITRO can handle either convex or nonconvex models However for nonconvex models they may converge to local rather than global optimal solutions 4 9 Calling without first derivatives A
129. y constraints MPCCs through the AMPL interface A complementarity constraint enforces that two variables are complementary to each other i e that the following conditions hold for scalar variables x and y xxy 0 2 gt 0 y gt 0 3 3 The condition above is sometimes expressed more compactly as 0O lt x 1 y gt 0 See Section 10 5 for more information about the mathematics of complementarity constraints These constraints must be formulated in a particular way through AMPL in order for KNITRO to effectively deal with them In particular complementarity constraints should be modeled using the AMPL complements command e g O lt x complements y gt 0 and they must be formulated as one variable complementary to another variable They may not be formulated as a function complementary to a variable or a function complementary to a function KNITRO will print a warning if functions are used in complementarity constraints but it is not able to fix the problem If a complementarity involves a function F x for example O0 lt F x L gt 0 then the user should reformulate the AMPL model by adding a slack variable as shown below so that it is formulated as a variable complementary to another variable 18 var x var s constraint_name_a F x s constraint_name_b 0 lt s complements x gt 0 Be aware that the AMPL presolver sometimes removes complementarity constraints Check carefully that the problem definition repo
130. y small already it is an indication that no more significant progress can be made It s possible the approximate feasible solution is optimal but perhaps the stopping tests cannot be satisfied because of degeneracy ill conditioning or bad scaling KTR_RC_FEAS_NO_IMPROVE Primal feasible solution estimate cannot be improved desired accuracy in dual feasibility could not be achieved No further progress can be made It s possible the approximate feasible solution is optimal but perhaps the stopping tests cannot be satisfied because of degeneracy ill conditioning or bad scaling 81 82 200 201 202 203 300 400 KTR_RC_INFEASIBLE Convergence to an infeasible point Problem may be locally infeasible If problem is believed to be feasible try multistart to search for feasible points The algorithm has converged to an infeasible point from which it cannot further decrease the infeasibility measure This happens when the problem is infeasible but may also occur on occasion for feasible problems with nonlinear constraints or badly scaled problems It is recommended to try various initial points with the multi start feature described in Section 9 6 If this occurs for a variety of initial points it is likely the problem is infeasible KTR_RC_INFEAS_XTOL Terminate at infeasible point because the relative change in solution estimate lt xtol Decrease xtol to try for more accuracy The optimization
131. zing 3 implement both options 1 and 2 above bar_feasmodetol tolerance for entering stay feasible mode 1 0e 4 bar_initmu initial value for barrier parameter 1 0e 1 bar_initpt initial point strategy for barrier algorithms 0 O let KNITRO choose the initial point strategy 1 shift the initial point to improve barrier performance 2 do not alter the initial point supplied by the user bar_maxbacktrack maximum number of linesearch backtracks 3 bar_maxrefactor maximum number of KKT refactorizations allowed 0 bar_murule barrier parameter update rule 0 O let KNITRO choose the barrier update rule 1 monotone decrease rule 2 adaptive rule based on complementarity gap 3 probing rule Interior Direct only 4 safeguarded Mehrotra predictor corrector type rule 5 Mehrotra predictor corrector type rule 6 rule based on minimizing a quality function 14 OPTION DESCRIPTION DEFAULT bar_penaltycons technique for penalizing constraints in the barrier algorithms 0 O let KNITRO choose the strategy 1 do not apply penalty approach to any constraints 2 apply a penalty approach to all general constraints bar_penaltyrule penalty parameter rule for step acceptance 0 O let KNITRO choose the strategy 1 use single penalty parameter approach 2 use more tolerant flexible strategy blasoption specify the BLAS LAPACK function library to u

KNITRO User`s Manual Version 6.0

Contents

Download Pdf Manuals

Related Search

Related Contents