CODEWITHSUNDEEP
vb.netminimum
SJ Johnson
SJ Johnson

Reputation: 105

Finding minimum point of a function

If I have a convex curve, and want to find the minimum point (x,y) using a for or while loop. I am thinking of something like

dim y as double
dim LastY as double = 0
for i = 0 to a large number
  y=computefunction(i)
  if lasty > y then exit for
next

how can I that minimum point? (x is always > 0 and integer)

Upvotes: 1

Views: 188

Answers (2)

Victor Zakharov
Victor Zakharov

Reputation: 26424

For a sample function:

y = 0.01 * (x - 50) ^ 2 - 5

or properly written like this:

enter image description here

A minimum is mathematically obvious at x = 50 and y = -5, you can verify with google:

enter image description here

Below VB.NET console application, converted from python, finds a minimum at x=50.0000703584199, y=-4.9999999999505, which is correct for the specified tolerance of 0.0001:

Module Module1

  Sub Main()
    Dim result As Double = GoldenSectionSearch(AddressOf ComputeFunction, 0, 100)
    Dim resultString As String = "x=" & result.ToString + ", y=" & ComputeFunction(result).ToString
    Console.WriteLine(resultString) 'prints x=50.0000703584199, y=-4.9999999999505
  End Sub

  Function GoldenSectionSearch(f As Func(Of Double, Double), xStart As Double, xEnd As Double, Optional tol As Double = 0.0001) As Double
    Dim gr As Double = (Math.Sqrt(5) - 1) / 2

    Dim c As Double = xEnd - gr * (xEnd - xStart)
    Dim d As Double = xStart + gr * (xEnd - xStart)

    While Math.Abs(c - d) > tol
      Dim fc As Double = f(c)
      Dim fd As Double = f(d)

      If fc < fd Then
        xEnd = d
        d = c
        c = xEnd - gr * (xEnd - xStart)
      Else
        xStart = c
        c = d
        d = xStart + gr * (xEnd - xStart)
      End If
    End While

    Return (xEnd + xStart) / 2
  End Function

  Function ComputeFunction(x As Double)
    Return 0.01 * (x - 50) ^ 2 - 5
  End Function

End Module

Side note: your initial attempt to find minimum is assuming a function is discrete, which is very unlikely in real life. What you would get with a simple for loop is a very rough estimate, and a long time to find it, as linear search is least efficient among other methods.

Upvotes: 1

David Wilson
David Wilson

Reputation: 4439

Very Close

you just need to

dim y as double
dim smallestY as double = computefunction(0)
for i = 0 to aLargeNumber as integer
    y=computefunction(i)
    if smallestY > y then smallestY=y
next
'now that the loop has finished, smallestY should contain the lowest value of Y

If this code takes a long time to run, you could quite easily turn it into a multi-threaded loop using parallel.For - for example

dim y as Double
dim smallestY as double = computefunction(0)
Parallel.For(0, aLargeNumber, Sub(i As Integer)
                                  y=computefunction(i)
                                  if smallestY > y then smallestY=y
                               End Sub)

This would automatically create separate threads for each iteration of the loop.

Upvotes: 1

Related Questions