% Loese das Problem min{ f(x) : x aus R^n } mittels CG-Verfahrens.
%
% Parameter:
% subprog	Funktion, um das eindimensionale Unterproblem zu loesen,
%				wobei [t, k] = subprog(u, du, ddu, t0, t1, epsilon)
%				mit t Loesung, k Iterationsanzahl;
%					u, du, ddu : R -> R, die Funktion und jeweiligen Ableitungen;
%					t0, t1 Intervalgrenzen
%					epsilon Genaurigkeitskonstante
% f			Zielfunktion mit f : R^n -> R
% df		Gradient von f (als Spalte geschrieben!)
% ddf		Hessematrix von f, wird nur von subprog verwendent.
% x			Startvektor
%
% epsilon	Genauerigkeitskonstante
%
% Rueckgabewerte:
% x		Minimalstelle
% k		Anzahl der Iterationen
%
% Das Verfahren berechnet nur die ersten 25 Iterationsschritte!!
%
function [x, k] = cg(subprog, f, df, ddf, x, epsilon);

% g		g(k)
% gg	g(k+1)

g = df(x);
if (norm(g) < epsilon)
	k = 0;
	return;
end

K = 25;
n = 4;
d = -g;

for k = 0:K
	u = @(t) f(x + t*d);
	du = @(t) d'*df(x + t*d);
	ddu = @(t) d'*ddf(x + t*d)*d;
	
   	[alpha, kk] = subprog(u, du, ddu, 0, 1, epsilon);
	x = x + alpha*d;
	
	gg = df(x);
	if norm(gg) < epsilon
		break; 
	end

	if (mod(k+1, n) == 0) 
		d = -gg;
	else
		beta = (gg'*gg) / (g'*g);
		d = -gg + beta*d;
	end

	g = gg;
end