8.5 Nonlinear Convex Optimization

8.5.1 The Interior-point Optimizer

For general convex optimization problems an interior-point type optimizer is available. The interior-point optimizer is an implementation of the homogeneous and self-dual algorithm. For a detailed description of the algorithm, please see [AY98], [AY99]. The Convexity Requirement

Continuous nonlinear problems are required to be convex. For quadratic problems MOSEK tests this requirement before optimizing. Specifying a non-convex problem results in an error message.

The following parameters are available to control the convexity check: The Differentiability Requirement

The nonlinear optimizer in MOSEK requires both first order and second order derivatives. This of course implies care should be taken when solving problems involving non-differentiable functions.

For instance, the function

\[f(x) = x^2\]

is differentiable everywhere whereas the function

\[f(x) = \sqrt{x}\]

is only differentiable for \(x > 0\) . In order to make sure that MOSEK evaluates the functions at points where they are differentiable, the function domains must be defined by setting appropriate variable bounds.

In general, if a variable is not ranged MOSEK will only evaluate that variable at points strictly within the bounds. Hence, imposing the bound

\[x \geq 0\]

in the case of \(\sqrt{x}\) is sufficient to guarantee that the function will only be evaluated in points where it is differentiable.

However, if a function is defined on a closed range, specifying the variable bounds is not sufficient. Consider the function

(1)\[f(x) = \frac{1}{x} + \frac{1}{1-x}.\]

In this case the bounds

\[0 \leq x \leq 1\]

will not guarantee that MOSEK only evaluates the function for \(x\) strictly between \(0\) and \(1\) . To force MOSEK to strictly satisfy both bounds on ranged variables set the parameter MSK_IPAR_INTPNT_STARTING_POINT to MSK_STARTING_POINT_SATISFY_BOUNDS.

For efficiency reasons it may be better to reformulate the problem than to force MOSEK to observe ranged bounds strictly. For instance, (1) can be reformulated as follows

\[\begin{split}\begin{array}{rcl} f(x) & = & \frac{1}{x} + \frac{1}{y} \\ 0 & = & 1 - x - y \\ 0 & \leq & x \\ 0 & \leq & y. \end{array}\end{split}\] Interior-point Termination Criteria

The parameters controlling when the general convex interior-point optimizer terminates are shown in Table 5.

Table 5 Parameters employed in termination criteria.
Parameter name Purpose
MSK_DPAR_INTPNT_NL_TOL_PFEAS Controls primal feasibility
MSK_DPAR_INTPNT_NL_TOL_DFEAS Controls dual feasibility
MSK_DPAR_INTPNT_NL_TOL_REL_GAP Controls relative gap
MSK_DPAR_INTPNT_TOL_INFEAS Controls when the problem is declared infeasible
MSK_DPAR_INTPNT_NL_TOL_MU_RED Controls when the complementarity is reduced enough