# High speed box constrained optimization with FindMinimum

Posted 1 year ago
2325 Views
|
2 Replies
|
8 Total Likes
|

# 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:
Answer
2 Replies
Sort By:
Posted 1 year ago
 - Congratulations! This post is now Staff Pick! Thank you for your wonderful contributions. Please, keep them coming!
Answer
Posted 1 year 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} ]
Answer
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments