Primal-Dual Interior-Point Method

Definition

An interior point optimization technique used to solve constrained optimization problems. Converging and accuracy are faster than Barrier Method

Algorithm

Consider the optimization problem with an inequality constraint

$\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

The KKT Conditions of the problem are the following

• $\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$^[Stationarity]
• $h(x)=0,g(x)\le 0$^[Primal feasibility]
• $\mu \ge 0$^[Dual feasibility]
• $\mu g(x)=0$^[Complementary slackness]

Interior point methods solve the problem whose complementary slackness condition is relaxed $\mu g(x)=-t$ where $t>0$

Instead of substituting $\mu$ in the stationary condition with $-\frac{t}{g(x)}$ like the Barrier Method, Primal-dual interior method directly solve the problem with Newton’s Method

Now, the conditions have to be satisfied are the following

• $\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$
• $\mu g(x)+t=0$
• $h(x)=0$
• $t>0$

and the problem with inequality become the problem with equality $\underset{x}{\min }f(x)$ subject to $\mu g(x)+t=0,h(x)=0$

It can be solved using Newton’s Method