Find the minimum value of a UniModal function - Coding

Given a Unimodal Function f(x) = A(x * x) + Bx + C and a range for the value of x in the form of [L, R], the task and is to find the minimum value of f(x) where the value of x can lie in the range [L, R] both inclusive. The minimum value should be accurate up to 6 decimal places.

Note: It is guaranteed that A > 0.

Examples:

Input: A = 2, B = -12, C = 7, L = 6, R = 8
Output: 7
Explanation: For x = 6, f(x) = 2 * (6 * 6) – 12 * 6 + 7 = 7.

Input: A = 2, B = -2, C = 8, L = -5, R = 5
Output:
Explanation: For x = 6, f(x) = 2 * (8 * 8) – 12 * 8 + 7 = 39.

Approach: To solve the problem, follow the below idea:

The problem can be solved using Ternary Search as Ternary Search can be used to find the min/max of a Unimodal Function. We can initialize the low of the range as L and high of the range as R. Now, we can take 2 mid points, say mid1 and mid2 and calculate the value of the function at those points. Now according to the value of res1 and res2, we can have 3 cases:

Case 1: f(mid1) == f(mid2), shift lo = mid1 and hi = mid2

Case 2: f(mid1) < f(mid2), shift hi = mid2

Case 3: f(mid1) > f(mid2), shift lo = mid1

Keep on reducing the range till we reach our answer.

Step-by-step algorithm:

The f function calculates the value of the quadratic expression Ax^2 + Bx + C for a given value of x.
Ternary search is used to find the minimum of a unimodal function within a given range [l, r].
The ternary search algorithm divides the range into three parts and eliminates one-third of the search space in each iteration.
The function compares the values at two points (mid1 and mid2) within the range and updates the search space accordingly.
The process continues for 200-300 iterations as this guarantees that the the search space has been reduced ans is now accurate up to 6 decimal places.
The result is printed as the f(l) or f(r).

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
double a, b, c;
 
// calculate the value of the given quadratic expression
// ax^2 + bx + c
double f(double a, double b, double c, double x)
{
    // The quadratic function: ax^2 + bx + c
    return a * x * x + b * x + c;
}
 
// Ternary search algorithm to find the minimum of a
// unimodal function within a given range [l, r]
double ternary_search(double l, double r)
{
    int cnt = 300;
    while (cnt--) {
        double mid1 = l + (r - l) / 3.0;
        double mid2 = r - (r - l) / 3.0;
        // Compare function values at mid1 and mid2 to
        // determine the search range
        if (f(a, b, c, mid1) < f(a, b, c, mid2))
            r = mid2;
        else
            l = mid1;
    }
    return f(a, b, c, l);
}
 
int main()
{
    // Driver code
    a = 2, b = -2, c = 8;
    double l, r;
    l = -5, r = 5;
    cout << fixed << setprecision(7) << ternary_search(l, r);
    return 0;
}

Java

import java.text.DecimalFormat;
 
public class TernarySearch {
 
    static double a, b, c;
 
    // Calculate the value of the given quadratic expression
    // ax^2 + bx + c
    static double f(double a, double b, double c, double x) {
        // The quadratic function: ax^2 + bx + c
        return a * x * x + b * x + c;
    }
 
    // Ternary search algorithm to find the minimum of a
    // unimodal function within a given range [l, r]
    static double ternarySearch(double l, double r) {
        int cnt = 300;
        while (cnt-- > 0) {
            double mid1 = l + (r - l) / 3.0;
            double mid2 = r - (r - l) / 3.0;
            // Compare function values at mid1 and mid2 to
            // determine the search range
            if (f(a, b, c, mid1) < f(a, b, c, mid2))
                r = mid2;
            else
                l = mid1;
        }
        return f(a, b, c, l);
    }
 
    public static void main(String[] args) {
        // Driver code
        a = 2;
        b = -2;
        c = 8;
        double l, r;
        l = -5;
        r = 5;
        DecimalFormat df = new DecimalFormat("#.#######");
        System.out.println(df.format(ternarySearch(l, r)));
    }
}
 
// This code is contributed by shivamgupta310570

Python3

# Calculate the value of the given quadratic expression
# ax^2 + bx + c
def f(a, b, c, x):
    # The quadratic function: ax^2 + bx + c
    return a * x * x + b * x + c
 
# Ternary search algorithm to find the minimum of a
# unimodal function within a given range [l, r]
def ternary_search(l, r):
    cnt = 300
    while cnt > 0:
        mid1 = l + (r - l) / 3.0
        mid2 = r - (r - l) / 3.0
        # Compare function values at mid1 and mid2 to
        # determine the search range
        if f(a, b, c, mid1) < f(a, b, c, mid2):
            r = mid2
        else:
            l = mid1
        cnt -= 1
    return f(a, b, c, l)
 
# Driver code
a, b, c = 2, -2, 8
l, r = -5, 5
print("{:.7f}".format(ternary_search(l, r)))

C#

using System;
 
public class MainClass
{
    static double a, b, c;
 
    // Calculate the value of the given quadratic expression
    // ax^2 + bx + c
    static double F(double x)
    {
        // The quadratic function: ax^2 + bx + c
        return a * x * x + b * x + c;
    }
 
    // Ternary search algorithm to find the minimum of a
    // unimodal function within a given range [l, r]
    static double TernarySearch(double l, double r)
    {
        int cnt = 300;
        while (cnt-- > 0)
        {
            double mid1 = l + (r - l) / 3.0;
            double mid2 = r - (r - l) / 3.0;
            // Compare function values at mid1 and mid2 to
            // determine the search range
            if (F(mid1) < F(mid2))
                r = mid2;
            else
                l = mid1;
        }
        return F(l);
    }
 
    public static void Main(string[] args)
    {
        // Driver code
        a = 2; b = -2; c = 8;
        double l, r;
        l = -5; r = 5;
        Console.WriteLine($"{TernarySearch(l, r):F7}");
    }
}

Javascript

let a, b, c;
 
// Function to calculate the value of the given quadratic expression ax^2 + bx + c
function f(a, b, c, x) {
    // The quadratic function: ax^2 + bx + c
    return a * x * x + b * x + c;
}
 
// Ternary search algorithm to find the minimum of a unimodal function within a given range [l, r]
function ternarySearch(l, r) {
    let cnt = 300;
    while (cnt--) {
        let mid1 = l + (r - l) / 3.0;
        let mid2 = r - (r - l) / 3.0;
        // Compare function values at mid1 and mid2 to determine the search range
        if (f(a, b, c, mid1) < f(a, b, c, mid2))
            r = mid2;
        else
            l = mid1;
    }
    return f(a, b, c, l);
}
 
// Driver code
a = 2, b = -2, c = 8;
let l = -5, r = 5;
console.log(ternarySearch(l, r).toFixed(7));

Output

7.5000000

Time Complexity: O(2 * log₃(N)), where N is the range of [L, R].
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Competitive Programming

Related
Find the lexicographically smallest string by prepending characters
Minimum cost to reach the last cell of a grid with directions
Optimal Construction of Roads
Maximize the number of boxes using red and yellow balls
Maximize number of indices with prefix sum equal to 0

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	15