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 :
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 monk in hiding himself from the world becomes not less than himself, not less of a person, but more of a person, more truly and perfectly himself: for his personality and individuality are perfected in their true order, the spiritual, interior order, of union with God, the principle of all perfection.”
—Thomas Merton (1915–1968)
“In order to really enjoy a dog, one doesn’t merely try to train him to be semihuman. The point of it is to open oneself to the possibility of becoming partly a dog.”
—Edward Hoagland (b. 1932)
“Unlike Descartes, we own and use our beliefs of the moment, even in the midst of philosophizing, until by what is vaguely called scientific method we change them here and there for the better. Within our own total evolving doctrine, we can judge truth as earnestly and absolutely as can be, subject to correction, but that goes without saying.”
—Willard Van Orman Quine (b. 1908)