add optimization library source code

git-svn-id: https://ws10smt.googlecode.com/svn/trunk@204 ec762483-ff6d-05da-a07a-a48fb63a330f

3 files changed, 365 insertions, 0 deletions

diff --git a/gi/posterior-regularisation/prjava/src/optimization/examples/GeneralizedRosenbrock.java b/gi/posterior-regularisation/prjava/src/optimization/examples/GeneralizedRosenbrock.java
new file mode 100644
index 00000000..25fa7f09
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/examples/GeneralizedRosenbrock.java
@@ -0,0 +1,110 @@
+package optimization.examples;
+
+
+import optimization.gradientBasedMethods.ConjugateGradient;
+import optimization.gradientBasedMethods.GradientDescent;
+import optimization.gradientBasedMethods.LBFGS;
+import optimization.gradientBasedMethods.Objective;
+import optimization.gradientBasedMethods.Optimizer;
+import optimization.gradientBasedMethods.stats.OptimizerStats;
+import optimization.linesearch.ArmijoLineSearchMinimization;
+import optimization.linesearch.LineSearchMethod;
+import optimization.stopCriteria.GradientL2Norm;
+import optimization.stopCriteria.StopingCriteria;
+import optimization.util.MathUtils;
+
+/**
+ * 
+ * @author javg
+ * f(x) = \sum_{i=1}^{N-1} \left[ (1-x_i)^2+ 100 (x_{i+1} - x_i^2 )^2 \right] \quad \forall x\in\mathbb{R}^N.
+ */
+public class GeneralizedRosenbrock extends Objective{
+
+	
+	
+	public GeneralizedRosenbrock(int dimensions){
+		parameters = new double[dimensions];		
+		java.util.Arrays.fill(parameters, 0);
+		gradient = new double[dimensions];
+		
+	}
+	
+	public GeneralizedRosenbrock(int dimensions, double[] params){
+		parameters = params;	
+		gradient = new double[dimensions];
+	}
+	
+	
+	public double getValue() {
+		functionCalls++;
+		double value = 0;
+		for(int i = 0; i < parameters.length-1; i++){
+			value += MathUtils.square(1-parameters[i]) + 100*MathUtils.square(parameters[i+1] - MathUtils.square(parameters[i]));
+		}
+		
+		return value;
+	}
+
+	/**
+	 * gx = -2(1-x) -2x200(y-x^2)
+	 * gy = 200(y-x^2)
+	 */
+	public double[] getGradient() {
+		gradientCalls++;
+		java.util.Arrays.fill(gradient,0);
+		for(int i = 0; i < parameters.length-1; i++){
+			gradient[i]+=-2*(1-parameters[i]) - 400*parameters[i]*(parameters[i+1] - MathUtils.square(parameters[i]));
+			gradient[i+1]+=200*(parameters[i+1] - MathUtils.square(parameters[i]));
+		}	
+		return gradient;
+	}
+
+	
+
+	
+
+	
+	
+	public String toString(){
+		String  res ="";
+		for(int i = 0; i < parameters.length; i++){
+			res += "P" + i+ " " + parameters[i];
+		}
+		res += " Value " + getValue();
+		return res;
+	}
+	
+	public static void main(String[] args) {
+		
+		GeneralizedRosenbrock o = new GeneralizedRosenbrock(2);
+		System.out.println("Starting optimization " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		;
+
+		System.out.println("Doing Gradient descent");
+		//LineSearchMethod wolfe = new WolfRuleLineSearch(new InterpolationPickFirstStep(1),100,0.001,0.1);
+		StopingCriteria stop = new GradientL2Norm(0.001);		
+		LineSearchMethod ls = new ArmijoLineSearchMinimization();
+		Optimizer optimizer = new GradientDescent(ls);		
+		OptimizerStats stats = new OptimizerStats();
+		optimizer.setMaxIterations(1000);
+		boolean succed = optimizer.optimize(o,stats, stop);
+		System.out.println("Suceess " + succed + "/n"+stats.prettyPrint(1));
+		System.out.println("Doing Conjugate Gradient descent");
+		o = new GeneralizedRosenbrock(2);
+	//	wolfe = new WolfRuleLineSearch(new InterpolationPickFirstStep(1),100,0.001,0.1);
+		optimizer = new ConjugateGradient(ls);
+		stats = new OptimizerStats();
+		optimizer.setMaxIterations(1000);
+		succed = optimizer.optimize(o,stats,stop);
+		System.out.println("Suceess " + succed + "/n"+stats.prettyPrint(1));
+		System.out.println("Doing Quasi newton descent");
+		o = new GeneralizedRosenbrock(2);
+		optimizer = new LBFGS(ls,10);
+		stats = new OptimizerStats();
+		optimizer.setMaxIterations(1000);
+		succed = optimizer.optimize(o,stats,stop);
+		System.out.println("Suceess " + succed + "/n"+stats.prettyPrint(1));
+
+	}
+	
+}
diff --git a/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2.java b/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2.java
new file mode 100644
index 00000000..f087681e
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2.java
@@ -0,0 +1,128 @@
+package optimization.examples;
+
+
+import optimization.gradientBasedMethods.ConjugateGradient;
+
+import optimization.gradientBasedMethods.GradientDescent;
+import optimization.gradientBasedMethods.LBFGS;
+import optimization.gradientBasedMethods.Objective;
+import optimization.gradientBasedMethods.stats.OptimizerStats;
+import optimization.linesearch.GenericPickFirstStep;
+import optimization.linesearch.LineSearchMethod;
+import optimization.linesearch.WolfRuleLineSearch;
+import optimization.stopCriteria.GradientL2Norm;
+import optimization.stopCriteria.StopingCriteria;
+
+
+/**
+ * @author javg
+ *
+ */
+public class x2y2 extends Objective{
+
+	
+	//Implements function ax2+ by2 
+	double a, b;
+	public x2y2(double a, double b){
+		this.a = a;
+		this.b = b;
+		parameters = new double[2];
+		parameters[0] = 4;
+		parameters[1] = 4;
+		gradient = new double[2];
+	}
+	
+	public double getValue() {
+		functionCalls++;
+		return a*parameters[0]*parameters[0]+b*parameters[1]*parameters[1];
+	}
+
+	public double[] getGradient() {
+		gradientCalls++;
+		gradient[0]=2*a*parameters[0];
+		gradient[1]=2*b*parameters[1];
+		return gradient;
+//		if(debugLevel >=2){
+//			double[] numericalGradient = DebugHelpers.getNumericalGradient(this, parameters, 0.000001);
+//			for(int i = 0; i < parameters.length; i++){
+//				double diff = Math.abs(gradient[i]-numericalGradient[i]);
+//				if(diff > 0.00001){
+//					System.out.println("Numerical Gradient does not match");
+//					System.exit(1);
+//				}
+//			}
+//		}
+	}
+
+	
+	
+	public void optimizeWithGradientDescent(LineSearchMethod ls, OptimizerStats stats, x2y2 o){
+		GradientDescent optimizer = new GradientDescent(ls);
+		StopingCriteria stop = new GradientL2Norm(0.001);
+//		optimizer.setGradientConvergenceValue(0.001);
+		optimizer.setMaxIterations(100);
+		boolean succed = optimizer.optimize(o,stats,stop);
+		System.out.println("Ended optimzation Gradient Descent\n" + stats.prettyPrint(1));
+		System.out.println("Solution: " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		if(succed){
+			System.out.println("Ended optimization in " + optimizer.getCurrentIteration());
+		}else{
+			System.out.println("Failed to optimize");
+		}
+	}
+	
+	public void optimizeWithConjugateGradient(LineSearchMethod ls, OptimizerStats stats, x2y2 o){
+		ConjugateGradient optimizer = new ConjugateGradient(ls);
+		StopingCriteria stop = new GradientL2Norm(0.001);
+
+		optimizer.setMaxIterations(10);
+		boolean succed = optimizer.optimize(o,stats,stop);
+		System.out.println("Ended optimzation Conjugate Gradient\n" + stats.prettyPrint(1));
+		System.out.println("Solution: " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		if(succed){
+			System.out.println("Ended optimization in " + optimizer.getCurrentIteration());
+		}else{
+			System.out.println("Failed to optimize");
+		}
+	}
+	
+	public void optimizeWithLBFGS(LineSearchMethod ls, OptimizerStats stats, x2y2 o){
+		LBFGS optimizer = new LBFGS(ls,10);
+		StopingCriteria stop = new GradientL2Norm(0.001);
+		optimizer.setMaxIterations(10);
+		boolean succed = optimizer.optimize(o,stats,stop);
+		System.out.println("Ended optimzation LBFGS\n" + stats.prettyPrint(1));
+		System.out.println("Solution: " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		if(succed){
+			System.out.println("Ended optimization in " + optimizer.getCurrentIteration());
+		}else{
+			System.out.println("Failed to optimize");
+		}
+	}
+	
+	public static void main(String[] args) {
+		x2y2 o = new x2y2(1,10);
+		System.out.println("Starting optimization " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		o.setDebugLevel(4);
+		LineSearchMethod wolfe = new WolfRuleLineSearch(new GenericPickFirstStep(1),0.001,0.9);;
+//		LineSearchMethod ls = new ArmijoLineSearchMinimization();
+		OptimizerStats stats = new OptimizerStats();
+		o.optimizeWithGradientDescent(wolfe, stats, o);
+		o = new x2y2(1,10);
+		System.out.println("Starting optimization " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+//		ls = new ArmijoLineSearchMinimization();
+		stats = new OptimizerStats();
+		o.optimizeWithConjugateGradient(wolfe, stats, o);
+		o = new x2y2(1,10);
+		System.out.println("Starting optimization " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+//		ls = new ArmijoLineSearchMinimization();
+		stats = new OptimizerStats();
+		o.optimizeWithLBFGS(wolfe, stats, o);	
+	}
+	
+	public String toString(){
+		return "P1: " + parameters[0] + " P2: " + parameters[1] + " value " + getValue();
+	}
+	
+	
+}
diff --git a/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2WithConstraints.java b/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2WithConstraints.java
new file mode 100644
index 00000000..391775b7
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/examples/x2y2WithConstraints.java
@@ -0,0 +1,127 @@
+package optimization.examples;
+
+
+import optimization.gradientBasedMethods.ProjectedGradientDescent;
+import optimization.gradientBasedMethods.ProjectedObjective;
+import optimization.gradientBasedMethods.stats.OptimizerStats;
+import optimization.linesearch.ArmijoLineSearchMinimizationAlongProjectionArc;
+import optimization.linesearch.InterpolationPickFirstStep;
+import optimization.linesearch.LineSearchMethod;
+import optimization.projections.BoundsProjection;
+import optimization.projections.Projection;
+import optimization.projections.SimplexProjection;
+import optimization.stopCriteria.CompositeStopingCriteria;
+import optimization.stopCriteria.GradientL2Norm;
+import optimization.stopCriteria.ProjectedGradientL2Norm;
+import optimization.stopCriteria.StopingCriteria;
+import optimization.stopCriteria.ValueDifference;
+
+
+/**
+ * @author javg
+ * 
+ * 
+ *ax2+ b(y2 -displacement)
+ */
+public class x2y2WithConstraints extends ProjectedObjective{
+
+
+	double a, b;
+	double dx;
+	double dy;
+	Projection projection;
+	
+	
+	public x2y2WithConstraints(double a, double b, double[] params, double dx, double dy, Projection proj){
+		//projection = new BoundsProjection(0.2,Double.MAX_VALUE);
+		super();
+		projection = proj;	
+		this.a = a;
+		this.b = b;
+		this.dx = dx;
+		this.dy = dy;
+		setInitialParameters(params);
+		System.out.println("Function " +a+"(x-"+dx+")^2 + "+b+"(y-"+dy+")^2");
+		System.out.println("Gradient " +(2*a)+"(x-"+dx+") ; "+(b*2)+"(y-"+dy+")");
+		printParameters();
+		projection.project(parameters);
+		printParameters();
+		gradient = new double[2];
+	}
+	
+	public double getValue() {
+		functionCalls++;
+		return a*(parameters[0]-dx)*(parameters[0]-dx)+b*((parameters[1]-dy)*(parameters[1]-dy));
+	}
+
+	public double[] getGradient() {
+		if(gradient == null){
+			gradient = new double[2];
+		}
+		gradientCalls++;
+		gradient[0]=2*a*(parameters[0]-dx);
+		gradient[1]=2*b*(parameters[1]-dy);
+		return gradient;
+	}
+	
+	
+	public double[] projectPoint(double[] point) {
+		double[] newPoint = point.clone();
+		projection.project(newPoint);
+		return newPoint;
+	}	
+	
+	public void optimizeWithProjectedGradientDescent(LineSearchMethod ls, OptimizerStats stats, x2y2WithConstraints o){
+		ProjectedGradientDescent optimizer = new ProjectedGradientDescent(ls);
+		StopingCriteria stopGrad = new ProjectedGradientL2Norm(0.001);
+		StopingCriteria stopValue = new ValueDifference(0.001);
+		CompositeStopingCriteria compositeStop = new CompositeStopingCriteria();
+		compositeStop.add(stopGrad);
+		compositeStop.add(stopValue);
+		
+		optimizer.setMaxIterations(5);
+		boolean succed = optimizer.optimize(o,stats,compositeStop);
+		System.out.println("Ended optimzation Projected Gradient Descent\n" + stats.prettyPrint(1));
+		System.out.println("Solution: " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1]);
+		if(succed){
+			System.out.println("Ended optimization in " + optimizer.getCurrentIteration());
+		}else{
+			System.out.println("Failed to optimize");
+		}
+	}
+	
+	
+	
+	public String toString(){
+		
+		return "P1: " + parameters[0] + " P2: " + parameters[1] + " value " + getValue() + " grad (" + getGradient()[0] + ":" + getGradient()[1]+")";
+	}
+	
+	public static void main(String[] args) {
+		double a = 1;
+		double b=1;
+		double x0 = 0;
+		double y0  =1;
+		double dx = 0.5;
+		double dy = 0.5	;
+		double [] parameters = new double[2];
+		parameters[0] = x0;
+		parameters[1] = y0;
+		x2y2WithConstraints o = new x2y2WithConstraints(a,b,parameters,dx,dy, new SimplexProjection(0.5));
+		System.out.println("Starting optimization " + " x0 " + o.parameters[0]+ " x1 " + o.parameters[1] + " a " + a + " b "+b );
+		o.setDebugLevel(4);
+		
+		LineSearchMethod ls = new ArmijoLineSearchMinimizationAlongProjectionArc(new InterpolationPickFirstStep(1));
+		
+		OptimizerStats stats = new OptimizerStats();
+		o.optimizeWithProjectedGradientDescent(ls, stats, o);
+		
+//		o = new x2y2WithConstraints(a,b,x0,y0,dx,dy);
+//		stats = new OptimizerStats();
+//		o.optimizeWithSpectralProjectedGradientDescent(stats, o);
+	}
+	
+	
+	
+	
+}