%%% This m file uses the Primal Dual Affine Scaling Algorithm to solve
%%% linear programming problems.

%%% Author: Henry Wolkowicz
%%% Modified by: Steven Furino 20051212

%%% Assumptions
%%% The user has already created the matrices A, b and c and has provided
%%% feasible vectors x, y, s.

clear all

%% Provide data. As an alternative, this section can be deleted and data
%% taken from the command window or imported from an m file.

A = [1 2 1 1 0; 3 1 -1 0 1; 0 1 1 1 0]
b = [5 8 3]'
c = [4 2 1 1 -3]'
x = [1 1 1 1 5]'
y = [5 1 0]'
s = [4 9 3 4 4]'

toler=1e-4;

while sum(x.*s) > toler
    
   %% Find affine scaling search direction
   [dx,dy,ds]=intpt(A,b,c,x,y,s);
   %% Backtrack if necessary
   alpha=1;
   while min( min(x+alpha*dx),min(s+alpha*ds) ) <= 0,
      alpha = .5*alpha;
   end
   %% update
   x=x+alpha*dx;s=s+alpha*ds; y=y+alpha*dy;
   
   %% display
   dg = sum(x.*s);
   disp(['The current duality gap is: ', num2str(dg)])
   disp('The search direction for x and the new x are:')
   [dx x]
   disp('The search direction for y and the new y are:')
   [dy y]
   disp('The search direction for s and the new s are:')
   [ds s]

end
disp('The optimal x and s are: ')
[x s]
