Main.java

import static java.lang.System.*;
import static java.lang.Math.*;

public class Main {
	/**
	 * Максимальное число итераций
	 */
	public static final int iterLimit = 50;
	
	/**
	 * Левая граница области поиска
	 */
	public static final double left  = -100;
	
	/**
	 * Правая граница области поиска
	 */
	public static final double right =  100;
	
	public static final double eps0  = 0.0;
	public static final double eps1  = 0.01;
	public static final double eps2  = 0.015;
	
	/**
	 * Норма вектора (квадратный корень из суммы квадратов координат)
	 * @param p вектор (точка)
	 * @return норма
	 */
	public static double norm(double[] p) {
		double sum = 0;
		for (double c : p) {
			sum += c * c;
		}
		return sqrt(sum);
	}
	
	/**
	 * Минимизируемая функция одной переменной t 
	 * (вектора v и df считаются константами). Цель - получить такую точку t
	 * в которой данная функция минимальна.
	 * @param f функция
	 * @param t переменная
	 * @param v вектор (точка)
	 * @param df градиент (вектор частных производных)
	 * @return значение функции x - t * grad(x)
	 */	
	private static double auxFunc(Function f, double t, double[] point, double[] grad) {
		int size = point.length;
		double[] x = new double[size];
		for (int i = 0; i < size; ++i) {
			x[i] = point[i] - t * grad[i];
		}
		return f.getValue(x);
	}	
	
	/**
	 * Метод дихотомии
	 * @param a левая граница
	 * @param b правая граница
	 * @param point начальная точка
	 * @param grad градиент
	 * @return
	 */
	public static double dichotomy(Function f, double[] point, double[] grad) {
		double e = 0.0001;		
		double l = e * 2;
		double a = left;
		double b = right;
		while (true) {
    		double y = (a + b - e) / 2;
    		double z = (a + b + e) / 2;
    		double Fy = auxFunc(f, y, point, grad);
    		double Fz = auxFunc(f, z, point, grad);
    		if (Fy <= Fz) {
    			b = z;
    		} else {
    			a = y;
    		}
			if (abs(b - a) <= l) {
				return (a + b) / 2;
			}    		
		}
	}	

	/**
	 * Метод наискорейшего градиентного спуска
	 * @param oldPoint начальная точка
	 * @param f функция
	 * @return точка, в которой функция принимает минимальное значение
	 */
	public static double[] fastGradientDescent(double[] oldPoint, Function f) {
		int size = oldPoint.length;
		double[] newPoint = new double[size];
		double[] gradFx = new double[size];
		double[] pointDif = new double[size];
		for (int k = 0; k < iterLimit; ++k) {
			for (int i = 0; i < size; ++i) {
				gradFx[i] = f.getDeriative(oldPoint, i);
			}
			//out.print("grad[F(x)] = ");
			//println(gradFx);
    		if (norm(gradFx) < eps1) {
    			return oldPoint;
    		}
    		//out.println("|| grad[F(x)] || = " + norm(gradFx));
    		double t = dichotomy(f, oldPoint, gradFx);
    		//out.println("t = " + t);
    		for (int i = 0; i < size; ++i) {
    			newPoint[i] = oldPoint[i] - t * gradFx[i];
    			pointDif[i] = abs(newPoint[i] - oldPoint[i]);
    		}
    		//out.println("x1 = ");
    		println(newPoint);
    		double funcDif = f.getValue(newPoint) - f.getValue(oldPoint);
    		if (norm(pointDif) < eps2 && abs(funcDif) < eps2) {
    			return newPoint;
    		}
    		arraycopy(newPoint, 0, oldPoint, 0, size);
		}
		return oldPoint;
	}
	
	
	/**
	 * Метод штрафов
	 * @param F вспомогательная функция - комбинация целевой функции и функций
	 * ограничений (см. класс LCFunction)
	 */
	public static void penaltyMethod(LCFunction F) {
		double c = 0.01;
		double[] x = new double[] { 0, 0 }; 

		for (int i = 0; i < iterLimit; ++i) {
			F.setR(0.01);
			x = fastGradientDescent(x, F);
			// !!!
			// остановился здесь
			// !!!
		}
	}
	
	public static void main(String[] args) {
		// Пример, как у Дашки
		
		// Целевая функция
		Function f = new Function() {
			public double getValue(double[] x) {
				return x[0]*x[0] - 8*x[0] + x[1]*x[1] - 8*x[1] + 32;
			}
			
			public double getDeriative(double[] x, int i) {
				if (i == 0) {
					return 2*x[0] - 8;
				}
				return 2*x[1] - 8;
			}
		};
		
		// Массив ограничений-равенств
		Function[] g1 = new Function[] {
			new Function() {
				public double getValue(double[] x) {
					return x[0] + x[1] - 2;
				}
				public double getDeriative(double[] x, int i) {
					return 1;
				}
			},
			
			new Function() {
				public double getValue(double[] x) {
					return x[0] + x[1] - 2;
				}
				public double getDeriative(double[] x, int i) {
					return 1;
				}				
			}
		};
		
		// Массив оОграничений-неравенств
		Function[] g2 = new Function[] {}; // (нет таких)
		
		// Вспомогательная функция
		LCFunction F = new LCFunction(f, g1, g2) {
			public double getDeriative(double[] x, int i) {
				// вывести производную
				return 0;
			}
		};
		
		penaltyMethod(F);
	}
	
	/**
	 * Печатает вектор вещественных чисел
	 * @param v
	 */
	private static void println(double[] v) {
		for (double d : v) {
			out.print(d + "\t");
		}
		out.println();
	}
}