The Interior Point Nonlinear Programming Solver: Overview of Interior Point Methods :: SAS/OR(R) 9.2 User's Guide: Mathematical Programming

The Interior Point Nonlinear Programming Solver -- Experimental

Overview of Interior Point Methods

Primal-dual interior point methods can be classified into two categories: feasible and infeasible. The first category requires the starting point as well as all subsequent iterations of the algorithm to strictly satisfy all the inequality constraints. The second category relaxes those requirements and allows the iterates to violate some or all of the inequality constraints during the course of the minimization procedure. Currently, the IPNLP solver implements an infeasible algorithm. For this reason we will concentrate on that type of algorithm.

To make the notation less cluttered and the fundamentals of interior point methods easier to understand, we consider, without loss of generality, the following simpler NLP problem:

$\displaystyle\mathop{\rm minimize}& f(x) \ {\rm subjectto}& g_{i}(x) \ge 0, i \in \mathcal{i} = \{ 1,2, ..., q \}$

Note that the equality and bound constraints have been omitted from the preceding problem. Initially, slack variables are added to the inequality constraints, giving rise to the following problem:

$\displaystyle\mathop{\rm minimize}& f(x) \ {\rm subjectto}& g_{i}(x) - s_{i} = 0, i \in \mathcal{i} \ & s \ge 0$

where $s = (s_{1}, ..., s_{q})^{\rm t}$ represents the vector of the slack variables, which are required to be nonnegative. Next, all the nonnegativity constraints on the slack variables are eliminated by being incorporated into the objective function, by means of a logarithmic function. This gives rise to the following equality-constrained NLP problem:

$\displaystyle\mathop{\rm minimize}& b(x,s) = f(x) - \mu \sum_{i\in \mathcal{i}} \ln (s_{i}) \ {\rm subjectto}& g_{i}(x) - s_{i} = 0, i \in \mathcal{i}$

where $\mu$ is a positive parameter. The preceding problem is often called the barrier problem . The nonnegativity constraints on the slack variables are implicitly enforced by the logarithmic functions, since the logarithmic function prohibits

from taking zero or negative values.

Depending on the size of the parameter $\mu$ , a local minimum of the barrier problem provides an approximation to the local minimum of the original NLP problem. The smaller the size of $\mu$ , the better the approximation becomes. Infeasible primal-dual interior point algorithms repetitively solve the barrier problem for different values of $\mu$ that progressively go to zero, in order to get as close as possible to a local minimum of the original NLP problem.

To solve the barrier problem we first define its Lagrangian function:

$\mathcal{l}_{b}(x,s,z) & = & b(x,s) - z^{\rm t} (g(x) - s)\ & = & f(x) - \mu \sum_{i\in i} \ln (s_{i}) - z^{\rm t} (g(x) - s)$

Then we define its first-order optimality conditions:

$\nabla_{x} \mathcal{l}_{b} &=& \nabla_{x} f(x) - j(x)^{\rm t} z &=& 0 \ \nabla_{s} \mathcal{l}_{b} &=& -\mu s^{-1} e + z &=& 0 \ & & g(x) - s &=& 0$

where

represents the Jacobian matrix of the vector function

represents the diagonal matrix whose elements are the elements of the vector

(i.e., $s = diag\{ s_{1}, ..., s_{q} \}$ ), and

represents a vector of all ones. By multiplying the second equation by

, we obtain the following equivalent nonlinear system:

$\nabla_{x} f(x) - j(x)^{\rm t} z &=& 0 \ -\mu e + s z &=& 0 \ g(x) - s &=& 0$

Note that if $\mu = 0$ , the preceding conditions represent the optimality conditions of the original optimization problem, after adding slack variables. One of the main aims of the algorithm is to gradually reduce the value of $\mu$ to zero, so that it converges to a local optimum of the original NLP problem. The rate by which $\mu$ approaches zero affects the overall efficiency of the algorithm.

At an iteration , the infeasible primal-dual interior point algorithm approximately solves the preceding system by using Newton's method. The Newton system is

$[h_{\mathcal{l}}(x^k, z^k) & 0 & -j(x^k)^{\rm t} \ 0 & z^k & s^k \ j(x^k) & -i... ... - [\nabla_{x} f(x^k) - j(x^k)^{\rm t} z \ -\mu e + s^k z^k \ g(x^k) - s^k ]$

where $h_{\mathcal{l}}$ is the Hessian matrix of the Lagrangian function $\mathcal{l}(x,z) = f(x) - z^{\rm t}g(x)$ of the original NLP problem, i.e.,

$h_{\mathcal{l}} (x,z) = \nabla^2 f(x) - \sum_{i\in \mathcal{i}} z_{i} \nabla^2 g_{i}(x)$

The solution $(\delta x^k, \delta s^k, \delta z^k)$ of the Newton system provides a direction to move from the current iteration

to the next:

$(x^{k+1},s^{k+1},z^{k+1}) = (x^k,s^k,z^k) + \alpha (\delta x^k, \delta s^k, \delta z^k)$

where $\alpha$ is the step length along the Newton direction. The step length is determined through a line-search procedure that ensures sufficient decrease of a merit function based on the augmented Lagrangian function of the barrier problem. The role of the merit function and the line-search procedure is to ensure that the objective and the infeasibility reduce sufficiently at every iteration and that the iterates approach a local minimum of the original NLP problem.

Top of Page