4. Interior Point Method

In the following week I intend to implement the interior-point trust-region algorithm described in [1].

Consider the general nonlinear programming problem:

minimize_x f(x)
subject to: g(x) >= 0
            h(x)  = 0

Introducing slack variables, this problem can be rewritten as:

minimize_(x, s) f(x)
subject to: g(x) - s  = 0
            h(x)      = 0 
                   s >= 0

The basic idea of the interior point method being implemented is to solve, instead of the above problem, the equality-constrained barrier problem:

minimize_(x, s) f(x) - mu * sum(log(s))
subject to: g(x) - s  = 0
            h(x)      = 0 

for progressively smaller values of the barrier parameter mu. The basic idea is to use the previously implemented SQP solver successively to those problems. The way of doing this efficiently described in [1] is not trying to solve the equality problem exactly, but rather to solve it inexactly with increasing accuracy as the problem gets closer to the solution. The local behaviour of the algorithm for different strategies for decreasing mu and the equality constrained SQP tolerance are provided in [2].

• Theoretical revision
• Read paper [1];
• Write blog post about the method.
• Read paper [2];
• Implementation
• Implement interior point method described in [1].
  • Implement strategy to deal with negative Lagrange multipliers ([1] p.p. 883-884);
  • Implement strategy to avoid abrupt changes on Lagrange multipliers ([1] p. 884);
  • Implement strategy to avoid abrupt changes on Trust-radius ([1] p. 892)
  • Functions for computing objective function, constraints and derivatives for the barrier problem in x and s:
    • Constraints;
    • Constraints Jacobian: according to formula (3.13) from [1];
    • Barrier objective function;
    • Barrier objective function gradient;
    • Lagrangian Hessian: according to formula (3.31) from [1];
  • Implement stop criteria for the SQP solver;
• Write constraints parser.
• Implement strategy to guarantee feasibility of some constraints (Reference [3], p.576).
• Implement strategies to decrease barrier parameter mu according to [2];
• Implement strategies to decrease SQP solver tolerances according to [2].
• Better way to choose s0
• Bugs
  • NaN on CUTEst problems HS116 and HS109 -> Roundoff errors.
  • NaN on CUTEst problems HS112 and HS105 -> Objective function needed to reinforce feasible constraints.
  • SingularFactor on HS109 -> The problem did not repeat after the other modifications.
  • Fails on HS85, HS97 HS98 -> only use different initial barier parameter.
  • Fails on HS99 -> Reported on the original paper.
  • Too many iterations to converge on COSHFUN -> only use different initial barier parameter.
  • Fails on READING1 and OPTMASS -> Problems with derivatives.
  • Different number of interactions on DIXCHLNV on my different computers.
  • Too many iterations to converge on NGONE.
• Testing
• Unittests;
  • Test inequality nonlinear constraints.
  • Test unconstrained problem.
  • Test lower and upper bounds.
  • Test linear constraints.
• Test on problems from CUTEst.
  • CORKSCRW.
  • COSHFUN.
  • DIXCHLNV.
  • GAUSSELM.
  • HAGER4.
  • HIMMELBK.
  • NGONE.
  • OPTCNTRL.
  • OPTMASS.
  • ORTHREGF.
  • READING1.
  • SVANBERG.
  • HS*.

References

[1]    Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. "An interior point algorithm for large-scale nonlinear programming." SIAM Journal on Optimization 9.4 (1999): 877-900.

[2]     Byrd, Richard H., Guanghui Liu, and Jorge Nocedal. "On the local behavior of an interior point method for nonlinear programming." Numerical analysis 1997 (1997): 37-56.

[3]   Nocedal, Jorge, and Stephen J. Wright. "Numerical optimization" Second Edition (2006).