Interior Point Method - Primal-dual Interior Point Method For Nonlinear Optimization

Primal-dual Interior Point Method For Nonlinear Optimization

The primal-dual method's idea is easy to demonstrate for constrained nonlinear optimization. For simplicity consider the all-inequality version of a nonlinear optimization problem:

minimize subject to .

The logarithmic barrier function associated with (1) is

Here is a small positive scalar, sometimes called the "barrier parameter". As converges to zero the minimum of should converge to a solution of (1).

The barrier function gradient is

where is the gradient of the original function and is the gradient of .

In addition to the original ("primal") variable we introduce a Lagrange multiplier inspired dual variable (sometimes called "slack variable")

(4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in KKT conditions.

We try to find those which turn gradient of barrier function to zero.

Applying (4) to (3) we get equation for gradient:

where the matrix is the constraint Jacobian.

The intuition behind (5) is that the gradient of should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small (4) can be understood as the condition that the solution should either lie near the boundary or that the projection of the gradient on the constraint component normal should be almost zero.

Applying Newton's method to (4) and (5) we get an equation for update :

\begin{pmatrix} W & -A^T \\ \Lambda A & C \end{pmatrix}\begin{pmatrix} p_x \\ p_\lambda \end{pmatrix}=\begin{pmatrix} -g + A^T \lambda \\ \mu 1 - C \lambda \end{pmatrix}

where is the Hessian matrix of and is a diagonal matrix of .

Because of (1), (4) the condition

should be enforced at each step. This can be done by choosing appropriate :

.

Read more about this topic:  Interior Point Method

Famous quotes containing the words interior, point and/or method:

    “The exterior must be joined to the interior to obtain anything from God, that is to say, we must kneel, pray with the lips, and so on, in order that proud man, who would not submit himself to God, may be now subject to the creature.”
    —Blaise Pascal (1623–1662)

    “When we are in love, the sentiment is too great to be contained whole within us; it radiates out to our beloved, finds in her a surface which stops it, forces it to return to its point of departure, and it is this rebound of our own tenderness which we call the other’s affection and which charms us more than when it first went out because we do not see that it comes from us.”
    —Marcel Proust (1871–1922)

    ““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
    —James Boswell (1740–1795)