Convexity 101 [Optimization Bootcamp]

[00:00:00]Welcome back. So we're talking about optimization theory and convexity is one of the cornerstone concepts we use all across the board in optimization of functions. So I'm going to have maybe a half a dozen or a dozen lectures on convexity. So there's going to be a whole bunch of deep dives into different aspects of convex sets and convex functions. But today I wanted to do kind of the very high level convexity 101.

[00:00:27]Just what does convexity mean? what are its implications in optimization at a high level before you go into the deep dive topics. So at a high level again we're generally talking about optimization problems of the following form. We're going to be trying to minimize some objective function uh subject to some constraints on the values that x can take and those constraints are typically uh inequality and equality constraints. So this comes up a lot in the context of machine learning. Maybe this is the loss function of you know some machine learning model that I'm trying to to optimize. And these constraint equations might be things like some parameters have to be non- negative or other parameters have to have some symmetry.

[00:01:09]There's all kinds of constraints that I would have given my objective function.

[00:01:14]Other examples might be that I'm trying to you know uh minimize uh downtime in a you know network flow problem and I have other constraints like connectivity constraints or maybe I'm trying to maximize a profit that's you know the opposite of minimization but let's say I'm trying to maximize a profit subject to constraints on you know how many employees I have how much um you know factory space I have how much time I have all kinds of constrained optimization ution problems are in this form. This is like the standard form and we have a cornerstone result of convex optimization theory that um this is a big deal. If my objective function f is a convex function like this uh kind of paraboid and if the set of feasible x's that are that satisfy these constraint equations is a convex set c. So if my function f is convex and my set of feasible points uh c is also convex then I have what is called a convex optimization problem and I have the following huge result that if I find a local minimum uh of the subjective function f then it's also going to be a global minimum um you know over all possible x's this will also be a global minimum and that's huge that means that if I can have some search strategy to find a local minimum, then I have guarantees that that local minimum is also global. It's the best I can possibly do for all x that satisfy these constraint equations. Okay, so I really want to know when are these constraint equations going to give me a convex set of feasible x? Um, this set is called C.

[00:02:59]And when is my objective function convex? Because if those two things are true, then I have this super powerful result in convex optimization. Okay, so that's why convexity is such an important idea because if you have convexity in your optimization problem, you have these powerful results and you have a lot of really really powerful tools to find these optimal solutions.

[00:03:21]Okay, so what is a convex set? Um, intuitively, if you've never seen convex set theory before, maybe you have, you've heard of it, and you have a picture in your mind of what a convex set is, like these uh these shapes here, but you don't know the definition. I'm going to define it for you. A convex set is a set so that if you take any two points in that set, any x and any y, then the line segment connecting those points is also inside the set. Okay? So this is convex and this is convex. A good example um yeah and so like any point on the line segment connecting these you can parameterize it like this.

[00:03:58]Any point on this line segment connecting any two points x and y has to be entirely in the set. And if that's true then that set is convex. If that's uh not true then the set is non-convex. So intuitively we think about it like if you have this shape that has this little bite taken out of it. Then there are points where the line segment connecting them there's pieces of that line segment that are not in the set. This is a non-convex set. That's the physical intuition and this is the definition. Similarly you can define convex functions to be any function. And here they're pictured in orange. The function is in orange. If you take any two points on that function, then the line segment connecting those two points has to be greater than or equal to that function. It can never dip below the function. So a lot of functions we're used to any even function like x^2, x 4th, x 6 like that is going to be a convex function. E to the x is a convex function. The rectified linear unit that we use in machine learning for um activation functions in neural networks is a convex function. A good example of a non-convex function is the sigmoidal hyperbolic tangent function because again there are points where that if you connect them with a line segment some of that line segment dips below the function. So that's a non-convex function. Okay. So this is just you know we're going to again have whole lectures uh diving into what it means to be a convex set what it means to be a convex function conditions on these related to the gradient of the function and thing you know things relating convex sets and convex functions there will be a whole bunch here but this is just the overview intuition of what it means to be convex.

[00:05:40]Okay.

[00:05:42]Um, good. And again going back to the fundamental result, this is why we care about convexity is because if you have a convex optimization problem, if your objective function f is convex and your feasible set that satisfies these constraint equations is convex, then any local minimum you find, if you find a local minimum uh, of this problem, then it's also a global minimum. That's a huge deal.

[00:06:07]Now, even if I have a non-convex function, this is a great example of a non-convex function again because there are points that if I connected them with a line segment, it would be under the the graph of the function. Even for non-convex uh objective functions, you can still optimize, but you're only going to be able to find a local optimum solution. You're going to find one of these local optima, and you're not guaranteed that it's global unless you search across all local optima. So you can use things like gradient uh descent um where you know the gradient of this function tells you the direction the function increases the fastest. Um and so you could specifically use gradient descent. You could take steps in the negative gradient uh grad f direction and that would walk you down to a little local minimum but you have no guarantees if that's a global minimum or not unless the function is convex. Okay. So that's the real power of convexity is that it tells you that if you find any local minima at all, it's also a global minima. That's a big deal. Okay, good. Um, so you know that's the picture here and I want to tell you when this uh optimization problem is a convex optimization problem. So we know that f our objective function has to be convex. But what are the conditions on these constraint equations for the feasible set to be convex? we need the inequality constraints the g to be a convex function and for the equality constraints h ofx equals d we need h to be what's called an aphine or a linear function okay so the way you can see this is pretty intuitive um I'm going to explain why these h of x have to be linear so if I have h ofx equals d you can actually write that as two inequality constraints we could say that h ofx is Um, this is incorrect. H of x is less than or equal to d or h of x is greater than or equal let me just make a a little uh correction here. Let's see if I can fix this on the spot. This should be a uh this should be a minus d here. So I can say if I have h ofx equals d then that is true if h ofx is greater than or equal to d and if h ofx is less than or equal to d and h ofx greater than or equal to d is the same as minus h ofx being less than or equal to negative d.

