4 ms·

sorry for sidetracking your answer but what actually does convex mean in the context of optimization. I remember looking at a book called convex optimization.

by alwahi 6y ago

sorry for sidetracking your answer but what actually does convex mean in the context of optimization. I remember looking at a book called convex optimization. Your statement that > Motion planning is very much non-convex, suggests to me that you are very much talking about the same thing. I understand convexity as in a shape. Why is convex good and concave bad in terms of optimization? I don't want you to dumb down the answer too much as I am a trained Mechanical Engineer but then my major isn't math. Hope you understand :)

fxtentacle 6y ago
Think of numerical optimization (e.g. gradient decent) as if you're letting a marble run down a hill. Only for some hill shapes can you be sure that the marble will reach the bottom. For other shapes, it'll get stuck on a small flat or in a small hole. Those would be called zero gradient or local minima failures. If your hill has a convex shape, then the marble will always roll up the bottom eventually.
- cpgxiii 6y ago
  It's generally understood that motion planning for nontrivial problems is very non-convex, and it's basically impossible to predict if a given initial condition can be optimized to the global optima. Even simple convex 3D geometry in the environment projects to very complex non-convex geometry in the configuration space of the robot (the space you're performing optimization in).
  - fxtentacle 6y ago
    While that is true, the critical question is whether it will be locally smooth once you get close enough to your goal. Long-distance planning is generally bad, even for humans. Short-distance planning tends to work well with A-star
    - cpgxiii 6y ago
      The problem is that "distance" here is not necessarily in any intuitive or useful space, and knowing if you are close to the goal may be as hard as finding the full solution. You can be quite "close" to a solution in, say, Euclidean distance over joint angles, while constraints like joint limits and collisions mean that the actual solution path will be quite long.
      - fxtentacle 6y ago
        I apologize, I hadn't thought about robot arms. All the planning stuff that I was involved with so far was either quadcopters or slowfliers or buggies, so only cases where the Euclidean norm is useful.
- alwahi 6y ago
  this was so apt and it makes so much sense. a bulb just went on in my head. thanks so much for your simple and precise explanation.
kajecounterhack 6y ago
> what actually does convex mean in the context of optimization It means there's a deterministic solution. Longer explanation: When you're optimizing a function in math, the function's solutions exist in N-dimensional space. If the space of solutions is a hyperplane in this space, and you want to find a value on that plane that minimizes the function, a convex plane will allow you to find the minimum every time, deterministically -- one way is to simply follow the negative gradient of the plane. A non-convex plane may have lots of holes or other shapes (e.g "saddle points"), so if you follow the negative gradient, you'll end up thinking you're at a minimum, but turns out you're only at a _local_ minimum and there may be another, better solution out there. So whenever you see "convex" read: a best solution exists. Whenever you see "non-convex" read: an approximation is your best hope. Motion planning is non-convex. From https://en.wikipedia.org/wiki/Convex_function https://en.wikipedia.org/wiki/Convex_function: "Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.[4]"
YeGoblynQueenne 6y ago
Convex/ non-convex optimisation refers to the shape of the error function we're trying to optimise. In convex optimisation we can assume it's, well, convex: . . ε \ / \ / \ / \ / '._ _.' ^ Global optimum In non-convex optimisation we can't make any assumption about the shape of the error function: ,--. .--. ε / \ / \ ,--. / \ / \ / \ / .' \ / \ / \ / \ / \ / \ / `--' \ / `--' ^ \ / ^ | `--' | | ^ | | | | | | | `--------- Local optima ----------' "Optimisation" means that we're trying to find an optimum of a function - a maximum or a minimum. We're usually interested in the minimum of a function, particularly a function that represents the error of an approximator on a set of training data. Generally we prefer to find a _global_ minimum of the error function because then we can expect the resulting approximator to generalise better to data that was not available during training. If the error function has a convex shape we're basically guaranteed to find its global minimum. In non-convex optimisation, we're guaranteed to get stuck to local minima. (Ok, the above is a bit tongue in cheek, there's no _guarantee_ of getting stuck to local minima, but it's very likely).
- dorgo 6y ago
  >Generally we prefer to find a _global_ minimum of the error function because then we can expect the resulting approximator to generalise better to data that was not available during training. Sorry to nitpick, but is this true? We are doing optimization here and a global minimum is just a better solution than a non-global minimum. Is there a connection to generalisation here?
  - cpgxiii 6y ago
    In an ML context, the global optima may often correspond to better performance and (hopefully) a more general solution. In a motion planning or controls context, a local minima can often mean a configuration or path that is infeasible due to collision or wildly inefficient.

by alwahi 6y ago

fxtentacle 6y ago

Think of numerical optimization (e.g. gradient decent) as if you're letting a marble run down a hill. Only for some hill shapes can you be sure that the marble will reach the bottom. For other shapes, it'll get stuck on a small flat or in a small hole. Those would be called zero gradient or local minima failures. If your hill has a convex shape, then the marble will always roll up the bottom eventually.

cpgxiii 6y ago
It's generally understood that motion planning for nontrivial problems is very non-convex, and it's basically impossible to predict if a given initial condition can be optimized to the global optima. Even simple convex 3D geometry in the environment projects to very complex non-convex geometry in the configuration space of the robot (the space you're performing optimization in).
- fxtentacle 6y ago
  While that is true, the critical question is whether it will be locally smooth once you get close enough to your goal. Long-distance planning is generally bad, even for humans. Short-distance planning tends to work well with A-star
  - cpgxiii 6y ago
    The problem is that "distance" here is not necessarily in any intuitive or useful space, and knowing if you are close to the goal may be as hard as finding the full solution. You can be quite "close" to a solution in, say, Euclidean distance over joint angles, while constraints like joint limits and collisions mean that the actual solution path will be quite long.
    - fxtentacle 6y ago
      I apologize, I hadn't thought about robot arms. All the planning stuff that I was involved with so far was either quadcopters or slowfliers or buggies, so only cases where the Euclidean norm is useful.
alwahi 6y ago
this was so apt and it makes so much sense. a bulb just went on in my head. thanks so much for your simple and precise explanation.

kajecounterhack 6y ago

> what actually does convex mean in the context of optimization It means there's a deterministic solution. Longer explanation: When you're optimizing a function in math, the function's solutions exist in N-dimensional space. If the space of solutions is a hyperplane in this space, and you want to find a value on that plane that minimizes the function, a convex plane will allow you to find the minimum every time, deterministically -- one way is to simply follow the negative gradient of the plane. A non-convex plane may have lots of holes or other shapes (e.g "saddle points"), so if you follow the negative gradient, you'll end up thinking you're at a minimum, but turns out you're only at a _local_ minimum and there may be another, better solution out there. So whenever you see "convex" read: a best solution exists. Whenever you see "non-convex" read: an approximation is your best hope. Motion planning is non-convex. From https://en.wikipedia.org/wiki/Convex_function https://en.wikipedia.org/wiki/Convex_function: "Any local minimum of a convex function is also a global minimum. A strictly convex function will have at most one global minimum.[4]"

YeGoblynQueenne 6y ago

Convex/ non-convex optimisation refers to the shape of the error function we're trying to optimise. In convex optimisation we can assume it's, well, convex: . . ε \ / \ / \ / \ / '._ _.' ^ Global optimum In non-convex optimisation we can't make any assumption about the shape of the error function: ,--. .--. ε / \ / \ ,--. / \ / \ / \ / .' \ / \ / \ / \ / \ / \ / `--' \ / `--' ^ \ / ^ | `--' | | ^ | | | | | | | `--------- Local optima ----------' "Optimisation" means that we're trying to find an optimum of a function - a maximum or a minimum. We're usually interested in the minimum of a function, particularly a function that represents the error of an approximator on a set of training data. Generally we prefer to find a _global_ minimum of the error function because then we can expect the resulting approximator to generalise better to data that was not available during training. If the error function has a convex shape we're basically guaranteed to find its global minimum. In non-convex optimisation, we're guaranteed to get stuck to local minima. (Ok, the above is a bit tongue in cheek, there's no _guarantee_ of getting stuck to local minima, but it's very likely).

dorgo 6y ago
>Generally we prefer to find a _global_ minimum of the error function because then we can expect the resulting approximator to generalise better to data that was not available during training. Sorry to nitpick, but is this true? We are doing optimization here and a global minimum is just a better solution than a non-global minimum. Is there a connection to generalisation here?
- cpgxiii 6y ago
  In an ML context, the global optima may often correspond to better performance and (hopefully) a more general solution. In a motion planning or controls context, a local minima can often mean a configuration or path that is infeasible due to collision or wildly inefficient.