CODEWITHSUNDEEP
javascriptalgorithm
flo
flo

Reputation: 671

How to retrieve the max value of a function output

I have a function f(x). I want to calculate x where f(x) = max. How can I do that in a script?

Given: x is a positive number, f(x) can be positive or negative. I want to start with x = 1. If f(1) is already negative I'm not interested anymore. With increasing x, also f(x) returns increasing values, until a peak is reached, and then f(x) decreases. x at the peak is what I am interested in.

EDIT: Ok what I tried so far:

I tried starting with x = 1, then x *=2. If f(x) is smaller then the last result, I set back x to x/4.

Example: f(16) = 9, f(32) = 11, f(64) = 10. The peak can be between x=16 and x=64. So my new starting point is f(16). From there on, I want to continue in a similar way, but I cant find an algorithm.

Here is what I got so far:

let x = 1
let lasty = 0
let holder = 1

while (iteration++ < 20) {   
    
    let y = myFunction(x)

    if(y < lasty ) {
        x = x / 4   
        holder = 1         
    }          
    
    x += holder * 2  
    holder += 1     

    lasty = y

}

EDIT2: My improved version which works quite good but for sure not perfect:

let x = 1
let lasty = 0  
let iteration = 0 
let previousX = 1
let lastX = 1
let step = 2
let maxY = -Infinity
let bestX = 0

let randomInput = Math.random

while (iteration++ < 20) {    

    let y = myFunction(x, randomInput) //added randomInput to show the function does not rely on x alone
    
    if (y < 0 && iteration == 1) break  

    if(y > maxY) {
        maxY = y
        bestX = x
    }

    if (y < lasty) {
        x = previousX
        step *= 0.8
        lasty = 0
    } else {
        previousX = lastX
        lastX = x
        x = x * step 
        lasty = y
    }
}

if(bestX > 0) {
    console.log(`Got best x: ${bestX}`)
}

EDIT3: Added random additional parameter to emphasise the needed approach

EDIT4: I should also mention that the probability of f(x) = max is the highest when 0 < x < 100000

Upvotes: 1

Views: 173

Answers (3)

Scott Sauyet
Scott Sauyet

Reputation: 50797

If you know the function has a single peak in a given range, and the closest value within a tolerance is acceptable, then a simple binary search should be all you need. Here we default the range to the entire safe integer range, but you can supply your own with findPeak (tolerance) (fn, rangeMin, rangeMax), perhaps something like findPeak (1e-8) (fn, 0, 100000).

const findPeak = (ε) => (
  fn, 
  min = Number.MIN_SAFE_INTEGER, 
  max = Number.MAX_SAFE_INTEGER, 
  mid = min / 2 + max / 2
) => 
  max - min < ε
    ? mid
  : fn (min) < fn (max)
    ? findPeak (ε) (fn, mid, max)
  : findPeak (ε) (fn, min, mid)

const fn = n => 600 + 50 * n - n ** 2

console .log (findPeak (1e-8) (fn)) //=> 24.99999991050572

This code is simple. It is less efficient than it might be if we took advantage of the fact that we will reuse fn (min) or fn (max) on each subsequent call, and probably would be faster with a while loop rather than the recursion. I'll leave such optimization to you. But I would first see if this is already fast enough, as simple code is much easier to work with.

Upvotes: 1

Aleks Shenshin
Aleks Shenshin

Reputation: 2196

It could be solved using recursive function calls.

// array of arguments
const args = [...Array(16).keys()];
// sample function
const sampleFunc = (x) => Math.sin(x);
// recursive function
function getElementWithFuncMaximum(arr, func, index = 0, currValue = 0) {
  const currFuncValue = func(arr[index]);
  return currFuncValue >= currValue 
    ? getElementWithFuncMaximum(arr, func, index + 1, currFuncValue)
    : arr[index - 1];
}
console.log(getElementWithFuncMaximum(args, sampleFunc));

Upvotes: 1

Tom
Tom

Reputation: 1188

Assuming you want to maximise y, You can just store the x and y values where xy is highest:

let highestX = 1; // this is just the corresponding x value for the highest y
let highestY = -Infinity;

let x = 1
let lasty = 0
let holder = 1

while (iteration++ < 20) {   
    
    let y = myFunction(x);

    // code for storing the highest y and corresponding x
    if (y > highestY) {
        highestY = y;
        highestX = x;
    }

    if(y < lasty ) {
        x = x / 4   
        holder = 1         
    }          
    
    x += holder * 2  
    holder += 1     

    lasty = y

}

console.log('f(x) is maximised when x =', highestX);

Upvotes: 2

Related Questions