[00:08:33]Okay. And both of these have to be uh convex functions. I'm telling you that these inequality constraints have to be convex functions. The only way for both h ofx and minus h ofx to both be convex is if h ofx is linear. That's the only way that I can have h of x um and minus h of x both be convex is if h is linear.

[00:08:56]So that's why these linear uh the these equality constraint equations have to be linear. Sometimes we say aphine, but I just mean linear. Okay? Because those are the only functions that are both convex and concave. And the g of x is the actual inequality constraints. the g of x's also have to be convex functions.

[00:09:13]Um, we're going to talk a lot more about that later, why that's true. Um, but just know that if these g's are all convex functions, then these inequality constraints will give you a convex feasible set. Good. And I think I turned this up a little too much.

[00:09:31]Good. So, that's kind of the big idea here. And this comes up um a lot in um in a lot of different optimization problems like linear programming and quadratic programming. So a couple of other things I want to tell you in this kind of highle convexity 101 is that you know we've been talking about minimizing functions but you can also talk about maximizing functions. It's really also a convex optimization problem. Here we're just doing a concave maximization problem instead of a convex minimization problem. If I want to maximize a function f, it's exactly the same as minimizing minus f. So even maximization problems can be easily posed as a convex minimization problem. So we still call it convex optimization even if we're maximizing a concave function. Same basic idea. Uh we also have and they have the same optimum value. So the same x that maximizes f will also minimize minus f.

[00:10:27]So if I find that optimum solution of the minimization problem, it's also the optimization the optimum solution of this equivalent maximization problem. Um other cases, so sometimes we this is clearly a convex function f.

[00:10:42]This is actually what's called strictly convex. Um I'll tell you why in a minute. There are other examples of functions that are kind of barely convex where maybe it has like a convex function with a flat bottom. And so still if I find one of these, you know, one of these local minima is still the global minima. These all have an equivalent value of f. So they're all equivalent uh minima and they are the lowest you can get your function. So it's a global minima, but they're non-unique in this case because my function is barely convex. It has this flat bottom. Whereas here my function is called strictly convex. It always has curvature greater than zero, not just greater than or equal to zero. Here my curvature is actually zero. Here my curvature is always strictly positive which means that I have a unique global minima. So this is a technical detail.

[00:11:33]We'll talk about this later. But usually I'm talking about strictly convex functions but sometimes I'm talking about these barely convex functions.

[00:11:40]Both of them are convex and convex optimization applies. Okay. Um there are two huge classes of problems where this applies to. One is linear programming where you have a linear objective function and a set of linear inequality constraints. Uh linear functions are convex and so this feasible region is going to be a convex polytope and this uh objective function is also convex. So you get the basic uh this is a convex optimization problem.

[00:12:12]Local minima are global minima in this problem. And you have this kind of cool property that um the the local minimum is always going to be uh at one of the vertices of this polytope of this feasible set given by these inequality constraints because my objective function is linear. Technically it's both convex and concave. And so I could also write this as a maximization problem. And the local maximum of that problem will also be the global maximum.

[00:12:41]Uh so sometimes in linear programming I'm trying to maximize profit something like that um or maximize productivity and you basically because this functions convex and concave uh you can also solve the maximization problem and get all of those convex uh guarantees. The other big category of problems is quadratic programming where you have a quadratic cost function and the same linear inequality constraints.

[00:13:07]So you still have a nice uh kind of poly polytope feasible region. But now my objective function is quadratic in the state variable x. This is not both convex and concave. This is only uh convex and it's only convex if q is positive semidefinite. Okay. So and in that case again you'll have a convex optimization problem where local minima are guaranteed to be global minima. So the biggest example of a quadratic program is the least squares regression uh family of problems. Le squared problems are uh quadratic programs and they have closed form analytic solutions. You can compute this gradient by hand and solve for when it equals zero in the le squares case and that's like one of the big success stories of convex optimization. Okay, so that kind of uh is the overview of this um you know convexity 101. The big idea here is that if I have a an optimization problem, minimize f ofx subject to these constraints, then I want both my function f, my objective function to be convex. And I want the set of feasible points x given by these uh constraint equations. I want that to be a convex set c. If both of those things are convex, then my optimization problem is convex. And I have this powerful statement, this powerful guarantee that any local minimum I find is also a global optimal minimum solution. Huge huge deal cornerstone of optimization theory. And we're going to talk a bunch about convexity. So I just wanted this to be very clearly motivated and for you to have the road map before we kind of go down the rabbit hole of convex functions and convex sets. Okay. Thank you.