Min and max of a function in C++

[ivaylo91]

Good evening to everyone. I have some troubles with a task I have to do. I need some assistance. Excuse me if I haven't searched thoroughly in the forum and there is a similar topic somewhere. Thank you!

Here's the issue:

Compute the minimal and the maximal value of function f(x,y) obtained on an integer point in a given rectangle [a, b] x [c, d]. The program should prompt the user to input numerical values of a, b, c and d, as floating point numbers, which are expected to be in a range from -100 thru 100. In case when minimal or maximal values do not exists, your program should output appropriate messages.
Send the source code of your program together with the calculated integer values of x and y for which f(x,y) reaches its minimum and maximum on [a, b] x [c, d].

My case:
16. a=5, b=7, c=1, d=20, f(x,y)=(x+1)/(y-1);

I'm really stuck and I don't know what exactly to do. I'll be very thankful if you give me some clues. Thank you one more time!

[VernonDozier]

Seems like part math problem, part computer science problem. You could brute force it, I suppose (i.e. don't solve it mathematically by deriving an equation ahead of time), or you could figure it out mathematically based on a, b, c, and d, stick some formula involving a, b, c, and d, then stick that into the program.

My advice would be to go the math route. It's a simple enough equation. Chart some rectangles, plot the graphs, and get the answer mathematically. When you have the math angle down, tackle the computer programming aspect of it.

>> In case when minimal or maximal values do not exists, your program should output appropriate messages.

This one is all math. Figure out the values where the equation can't be calculated (i.e. divide by zero error).

[vijayan121]

Since x, y are integers limited to the inteval [ -100, +100 ] there are just 200*200 == 40000 possible tuples (x,y). Just use brute force.

[arkoenig]

Since x, y are integers limited to the inteval [ -100, +100 ] there are just 200*200 == 40000 possible tuples (x,y). Just use brute force.

201 * 201 = 40401 possible tuples.

[vijayan121]

> 201 * 201 = 40401 possible tuples.
Yes, 40401 tuples. Thanks.

[ivaylo91]

God, I've always had troubles with maths. Anyway, going to bed right now. Tomorrow I'll take your advices into consideration and see what is going on. Thank you very much for the support.

[StuXYZ]

First off, absolute brute force isn't going to work in this case as the input is in floating point, and you can easily get a function that has maxima at non-integer values.

Next, the finding of minima/maxima of a function in a range, is still an active research topic. Even some very simple functions have large number of mimina/maxima in an interval and determining the global maxima is difficult.

Given that, here are two approaches that you might like to consider, first is to calculate the partial derivatives and solve the simulation equation you get when you set both to zero. Note that you will, get maximums, minimiums and saddle points [dependent on the function]. The find the range that you have selected and if any are valid. This will lead to a large and complex program if it has to be done for a user entered function. It will lead to a simple program, that might not even need the user function for a specified function as given. [You just put in a table of the max/min. and find out if you which are within the users input interval]

Now, you can observer that for a function of 2 or more variables there is not a simple solution bracketing approach [as is often done with 1 variable problems]. There are approaches that use the steepest decent method [Let us consider finding a minima, just reverse the logic for a maxima] and then you can use this horribly simplified algorithm to find ONE minima over the range. [Then it gets messy to find all the others.]

Consider the interval point (a,b,c and d).

First calculate the direction of the derivative at each point either numerically, or analytically.

If all go up, then you may have no solutions not -- that takes more subdivision to find.

If one or more go down project down that direction of the steepest decent point, e.g. a -> a'. and find the lowest point along that trajectory. Do on exceed the interval bounds. Continue doing that at point a' to point a'' an so on.
Eventually, you will come to a point which is within numerical tolerance, the minimum, or at the boundary.

There are some server numerical issues with that simple approach, so please read up on it. [It is called the steepest decent method]

There are many other, for a multi-bound system, a simplex reduction often is used, as are more sophisticated and numerically robust methods.

Hope this helps, if you go down one of these numerical routes, feel do post follow up questions. There are several very numerically able people on these forum, can often provide highly insightful analysis.

Finally, the problem with your function as given is the singularity at y=1 and the lack of a proper max/minima. I would check it, if given in a question paper.

[ivaylo91]

Wow, thank you very much. Appreciate the fact you gave such an explanation. Thank you!

[arkoenig]

First off, absolute brute force isn't going to work in this case as the input is in floating point, and you can easily get a function that has maxima at non-integer values.

The original problem statement constrains the arguments to integer values.

[VernonDozier]

>> First off, absolute brute force isn't going to work in this case as the input is in floating point, and you can easily get a function that has maxima at non-integer values.

From the original problem statement (see red):

Compute the minimal and the maximal value of function f(x,y) obtained on an integer point in a given rectangle [a, b] x [c, d]. The program should prompt the user to input numerical values of a, b, c and d, as floating point numbers, which are expected to be in a range from -100 thru 100. In case when minimal or maximal values do not exists, your program should output appropriate messages.
Send the source code of your program together with the calculated integer values of x and y for which f(x,y) reaches its minimum and maximum on [a, b] x [c, d].

The INPUT is floating point, but that floating point is going to quickly be rounded to make it an integer The SOLUTION has the stipulation that x and y must be integers. Therefore if the formula had a maximum at, say (2.5, 3.5), that would not be the correct answer. You need to find the (x,y) pair where f(x,y) has the maximum value and x any y are integers. The program needs to take the floating point input and figure out the appropriate rectangle bounds, which will also be integers (i.e. if the user enters bounds of (-9.5, -9.5) to (9.5, 9.5), the real boundaries would be (-9,9) to (9,9)). If that was the case, you would have 19 times 19 = 361 values to compute and compare, so brute force could work.

That's my reading of it anyway. However, even if my reading of the problem statement is accurate, I've seen far too many professors who will give the following assignment:

Now change your program so that the boundaries are -2 billion to 2 billion instead of -100 to 100.

Brute force in this case is less feasible, so you would want to do some math and get rid of a lot of those points.

[ivaylo91]

I make a huge mistake somewhere when I need to obtain the min and the max. Something with the if conditions perhaps. And what happens if y=1 ... It's a division by 0, so perhaps I should write a statement to check this.

One more time, excuse me for my great incompetence in maths and thanks for all the help.

#include <iostream>
using namespace std;

int main()
{
 double a,b,c,d,x,y,f;
 int min=0;
 int max=0;

 cout<<"Please, enter values for a,b,c and d:"<<"\n";
 cout<<"a = ";
 cin>>a;

 cout<<"b = ";
 cin>>b;

 cout<<"c = ";
 cin>>c;

 cout<<"d = ";
 cin>>d;
if (a>100 || b>100 || c>100 || d>100 || a<-100 || b<-100 || c<-100 || d<-100)
{
cout << "Bad input. The numbers must be in the interval [-100, 100] ";
}
else
 {
      for ( x=a; x<=b; x=x+0.01)
           {
            for ( y=c; y<=d; y=y+0.01)

                  f=(x+1)/(y-1);
                  if (min>f) f=min;
                  if (max<f) f=max;
                  cout<<"f = "<<f<<"\n";
                  

          }
 }
 
 


 
 cout << "f(min) = " << min << "\n";
 cout << "f(max) = " << max << "\n";
 
 system ("PAUSE");
 return 0;
}

[VernonDozier]

>> And what happens if y=1 ... It's a division by 0, so perhaps I should write a statement to check this.

Yes, you should check this. But before you check whether y is 1, you should decide what needs to be done when y is 1. You won't divide, but what will you do?

[StuXYZ]

First off I wish to apologizes for failing to read the ivaylos91's question properly, as was pointed out by arkoenig and VernonDozier.

Second, I have not re-read the question, and would like to ask another about ivaylos91's code.

1) The question does not seem to imply that (a) f(x,y) is itself integer, only that the values x and y are integer. Thus you should be very careful defining min and max as integer, they would be probably be better as float.

2) min and max should not be initialized to zero. For example the function f(x,y)
might have a maximum value of -1.0, or a minimum value above zero. (It is normal to initialize to a start value of x,y e.g. if the range is -50,-50 to 50,50 you might like to start with min=max=f(-50,-50); but any value within the range
is perfectly acceptable. (e.g. f(0,0) if you like.)

3) Be careful on line 33/34 that you can't set f to max but you want to set max to f.

4) you look increases by 0.01, was that just for testing, because I expected an increase of 1.0 per step.

5) Subtle I know, but you have missed the inner brace pair { } on the inner loop.

Finally, I horribly suspect that VernonDozier is right, that you will be asked to change the boundaries, especially since such an unpleasant function was picked to test your algorithm with. In that case a steepest decent method, with integer step numerical derivatives and integer steps is going to be a possible solution, if the solution does not have too many local max/minima.

[Cosmin871]

A more elegant solution to this problem is to search in all directions for the improvement and advance step-by-step, like optimization methods do.

#include <stdio.h>

float functionValue( float x, float y )
{
	if ( y != 1 )
		return ( x + 1 ) / ( y - 1 );
}

void calculateMinimumValue( float a, float b, float c, float d )
{
	float x = ( a + c ) / 2;
	float y = ( b + d ) / 2;
	float searchPrecision = 0.0000001;

	while ( true )
	{
		// search in all 8 directions for a smaller value
		if ( ( functionValue( x + searchPrecision, y ) < functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) )
		{
			x += searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision, y ) < functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) )
		{
			x -= searchPrecision;
		}
		else if ( ( functionValue( x , y + searchPrecision ) < functionValue( x, y ) ) &&  ( y >= b ) && ( y <= d ) )
		{
			y += searchPrecision;
		}
		else if ( ( functionValue( x , y - searchPrecision ) < functionValue( x, y ) ) &&  ( y >= b ) && ( y <= d ) )
		{
			y -= searchPrecision;
		}
		else if ( ( functionValue( x + searchPrecision , y + searchPrecision )  < functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x += searchPrecision;
			y += searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision , y - searchPrecision )  < functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x -= searchPrecision;
			y -= searchPrecision;
		}
		else if ( ( functionValue( x + searchPrecision , y - searchPrecision )  < functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d )  )
		{
			x += searchPrecision;
			y -= searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision , y + searchPrecision )  < functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x -= searchPrecision;
			y += searchPrecision;
		}
		else 
			break; // Quit if there isn't an improvement
	}
	printf( "The minimum value was found in (%f,%f)", x, y );
}

