InteriorPoint



In [15]:
from IPython.display import HTML

HTML('''
<script>
  function code_toggle() {
    if (code_shown){
      $('div.input').hide('500');
      $('#toggleButton').val('Show Code')
    } else {
      $('div.input').show('500');
      $('#toggleButton').val('Hide Code')
    }
    code_shown = !code_shown
  }

  $( document ).ready(function(){
    code_shown=false;
    $('div.input').hide()
  });
</script>
<form action="javascript:code_toggle()"><input type="submit" id="toggleButton" value="Show Code"></form>
<ul>
<li>The code is in Python. Matlab does not work with the interactive elements used in this notebook.
<li>The current version of ipywidgets shows only static images online.  Interactivity can only be viewed by downloading and running in a Jupyter Notebook server.  The next version of ipywidgets will permit online viewing of interactivity.
</ul>
''')


Out[15]:
  • The code is in Python. Matlab does not work with the interactive elements used in this notebook.
  • The current version of ipywidgets shows only static images online. Interactivity can only be viewed by downloading and running in a Jupyter Notebook server. The next version of ipywidgets will permit online viewing of interactivity.

Interior Point Methods

Let's do a simple 1D problem, just for illustration:

\begin{align} \text{minimize} &\quad f(x) = -x\\ \text{subject to} &\quad x \le 5 \end{align}

Clearly, the answer is $x^* = 5$, but let's see how it looks like with a (simplified) interior point approach. First, let's write our constraint in a standard constraint form $c(x) \le 0$ and form a new objective.

$$c(x) = x - 5 \le 0$$

Thus,

\begin{align} \pi(x) &= f(x) - \mu \log(-c(x)) \\ &= -x - \mu \log(5 - x) \end{align}

First, let's just plot the penalty portion $-\mu\log(-c(x))$, starting with the case $\mu = 1$.


In [16]:
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('fivethirtyeight')

x = np.linspace(0, 4.9999, 1000)

plt.figure()
plt.plot(x, -np.log(5 - x))
plt.xlim([0, 5.2])
plt.show()


We can see that it actus like a steep wall near $x=5$ with small effect elsewhere. The next example is interactive, letting you set a $\mu$. Notice that as $\mu$ becomes smaller and smaller the penalty more closely represents a perfect barrier.


In [17]:
from ipywidgets import interact

@interact(mu=(0.1, 2.0, 0.1))
def logbarrier(mu):
    f = -mu*np.log(5 - x)
    plt.plot(x, f)
    plt.xlim([0, 5.1])
    plt.ylim([-2, 2])
    plt.xlabel('x')
    plt.ylabel('f')
    plt.show()


Let's now plot this objective plus the penalty, or in other words our new function to minimize. We start with $\mu = 1.0$. Also shown for reference is the line $f(x) = -x$ which is the objective function. The constraint $x \le 5$ is like a wall at $x = 5$. We see that the log function creates a barrier that approximates the wall. As we decrease the valye of $\mu$, the barrier will increase in steepness and closer approximate the wall.


In [18]:
plt.figure()
plt.plot(x, -x, 'k--')
mu = 1.0
f = -x - mu*np.log(5 - x)
plt.plot(x, f)
plt.xlim([0, 5.1])
plt.ylim([-5, 2])
plt.xlabel('x')
plt.ylabel('f')
plt.show()


We can add a slider to try a range of values of $\mu$.


In [19]:
@interact(mu=(0.1, 2.0, 0.1))
def barrier(mu):
    f = -x - mu*np.log(5 - x)
    plt.plot(x, -x, 'k--')
    plt.plot(x, f)
    plt.xlim([0, 5.1])
    plt.ylim([-5, 2])
    plt.xlabel('x')
    plt.ylabel('f')
    idx = np.argmin(f)
    plt.plot(x[idx], f[idx], 'r*', ms=14)
    plt.show()


For those of you viewing this statically, rather than interactively, here are a few snapshots at $\mu = 1.0, 0.5, 0.25, \text{ and } 0.125$


In [20]:
plt.figure()
plt.plot(x, -x, 'k--')

muvec = [1.0, 0.5, 0.25, 0.125]

for mu in muvec:

    f = -x - mu*np.log(5 - x)
    plt.plot(x, f)

plt.xlim([0, 5.1])
plt.ylim([-5, 2])
plt.xlabel('x')
plt.ylabel('f')
plt.show()



In [ ]: