Results 1 to 1 of 1

Math Help - [MATLAB] Optimization - Reduce Step size?

  1. #1
    Member
    Joined
    Mar 2007
    Posts
    206
    Awards
    1

    [MATLAB] Optimization - Reduce Step size?

    Hi All,
    I have made a number of post lately relating to this problem so I thought I would make a decent post and highlight exactly what my problem is so that hopefully I can get some feedback. Basically what I am doing is using the optimisation toolbox in matlab to find optimize the geometric potential of a system of nodes (put simply trying to get the nodes to disperse to find a minimum energy state).

    The geometric potential of a system of uniformly weighted nodes is expressed by:


    G = \sum_{i=1}^{n}\frac{1}{d_{ij}^q}

    Where:
    n is the number of nodes in the system
    q is the power index
    d_{ij} is the distance between node i and node j

    Two forms of geometric potential are considered:
    Global Geometric Potential \left( G_G \right) and Relative Geometric Potential \left( G_R \right)

    In the case of G_G, each node is considered to be connected to every other node. G_R only considers the contributions from adjacent nodes that are connected directly. G_R is the form used by the objective function in this example.

    The figure below shows a set of 9 nodes placed at random inside a unit square. The black lines represent the connections between nodes and the blue lines represent the voronoi diagram of the points.


    The problem is that the optimization routine is changing the values of x_i and y_i by too large a value per iteration. The connectivity as determined by the Delaunay triangulation is only valid inside each nodes Voronoi cell (in blue) so the maximum amount any node should move after only 1 iteration is to the edge of its respective Voronoi cell.


    My understanding is that the optimization routine recognizes that moving node 1 and node 4 together to the point \left(1,0\right) (for example) is a valid since the two nodes are not connected. The problem then arises that the Delaunay triangulation can no longer be recomputed since two nodes would now occupy the same position so there are duplicate nodes in the system.

    I have tried writing a constraint function to limit how close 2 nodes can get to each other, but the step size taken by the routine appears to be the biggest issue that needs addressing. my problem in a nutshell is:

    Is there a way to reduce the step size of the problem limit
    x_i and y_i to move by a maximum absolute value of say \delta = 0.05 per iteration?


    The matlab code used is given here. Running the code without any parameters will use the default values shown in the figure above. I am useing MATLAB 2008b with the optimisation toolbox version 4.1.
    Code:
    function [xy,fval,eflag] = Relative_Geometric_Potential(xy_start,q)
    % Take the nodes xy_start and optimize their position inside a 
    % unit sqaure in order to minimize the relative geometric
    % potential of the system subject to the power index q.
    % > xy_start is a 1x2n vector where there are n nodes in the system.
    % > q is a possitive integer.
    
    if nargin < 2;q = 2;end%set q=2 by default.(Not that important for this example)
    %Start position of nodes [x,y]
    if nargin < 1 % use default 
    xy_start = [0.196 0.992 0.802 0.729 0.498 0.809 0.357 0.073 0.591,...%xvals
         0.910 0.194 0.432 0.749 0.946 0.764 0.559 0.184 0.498];%yvals
    end
    
    n = length(xy_start)/2;%number of nodes
    LBounds = zeros(1,2*n);%lower Bounds
    UBounds = ones(1,2*n);%upper bounds
    
    options = optimset('Display','iter','Algorithm','active-set');
    f = @(xy)Gr(xy,q);%use power index of 2 for Geometric Potential Function
    
        [xy,fval,eflag] = fmincon(f,xy_start,...
            [],[],[],[],LBounds,UBounds,[],options);
        
    xy = reshape(xy,length(xy)/2,2);%reshape to nx2 matrix
    end
    
    function fval = Gr(xy,q)
    %xy is row vector = [x y]
    %q is power index
    
    xy = reshape(xy,length(xy)/2,2);%reshape to nx2 matrix
    x = xy(:,1);y = xy(:,2);%pull column vectors
    
    TRI = delaunay(x,y,{'QJ' 'Pp'});%determine connectivity between local nodes
    tmp = [TRI(:,[1,2]);TRI(:,[2,3])];%find nodes i,j of individual element
    tmp = sort(tmp,2);%sort so node i < node j
    mem_ij = unique(tmp,'rows');%take unique rows to get connectivity
    
    k = xy(mem_ij(:,1),:)-xy(mem_ij(:,2),:);%vector delta
    dij = sqrt(sum(k.^2,2));%normal of k
    foo = sum(dij.^(-q));%sum for final ans
    fval = 2*foo;%account for dij -> dji connections  (ie symetric dij matrix)
    end
    Any advice on how to solve this issue would be greatly appreciated.

    Kind Regards,
    Elbarto
    Attached Thumbnails Attached Thumbnails [MATLAB] Optimization - Reduce Step size?-gr.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Determining step size using golden ratio
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: December 12th 2011, 07:46 AM
  2. Optimization of functions of two variables in Matlab
    Posted in the Math Software Forum
    Replies: 1
    Last Post: December 8th 2011, 08:47 PM
  3. Matlab optimization help
    Posted in the Math Software Forum
    Replies: 7
    Last Post: July 22nd 2010, 03:54 PM
  4. step size function
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: November 30th 2009, 01:33 AM
  5. matrix size in matlab
    Posted in the Math Software Forum
    Replies: 4
    Last Post: November 23rd 2008, 02:38 AM

Search Tags


/mathhelpforum @mathhelpforum