# Interior point method for unconstrained problems

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"]


• Look e.g. at: en.wikipedia.org/wiki/Interior-point_method Sep 13, 2022 at 19:55
• Interior to what? Sep 13, 2022 at 21:36
• Hello Daniel, thanks for your reply. My question above has been edited for clarity. Sep 14, 2022 at 15:18
• I cannot say for sure but possibly the non-default Method setting is just being ignored in this case. Sep 14, 2022 at 18:23

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]]]


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

Names["**IPSolve*"]
(*
{"OptimizationNonlinearInteriorPointDumpIPSolve", \
"OptimizationNonlinearInteriorPointDumpIPSolveInternal", \
"OptimizationNonlinearInteriorPointDumpIPSolveMessage", \
"OptimizationNonlinearInteriorPointDumpIPSolveOneIter"}
*)


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

Names["O**DEBUG*"]
(*
{"OptimizationNonlinearInteriorPointDumpDEBUG", \
"OptimizationNonlinearInteriorPointDumpDEBUGcomplementary", \
"OptimizationNonlinearInteriorPointDumpDEBUGdirection", \
"OptimizationNonlinearInteriorPointDumpDEBUGfilter", \
"OptimizationNonlinearInteriorPointDumpDEBUGIterations", \
"OptimizationNonlinearInteriorPointDumpDEBUGLinearSolve", \
"OptimizationNonlinearInteriorPointDumpDEBUGMonitor", \
"OptimizationNonlinearInteriorPointDumpDEBUGNewton", \
"OptimizationNonlinearInteriorPointDumpDEBUGPenaltyIncrease", \
"OptimizationNonlinearInteriorPointDumpDEBUGpoints", \
"OptimizationNonlinearInteriorPointDumpDEBUGProblemdef", \
"OptimizationNonlinearInteriorPointDumpDEBUGrhs", \
"OptimizationNonlinearInteriorPointDumpDEBUGScaling", \
"OptimizationNonlinearInteriorPointDumpDEBUGstep", \
"OptimizationNonlinearInteriorPointDumpDEBUGsteplength"}
*)


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

Block[{OptimizationNonlinearInteriorPointDumpDEBUG =
(*2^OptimizationNonlinearInteriorPointDumpDEBUGProblemdef+*)
2^OptimizationNonlinearInteriorPointDumpDEBUGIterations +
2^OptimizationNonlinearInteriorPointDumpDEBUGstep +
(*2^OptimizationNonlinearInteriorPointDumpDEBUGNewton+*)
2^OptimizationNonlinearInteriorPointDumpDEBUGMonitor},
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.

• Michael, do you happen to have an insight on how to make Gurobi work under Mathematica (please see this Q)? I have explored both the "GurobiLink" and "OptimizationMethodFramework" packages, with no success. Dec 18, 2023 at 11:04