Interior-point method: Difference between revisions

Revision as of 13:53, 12 December 2023

Revision as of 13:55, 12 December 2023

Line 107:

The primal-dual method's idea is easy to demonstrate for constrained [[nonlinear optimization]].<ref>{{Cite journal |last1=Mehrotra |first1=Sanjay |year=1992 |title=On the Implementation of a Primal-Dual Interior Point Method |journal=SIAM Journal on Optimization |volume=2 |issue=4 |pages=575–601 |doi=10.1137/0802028}}</ref><ref>{{cite book |last=Wright |first=Stephen |title=Primal-Dual Interior-Point Methods |publisher=SIAM |year=1997 |isbn=978-0-89871-382-4 |___location=Philadelphia, PA}}</ref> For simplicity, consider the following nonlinear optimization problem with inequality constraints:

:<math display="block">\begin{aligned}

\operatorname{minimize}\quad & f(x) \\

\text{subject to}\quad

Line 117:

This inequality-constrained optimization problem is solved by converting it into an unconstrained objective function whose minimum we hope to find efficiently.

Specifically, the logarithmic [[barrier function]] associated with (1) is

:<math display="block">B(x,\mu) = f(x) - \mu \sum_{i=1}^m \log(c_i(x)). \quad (2)</math>

Here <math>\mu</math> is a small positive scalar, sometimes called the "barrier parameter". As <math>\mu</math> converges to zero the minimum of <math>B(x,\mu)</math> should converge to a solution of (1).

Line 123:

The [[gradient]] of a differentiable function <math>h : \mathbb{R}^n \to \mathbb{R}</math> is denoted <math>\nabla h</math>.

The gradient of the barrier function is

:<math display="block">\nabla B(x,\mu) = \nabla f(x) - \mu \sum_{i=1}^m \frac{1}{c_i(x)} \nabla c_i(x). \quad (3)</math>

In addition to the original ("primal") variable <math>x</math> we introduce a [[Lagrange multiplier]]-inspired [[Lagrange multiplier#The strong Lagrangian principle: Lagrange duality|dual]] variable <math>\lambda \in \mathbb{R} ^m</math>

:<math display="block">c_i(x) \lambda_i = \mu,\quad \forall i = 1, \ldots, m. \quad (4)</math>

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

Line 133:

Substituting <math>1/c_i(x) = \lambda_i / \mu</math> from (4) into (3), we get an equation for the gradient:

:<math display="block">\nabla B(x_\mu, \lambda_\mu) = \nabla f(x_\mu) - J(x_\mu)^T \lambda_\mu = 0, \quad (5)</math>

where the matrix <math>J</math> is the [[Jacobian matrix and determinant|Jacobian]] of the constraints <math>c(x)</math>.

Line 140:

Let <math>(p_x, p_\lambda)</math> be the search direction for iteratively updating <math>(x, \lambda)</math>.

Applying [[Newton method|Newton's method]] to (4) and (5), we get an equation for <math>(p_x, p_\lambda)</math>:

:<math display="block">\begin{pmatrix}

H(x, \lambda) & -J(x)^T \\

\operatorname{diag}(\lambda) J(x) & \operatorname{diag}(c(x))