

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 [ ]: