Numerical Methods and Optimization

Constrained Optimization 381

14.4.3 Interior point methods

Interior point methods take advantage of fast convergence of Newton’s

method for approximately solving the barrier problems. They are generally

preferred to other available techniques for convex optimization due to their su-

perior theoretical convergence properties and excellent practical performance.

Consider the problem

minimize f(x)

subject to h(x)=0

g(x) ≤ 0,

where f(x):IR

n

→ IR ,h(x):IR

n

→ IR

m

(m<n), and g(x):IR

n

→ IR

p

.

Introducing p slack variables given by a p-dimensional vector s, we obtain the

following equivalent problem:

minimize f(x)

subject to h(x)=0

g(x)+s =0

s ≥ 0.

Using the logarithmic barrier for the nonnegativity constraints, we write the

corresponding barrier problem

minimize f(x) −