/*
 * Simplex.java by Richard J. Davies
 * from `Introductory Java for Scientists and Engineers'
 * chapter: `Numerical Computation'
 * section: `The Simplex Method'
 *
 * This program minimizes a function of two variables
 * by walking a tetrahedron downhill across it.
 */
public class Simplex
{
  // Constants for the method
  public static final double SHRINKAGES = 30;


  // The function to be minimized
  public static double f(double x, double y)
  {
    return (x-3)*(x-7) + Math.exp(y+2) + (y-1)*(y-3);
  }


  // The `main' method actually implements
  // the simplex method.
  public static void main(String[] argv)
  {
    int i;

    // Set up array for the corners of the simplex
    // and insert initial values. First index is
    // which corner, second is which coordinate
    // of that corner (x, y, f).
    double[][] c = { { 0, 0, f(0, 0) },
                     { 0, 1, f(0, 1) },
                     { 1, 0, f(1, 0) } };

    // Count the number of times we shrink
    // the simplex.
    int shrink = 0;

    // Iterate until this has been
    // done enough times.
    while (shrink < SHRINKAGES)
    {
      // Find the highest corner
      int highest = 0;

      for (i=0; i<3; i++)
        if (c[i][2] > c[highest][2])
          highest = i;

      // Calculate the centre of the opposite face.
      double cx = 0;
      double cy = 0;
      
      for (i=0; i<3; i++)
        if (i != highest)
        {
          cx += c[i][0];
          cy += c[i][1];
        }

      cx /= 2;
      cy /= 2;

      // Try reflecting the highest corner in that
      double rx = 2 * cx - c[highest][0];
      double ry = 2 * cy - c[highest][1];
      double rf = f(rx, ry);

      if (rf < c[highest][2])
      {
        // If this is lower than its current position
        // then move the simplex.
        c[highest][0] = rx;
        c[highest][1] = ry;
        c[highest][2] = rf;
      }
      else
      {
        // Otherwise, we're near a minimum, so shrink
        // the simplex
        for (i=1; i<3; i++)
        {
          c[i][0] = (c[i][0] + c[0][0])/2;
          c[i][1] = (c[i][1] + c[0][1])/2;
          c[i][2] = f(c[i][0], c[i][1]);
        }

        shrink++;
      }
    }

    // The method has terminated, so we're at a min.
    System.out.println("The minimum is " + c[0][2]
                       + " at x = " + c[0][0]
                       + " and y = " + c[0][1]);
  }
}