Special problem classes

The following sections describe 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 particular types of problems.

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(). If this is not done, Knitro will not apply special treatment to the LP and will typically be less efficient in solving the LP.

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(). 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 specializations will only help on convex QPs.

Systems of nonlinear equations

Knitro is effective at solving systems of nonlinear equations.

There are two ways to try to solve a square system of nonlinear equations using Knitro. In the first way, you can use the least-squares API (see Nonlinear Least-Squares) and just specify the nonlinear equations as the residual functions. Knitro will then formulate your model as an unconstrained optimization problem where the objective function to be minimized is the sum of squares of the nonlinear equations and apply the Gauss-Newton Hessian.

In the second way, you can use the standard Knitro API and specify the nonlinear equations as equality constraints and specify the objective function as zero (i.e., f(x)=0).

The first approach is the recommended approach, however, you should experiment with both formulations to see which one works better.

If Knitro is converging to a stationary point for which the nonlinear equations are not satisfied, the multi-start option may help in finding a solution by trying different starting points.

Least squares problems

Knitro offers a specialized API for solving least-squares problems,

\min f(x) = 0.5 * (r_1(x)^2 + r_2(x)^2 + ... + r_q(x)^2)

with or without bounds on the variables (see Nonlinear Least-Squares). By default, this specialized interface will apply the Gauss-Newton Hessian

J(x)^T \, J(x)

where J(x) is the Jacobian matrix of the residual functions r_j(x) at x. Knitro will behave like a Gauss-Newton method by using the linesearch methods algorithm = KTR_ALG_BAR_DIRECT or KTR_ALG_ACT_SQP, and will be very similar to the classical Levenberg-Marquardt method when using the trust-region methods algorithm = KTR_ALG_BAR_CG or KTR_ALG_ACT_CG. The Gauss-Newton and Levenberg-Marquardt approaches consist of using this approximate value for the Hessian and ignoring the remaining term. Using the specialized least-squares interface will generally be the most effective way to solve least-squares models with Knitro, as it only requires first derivatives of the residual functions, r_j(x), and yet can converge rapidly in most cases.

However, in some cases, if the value of the objective function at the solution is not close to zero (the large residual case), and/or the user can provide the full, exact Hessian matrix, then it may be more efficient to use the standard API and solve the least-squares model as any other optimization problem. Any of the Knitro options can be used.

See Nonlinear Least Squares for an implementation in knitromatlab.

Complementarity constraints (MPCCs)

As we have seen in Complementarity constraints, 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 that enforces that two variables x_1 and x_2 are complementary to each other, i.e. that the following conditions hold:

x_1 \* x_2 = 0, x_1 \geq 0, x_2 \geq 0.

These constraints sometimes occur in practice and deserve special handling. See Complementarity constraints for details on how to use complementarity constraints with Knitro.

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 convex all locally optimal solutions are also globally optimal solutions. The ability to guarantee convergence to the global solution on large-scale nonconvex problems is a nearly impossible task on most problems 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 that attempts to find multiple local solutions in the hopes of locating the global solution. See Multistart.

Mixed integer programming (MIP)

Knitro provides tools for solving optimization models (both linear and nonlinear) with binary or integer variables. See the dedicated chapter Mixed-integer nonlinear programming for a discussion on this topic.