Interior Point Method

if we are within the feasible set already, we can do these to prevent us form getting out:
inequality constrained optimization Generally things are of t]shape:

\begin{align} \min_{x}\quad & f_{0}\left(x\right) \\ \textrm{s.t.} \quad & f_{i}\left(x\right) \leq 0, i = 1\dots m \\ & Ax =b \end{align}

convex, tie differentiable p^{*} is finite and attained strictly feasible These include… LP, QP, QCQP, geometric program.
indicator barrier Reformulate:

\begin{align} \min_{x}\quad & f_{0}\left(x\right) + \sum_{i=1}^{m} I_{-}\left(f_{i}\left(x\right)\right) \\ \textrm{s.t.} \quad & Ax = b \end{align}

where I\left(u\right) = \infty for u > 0, otherwise 0.
logarithmic barrier Reformulate:

\begin{align} \min_{x}\quad & f_{0}\left(x\right) - \left(\frac{1}{t}\right) \sum_{i=1}^{m} \log \left(-f_{i}\left(x\right)\right) \\ \textrm{s.t.} \quad & Ax =b \end{align}

where for t>0, t\to \infty is the indicator barrier. The problem with solving this via the Newton’s Method will result in huge third derivative because of the log shooting up.
central path Consider:

\begin{align} \min_{x}\quad & t f_{0}\left(x\right) + \phi\left(x\right) \\ \textrm{s.t.} \quad & Ax = b \end{align}

same formulation as above scaled by t. Let’s define x^{*}\left(t\right) as the solution of the above in terms of t. We call the path traced by x^{*}\left(t\right) as the central path given by x^{*}.
duality gap Compute the dual for the lower bound. We will eventually obtain that:

\begin{equation} p^{*} \geq f_{0}\left(x^{*}\right) - \frac{m}{t} \end{equation}

where m is the number of inequalities.
intuition using KKT Conditions Instead the usual complementary slackness, we obtain:

\begin{equation} -\lambda_{i} f_{i}\left(x\right) = 0 \end{equation}

The complementary slackness of this expression would be:

\begin{equation} -\lambda_{i}f_{i}\left(x\right) = \frac{1}{t} \end{equation}

which is “almost satisfying” for the KKT conditions.
barrier method pathway to solutions intuition: parameterize F such that F\left(x, \theta\right) such that F\left(x\right) = F\left(x,1\right), F\left(x, 0\right) = 0. And then solve slowly starting from 0, …, 0.5, …. 1
centering: compute x^{*}\left(t\right) by by minimizing t f_{0} + \phi, subject to Ax = b, using infeasible newton’s method or something; start at cached x update: set x = x^{*}\left(t\right) check if \frac{m}{t} < \varepsilon increase t := \mu t we find that this process’s growth of number of iterations very slowly as m increases, and thus is roughly sublinear / constant.
phase-1 methods A conventional barrier method would need a strictly feasible starting point (if you use infeasible newton’s method you don’t even need to…) So this is rarely used.
But phase-1 methods solve a set of inequalities for the feasibility problem. We do this by introducing slack variable s such that:

\begin{align} \min_{x,s}\quad & s \\ \textrm{s.t.} \quad & f_{i}\left(x\right) \leq s \\ & Ax =b \end{align}

with optimal value \bar{p}^{*}. We can solve this either…
choose an x to start such that Ax =b, choose s = 1 + \max_{i}f_{i}\left(x\right) — this will put things up to the edge and give up; so spiky minimize 1^{T}s such that s \succeq 0, f_{i}\left(x\right) \leq s_{i} — this will find a strictly feasible point if one exists; so even if infesabile it wil try to keep pushing Newton Iteration Per Step x^{*} = x^{*}\left(\mu t\right). And thus, self-concordance theory gives:

\begin{equation} \text{#Newton iter} \leq \frac{u tf_{0}\left(x\right) + \phi\left(x\right) - \mu t f_{0}\left(x^{+}\right) - \phi\left(x^{+}\right)}{\gamma} + c \end{equation}

\begin{equation} \log u \leq m\left(\mu - 1 - \log\mu\right) \end{equation}

and so for a choice of \mu (barrier change scale) with barrier methods for \mu = 1 + \frac{1}{\sqrt{m}}, we can figure out the number of iteration is the order of :

\begin{equation} N = O\left(\sqrt{m} \log\left(\frac{\frac{m}{t^{(0)}}}{\varepsilon }\right)\right) \end{equation}

inheritor point for generalized inequalities \begin{align} \min_{m}\quad & f_{0}\left(x\right) \ \textrm{s.t.} \quad & f_{i}\left(x\right) \preceq_{k_{i}} 0, i = 1 \dots m \ & Ax =b \end{align}
for some generalized inequality
log barrier with central path For fi\left(x\right) ≼k_1 0 …

\begin{equation} \phi\left(x\right) = - \sum_{i=1}^{m} \psi \left(-f_{i}\left(x\right)\right) \end{equation}

where \psi is the generalized logarithm over k