add optimization library source code

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

3 files changed, 303 insertions, 0 deletions

diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java
new file mode 100644
index 00000000..0429d531
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/projections/BoundsProjection.java
@@ -0,0 +1,104 @@
+package optimization.projections;
+
+
+import java.util.Random;
+
+import optimization.util.MathUtils;
+import optimization.util.MatrixOutput;
+
+/**
+ * Implements a projection into a box set defined by a and b.
+ * If either a or b are infinity then that bound is ignored.
+ * @author javg
+ *
+ */
+public class BoundsProjection extends Projection{
+
+	double a,b;
+	boolean ignoreA = false;
+	boolean ignoreB = false;
+	public BoundsProjection(double lowerBound, double upperBound) {
+		if(Double.isInfinite(lowerBound)){
+			this.ignoreA = true;
+		}else{
+			this.a =lowerBound;
+		}
+		if(Double.isInfinite(upperBound)){
+			this.ignoreB = true;
+		}else{
+			this.b =upperBound;
+		}
+	}
+	
+	
+	
+	/**
+	* Projects into the bounds
+	* a <= x_i <=b
+	 */
+	public void project(double[] original){
+		for (int i = 0; i < original.length; i++) {
+			if(!ignoreA && original[i] < a){
+				original[i] = a;
+			}else if(!ignoreB && original[i]>b){
+				original[i]=b;
+			}
+		}
+	}
+	
+	/**
+	 * Generates a random number between a and b.
+	 */
+
+	Random r = new Random();
+	
+	public double[] samplePoint(int numParams) {
+		double[] point = new double[numParams];
+		for (int i = 0; i < point.length; i++) {
+			double rand = r.nextDouble();
+			if(ignoreA && ignoreB){
+				//Use const to avoid number near overflow
+				point[i] = rand*(1.E100+1.E100)-1.E100;
+			}else if(ignoreA){
+				point[i] = rand*(b-1.E100)-1.E100;
+			}else if(ignoreB){
+				point[i] = rand*(1.E100-a)-a;
+			}else{
+				point[i] = rand*(b-a)-a;
+			}
+		}
+		return point;
+	}
+	
+	public static void main(String[] args) {
+		BoundsProjection sp = new BoundsProjection(0,Double.POSITIVE_INFINITY);
+		
+		
+		MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 1");
+		MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 2");
+		MatrixOutput.printDoubleArray(sp.samplePoint(3), "random 3");
+		
+		double[] d = {-1.1,1.2,1.4};
+		double[] original = d.clone();
+		MatrixOutput.printDoubleArray(d, "before");
+		
+		sp.project(d);
+		MatrixOutput.printDoubleArray(d, "after");
+		System.out.println("Test projection: " + sp.testProjection(original, d));
+	}
+	
+	double epsilon = 1.E-10;
+	public double[] perturbePoint(double[] point, int parameter){
+		double[] newPoint = point.clone();
+		if(!ignoreA && MathUtils.almost(point[parameter], a)){
+			newPoint[parameter]+=epsilon;
+		}else if(!ignoreB && MathUtils.almost(point[parameter], b)){
+			newPoint[parameter]-=epsilon;
+		}else{
+			newPoint[parameter]-=epsilon;
+		}
+		return newPoint;
+	}
+
+	
+}
diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java
new file mode 100644
index 00000000..b5a9f92f
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/projections/Projection.java
@@ -0,0 +1,72 @@
+package optimization.projections;
+
+import optimization.util.MathUtils;
+import optimization.util.MatrixOutput;
+import util.ArrayMath;
+import util.Printing;
+
+
+
+public abstract class Projection {
+
+	
+	public abstract void project(double[] original);
+	
+	
+	/**
+	 *  From the projection theorem "Non-Linear Programming" page
+	 *  201 fact 2.
+	 *  
+	 *  Given some z in R, and a vector x* in X;
+	 *  x* = z+ iif for all x in X 
+	 *  (z-x*)'(x-x*) <= 0 where 0 is when x*=x
+	 *  See figure 2.16 in book
+	 *  
+	 * @param original
+	 * @param projected
+	 * @return
+	 */
+	public boolean testProjection(double[] original, double[] projected){
+		double[] original1 = original.clone();
+		//System.out.println(Printing.doubleArrayToString(original1, null, "original"));
+		//System.out.println(Printing.doubleArrayToString(projected, null, "projected"));
+		MathUtils.minusEquals(original1, projected, 1);
+		//System.out.println(Printing.doubleArrayToString(original1, null, "minus1"));
+		for(int i = 0; i < 10; i++){
+			double[] x = samplePoint(original.length);
+		//	System.out.println(Printing.doubleArrayToString(x, null, "sample"));
+			//If the same this returns zero so we are there.	
+			MathUtils.minusEquals(x, projected, 1);
+		//	System.out.println(Printing.doubleArrayToString(x, null, "minus2"));
+			double dotProd = MathUtils.dotProduct(original1, x);
+			
+		//	System.out.println("dot " + dotProd);
+			if(dotProd > 0) return false;
+		}
+		
+		//Perturbs the point a bit in all possible directions
+		for(int i = 0; i < original.length; i++){
+			double[] x = perturbePoint(projected,i);
+		//	System.out.println(Printing.doubleArrayToString(x, null, "perturbed"));
+			//If the same this returns zero so we are there.	
+			MathUtils.minusEquals(x, projected, 1);
+		//	System.out.println(Printing.doubleArrayToString(x, null, "minus2"));
+			double dotProd = MathUtils.dotProduct(original1, x);
+			
+		//	System.out.println("dot " + dotProd);
+			if(dotProd > 0) return false;
+		}
+		
+		
+		
+		return true;
+	}
+
+	//Samples a point from the constrained set
+	public abstract double[] samplePoint(int dimensions);
+	
+	//Perturbs a point a bit still leaving it at the constraints set
+	public abstract double[] perturbePoint(double[] point, int parameter);
+	
+	
+}
diff --git a/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java b/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java
new file mode 100644
index 00000000..eec11bcf
--- /dev/null
+++ b/gi/posterior-regularisation/prjava/src/optimization/projections/SimplexProjection.java
@@ -0,0 +1,127 @@
+package optimization.projections;
+
+
+
+import java.util.Random;
+
+import optimization.util.MathUtils;
+import optimization.util.MatrixOutput;
+
+public class SimplexProjection extends Projection{
+
+	double scale;
+	public SimplexProjection(double scale) {
+		this.scale = scale;
+	}
+	
+	/**
+	 * projects the numbers of the array 
+	 * into a simplex of size. 
+	 * We follow the description of the paper
+	 * "Efficient Projetions onto the l1-Ball
+	 * for learning in high dimensions"
+	 */
+	public void project(double[] original){
+		double[] ds = new double[original.length];
+		System.arraycopy(original, 0, ds, 0, ds.length);
+		//If sum is smaller then zero then its ok
+		for (int i = 0; i < ds.length; i++) ds[i] = ds[i]>0? ds[i]:0;
+		double sum = MathUtils.sum(ds);
+		if (scale - sum >=  -1.E-10 ){
+			System.arraycopy(ds, 0, original, 0, ds.length);
+			//System.out.println("Not projecting");
+			return;
+		}
+		//System.out.println("projecting " + sum + " scontraints " + scale);	
+		util.Array.sortDescending(ds);
+		double currentSum = 0;
+		double previousTheta = 0;
+		double theta = 0;
+		for (int i = 0; i < ds.length; i++) {
+			currentSum+=ds[i];
+			theta = (currentSum-scale)/(i+1);
+			if(ds[i]-theta <= 0){
+				break;
+			}
+			previousTheta = theta;
+		}
+		//DEBUG
+		if(previousTheta < 0){
+			System.out.println("Simple Projection: Theta is smaller than zero: " + previousTheta);
+			System.exit(-1);
+		}
+		for (int i = 0; i < original.length; i++) {
+			original[i] = Math.max(original[i]-previousTheta, 0);
+		}
+	}
+	
+	
+	
+	
+	
+
+	/**
+	 * Samples a point from the simplex of scale. Just sample
+	 * random number from 0-scale and then if
+	 * their sum is bigger then sum make them normalize.
+	 * This is probably not sampling uniformly from the simplex but it is
+	 * enough for our goals in here.
+	 */
+	Random r = new Random();
+	public double[] samplePoint(int dimensions) {
+		double[] newPoint = new double[dimensions];
+		double sum =0;
+		for (int i = 0; i < newPoint.length; i++) {
+			double rand = r.nextDouble()*scale;
+			sum+=rand;
+			newPoint[i]=rand;
+		}
+		//Normalize
+		if(sum > scale){
+			for (int i = 0; i < newPoint.length; i++) {
+				newPoint[i]=scale*newPoint[i]/sum;
+			}
+		}
+		return newPoint;
+	}
+	
+	public static void main(String[] args) {
+		SimplexProjection sp = new SimplexProjection(1);
+		
+		
+		double[] point = sp.samplePoint(3);
+		MatrixOutput.printDoubleArray(point , "random 1 sum:" + MathUtils.sum(point));
+		point = sp.samplePoint(3);
+		MatrixOutput.printDoubleArray(point , "random 2 sum:" + MathUtils.sum(point));
+		point = sp.samplePoint(3);
+		MatrixOutput.printDoubleArray(point , "random 3 sum:" + MathUtils.sum(point));
+		
+		double[] d = {0,1.1,-10};
+		double[] original = d.clone();
+		MatrixOutput.printDoubleArray(d, "before");
+		
+		sp.project(d);
+		MatrixOutput.printDoubleArray(d, "after");
+		System.out.println("Test projection: " + sp.testProjection(original, d));
+		
+	}
+	
+	
+	double epsilon = 1.E-10;
+	public double[] perturbePoint(double[] point, int parameter){
+		double[] newPoint = point.clone();
+		if(MathUtils.almost(MathUtils.sum(point), scale)){
+			newPoint[parameter]-=epsilon;
+		}
+		else if(point[parameter]==0){
+			newPoint[parameter]+=epsilon;
+		}else if(MathUtils.almost(point[parameter], scale)){
+			newPoint[parameter]-=epsilon;
+		}
+		else{
+			newPoint[parameter]-=epsilon;
+		}
+		return newPoint;
+	}
+	
+}