A one-phase interior point method for nonconvex optimization

This package is the implementation of a one-phase interior point method that finds KKT points of optimization problems of the form:

where the functions and are twice differentiable. The one-phase algorithm also handles bound constraints and nonlinear equalities.

Currently, the package is in development. Although you are welcome to try it out. Please let me know if there are any bugs etc. Note that the code is generally significantly slower than Ipopt in terms of raw runtime, particularly on small problems (the iteration count is competitive). However, we recommend trying our one-phase IPM if: Ipopt is failing to solve, the problem is very large or might be infeasible.

How to install

add https://github.com/ohinder/advanced_timer.jl
add https://github.com/ohinder/OnePhase.git

How to use with JuMP

Here is a simple example where a JuMP model is passed to the one-phase solver

using OnePhase, JuMP

m = Model(solver=OnePhaseSolver())
@variable(m, x, start=-3)
@objective(m, Min, x)
@NLconstraint(m, x^2 >= 1.0)
@NLconstraint(m, x >= -1.0)

status = solve(m)

Example using CUTEst

Install CUTEst then run

using OnePhase, CUTEst
nlp = CUTEstModel("CHAIN")
iter, status, hist, t, err, timer = one_phase_solve(nlp);
@show get_original_x(iter) # gives the primal solution of the solver
@show get_y(iter) # gives the dual solution of the solver

Feedback?

If you have found some bug or think there is someway I can improve the code feel free to contact me! My webpage is https://stanford.edu/~ohinder/.

Solver output

it = iteration number

step = step type, either stabilization step (s) or aggressive step (a)

eta = targeted reduction in feasibility/barrier parameter, eta=1 for stabilization steps eta<1 for aggressive steps

α_P = primal step size

α_D = dual step size

ls = number of points trialled during line search

|dx| = infinity norm of primal direction size

|dy| = infinity norm of dual direction size

N err = relative error in linear system solves.

mu = value of barrier parameter

dual = gradient of lagragian scaled by largest dual variable

primal = error in primal feasibility

cmp scaled = | Sy |/(1 + |y|)

inf = how close to infeasible problem is, values close to zero indicate infeasibility

delta = size of perturbation

#fac = number of factorizations (split into two numbers -- first is how many factorization needed to ensure primal schur complement is positive definite, second number represents total number of factorizations including any increases in delta to avoid issues when direction quality is very poor)

|x| = infinity norm of x variables

|y| = infinity norm of y variables

∇phi = gradient of log barrier

phi = value of log barrier