Non linear - The final Flashcards
Why do we want convex constraints? What do they do graphically?
If we have a convex constraint, for instance x^2, we know that if we traverse along it, once we enter the point where we are no longer inside of the feasible region, we will never come back into the feasible region.
In the image, h is the objective function. As we can see, if we traverse along x-values from right to left, the objective function keeps increasing and increasing as we move. then, when we eventually reach x=-2, we know, since the constraint is convex, that we we are leaving the feasible region for good. Therefore, we can say with confidence that the point we have found as optimal up to now will be the global optimal.
Explain why a constraint on the form g(x)<=b results in a convex feasible region when g(x) is convex. Does this even make any sense? We know that all points BELOW a convex function g(x) marks a convex set, but this is not the region we are after????
We use the line given by “b” as a concave function. It is linear, so it will be both convex AND concave. This is because it is linear.
We further know that all points BELOW any concave function is a convex set/region.
Then we use the constraint function g(x). If this function is convex, we know that all points lying ABOVE it marks a convex set.
Then we use the property that the intersection of convex sets is in fact a convex set as well. Therefore, the feasible region becomes a convex set/region under these circumstances.
why is concave constraint bad?
Consider what happens on the image.
Due to the concave nature of the constraint, once we leave the feasible region, we dont know if we will re-enter it. Therefore, we need to continue searching/traversing along the x-values.
Elaborate on gradients
The gradient tells us “the rate of change we will get if we move in the direction of steepest ascent”. the gradient is a vector. Its size represent the steepest ascent. Its direction, given by tan^(-1)(y/x) if 2D, is the relative movement across axes.
The direction of the gradient is always perpendicular to the level curve in the specific point.
Consider 1D: Say we have the function f(x)=3+2x. The gradient would be [2]. The size of the gradient is 2, indicating that if we move in the direction of steepest ascent, we will move at rate equal to 2 per unit in this direction. Since the vector is only single variable, we know it is only along x direction. Therefore, it tells us that if we move along x direction towards right, we will move at the direciton of the steepest ascent.
What does grad(f) = u grad(g) mean?
It is essentially an equation expressing parallel functions in a certain point. If gradient of f and gradient of g is the same direction, which we can more easily find by using the scalar as well, we can find important facts.
Elaborate on derivation of the Lagrange multiplier method
We start by recognizing that the point we are interested in possess the property that the gradient of f is equal to the gradient of g times some scalar, u.
However, because this equation is difficult to handle, we look for altenratives.
We then recognize the fact that if we take f - ug, and differentiate it for all different variables, we end up with the same expression as earlier: grad f - u times grad g => grad f = u grad g.
This is a good clue, and we continue on this path.
We also know that if g is equal t 0, the lagrangian function is not actually being changed in terms of value.
So, when we solve the system of equaitons from the different differentiations we get, we end up finding a point where we know that we are somewhere on the line/curve/surface/etc of the constraint, and the function we are optimizing will be located so that it stands tangential to g with regards to all different directions. In other words, the function f and function g are now parallell in all directions, AND we are located on the equality constraint.
Elaborate on why the first KKT condition is like it is
ok, so if we reach the point where increasing f incrementally in the “best” direction will violate g, we want gradient of g times u to make sure it never goes there. so, if the function f naturally wants to push itself as far out in the (x,y) plane as possible (or space etc), we will likely experience gradient g u as a “stopper” for this movement.
however, if f is such that it does not necessarily want to go as far out in the region as possible, then we would expect the gradient of f to be much smaller than gradient of g times u, because f is considering optimality at a point where the constraint is not binding. Therefore, the inuition is probably that the function f is being optimized and finds its “stationary” point while the gradient of g still have (probably) a positive gradient indicating that it would increase in value if relaxed.
