// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab // Copyright (C) 2008-2009 - INRIA - Michael Baudin // // This file must be used under the terms of the CeCILL. // This source file is licensed as described in the file COPYING, which // you should have received as part of this distribution. The terms // are also available at // http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt // References // Han, Lixing and Neumann, Michael(2006) // 'Effect of dimensionality on the Nelder-Mead simplex method', // Optimization Methods and Software,21:1,1 — 16 // // computeroots1 -- // Compute the roots of the characteristic equations of // usual Nelder-Mead method. // function computeroots1 ( n ) // Polynomial for outside contraction : // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0 mprintf("Polynomial for outside contraction :\n"); coeffs = zeros(1,n+1); coeffs(1) = n coeffs(2:n) = -3 coeffs(n+1) = 2 * n p=poly(coeffs,"x","coeff") disp(p) mprintf("Roots :\n"); r = roots(p) for i=1:n mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) end // Polynomial for inside contraction : // - n - x - ... - x^(n-1) + 2n x^(n)= 0 mprintf("Polynomial for inside contraction :\n"); coeffs = zeros(1,n+1); coeffs(1) = -n coeffs(2:n) = -1 coeffs(n+1) = 2 * n p=poly(coeffs,"x","coeff") disp(p) mprintf("Roots :\n"); r = roots(p) for i=1:n mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) end // Polynomial for reflection : // n - 2x - ... - 2x^(n-1) + n x^(n) = 0 mprintf("Polynomial for reflection :\n"); coeffs = zeros(1,n+1); coeffs(1) = n coeffs(2:n) = -2 coeffs(n+1) = n p=poly(coeffs,"x","coeff") disp(p) r = roots(p) mprintf("Roots :\n"); for i=1:n mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) end endfunction computeroots1(10) function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n ) // Polynomial for outside contraction : // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0 coeffs = zeros(1,n+1); coeffs(1) = n coeffs(2:n) = -3 coeffs(n+1) = 2 * n p=poly(coeffs,"x","coeff") r = roots(p , "e") rminoc = min(abs(r)) rmaxoc = max(abs(r)) // Polynomial for inside contraction : // - n - x - ... - x^(n-1) + 2n x^(n)= 0 coeffs = zeros(1,n+1); coeffs(1) = -n coeffs(2:n) = -1 coeffs(n+1) = 2 * n p=poly(coeffs,"x","coeff") r = roots(p , "e") rminic = min(abs(r)) rmaxic = max(abs(r)) mprintf("%d & %f & %f & %f & %f\\\\\n", n, rminoc, rmaxoc, rminic, rmaxic) endfunction function drawfigure1 ( nbmax ) rminoctable = zeros(1,nbmax) rmaxoctable = zeros(1,nbmax) rminictable = zeros(1,nbmax) rmaxictable = zeros(1,nbmax) for n = 1 : nbmax [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n ) rminoctable ( n ) = rminoc rmaxoctable ( n ) = rmaxoc rminictable ( n ) = rminic rmaxictable ( n ) = rmaxic end plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] ) f = gcf(); f.children.title.text = "Nelder-Mead characteristic equation roots"; f.children.x_label.text = "Number of variables (n)"; f.children.y_label.text = "Roots of the characteristic equation"; captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]); f.children.children(1).legend_location="in_lower_right"; for i = 1:4 mypoly = f.children.children(2).children(i); mypoly.foreground=i; mypoly.line_style=i; end xs2png(0,"neldermead-roots.png"); endfunction