Barrier function

A barrier function penalizes approaching the boundary of a feasible set from its interior, typically diverging to $+\infty$ there. An interior-point method minimizes the original objective function plus a positive multiple of this penalty, then reduces that multiple. The logarithmic barrier is the basic example for smooth inequality optimization constraints.

For optimization constraints $c_i(x)\ge 0$ and $\mu >0$, the logarithmic barrier objective is $f_{\mu }(x)=f(x)-\mu {\sum }_i\log c_i(x)$ on $D=\{x:c_i(x)>0\forall i\}$. Its derivatives are defined only on this strictly feasible open subset. One may extend its value to $+\infty$ off $D$ to formulate an extended-real convex function. The penalty alone is $-{\sum }_i\log c_i$, while $f_{\mu }$ includes the original objective function.

When $f$ is convex and each $c_i$ is concave, $D$ is a convex set andEvery term of this Hessian matrix is a positive semidefinite matrix, so $f_{\mu }$ is convex. Its critical point satisfies the stationarity part of the Karush-Kuhn-Tucker conditions with estimates ${\lambda }_i=\mu /c_i(x)>0$ and perturbed complementary slackness ${\lambda }_i{c}_i(x)=\mu$.

Let $c_i$ be concave and continuously differentiable, and let a strict feasible point $z$ satisfy $\delta ={\min }_i{c}_i(z)>0$. Suppose $x_k\to x_{\ast }$, $c_i(x_k)>0$, ${\mu }_k\to 0$, and the logarithmic barrier residuals $r_k=\nabla f(x_k)-{\sum }_i{\lambda }_{k,i}\nabla c_i(x_k)$ tend to zero, where ${\lambda }_{k,i}={\mu }_k/c_i(x_k)$. By concavity,The right-hand side is bounded when $\nabla f$ is continuous near $x_{\ast }$. Thus the nonnegative Lagrange multiplier estimates are bounded. A convergent subsequence gives ${\lambda }_{\ast }\ge 0$; passing to the limit in stationarity and ${\lambda }_{k,i}{c}_i(x_k)={\mu }_k$ proves the Karush-Kuhn-Tucker conditions at $x_{\ast }$. An inactive optimization constraint has $c_i(x_{\ast })>0$ and hence ${\lambda }_{k,i}\to 0$ even without selecting a subsequence. With a convex objective function, these conditions certify a global minimum. This result is conditional on the stated residual and primal convergence assumptions; it does not assert that every barrier subproblem has a minimizer.

Near an active constraint with limiting Lagrange multiplier ${\lambda }_i^{\ast }>0$, a convergent barrier sequence has $c_i(x_k)\sim {\mu }_k/{\lambda }_i^{\ast }$. Its Hessian matrix therefore contains the termFor a nonzero constraint gradient, this gives large curvature in a direction normal to the boundary. If a nonzero common tangent direction retains positive curvature of order one, while the remaining terms stay bounded, the condition number typically grows like $1/{\mu }_k$. This is a mechanism rather than a universal rate: there may be no tangent direction, all curvatures may grow together, or an active constraint may have zero limiting Lagrange multiplier.