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:

    “Anyone with a real taste for solitude who indulges that taste encounters the dangers of any other drug-taker. The habit grows. You become an addict.... Absorbed in the visions of solitude, human beings are only interruptions. What voice can equal the voices of solitude? What sights equal the movement of a single day’s tide of light across the floor boards of one room? What drama be as continuously absorbing as the interior one?”
    —Jessamyn West (1902–1984)

    “You should go to picture-galleries and museums of sculpture to be acted upon, and not to express or try to form your own perfectly futile opinion. It makes no difference to you or the world what you may think of any work of art. That is not the question; the point is how it affects you. The picture is the judge of your capacity, not you of its excellence; the world has long ago passed its judgment upon it, and now it is for the work to estimate you.”
    —Anna C. Brackett (1836–1911)

    “The method of scientific investigation is nothing but the expression of the necessary mode of working of the human mind. It is simply the mode in which all phenomena are reasoned about, rendered precise and exact.”
    —Thomas Henry Huxley (1825–95)