The Log Barrier Method

The algorithm

The log barrier method or interior point method is a general algorithm that can be used to solve optimization problems where the inequality constraints are convex and twice differentiable, such as LP, QP, and convex programming.

Consider a convex optimization problem with the $m$ constraints as follows:

where $g(.)$ is a convex objective and $h_i(.)'s$ are convex and twice differentiable constraints.

The main idea of the log barrier method is to transform the optimization problem with inequality constraints into a sequence of unconstrained optimization problems that can be solved using the standard gradient descent algorithms. The transformation involves replacing the indicator functions that enforce the constraints with smooth functions that approximate them as follows:

where $t>0$. The log barrier function has some nice properties, such as the following:

• It is convex and smooth, which makes it easier to optimize using gradient descent.

• It approaches infinity as $x$ approaches the boundary of the feasible region, which prevents the solution from violating the constraints.

The figure below illustrates how the log barrier method prevents the solution from violating the constraints for the following constrained optimization:

In the left figure, we can see that adding an indicator function makes the overall objective discontinuous, nondifferentiable, and eventually difficult to optimize. However, in the right figure, we see that the log barrier function replaces the indicator functions that enforce the constraints with smooth functions. This makes the overall log barrier objective continuous, differentiable, and easy to optimize.

Note: The augmented objective $\hat{g}(x, t)$ ...