how to minimize the non-smooth function (- min(x,y) )

I want to minimize - min(x,y) subject to the constraint x + y <= 10 .

Which function / Tool should I use?

Answer 1

[Walter Roberson]

If the function is not smooth then it could have any number of "exceptions" that are arbitrarily narrow. You would need a global minimizer and even then it might not be able to find the minimum.

For example, x - (A*(x-17)).^(-1000) is effectively x except in the range [17-1/A, 17+1/A] with it being x-1 at those boundaries and effectively negative infinity inside the boundaries.

Because your non-smooth formula might have any number of narrow arbitrarily deep minima, the only way to minimize would be to examine every floating point number pair that satisfies the boundary condition.

If you had more information about the manner in which the function was non-smooth, it is possible that work-arounds might be found to allow minimization. For example if the location of the jumps was known ahead of time, then the problem could be broken up into a series of minimizations over limited ranges of values, with the global minima chosen as the smallest of those piecewise minima.

Answer 2

[JJLeov]

thank you for the comment.. My objective function is (- min(x,y) .. (subject to x+y <= 10) I suppose I cannot use fmincon.. but I am not sure how to proceed. Lv.

[Walter Roberson]

The solution to that is x = 5, y = 5.

The value of the function is not affected by whether we interchange x and y, so we can arbitrarily order them with x being the smaller member of the pair. This gives us the constraint that

x <= y <= 10-x

and so transitively, x <= 10-x . If x is negative then 10-x is always greater than x, but if x > 5 then 10-x is less than x. Therefore we have the constraint that

x <= y <= 5

Check the boundary condition first, x = 5, y = 5: -min(5,5) = -5 . So that is what we would have to beat to minimize -min(5,5)

But minimizing -min(x,y) is the same as maximizing min(x,y) . And that is obviously going to happen when x = y at the boundary, 5, so x = 5, y = 5

[JJLeov]

I see. Thank you. I see as well that in the solution.. x - y = 0 (it comes from the function -min(x,y)) x + y = 10 (it comes from the constraint). so..everything reduces to a linear system of equations. I only wonder if that I could do without using any special toolbox of Matlab.

[Walter Roberson]

The constrained minimizer fmincon() requires the Optimization Toolbox. If you do not have that then you need to reason you way through.

When you have a function in two variables in which the variables can be interchanged without affecting the form of the function, then you know that the optimum is going to occur when (A) the two variables are the same, or when at least one of them is +/- infinity, or at least one of them sets up a 0 or an infinity that makes the other one irrelevant, or at the boundary conditions of at least one of the variables. Or (B) possibly along a shape such as a circle, or every x within the constraints. The (A) group involves tests at a finite number of points; the (B) group involves an infinite number of solutions.

Answer 3

[Johan Löfberg]

You can write this particular instance using linear programming. Note that you are minimizing max(-x,-y). The function max is a convex function, and you can rewrite this using an epigraph reformulation (standard practice in optimization modelling). Introduce a new variable z, and you can minimize z under the constraints -x<=z, -y <=z, x+y<=10. Of course, you could just as well have worked with the concave min operator and z >= -min(x,y) to obtain z + min(x,y)>=0 which is equivalent to z + x >=0, z + y >=0.

I assume you actually want to solve something more complex though, as this trivially is solved manually.