# Minimizing 1D convex function without derivatives?

I have a function which is nicely behaved, but expensive to compute. What's the fastest way to get 2-3 digits of accuracy?

Using NMinimize is much slower calling Plot and eyeballing the minimum, both are too slow since I need to solve this minimization problem a couple thousand times. Even after downgrading all of [AccuracyGoal, PrecisionGoal, MaxIterations] it takes a while, so I may be missing some magic options.

(* Find number of steps needed for SGD to achieve lossFactor \
reduction in loss *)
stepsSGDopt[h_, lossFactor_, relativeAlpha_] :=
Module[{d, ii, X2, \[Alpha], mat, ones, evals, evecs,
partialProduct, fastMatrixPower, objfunc, loss0, lossTarget, k,
alphaCrit},

d = Length[h];
ii = IdentityMatrix[d];
X2 = DiagonalMatrix[h];
ones = ConstantArray[1., {d}];
alphaCrit = 2/(2 Max[h] + Total[h]);
\[Alpha] = relativeAlpha*alphaCrit;

(* Matrix governing evolution of diagonal cov for Gaussian SGD *)
mat =
ii - 2 \[Alpha] X2 +
2 \[Alpha]^2 X2 . X2 + \[Alpha]^2 Outer[Times, h, h];

(* 100x faster version of MatrixPower[mat,k,ones].h *);
{evals, evecs} = Eigensystem[mat];
partialProduct = Inverse[evecs\[Transpose]] . ones;
fastMatrixPower = Compile[{{k, _Real}},
(evecs\[Transpose] . (evals^k*partialProduct)) . h
];
objfunc[k_?NumericQ] := fastMatrixPower[k];

loss0 = Total[h];
lossTarget = loss0/lossFactor;
Assert[lossTarget < Total[h]];
k /. FindRoot[objfunc[k] == lossTarget, {k, 2}]
];

d = 50;
h = RandomReal[{0, 1}, {d}];
lossFactor = 20;
Plot[stepsSGDopt[h, lossFactor, alpha], {alpha, 0.01, 1}]
objfunc[relativeAlpha_?NumericQ] :=
stepsSGDopt[h, lossFactor, relativeAlpha];
NMinimize[{objfunc[alpha], 0.1 < alpha < 1}, alpha]

• How about FindMinimum[..., {x, x0, x1}], which if I remember correctly is only numeric? Sep 19 at 6:03
• @HansOlo the difference is, FindMinimum looks for local minimum while NMinimize finds the global one. Sep 19 at 6:05

NMinmize looks for a global minimum. Since we know objfunc is convex (which MMA cannot easily infer), FindMinimum would be more efficient, which looks for local minimum.

NMinimize[{objfunc[alpha], 0.1 < alpha < 1}, alpha, PrecisionGoal -> 2] //Timing

{13.4694, {162.201, {alpha -> 0.507269}}}

FindMinimum[{objfunc[alpha], 0.1 < alpha < 1}, {alpha, 0.5}, PrecisionGoal -> 2] // Timing

{0.430142, {162.201, {alpha -> 0.507269}}}
$$$$


BayesianMinimization can be also usefull here.

Objective with counter:

count = 0 ;
objfunc[relativeAlpha_?NumericQ] := (count++; stepsSGDopt[h, lossFactor, relativeAlpha]) ;


FindMinimum:

count = 0 ;
FindMinimum[{objfunc[alpha], 0.1 < alpha < 1}, {alpha, 0.5}, AccuracyGoal -> 2]
count
(* {168.911243232702,{alpha\[Rule]0.5156544651037186}} *)
(* 48 *)


BayesianMinimization:

count = 0 ;
bo = BayesianMinimization[objfunc, Interval[{0.1, 1.0}], Method -> "MaxExpectedImprovement"] ;
bo["MinimumConfiguration"]
count
(* 0.5148846730372676 *)
(* 15 *)


You can control BayesianMinimization manually by setting two iterations at first and then using one iteration and previous history.