CONOPT is designed for the following mathematical optimization model:
\begin{align*} \text{Min or Max} \quad& x_{obj} \text{ or } g_{obj}(x) \\
\text{Subject to} \quad& g_{i}(x) \text{ =R= } b_{i} &\quad \forall i \in {1, \ldots, Nrow} \\
&lb_j < x_j < ub_j &\quad \forall j \in {1, \ldots, Ncol}
\end{align*}
where:
- \(x\) is a vector of continuous optimization variables with Ncol elements to be determined by CONOPT,
- \(lb\) is a fixed vector of lower bounds on the optimization variables. Some lower bounds can be –Inf corresponding to variables without a lower bound,
- \(ub\) is a fixed vector of upper bounds on the optimization variables. Some upper bounds can be +Inf corresponding to variables without an upper bound,
- \(g\) is a vector of constraint functions with Nrow elements. The constraint functions must be differentiable and their derivatives must be available,
- \(b\) is a fixed vector of right hand sides,
=R=
represent a relationship. For each constraint =R=
can be one of the four relationships: \(\leq\), less than or equal; \(=\), equal; \(\geq\), greater than or equal; or non-binding,
- \(obj\) is a fixed index of a variable or function (of type non-binding) to be minimized or maximized.
CONOPT has been implemented based on the following assumptions:
- The model is large: This means that both
Nrow
and Ncol
are large which by today’s standards means above 1000 variables and constraints. The targets for our current developments are models with 10,000-100,000 variables and constraints. CONOPT has successfully solved models with more than 250,000 variables and constraints.
- The matrix of first derivatives of the constraints with respect to the variables is sparse: This means that although there are many constraints, each variable appear on average only in a small number of constraints.
- The constraint functions have low noise level: This means that function values computed in a small region closely match the hyperplane defined by the first derivatives. The noise, defined as the average deviation from the hyperplane, is assumed to be close to the machine precision.
- Constraint functions are relatively cheap to compute: Some solvers will do a large amount of work based on an approximating model such as a linear-quadratic approximation, and only infrequently test the model against the true function values. CONOPT assumes that functions are cheap and it will evaluate the constraint functions a large number of times. CONOPT may therefore not be suitable for models in which the constraint functions involve an elaborate simulation. On the other hand, CONOPT is ideally suited for models defined in modern modeling systems.
- The first derivatives are available in analytical form: The implication is that derivatives are cheap to compute (they are not computed using finite differences), and that they are computed with a precision close to the machine precision.
- The number of degrees of freedom in the final point is limited: The degree of freedom, DF, is here defined as the number of variables that are not at one of their bounds, minus the number of active constraints. Conceptually, CONOPT reduces the overall optimization model to an unconstrained model with DF variables, and approximates the second derivatives of this reduced model. This approximation can be expensive, both in terms of memory and computer time, if DF is larger than a one thousand.
- For models with very large DF CONOPT now offers methods based on second derivative information. The efficiency of these methods rely on second order information supplied by the modeler.