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

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\)
2. update: set \(x = x^{*}\qty(t)\)
3. check if \(\frac{m}{t} < \varepsilon\)
4. 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 $f_i\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\)