How Can I Optimize a Function with Nested Variables in C++?

[erotavlas85]

Hi,
I have to compute the optimal value of function of several variables. The function is maximized and/or minimized by nested variables x,y... For instance min(x) max(y) f(x,y).
The function is known and the variables take a values from a known finite domain. I have thought a solution where I store a matrix of all possible values for x, y and the value of the function for every pair of values. After I can find the value of y for which the function is maximum, then I can find in the set of the remaining possible values for x, the value for which the function is minimized by x. This reasoning can be extended to a big number of nested variables.
My approach is not very efficient for a large number of variables...
Do you have a better idea than mine?

Thank you

 

[chiro]

Hi,
I have to compute the optimal value of function of several variables. The function is maximized and/or minimized by nested variables x,y... For instance min(x) max(y) f(x,y).
The function is known and the variables take a values from a known finite domain. I have thought a solution where I store a matrix of all possible values for x, y and the value of the function for every pair of values. After I can find the value of y for which the function is maximum, then I can find in the set of the remaining possible values for x, the value for which the function is minimized by x. This reasoning can be extended to a big number of nested variables.
My approach is not very efficient for a large number of variables...
Do you have a better idea than mine?

Thank you

Hey erotavlas85 and welcome to the forums.

I'm not exactly sure what you're trying to find. When I read your statement min(x) max(y) f(x,y) I read that as first getting the smallest x, the largest y and finding f(x,y) which would be trivial.

If however you want to find say max(f(x,y)) or min(f(x,y)) and you have no constraints on your function values in your domain (i.e. the function could be polynomial, rational, or some other function like a superpolynomial etc), then the general case would simply be the size of the data set with a running time of O(n).

Maybe I'm completely off on what you're asking. If you want to find something like min(f(x,y)) or max(f(x,y)), its going to going through all of the elements (with the assumption that there is no information you can use to reduce your search time) which is a simple for loop.

I think I'm misunderstanding you though.

 

[erotavlas85]

Thank you for welcome and for the answer.
Probably I have not explained well what I should do.
I have a function of several variables like f(x,y,z) = x+y+z (trivial example) and I want to find the value of the variables x,y,z for which the function assume the assume the optimal value. The operations of min/max are nested like min over x min over y max over z of f(x,y,z). The optimal value depends on the domain from which the variables x,y,z take the their values. The domain is known.

For example in trivial case where the domain for all variables is the same and it is composed of (0,1)
max over z f(x,y,z) = 3 (x = 1, y = 1, z = 1)
min over y f(x,y,1) = 1 (x = 0, y = 0, z = 1)
min over x f(x,0,1) = 1 (x = 0, y = 0, z = 1)
The optimal value is 1 for x = 0, y = 0, z = 1.

I can use a sort of recursive method to evaluate a variable at a time. From the internal one to the external one.

Now, I hope I was more clear.

 

[chiro]

Thank you for welcome and for the answer.
Probably I have not explained well what I should do.
I have a function of several variables like f(x,y,z) = x+y+z (trivial example) and I want to find the value of the variables x,y,z for which the function assume the assume the optimal value. The operations of min/max are nested like min over x min over y max over z of f(x,y,z). The optimal value depends on the domain from which the variables x,y,z take the their values. The domain is known.

For example in trivial case where the domain for all variables is the same and it is composed of (0,1)
max over z f(x,y,z) = 3 (x = 1, y = 1, z = 1)
min over y f(x,y,1) = 1 (x = 0, y = 0, z = 1)
min over x f(x,0,1) = 1 (x = 0, y = 0, z = 1)
The optimal value is 1 for x = 0, y = 0, z = 1.

I can use a sort of recursive method to evaluate a variable at a time. From the internal one to the external one.

Now, I hope I was more clear.

Let me see if I am getting you right (thinking out aloud).

you have a function of so many variables like in your example you had three, but you could have as many as you want. The function returns a single number.

Lets use the above example you gave as a template:

