---
title: "Interior Point Method"
source: https://www.jemoka.com/posts/kbhinterior_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 &amp; f_{0}\qty(x) \\ \textrm{s.t.} \quad &amp; f_{i}\qty(x) \leq 0, i = 1\dots m \\ &amp; Ax =b \end{align}
convex, tie differentiable \(p^{*}\) is finite and attained strictly feasible These include&hellip; LP, QP, QCQP, geometric program.
indicator barrier Reformulate:
\begin{align} \min_{x}\quad &amp; f_{0}\qty(x) + \sum_{i=1}^{m} I_{-}\qty(f_{i}\qty(x)) \\ \textrm{s.t.} \quad &amp; Ax = b \end{align}
where \(I\qty(u) = \infty\) for \(u &gt; 0\), otherwise \(0\).
logarithmic barrier Reformulate:
\begin{align} \min_{x}\quad &amp; f_{0}\qty(x) - \qty(\frac{1}{t}) \sum_{i=1}^{m} \log \qty(-f_{i}\qty(x)) \\ \textrm{s.t.} \quad &amp; Ax =b \end{align}
where for \(t&gt;0\), \(t\to \infty\) is the indicator barrier. The problem with solving this via the Newton&rsquo;s Method will result in huge third derivative because of the log shooting up.
central path Consider:
\begin{align} \min_{x}\quad &amp; t f_{0}\qty(x) + \phi\qty(x) \\ \textrm{s.t.} \quad &amp; Ax = b \end{align}
same formulation as above scaled by \(t\). Let&rsquo;s define \(x^{*}\qty(t)\) as the solution of the above in terms of \(t\). We call the path traced by \(x^{*}\qty(t)\) 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}\qty(x^{*}) - \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}\qty(x) = 0 \end{equation}
The complementary slackness of this expression would be:
\begin{equation} -\lambda_{i}f_{i}\qty(x) = \frac{1}{t} \end{equation}
which is &ldquo;almost satisfying&rdquo; for the KKT conditions.
barrier method pathway to solutions intuition: parameterize \(F\) such that \(F\qty(x, \theta)\) such that \(F\qty(x) = F\qty(x,1)\), \(F\qty(x, 0) = 0\). And then solve slowly starting from 0, &hellip;, 0.5, &hellip;. 1
centering: compute \(x^{*}\qty(t)\) by by minimizing \(t f_{0} + \phi\), subject to \(Ax = b\), using infeasible newton&rsquo;s method or something; start at cached \(x\) update: set \(x = x^{*}\qty(t)\) check if \(\frac{m}{t} &lt; \varepsilon\) increase \(t := \mu t\) we find that this process&rsquo;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&rsquo;s method you don&rsquo;t even need to&hellip;) 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 &amp; s \\ \textrm{s.t.} \quad &amp; f_{i}\qty(x) \leq s \\ &amp; Ax =b \end{align}
with optimal value \(\bar{p}^{*}\). We can solve this either&hellip;
choose an \(x\) to start such that \(Ax =b\), choose \(s = 1 + \max_{i}f_{i}\qty(x)\) &mdash; this will put things up to the edge and give up; so spiky minimize \(1^{T}s\) such that \(s \succeq 0\), \(f_{i}\qty(x) \leq s_{i}\) &mdash; 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^{*}\qty(\mu t)\). And thus, self-concordance theory gives:
\begin{equation} \text{#Newton iter} \leq \frac{u tf_{0}\qty(x) + \phi\qty(x) - \mu t f_{0}\qty(x^{+}) - \phi\qty(x^{+})}{\gamma} + c \end{equation}
\begin{equation} \log u \leq m\qty(\mu - 1 - \log\mu) \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\qty(\sqrt{m} \log\qty(\frac{\frac{m}{t^{(0)}}}{\varepsilon })) \end{equation}
inheritor point for generalized inequalities \begin{align} \min_{m}\quad &amp; f_{0}\qty(x) \\ \textrm{s.t.} \quad &amp; f_{i}\qty(x) \preceq_{k_{i}} 0, i = 1 \dots m \\ &amp; Ax =b \end{align}
for some generalized inequality
log barrier with central path For $fi\qty(x) ≼k_1 0 &hellip;$
\begin{equation} \phi\qty(x) = - \sum_{i=1}^{m} \psi \qty(-f_{i}\qty(x)) \end{equation}
where \(\psi\) is the generalized logarithm over \(k\)
