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

7 次查看（过去 30 天）
JJLeov
JJLeov 2015-9-29
编辑： Walter Roberson 2015-10-1
I want to minimize - min(x,y) subject to the constraint x + y <= 10 .
Which function / Tool should I use?

请先登录，再回答此问题。

回答（3 个）

Walter Roberson
Walter Roberson 2015-9-29
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.
JJLeov
JJLeov 2015-9-29
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.
  3 个评论
显示 1更早的评论
JJLeov
JJLeov 2015-9-30
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
Walter Roberson 2015-9-30
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.

请先登录，再进行评论。

Johan Löfberg
Johan Löfberg 2015-10-1
编辑：Walter Roberson 2015-10-1
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.

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by