%--------------------------------------------------------------------------
% Exercise 8, Numerische Verfahren der restringierten Optimierung, WS 16/17
% Author: Sabrina Rogg
% Date:   December 2nd 2016
%--------------------------------------------------------------------------

function [x_new,lambda_new,mu_new,eta] = oneStep(A,b,c,x,lambda,mu,sigma)
%--------------------------------------------------------------------------
%
% Input: problem data (A,b,c), triple (x,lambda,mu) with
%                              x>0,mu>0, 0 <= sigma <= 1
%
% Output: triple (dx,dlambda,dmu),
%--------------------------------------------------------------------------
[m,n]=size(A);

% Compute eta
eta = x'*mu/n;

% Set up system matrix
S = [spalloc(n,n,0),A',speye(n,n); ...
     A,spalloc(m,m,0),spalloc(m,n,0); ... 
     spdiags(mu,0,n,n),spalloc(n,m,0),spdiags(x,0,n,n)];

% Compute resisuals:
rc = A'*lambda + mu - c;
rb = A*x - b;

% Compute direction
d = S\[-rc;-rb;-x.*mu + sigma*eta];

dx      = d(1:n);
dlambda = d(n+1:n+m);
dmu     = d(n+m+1:end);

% Compute primal and dual step size 
idx_dx  = dx < 0;
idx_dmu = dmu < 0;
alpha_p = min(1,min(-x(idx_dx)./dx(idx_dx)));
alpha_d = min(1,min(-mu(idx_dmu)./dmu(idx_dmu)));

% Compute step
x_new      = x + alpha_p*dx;
lambda_new = lambda + alpha_d*dlambda;
mu_new     = mu + alpha_d*dmu;
%--------------------------------------------------------------------------
end