The KNITRO optimizer is a tool that is designed specifically to find local solutions of continuous, smooth nonlinear optimization problems. It encompasses various state of the art methods to solve these classes of problems. KNITRO for MPL gives users access to this renowned solver of nonlinear programming problems. Like all our solvers the KNITRO optimizer is actually accessed from MPL for Windows as a Dynamic Link Library (DLL). This tight integration allows MPL users to transparently access KNITRO's solution algorithms and options from their MPL application.
KNITRO can solve linear as well quadratic problems, though its principle area of expertise and commercial usage is in the area of nonlinear programming problems. KNITRO implements both state of the art interior-point and active-set methods for solving nonlinear optimization:
In the interior method (also known as a barrier method), the nonlinear programming problem is replaced by a series of barrier sub-problems controlled by a barrier parameter �. The algorithm uses trust regions and a merit function to promote convergence. The algorithm performs one or more minimization steps on each barrier problem, then decreases the barrier parameter, and repeats the process until the original problem has been solved to the desired accuracy. There are two variations on the interior method, which are based on the methodology ulitized for computing the steps within the interior point approach.
Interior-point Direct algorithmApplies barrier techniques and directly factorizes the KKT matrix of the nonlinear system. It performs best on ill-conditioned problems.
Interior-point CG algorithmApplies barrier techniques using the conjugate gradient method to solve KKT subproblems. It provides an alternative to the Interior-point Direct algorithm when the KKT factorization is impractical or inefficient to form.
Active Set algorithmKNITRO also implements an active-set sequential linear-quadratic programming (SLQP) algorithm that is called the Active algorithm. This method is similar in nature to a sequential quadratic programming method but uses linear programming sub-problems to estimate the active-set at each iteration. This active-set code may be preferable when a good initial point can be provided; for example, when solving a sequence of related problems. It's behavior is significantly different from Interior-point algorithms, and it converges precisely to the active set to provide highly accurate sensitivity information.
Every nonlinear optimization problem is unique, and it can be quite difficult to predict performance of any algorithm on a given problem. Having the option to choose amongst KNITRO's three algorithms greatly increases the chances of solving your problem efficiently. We encourage the user to try all algorithmic options to determine which one is more suitable for the model at hand. The default algorithm setting allows KNITRO to try to determine which algorithm to use based on the problem characteristics. The principle performance factor will be with the algorithmic option chosen to solve the NLP problem, though there are some settings one can modify depending on the model characteristics.
KNITRO uses hessian matrix calculations in its search methods, the default is to calculate exact the hessian matrix which can be computationally expensive. In highly nonlinear models or large models (> 1000 variables) undertaking these complex calculations can hinder performance, KNITRO provides other methods which are less computationally intense. Typically on these large models or where the hessian is very expensive to calculate we would typically recommend using the finite-difference Hessian-vector method or the limited-memory quasi-Newton BFGS Hessian. This methodology is highly recommended for very large problems. To implement these settings one needs to set the option "HessianCalcMethod" to 4 for the finite difference method and to 6 for the quasi-Newton method.
NLPs are often nonconvex due to the objective function, constraint functions, or both. When this is true, there can be numerous points that satisfy local optimality conditions. The 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 the option, "MultiStart" to one. The multi-start procedure generates new start points by randomly selecting x components that satisfy the variable bounds. The number of start points to try is specified with the option "MaxMultiStartPoints". KNITRO finds a local optimum from each start point and returns the best local optimum from all the multi starts.
MPL shows the progress of KNITRO during an optimisation run in the message window that also can be relayed to a log file. The log initially displays information about the model, and any specific option setting changes KNITRO has done, the message log has the following appearance:
KNITRO: ====================================== KNITRO: Trial Ziena License (NOT FOR COMMERCIAL USE) KNITRO: KNITRO 5.1.1 KNITRO: Ziena Optimization, Inc. KNITRO: website: www.ziena.com KNITRO: email: info@ziena.com KNITRO: ====================================== KNITRO: KNITRO changing algorithm from AUTO to 1. KNITRO: KNITRO changing bar_murule from AUTO to 1. KNITRO: KNITRO changing bar_initpt from AUTO to 2. KNITRO: KNITRO shifted start point to honor bounds (100 variables). KNITRO: Problem Characteristics KNITRO: ----------------------- KNITRO: Objective goal: Minimize KNITRO: Number of variables: 120 KNITRO: bounded below: 0 KNITRO: bounded above: 0 KNITRO: bounded below and above: 100 KNITRO: fixed: 0 KNITRO: free: 20 KNITRO: Number of constraints: 32 KNITRO: linear equalities: 0 KNITRO: nonlinear equalities: 20 KNITRO: linear inequalities: 12 KNITRO: nonlinear inequalities: 0 KNITRO: range: 0 KNITRO: Number of nonzeros in Jacobian: 220 KNITRO: Number of nonzeros in Hessian: 143 KNITRO: Iter Objective Feas err Opt err ||Step|| CG its KNITRO: -------- -------------- ---------- ---------- ---------- ------- KNITRO: 0 -1.755000e+003 9.505e+001 KNITRO: 10 -1.724807e+003 2.117e-002 5.493e-001 1.847e+001 0 KNITRO: 20 -1.735503e+003 2.483e-004 6.148e-003 3.570e+000 0 KNITRO: 23 -1.735569e+003 2.060e-006 5.197e-005 5.360e-001 0 KNITRO: EXIT: LOCALLY OPTIMAL SOLUTION FOUND. KNITRO: Final Statistics KNITRO: ---------------- KNITRO: Final objective value = -1.73556932799312e+003 KNITRO: Final feasibility error (abs / rel) = 2.06e-006 / 2.17e-008 KNITRO: Final optimality error (abs / rel) = 5.20e-005 / 5.20e-007 KNITRO: # of iterations (major / minor) = 23 / 23 KNITRO: # of function evaluations = 24 KNITRO: # of gradient evaluations = 24 KNITRO: # of Hessian evaluations = 23 KNITRO: Total program time (secs) = 0.363 ( 0.375 CPU time) KNITRO: Time spent in evaluations (secs) = 0.109 KNITRO: ========================================================================= Solver Statistics Solver name: Knitro Objective value: -1735.56932799312 Iterations: 23 Solution time: 0.42 sec Result code: 0
KNITRO displays the objective and respective feasibility and optimality errors and step calculations per iteration. On completion of the solve, a synopsis of the evaluations and iterations are given.
For full description of all the Knitro Parameters that are supported in MPL, please go to the Knitro Option Parameters page.