3
$\begingroup$

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

Interior point method for an unconstrained problem

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

2 Answers 2

0
$\begingroup$

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]]]
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.