void calculateMaximumValue( float a, float b, float c, float d )
{
	float x = ( a + c ) / 2;
	float y = ( b + d ) / 2;
	float searchPrecision = 0.0000001;
	
	while ( true )
	{
		// search in all 8 directions for a bigger value
		if ( ( functionValue( x + searchPrecision, y ) > functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) )
		{
			x += searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision, y ) > functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) )
		{
			x -= searchPrecision;
		}
		else if ( ( functionValue( x , y + searchPrecision ) > functionValue( x, y ) ) &&  ( y >= b ) && ( y <= d ) )
		{
			y += searchPrecision;
		}
		else if ( ( functionValue( x , y - searchPrecision ) > functionValue( x, y ) ) &&  ( y >= b ) && ( y <= d ) )
		{
			y -= searchPrecision;
		}
		else if ( ( functionValue( x + searchPrecision , y + searchPrecision )  > functionValue( x, y ) ) &&  ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x += searchPrecision;
			y += searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision , y - searchPrecision )  > functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x -= searchPrecision;
			y -= searchPrecision;
		}
		else if ( ( functionValue( x + searchPrecision , y - searchPrecision )  > functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d )  )
		{
			x += searchPrecision;
			y -= searchPrecision;
		}
		else if ( ( functionValue( x - searchPrecision , y + searchPrecision )  > functionValue( x, y ) ) && ( x >= a ) &&  ( x <= c ) &&  ( y >= b ) && ( y <= d ) )
		{
			x -= searchPrecision;
			y += searchPrecision;
		}
		else 
			break; // Quit if there isn't an improvement
	}
	printf( "\nThe maximum value was found in (%f,%f)", x, y );
}

int main()
{
	float a, b, c, d;
	printf("a = ");
	scanf( "%f", &a );
	printf("b = ");
	scanf( "%f", &b );
	printf("c = ");
	scanf( "%f", &c );
	printf("d = ");
	scanf( "%f", &d );
	calculateMinimumValue( a, b, c, d );
	calculateMaximumValue( a, b, c, d );
}

[ivaylo91]

StuXYZ, thanks for breaking the problem down into simple parts and explaining it to me, i think i finally got it all the way. :)
Cosmin871, very elaborate and interesting approach. I got the idea and seeing how the things work gave me even more light on the problem.

I'll put your advices and examples on the line and I hope it will be all right. Appreciate all the help. I wish you all the best and perhaps we'll discuss more issues for days to come. And forgive me for being such a lame. Thanks! :)