mathematical optimization - Frank - Wolfe Algorithm in matlab -


i'm trying solve following question :

  maximize  x^2-5x+y^2-3y     x+y <=  8   x<=2    x,y>= 0

by using frank wolf algorithm ( according http://web.mit.edu/15.053/www/amp-chapter-13.pdf ).

but after running of following program:

    syms x y t;      f = x^2-5*x+y^2-3*y;       fdx = diff(f,1,x); % f'x     fdy = diff(f,1,y); % y'x      x0 = [0 0];      %initial point      = [1 1;1 0];    %constrains matrix     b = [8;2];        lb = zeros(1,2);         eps = 0.00001;      = 1;     x = [inf inf];     z = zeros(2,200); %result end points (x1,x2)       rr = zeros(1,200);     options = optimset('display','none');      while( all(abs(x-x0)>[eps,eps]) && < 200)          %f'x(x0)          c1 = subs(fdx,x,x0(1));         c1 = subs(c1,y,x0(2));          %f'y(x0)          c2 = subs(fdy,x,x0(1));         c2 = subs(c2,y,x0(2));          %optimization point of linear taylor function         ys = linprog((-[c1;c2]),a,b,[],[],lb,[],[],options);            %parametric representation of line         xt = (1-t)*x0(1)+t*ys(1,1);         yt = (1-t)*x0(2)+t*ys(2,1);          %f(x=xt,y=yt)         ft = subs(f,x,xt);         ft = subs(ft,y,yt);          %f't(x=xt,y=yt)         ftd = diff(ft,t,1);           %f't(x=xt,y=yt)=0 -> max point          [t1] = solve(ftd); % (t==theta)           x = double(x0);%%%%%%%%%%%%%%%%%          %  [ xt(t=t1)  yt(t=t1)]         xnext(1) = subs(xt,t,t1) ;         xnext(2) =  subs(yt,t,t1) ;          x0 = double(xnext);         z(1,i) = x0(1);         z(2,i) = x0(2);           = + 1;     end          x_point = z(1,:);     y_point = z(2,:);    % draw result scatter(x_point,y_point); hold on;  % print results fprintf('the answer is:\n');  fprintf('x = %.3f \n',x0(1)); fprintf('y = %.3f \n',x0(2));   res = x0(1)^2 - 5*x0(1) + x0(2)^2 - 3*x0(2); fprintf('f(x0) = %.3f\n',res);

i following result:

    x = 3.020      y = 0.571      f(x0) = -7.367

and no matter how many iterations running program (1,50 or 200).

even if choose different starting point (for example, x0=(1,6) ), negative answer most.

i know approximation, result should positive (for x0 final, in case).

my question : what's wrong implementation?

thanks in advance.

i changed few things, still doesn't right getting in right direction. looks intial x0 points make difference how algorithm converges.

also make sure check i after running program, determine if ran completion or exceeded maximum iterations

lb = zeros(1,2);  ub = [2,8]; %if x+y<=8 , x,y>0 both x,y < 8    eps = 0.00001;  i_max = 100; = 1; x = [inf inf]; z = zeros(2,i_max); %result end points (x1,x2)   rr = zeros(1,200); options = optimset('display','none');  while( all(abs(x-x0)>[eps,eps]) && < i_max)      %f'x(x0)      c1 = subs(fdx,x,x0(1));     c1 = subs(c1,y,x0(2));      %f'y(x0)      c2 = subs(fdy,x,x0(1));     c2 = subs(c2,y,x0(2));      %optimization point of linear taylor function     [ys, ~ , exit_flag] = linprog((-[c1;c2]),a,b,[],[],lb,ub,x0,options);

so here explanation of changes

ub, uses our upper bound. after added ub, result changed

x0, start iteration previous point

exit_flag allows check exit_flag after execution (it seems 1 indicating solved problem correctly)


Comments

Post a Comment

Popular posts from this blog

java - Spring Data JPA: Why findOne(id) executing delete query internally? -

i have 1 application using @manytomany annotation link 2 different entities 1 parent entity. not sure if have implemented properly. when execute .findone() on parent entity's repository find it, @ first fetch data along executing delete queries internally delete record mapping table (a table jpa creates after adding @manytomany annotation.). following generated sql queries , code snippet: java class @entity @table(name = "inventory") public class inventory { @id long id; // many other properties @manytomany(fetch=fetchtype.lazy) private list<stream> streams; @manytomany(fetch=fetchtype.lazy) private list<subject> subjects; } there no other annotation i've put in stream , subject entity class link inventory class. when run app, create following tables: inventory stream subject inventory_stream inventory_subject (inventory_stream , inventory_subject, 2 tables created automatically, don't k...
Read more

python - Mongodb How to add addtional information when aggregating? -

i beginner , wrote line pipeline works, wanna add other information output, screen name , or number of tweets.i tried add under $group gave me syntax error everytime here pipeline: def make_pipeline(): # complete aggregation pipeline pipeline = [ { '$match': { "user.statuses_count": {"$gt":99 }, "user.time_zone": "brasilia" } }, { "$group": { "_id": "$user.id", "followers": { "$max": "$user.followers_count" } } }, { "$sort": { "followers": -1 } }, { "$limit" : 1 } ]; i using on example : { "_id" : objectid("5304e2e3cc9e684aa98bef97"), "text" : "first week of school on :p", "in_reply_to_status_id" : null, "retweet_count" : null, ...
Read more

java - Incorrect order of records in M-M relationship in hibernate -

Image
i have 4 records in bridge table in mysql database. using @manytomany in hibernate, accurate order of employees incorrect incorrect of projects. following required material figure out doing mistake. this source. @entity @table(name="project") public class projectbean { @id @generatedvalue @column(name="project_id") private int projectid; @column(name="title") private string projecttitle; @manytomany(mappedby="projects") private collection<employeebean> employees; public projectbean() { employees = new arraylist<employeebean>(); } //getters & setters } @entity @table(name="employee") public class employeebean { @id @generatedvalue @column(name="employee_id") private int employee_id; @column(name="first_name") private string ...
Read more