{"id":145,"date":"2008-07-08T14:05:11","date_gmt":"2008-07-08T19:05:11","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2008\/07\/08\/help-i-got-the-wrong-answer-for-my-optimization\/"},"modified":"2008-06-27T14:16:59","modified_gmt":"2008-06-27T19:16:59","slug":"help-i-got-the-wrong-answer-for-my-optimization","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2008\/07\/08\/help-i-got-the-wrong-answer-for-my-optimization\/","title":{"rendered":"HELP &#8211; I Got the Wrong Answer for My Optimization!"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>How often I have heard this!?!  It turns out there are a bunch of reasons why you might not get the answer you expect when\r\n         performing an optimization task.  These possibilities include the answer not being unique, the optimization method used isn't\r\n         global and therefore returns a local optimal solution, and the problem, as stated, isn't the problem you really want to solve.\r\n          Let me tell you more about a recent case.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">What We Heard<\/a><\/li>\r\n         <li><a href=\"#2\">The Function<\/a><\/li>\r\n         <li><a href=\"#3\">Run the Example<\/a><\/li>\r\n         <li><a href=\"#7\">Why Did the Optimization Not Find Zero?<\/a><\/li>\r\n         <li><a href=\"#9\">How to Fix the Optimization<\/a><\/li>\r\n         <li><a href=\"#10\">Change the Objective Function<\/a><\/li>\r\n         <li><a href=\"#13\">Have You Hit a Similar Snag?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>What We Heard<a name=\"1\"><\/a><\/h3>\r\n   <p>We heard from a user that <a href=\"https:\/\/www.mathworks.com\/help\/optim\/ug\/fmincon.html\"><tt>fmincon<\/tt><\/a>, from <a href=\"https:\/\/www.mathworks.com\/products\/optimization\/\">Optimization Toolbox<\/a>, gets the wrong answer for the problem posed in <tt>myOptFun<\/tt>.  In fact, the optimization gets stuck at the initial point.\r\n   <\/p>\r\n   <h3>The Function<a name=\"2\"><\/a><\/h3>\r\n   <p>Let's take a quick look at the function.  The user told us that it was a simple <a href=\"http:\/\/en.wikipedia.org\/wiki\/Paraboloid\">paraboloid of revolution<\/a>. I'll calculate <tt>z<\/tt> values on a grid and display as a surface.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">[xx,yy] = meshgrid(-2:.1:2);\r\nzz = xx.^2+yy.^2;\r\nsurfc(xx,yy,zz)\r\nshading <span style=\"color: #A020F0\">interp<\/span>\r\ncolorbar\r\nview(-37.5,50)<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/loren\/145\/optimAcc_01.png\"> <h3>Run the Example<a name=\"3\"><\/a><\/h3>\r\n   <p>First I do some housekeeping.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">opt = optimset(<span style=\"color: #A020F0\">'display'<\/span>, <span style=\"color: #A020F0\">'final'<\/span>);\r\nwarning <span style=\"color: #A020F0\">off<\/span> <span style=\"color: #A020F0\">optim:fmincon:SwitchingToMediumScale<\/span><\/pre><p>Next, I'll run the example using the user's objective function.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">lb = [-5;-5];\r\nub = [5;5];\r\nx0 = [1;1];\r\n[x fval exitflag output lamb grad hess] = <span style=\"color: #0000FF\">...<\/span>\r\n           fmincon(@myOptFun,x0,[],[],[],[],lb,ub,[],opt);<\/pre><pre style=\"font-style:oblique\">Optimization terminated: first-order optimality measure less\r\n than options.TolFun and maximum constraint violation is less\r\n than options.TolCon.\r\nNo active inequalities.\r\n<\/pre><p>According the user, the optimal answer is <tt>0<\/tt> and can be found at <tt>(0,0)<\/tt>.  Instead, look what we find.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">x<\/pre><pre style=\"font-style:oblique\">x =\r\n     1\r\n     1\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">fval<\/pre><pre style=\"font-style:oblique\">fval =\r\n     2\r\n<\/pre><h3>Why Did the Optimization Not Find Zero?<a name=\"7\"><\/a><\/h3>\r\n   <p>The source of the confusion is in <tt>myOptFun<\/tt>.  Now let me show you the code.\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">type <span style=\"color: #A020F0\">myOptFun<\/span><\/pre><pre style=\"font-style:oblique\">\r\nfunction f = myOptFun(X)\r\nformule = 'x.*x+y.*y';\r\nformule = strrep(formule,'x',num2str(X(1)));\r\nformule = strrep(formule,'y',num2str(X(2)));\r\nf = eval(formule);\r\n<\/pre><p>It's the use of <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/num2str.html\"><tt>num2str<\/tt><\/a> specifically.  As the documentation says, the default format for <tt>num2str<\/tt> is <tt>'%11.4g'<\/tt> which means I am calculating results to 4 significant figures. Calling <tt>num2str(1)<\/tt>, the result is <tt>1<\/tt> and <b>the same is true<\/b> for <tt>num2str(1+1e-5)<\/tt>. In other words the accuracy of the customer's objective function cannot be expected to be better than 1e-4. However, the\r\n      default tolerances for <tt>TolFun<\/tt> and <tt>TolX<\/tt> are 1e-6. More importantly <tt>DiffMinChange<\/tt> (\"minimum change in variables for finite difference derivatives\") is 1e-8. When the first finite difference calculations\r\n      are done, the approximate first-order derivatives of the customer's objective function are zero and <tt>fmincon<\/tt> stops.\r\n   <\/p>\r\n   <h3>How to Fix the Optimization<a name=\"9\"><\/a><\/h3>\r\n   <p>I have several options for obtaining a \"better\" result.  I can<\/p>\r\n   <div>\r\n      <ul>\r\n         <li>increase the accuracy of the objective function<\/li>\r\n         <li>adjust the relevant tolerances to be larger to accomodate the resolution of the objective function<\/li>\r\n         <li>provide exact first-order derivatives (<tt>TolFun<\/tt> and <tt>TolX<\/tt> still need to be less than 1e-4).\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Change the Objective Function<a name=\"10\"><\/a><\/h3>\r\n   <p>Let's try the same optimization with a modified objective function.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">[xFixed fvalFixed exitflag output lamb grad hess] = <span style=\"color: #0000FF\">...<\/span>\r\n           fmincon(@myOptFunFixed,x0,[],[],[],[],lb,ub,[],opt);<\/pre><pre style=\"font-style:oblique\">Optimization terminated: first-order optimality measure less\r\n than options.TolFun and maximum constraint violation is less\r\n than options.TolCon.\r\nNo active inequalities.\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">xFixed<\/pre><pre style=\"font-style:oblique\">xFixed =\r\n  1.0e-015 *\r\n    0.4441\r\n   -0.2220\r\n<\/pre><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">fvalFixed<\/pre><pre style=\"font-style:oblique\">fvalFixed =\r\n  2.4652e-031\r\n<\/pre><h3>Have You Hit a Similar Snag?<a name=\"13\"><\/a><\/h3>\r\n   <p>If you have hit a similar snag, it would be great if you could share it <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p145#respond\">here<\/a>.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_0cfde2379332430ea2b1ae0432d0800e() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='0cfde2379332430ea2b1ae0432d0800e ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 0cfde2379332430ea2b1ae0432d0800e';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Loren Shure';\r\n        copyright = 'Copyright 2008 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_0cfde2379332430ea2b1ae0432d0800e()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.6<br><\/p>\r\n<\/div>\r\n<!--\r\n0cfde2379332430ea2b1ae0432d0800e ##### SOURCE BEGIN #####\r\n%% HELP - I Got the Wrong Answer for My Optimization!\r\n% How often I have heard this!?!  It turns out there are a bunch of reasons\r\n% why you might not get the answer you expect when performing an\r\n% optimization task.  These possibilities include the answer not being\r\n% unique, the optimization method used isn't global and therefore returns a\r\n% local optimal solution, and the problem, as stated, isn't the problem you\r\n% really want to solve.  Let me tell you more about a recent case.\r\n%% What We Heard\r\n% We heard from a user that \r\n% <https:\/\/www.mathworks.com\/help\/optim\/ug\/fmincon.html |fmincon|>, \r\n% from <https:\/\/www.mathworks.com\/products\/optimization\/ Optimization Toolbox>, \r\n% gets the wrong answer for the problem posed in |myOptFun|.  In fact, the\r\n% optimization gets stuck at the initial point.\r\n%% The Function\r\n% Let's take a quick look at the function.  The user told us that it was a\r\n% simple <http:\/\/en.wikipedia.org\/wiki\/Paraboloid paraboloid of revolution>.\r\n% I'll calculate |z| values on a grid and display as a surface.\r\n[xx,yy] = meshgrid(-2:.1:2);\r\nzz = xx.^2+yy.^2;\r\nsurfc(xx,yy,zz)\r\nshading interp\r\ncolorbar\r\nview(-37.5,50)\r\n%% Run the Example\r\n% First I do some housekeeping.\r\nopt = optimset('display', 'final');\r\nwarning off optim:fmincon:SwitchingToMediumScale\r\n%%\r\n% Next, I'll run the example using the user's objective function.\r\nlb = [-5;-5];\r\nub = [5;5];\r\nx0 = [1;1];\r\n[x fval exitflag output lamb grad hess] = ...\r\n           fmincon(@myOptFun,x0,[],[],[],[],lb,ub,[],opt);\r\n%%\r\n% According the user, the optimal answer is |0| and can be found at\r\n% |(0,0)|.  Instead, look what we find.\r\nx\r\n%%\r\nfval\r\n%% Why Did the Optimization Not Find Zero?\r\n% The source of the confusion is in |myOptFun|.  Now let me show you the\r\n% code.\r\ntype myOptFun\r\n%%\r\n% It's the use of \r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/num2str.html |num2str|> \r\n% specifically.  As the documentation says, the default format for |num2str| is\r\n% |'%11.4g'| which means I am calculating results to 4 significant figures.\r\n% Calling |num2str(1)|, the result is |1| and *the same is true* for\r\n% |num2str(1+1e-5)|. In other words the accuracy of the customer's\r\n% objective function cannot be expected to be better than 1e-4. However, the\r\n% default tolerances for |TolFun| and |TolX| are 1e-6.\r\n% More importantly |DiffMinChange| (\"minimum change in\r\n% variables for finite difference derivatives\") is 1e-8. When the first\r\n% finite difference calculations are done, the approximate first-order\r\n% derivatives of the customer's objective function are zero and |fmincon|\r\n% stops.\r\n%% How to Fix the Optimization\r\n% I have several options for obtaining a \"better\" result.  I can\r\n%\r\n% * increase the accuracy of the objective function\r\n% * adjust the relevant tolerances to be larger to accomodate the\r\n% resolution of the objective function\r\n% * provide exact first-order derivatives (|TolFun| and |TolX| still need\r\n% to be less than 1e-4).\r\n%\r\n%% Change the Objective Function\r\n% Let's try the same optimization with a modified objective function.\r\n[xFixed fvalFixed exitflag output lamb grad hess] = ...\r\n           fmincon(@myOptFunFixed,x0,[],[],[],[],lb,ub,[],opt);\r\n%%\r\nxFixed\r\n%%\r\nfvalFixed\r\n%% Have You Hit a Similar Snag?\r\n% If you have hit a similar snag, it would be great if you could share it\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p145#respond here>. \r\n\r\n##### SOURCE END ##### 0cfde2379332430ea2b1ae0432d0800e\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      How often I have heard this!?!  It turns out there are a bunch of reasons why you might not get the answer you expect when\r\n         performing an optimization task.  These... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2008\/07\/08\/help-i-got-the-wrong-answer-for-my-optimization\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[14,26,11],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/145"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=145"}],"version-history":[{"count":0,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/145\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}