Interior Point Method

“Justice will not be served until those who are unaffected are as outraged as those who are. – Benjamin Franklin”

Summary:

Starts within a feasible region, using a slack variable that is always >= 0 to convert all inequality constraints to equality constraints.

Intuition:

Punish the proximity to the constraint instead of the violation of it.

Steps:

  1. Introduce slack variables in inequality conditions, convert them to equality condition.

  2. Convert objective function to Lagrangian form, with additional term of -ve log of slack variable.

  3. To satisfy KKT conditions of the new objective function, we obtained as system of linear equations.

  4. Rearrange the system of linear equations into symmetric linear system of equations, by only including the non-slack variables. Solving it explictly.

  5. Use the solution from step 4 above to find the search direction of slack variable.

  6. Use line search methods to find a step size that optimizes the merit function.

  7. Optimize iteratively by repeating the steps above.

Reference:

https://www.youtube.com/watch?v=zm4mfr-QT1E