% Loese das Problem min{ f(x) : Ax = b, x >= 0 }
% mittels Algorithmus' von Frank-Wolfe.
%
% Parameter:
% f		Zielfunktion mit f : R^n -> R
% df	Gradient von f (als Spalte geschrieben!)
% A		m x n Matrix
% b		Vektor aus R^m
% E 	Menge der extremen Randpunkten von
%			M = { x : Ax = b, x >= 0 }
%			(als Spalten geschrieben!)
% x		x aus M, Startvektor
%
% epsilon	Genauerigkeitskonstante
%
% Rueckgabewerte:
% x		Minimalstelle
% k		Anzahl der Iterationen
%
% Das Verfahren berechnet nur die ersten 25 Iterationsschritte!!
%
% Annahmen: 
% Die Zielfunktion ist quadratisch.
% 	Ansonsten Bisektion, Hybrid-Newtow usw. fuer das 
% 	eindimensinale Unterproblem verwenden.
% Die Menge M ist beschraenkt, sodass das linearisierte
% 	Problem immer loesbar ist.
%	Ansonsten Simplex-Algrithmus usw. verwenden.
%
function [x,k] = frankWolfe(f, df, A, b, E, x, epsilon);

K = 25;
for k = 0:K
	
	% Loese das linearisierte Minimierungsproblem
	% min{ (y-x)'*df(x) : Ay = b, y >= 0 }
	% "Negativer Abbruch", wenn das Problem nicht loesbar ist.
	
	u = @(y) (y - x)'*df(x);
	
	% Hier Spezialfall: Die Menge M ist beschraenkt.
	% 	Ansonsten Simplex-Algorithmus usw. verwenden 
	%	(kann zu negativen Abbruch fuehren).
	y = minLinProb(u, E);
	
	
	% Neue Richtung
		
	d = (y - x);
	
	
	% Wenn d'*df(x) = 0, dann x ein KKT-Punkt
	% Abbruch
	
	if abs(d'*df(x)) < epsilon
		break;
	end
	
	
	% Loese das eindimensionale Unterproblem
	% min{ f(x + t*d) : 0 <= t <= 1 }
	
	v = @(t) f(x + t*d);
	dv = @(t) d'*df(x + t*d);

	% Hier Spezialfall: Die Zielfunktion ist quadratisch.
	% Ansonsten Bisektion, Hybrid-Newtow usw. verwenden.
	
	t = minQuadPoly(v, dv, 0, 1);
	
	
	% Neuer Iterationspunkt
	
	x = x + t*d;
end




% Loese das linearisierte Problem mittels extr. Randpunkten.
% Berechne die Werte von u an jeden Punkt in E und
% bestimme den kleinsten Funktionswert.

function y = minLinProb(u, E);

y = E(:, 1);
for x = E
	if (u(x) < u(y))
		y = x;
	end
end
