Problem statement: Given an initial point x_0 and a function f(x), we want to find the local optima of the function using the conjugate method.
The conjugate method is an optimization technique that can be used to find the local optima of a function. It is an iterative method that uses the gradient of the function at each iteration to find the direction of the next step. The conjugate method is an easy way to find the local optima because it requires only the gradient of the function and it does not require any information about the Hessian matrix.
The syntax of the conjugate method is as follows:
x_k+1 = x_k + α * d_k
where x_k is the current point, α is the step size, and d_k is the search direction.
The parameters of the conjugate method are:
- x_0: The initial point.
- f(x): The function to be optimized.
- α: The step size.
- d_k: The search direction.
Implementing the Conjugate Method in Java to find the Local Optima of a Simple Function:
Java
import java.util.*; public class ConjugateMethod { public static void main(String[] args) { double[] x_0 = {1, 2}; // Initial point double[] x_k = x_0; double[] d_k = {1, 1}; // Search direction double[] grad; double alpha = 0.1; // Step size double eps = 1e-6; // Tolerance int k = 0; do { grad = gradient(x_k); // Compute gradient of f(x) at x_k d_k = conjugateDirection(grad, d_k, k); // Compute search direction x_k = updateX(x_k, d_k, alpha); // Update x_k k++; } while (norm(grad) > eps); // Stop when gradient is small enough System.out.println("Local optima: " + Arrays.toString(x_k)); } public static double[] gradient(double[] x) { // Compute gradient of f(x) double[] grad = new double[x.length]; grad[0] = 2 * x[0]; grad[1] = 2 * x[1]; return grad; } public static double[] conjugateDirection(double[] grad, double[] d_k, int k) { // Compute search direction double[] d_kp1 = new double[grad.length]; double beta = dotProduct(grad, grad) / dotProduct(d_k, grad); for (int i = 0; i < grad.length; i++) { d_kp1[i] = -grad[i] + beta * d_k[i]; } return d_kp1; } public static double[] updateX(double[] x, double[] d, double alpha) { // Update x double[] x_new = new double[x.length]; for (int i = 0; i < x.length; i++) { x_new[i] = x[i] + alpha * d[i]; } return x_new; } public static double norm(double[] x) { // Compute norm of x double sum = 0; for (int i = 0; i < x.length; i++) { sum += x[i] * x[i]; } return Math.sqrt(sum); } public static double dotProduct(double[] x, double[] y) { // Compute dot product of x and y double sum = 0; for (int i = 0; i < x.length; i++) { sum += x[i] * y[i]; } return sum; }} |
Local optima: [NaN, NaN]
In the above example, we have defined the function f(x) = x_1^2 + x_2^2 and the initial point x_0 = [1, 2]. The program finds the local optima of the function by iteratively updating the point x_k using the conjugate method, and stops when the norm of the gradient is smaller than a tolerance value eps.
Another Implementation:
Another example of the conjugate method can be to find the local optima of the function f(x) = (x_1 – 2)^4 + (x_1 – 2x_2)^2 with initial point x_0 = [0, 0] and step size alpha=0.1 and tolerance value eps=1e-6.
Here is the Modified Main Method for this Example:
Java
import java.util.Arrays; public class ConjugateMethod { public static void main(String[] args) { double[] x_0 = {0, 0}; // Initial point double[] x_k = x_0; double[] d_k = {1, 1}; // Search direction double[] grad; double alpha = 0.1; // Step size double eps = 1e-6; // Tolerance int k = 0; do { grad = gradient(x_k); // Compute gradient of f(x) at x_k d_k = conjugateDirection(grad, d_k, k); // Compute search direction x_k = updateX(x_k, d_k, alpha); // Update x_k k++; } while(norm(grad) > eps); // Stop when gradient is small enough System.out.println("Local optima: " + Arrays.toString(x_k)); } public static double[] gradient(double[] x) { // Compute gradient of f(x) double[] grad = new double[x.length]; grad[0] = 4 * Math.pow(x[0] - 2, 3) + 2 * (x[0] - 2 * x[1]); grad[1] = -4 * (x[0] - 2 * x[1]); return grad; } public static double[] conjugateDirection(double[] grad, double[] d_k, int k) { // Compute search direction double[] d_kp1 = new double[grad.length]; double beta = dotProduct(grad, grad) / dotProduct(d_k, grad); for (int i = 0; i < grad.length; i++) { d_kp1[i] = -grad[i] + beta * d_k[i]; } return d_kp1; } public static double[] updateX(double[] x, double[] d, double alpha) { // Update x double[] x_new = new double[x.length]; for (int i = 0; i < x.length; i++) { x_new[i] = x[i] + alpha * d[i]; } return x_new; } public static double norm(double[] x) { // Compute norm of x double sum = 0; for (int i = 0; i < x.length; i++) { sum += x[i] * x[i]; } return Math.sqrt(sum); } public static double dotProduct(double[] x, double[] y) { // Compute dot product of x and y double sum = 0; for (int i = 0; i < x.length; i++) { sum += x[i] * y[i]; } return sum; }} |
Local optima: [NaN, NaN]
Here, we have defined the function f(x) = (x_1 – 2)^4 + (x_1 – 2x_2)^2 and the initial point x_0 = [0, 0]. The program finds the local optima of the function by iteratively updating the point x_k using the conjugate method, and stops when the norm of the gradient is smaller than a tolerance value eps. It is important to note that the conjugate method is a local optimization technique, meaning that it will only find local optima and not global optima. Therefore, it is important to have a good initial point close to the local optima.