You find the maximum value of the function for any x,y and z. You record the z value for later use. If there are two or more values that give the same maximum value, you choose the smallest z (you haven't specified what to do in this case so if its wrong please correct me)

Then then find the minimum value of the function making z constant (the value you found in the first run) and record the y value. Again if there are two minimums, you take the lowest y value (Again correct me if this is wrong).

You then find the minimum value of the function making both z and y constant (found in previous calculations) and find the x that gives a minimum value. If there are more than one x that give a minimum value you choose the lowest x value.

You record the values you found for x, y and z and return them back to your program.

So just to recap, you find max(f(x,y,z)) for all values of x,y and z and store a z. Then you find min(f(x,y,Z)) (Z is fixed) and get your y. Then you find min(f(x,Y,Z)) (you know Z and Y) to get your x. Then you return your X, Y, and Z.

Is this the right algorithm?

 

[Dale]

Thank you for welcome and for the answer.
Probably I have not explained well what I should do.
I have a function of several variables like f(x,y,z) = x+y+z (trivial example) and I want to find the value of the variables x,y,z for which the function assume the assume the optimal value. The operations of min/max are nested like min over x min over y max over z of f(x,y,z). The optimal value depends on the domain from which the variables x,y,z take the their values. The domain is known.

For example in trivial case where the domain for all variables is the same and it is composed of (0,1)
max over z f(x,y,z) = 3 (x = 1, y = 1, z = 1)
min over y f(x,y,1) = 1 (x = 0, y = 0, z = 1)
min over x f(x,0,1) = 1 (x = 0, y = 0, z = 1)
The optimal value is 1 for x = 0, y = 0, z = 1.

I can use a sort of recursive method to evaluate a variable at a time. From the internal one to the external one.

Now, I hope I was more clear.

This sounds like a standard "constrained optimization" question. When solving any optimization problem you will need to classify your function a bit. Specifically, do you know the derivative of your function within the domain. Is it a smooth and well-behaved function everywhere. Are there multiple local minima. Etc.? Those answers will limit which approaches you can use.

 

[erotavlas85]

Let me see if I am getting you right (thinking out aloud).

you have a function of so many variables like in your example you had three, but you could have as many as you want. The function returns a single number.

Lets use the above example you gave as a template:

You find the maximum value of the function for any x,y and z. You record the z value for later use. If there are two or more values that give the same maximum value, you choose the smallest z (you haven't specified what to do in this case so if its wrong please correct me)

Then then find the minimum value of the function making z constant (the value you found in the first run) and record the y value. Again if there are two minimums, you take the lowest y value (Again correct me if this is wrong).

You then find the minimum value of the function making both z and y constant (found in previous calculations) and find the x that gives a minimum value. If there are more than one x that give a minimum value you choose the lowest x value.

You record the values you found for x, y and z and return them back to your program.

So just to recap, you find max(f(x,y,z)) for all values of x,y and z and store a z. Then you find min(f(x,y,Z)) (Z is fixed) and get your y. Then you find min(f(x,Y,Z)) (you know Z and Y) to get your x. Then you return your X, Y, and Z.

Is this the right algorithm?

The answer is yes, but with little trick. When you say "If there are two or more values that give the same maximum value, you choose the smallest z" is not correct. The correct expression is "If there are two or more values of a variable that gives the same maximum/minimum value, I choose all the the value of z". Then I can proceed to minimizing/maximizing the next variable (y) considering only the subset of values at the previous step. After the procedure continues and searches the value for the last variable (z) in the remaining available values.

 

[erotavlas85]

This sounds like a standard "constrained optimization" question. When solving any optimization problem you will need to classify your function a bit. Specifically, do you know the derivative of your function within the domain. Is it a smooth and well-behaved function everywhere. Are there multiple local minima. Etc.? Those answers will limit which approaches you can use.

This is no true. The problem is not constrained neither Linear Programming. I don't know the properties of the function and I can't use the information from the analysis because I'm on discrete field (unfortunately I don't know the discrete mathematics). My aim is to find the values for the variables for which the function is maximized or minimized from the variables in the correct order.

 

[Dale]

The domain can always be expressed as constraints.

 

[erotavlas85]

The domain can always be expressed as constraints.

Please, can you tell me how? Can you formulate my example as constrained optimization problem?

 

[erotavlas85]

Hi all,

I'm trying to solve my problem of optimize the function. The procedure that I have described in the previous post is valid? i.e. Can I optimize the function and finding the optimal value of each variable step by step?

Thank you

 

[chiro]

Hi all,

I'm trying to solve my problem of optimize the function. The procedure that I have described in the previous post is valid? i.e. Can I optimize the function and finding the optimal value of each variable step by step?

Thank you

Assuming you have a two dimensional function (like say z = x + y its two dimensional since z is linearly dependent on x and y) all you have to do is have three loops and inside these loops just implement your checking routine.

So for getting say the max of z you would have your two loops for x and y and some array for your z result and in the max case you store a temp variable and every time you get a bigger result than your temp (which is initialized to zero before your loop starts), you just store the index and the result.

At the end of this you'll have the maximum function value and the points (x and y) that created it.

Just adjust your test function and that will give you what you want

 

[erotavlas85]

Hi,

I have solved the problem (I hope). Here is the code that can compute an arbitrary number of nested variables (forall and exist) for a predefined function. Now, my question is: is my procedure valid?
Can I optimize the function step by step from the inner variable to the outer one?

int compute(const std::vector<std::pair<std::string, int> > & Indexes)
{

    int f = 0;
    for (int k = 0; k < Indexes.size(); ++k)
    {
        f += Indexes[k].second;
    }
    return f;

}

int min(const std::vector<int>& valueVector)
{

    int temp = valueVector[0];
    for (int i = 1; i < valueVector.size(); ++i)
    {
        if (valueVector[i] < temp)
            temp = valueVector[i];
    }

    return temp;

}

int max(const std::vector<int>& valueVector)
{

    int temp = valueVector[0];
    for (int i = 1; i < valueVector.size(); ++i)
    {
        if (valueVector[i] > temp)
            temp = valueVector[i];
    }

    return temp;

} 

    std::vector<std::pair<std::string, int> > myVector;
    std::vector<std::string> operatorType;

    std::pair<std::string, int> element1("x", 2);
    std::pair<std::string, int> element2("y", 3);
    std::pair<std::string, int> element3("z", 2);

    myVector.push_back(element1);
    myVector.push_back(element2);
    myVector.push_back(element3);
    
    operatorType.push_back("forall");
    operatorType.push_back("exists");
    operatorType.push_back("exists");
   
    unsigned long cardinality = 1;

    std::vector<std::vector<int> > tempResults;
    std::vector<std::vector<int> > finalResults;

    // new "cardinality", index
    std::vector<std::pair<int, int> > cardinalityIndexVector;

    // reverse the order of the vector of the variables
    reverse(myVector.begin(), myVector.end());
    reverse(operatorType.begin(), operatorType.end());

    std::vector<int> temp(0);

     std::cout << "Function " << std::endl;

    for (int i = 0; i < myVector.size(); ++i)
    {
        cardinality *= myVector[i].second;
        cardinalityIndexVector.push_back(std::pair<int, int> (cardinality, 0));
        tempResults.push_back(temp);
        finalResults.push_back(temp);
        std::cout << operatorType[i] << " " << myVector[i].first << " (" << myVector[i].second << ") ";
    }

    std::cout << "f() =" << std::endl;
    finalResults.push_back(temp);
    for (int i = 0; i < cardinalityIndexVector.size(); ++i)
    {
        cardinalityIndexVector[i].first = cardinalityIndexVector[i].first / myVector[i].second;
        
    }

    std::cout << "Cardinality " << cardinality << std::endl;

    for (unsigned long i = 0; i < cardinality; ++i)
    {
        std::vector<std::pair<std::string, int> > Indexes;
        std::vector<std::pair<std::string, int> > domainsVector;

        // loop over the vector of the quantified variable
        for (int j = 0; j < myVector.size(); ++j)
        {
            if (j == 0)
            {
                // first variable, initialization
                Indexes.push_back(std::pair<std::string, int> (myVector[j].first, i % myVector[j].second));
                domainsVector.push_back(std::pair<std::string, int> (myVector[j].first, i / myVector[j].second));

            }
            else if (j < myVector.size())
            {
                Indexes.push_back(std::pair<std::string, int> (myVector[j].first, domainsVector[j - 1].second % myVector[j].second));
                domainsVector.push_back(std::pair<std::string, int> (myVector[j].first, domainsVector[j - 1].second / myVector[j].second));
            }

            if (i == 0)
            {
                std::cout << myVector[j].first << " ";
            }

        }

        if (i == 0)
            std::cout << std::endl;

        for (int k = 0; k < Indexes.size(); ++k)
        {
            std::cout << Indexes[k].second << " ";
        }
        std::cout << std::endl;

        // loop over the vector of the quantified variable
        for (int j = 0; j < myVector.size(); ++j)
        {
            //std::cout << "i " << i << "j " << j << std::endl;
            // check if the current for loop is termined
            if (cardinalityIndexVector[j].second == cardinalityIndexVector[j].first - 1)
            {
                // compute the value of the function
                if (j == 0)
                {
                    //std::cout << "Compute " << compute(Indexes) << std::endl;
                    tempResults[j].push_back(compute(Indexes));
                    finalResults[j].push_back(compute(Indexes));
                }
                if (j > 0)
                {
                    if (operatorType[j - 1] == "forall")
                    {
                        //std::cout << "Max " << max(tempResults[j - 1]) << std::endl;
                        tempResults[j].push_back(max(tempResults[j - 1]));
                        finalResults[j].push_back(max(tempResults[j - 1]));
                        tempResults[j - 1].clear();
                    }
                    else if (operatorType[j - 1] == "exists")
                    {
                        //std::cout << "Min " << min(tempResults[j - 1]) << std::endl;
                        tempResults[j].push_back(min(tempResults[j - 1]));
                        finalResults[j].push_back(min(tempResults[j - 1]));
                        tempResults[j - 1].clear();
                    }
                }
                cardinalityIndexVector[j].second = 0;
            }
            else
                cardinalityIndexVector[j].second++;
        }

        if (i == cardinality - 1)
        {
            if (operatorType.back() == "forall")
            {
               // std::cout << "Final Max " << max(tempResults[myVector.size() - 1]) << std::endl;
                finalResults.back().push_back(max(tempResults[myVector.size() - 1]));
            }
            else if (operatorType.back() == "exists")
            {
                //std::cout << "Final Min " << min(tempResults[myVector.size() - 1]) << std::endl;
                finalResults.back().push_back(min(tempResults[myVector.size() - 1]));
            }

        }

    }
   
    std::cout << "Results " << std::endl;
    for (int i = 0; i < finalResults.size(); ++i)
    {
        for (int j = 0; j < finalResults[i].size(); ++j)
            std::cout << finalResults[i][j] << " ";
        std::cout << std::endl;
    }
    std::cout << std::endl;

Thank you