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:

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

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

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:

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:

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

The complementary slackness of this expression would be:

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:

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:

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 :

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 …

where \psi is the generalized logarithm over k