Message Boards Message Boards

High speed box constrained optimization with FindMinimum

GROUPS:

Method


FindMinimum allows setting bounds on variables (box-constrained minimization) but does not find the minimum, instead giving a warning that the boundary was reached.

In[6]:= AbsoluteTiming @ 
 FindMinimum[(x - 1.5)^2 + (y + 1.3)^2, {{x, 0, -1, 1}, {y, 0, -1, 1}}]

During evaluation of In[6]:= FindMinimum::reged: The point {1.,-0.866667} is at the edge of the search region {-1.,1.} in coordinate 1 and the computed search direction points outside the region.

Out[6]= {0.00137144, {0.437778, {x -> 1., y -> -0.866667}}}

Rerunning the optimization, eliminating the variable at its bound finds the actual minimum.

In[11]:= AbsoluteTiming @ 
 FindMinimum[(x - 1.5)^2 + (y + 1.3)^2 /. x -> 1, {{y, 0, -1, 1}}]

Out[11]= {0.000507734, {0.34, {y -> -1.}}}

This is much faster than putting in the bounds in as constraints.

In[5]:= AbsoluteTiming @ 
 FindMinimum[{(x - 1.5)^2 + (y + 1.3)^2, -1 <= x <= 1, -1 <= y <= 
    1}, {{x, 0}, {y, 0}}]

Out[5]= {0.0341419, {0.34, {x -> 1., y -> -1.}}}

The function in the attached file automates this process, repeatedly elimating variables which reach their bounds, and is much faster than putting in constraints.

In[10]:= AbsoluteTiming @ 
 fmbox[(x - 1.5)^2 + (y + 1.3)^2, {{x, 0, -1, 1}, {y, 0, -1, 1}}]

Out[10]= {0.000847333, {0.34, {x -> 1, y -> -1.}}}

Automated function


fmbox[obj_,vwbi_List]:=
Block[{nvars,newobj,starts,var,init,lb,ub,testlist,resrls,fmres,allrls,test,objrl,val,bndvars},
Off[FindMinimum::reged];
nvars = Length[vwbi];
newobj = obj;
starts = vwbi;
testlist = Flatten[vwbi /. {var_,lb_?NumberQ, init_?NumberQ, ub_?NumberQ}-> {var == lb, var==ub}];
resrls = {};
allrls=Do[
fmres = FindMinimum[newobj,starts];
test = Select[testlist,#/. fmres[[2]]&];
If[Length[test]==0,
Return[Join[resrls,fmres[[2]]]],
objrl = test /. Equal[var_,val_?NumberQ] -> (var -> val);
newobj = newobj /. objrl;
bndvars = objrl[[All,1]];
starts = Select[starts,!MemberQ[bndvars,#[[1]]]&];
resrls = Join[resrls,objrl];
If[nvars==Length[resrls],Return[resrls]];
]; (*End If *)
,{i,nvars}]; (* End Do *)
{obj /.allrls,allrls}
]

Benchmarking

AbsoluteTiming @ fmbox[(x - .5)^2 + (y + .3)^2, {{x, 0, -1, 1}, {y, 0, -1, 1}}]

{0.000608449, {0., {x -> 0.5, y -> -0.3}}}

AbsoluteTiming @ fmbox[(x - 1.5)^2 + (y + .3)^2, {{x, 0, -1, 1}, {y, 0, -1, 1}}]

{0.00110092, {0.25, {x -> 1, y -> -0.3}}}

AbsoluteTiming @ fmbox[(x - 1.5)^2 + (y + 1.3)^2, {{x, 0, -1, 1}, {y, 0, -1, 1}}]

{0.000847333, {0.34, {x -> 1, y -> -1.}}}

Attachments:
POSTED BY: Frank Kampas
Answer
7 months ago

enter image description here - Congratulations! This post is now Staff Pick! Thank you for your wonderful contributions. Please, keep them coming!

POSTED BY: Moderation Team
Answer
7 months ago

Found an error in the code. Here's the corrected function.

fmbox[obj_, vwbi_List] :=
 Block[{nvars, newobj, starts, var, init, lb, ub, testlist, resrls, 
   fmres, allrls, test, objrl, val, bndvars},
  Off[FindMinimum::reged];
  nvars = Length[vwbi];
  newobj = obj;
  starts = vwbi;
  testlist = 
   Flatten[vwbi /. {var_, init_?NumberQ, lb_?NumberQ, 
       ub_?NumberQ} -> {var == lb, var == ub}];
  resrls = {};
  allrls = Do[
    fmres = FindMinimum[newobj, starts];
    test = Select[testlist, # /. fmres[[2]] &];
    If[Length[test] == 0,
     Return[Join[resrls, fmres[[2]]]],
     objrl = test /. Equal[var_, val_?NumberQ] -> (var -> val);
     newobj = newobj /. objrl;
     bndvars = objrl[[All, 1]];
     starts = Select[starts, ! MemberQ[bndvars, #[[1]]] &];
     resrls = Join[resrls, objrl];
     If[nvars == Length[resrls], Return[resrls]];
     ]; (*End If *)
    , {i, nvars}]; (* End Do *)
  {obj /. allrls, allrls}
  ]
POSTED BY: Frank Kampas
Answer
7 months ago

Group Abstract Group Abstract