Interior point method for unconstrained problems

Question

I was recently working on applying the FindMinimum function to $f(x)=(x+1)(x-1)$, and chose the interior point method as the 'method', which yielded $x=0$. I would like to better understand how the interior point method works (is implemented) in this unconstrained case. Thanks!

The command and the result are indicated below:

FindMinimum[(x + 1) (x - 1), x, Method -> "InteriorPoint"]

Answer 1

Not a complete answer, but one can get some idea of what is going on behind the scenes by keeping track of the values at which the function is evaluated:

f[x_?NumericQ]:=(Sow[x];(x+1)*(x-1));
Reap[FindMinimum[f[x],x,Method->"InteriorPoint"]]

The output tells us that the function was evaluated at

0.9999939445455476
1.0000060554544523
-4.000024221798069
-3.99997577816245
-4.000024221798069
-3.99997577816245
-4.000024221798069
-3.99997577816245, 
-4.000488281230257
-3.9995117187302616
-4.000464056455683
-3.9994874998692174, 
-3.9999999999802593
-9.247662058342598*^-8
-6.147931072976769*^-6
5.962977831809917*^-6
-0.00012216278912058343
0.00012197783587941657
-0.00011610733466819008 
0.00012803329033180992
-9.247662058342598*^-8

This changes when another Method is used.

Alternative syntax. This gives the same result as above:

f[x_?NumericQ]:=(x+1)*(x-1);
Reap[FindMinimum[f[x],x,Method->"InteriorPoint",
                 EvaluationMonitor:>Sow[x]]]

This gives a different result:

Reap[FindMinimum[(x+1)*(x-1),x,Method->"InteriorPoint",
                 EvaluationMonitor:>Sow[x]]]

Answer 2

The code may be inspected with GeneralUtilities`PrintDefintions. The principal components of the method are the 1st, 2nd, and 4th functions here:

Names["*`*IPSolve*"]
(*
{"Optimization`NonlinearInteriorPointDump`IPSolve", \
"Optimization`NonlinearInteriorPointDump`IPSolveInternal", \
"Optimization`NonlinearInteriorPointDump`IPSolveMessage", \
"Optimization`NonlinearInteriorPointDump`IPSolveOneIter"}
*)

The method has built-in debug hooks implemented as bit-flags:

Names["O*`*DEBUG*"]
(*
{"Optimization`NonlinearInteriorPointDump`DEBUG", \
"Optimization`NonlinearInteriorPointDump`DEBUGcomplementary", \
"Optimization`NonlinearInteriorPointDump`DEBUGdirection", \
"Optimization`NonlinearInteriorPointDump`DEBUGfilter", \
"Optimization`NonlinearInteriorPointDump`DEBUGIterations", \
"Optimization`NonlinearInteriorPointDump`DEBUGLinearSolve", \
"Optimization`NonlinearInteriorPointDump`DEBUGMonitor", \
"Optimization`NonlinearInteriorPointDump`DEBUGNewton", \
"Optimization`NonlinearInteriorPointDump`DEBUGPenaltyIncrease", \
"Optimization`NonlinearInteriorPointDump`DEBUGpoints", \
"Optimization`NonlinearInteriorPointDump`DEBUGProblemdef", \
"Optimization`NonlinearInteriorPointDump`DEBUGrhs", \
"Optimization`NonlinearInteriorPointDump`DEBUGScaling", \
"Optimization`NonlinearInteriorPointDump`DEBUGstep", \
"Optimization`NonlinearInteriorPointDump`DEBUGsteplength"}
*)

They may be toggled on/off with comments as follows:

Block[{Optimization`NonlinearInteriorPointDump`DEBUG =
    (*2^Optimization`NonlinearInteriorPointDump`DEBUGProblemdef+*)
    2^Optimization`NonlinearInteriorPointDump`DEBUGIterations +
    2^Optimization`NonlinearInteriorPointDump`DEBUGstep +
    (*2^Optimization`NonlinearInteriorPointDump`DEBUGNewton+*)
    2^Optimization`NonlinearInteriorPointDump`DEBUGMonitor},
 FindMinimum[(x + 1)*(x - 1), x, Method -> "InteriorPoint"]
 ]

The code is complicated, but I suspect the method follows the standard IP algorithm. Between the code and the debug, it might take just a morning to figure the outline of how it works.