[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhinterior_point_method.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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 & f_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) \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}\qty(x) + \sum_{i=1}^{m} I_{-}\qty(f_{i}\qty(x)) \\ \textrm{s.t.} \quad & Ax = b \end{align} where \(I\qty(u) = \infty\) for \(u > 0\), otherwise \(0\). logarithmic barrier Reformulate: \begin{align} \min_{x}\quad & f_{0}\qty(x) - \qty(\frac{1}{t}) \sum_{i=1}^{m} \log \qty(-f_{i}\qty(x)) \\ \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}\qty(x) + \phi\qty(x) \\ \textrm{s.t.} \quad & Ax = b \end{align} same formulation as above scaled by \(t\). Let’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 “almost satisfying” 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, …, 0.5, …. 1 centering: compute \(x^{*}\qty(t)\) 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^{*}\qty(t)\) 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}\qty(x) \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}\qty(x)\) — 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}\) — 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 & f_{0}\qty(x) \\ \textrm{s.t.} \quad & f_{i}\qty(x) \preceq_{k_{i}} 0, i = 1 \dots m \\ & Ax =b \end{align} for some generalized inequality log barrier with central path For $fi\qty(x) ≼k_1 0 …$ \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\)