Convex Optimization

Convex optimization is the rare part of AI where we get guarantees — if you can frame a problem as convex, the algorithm will reliably find the absolute best answer, not just a decent one. Understanding convexity helps you recognise when you can trust a tool, and when you cannot. It unlocks deeper study of gradient descent, why deep learning is so finicky, and why robust regression uses losses like the Huber function. Many real-world problems — like fitting lines to data, minimising risk in finance, or allocating resources — are convex, and you will be able to solve them with confidence.

Start with something simpler: you are standing on a mountain range at night, and you want to find the lowest point in the valley. If the mountain is smooth and shaped like a giant bowl — a single depression with no small dips — then you can be certain the lowest point you find is the lowest point for the whole range. You don't have to worry about getting tricked into thinking a small local dip is the real bottom. But if the mountain has many valleys and ridges, you might descend into a small gap and think you've reached the bottom, only to realise later that there's a deeper valley elsewhere. Convexity is exactly the property of 'no small dips'. In the language of optimisation, we want to minimise a function f(x). The function is convex if, taking any two points on it, the straight line segment joining them lies above or on the graph. This ensures that every local minimum (a point lower than all nearby points) is also the global minimum (the lowest overall). For a convex function, there is only one valley bottom. So when you walk downhill, you will always end up at the true bottom, whatever path you take.

Imagine you are a ball rolling on a curved surface, and you want to find the lowest point. If the surface is shaped like a smooth bowl, then roll the ball anywhere — it will eventually settle at the very bottom, and that bottom is the same no matter where you start. The ball might roll back and forth a bit, but it will never get stuck in a local dip because there are none. That's convexity. Now, imagine a surface with many bumps and craters — a rugged terrain. If you drop a ball into one of the small craters, it might stay there, thinking it has reached the lowest point, but there could be a deeper crater elsewhere. That's a non-convex landscape, where local minima are not global. The bowl analogy holds for the definition as well: if you take two points on the edge of the bowl and stretch a string tightly between them, the string will lie above or on the surface of the bowl — never dipping below. That is exactly the 'line segment above the graph' property. Where the analogy breaks down: convex functions can also be flat regions, like a plateau, where any point is a minimum. And the 'ball' doesn't have to be physical; the algorithm just moves downhill based on the slope, which is like rolling, but we choose the steps.

A convex optimization problem is one where the function to be minimized (the objective) is convex — meaning the line segment between any two points on its graph lies above or on the graph — so that any local minimum is guaranteed to be the global minimum, and reliable algorithms can always find it.

You have not studied any mathematics beyond arithmetic, so we build from scratch. This concept belongs to the branch of mathematics called optimisation, which is about finding the best value of something (like minimum cost or maximum profit). Convex optimisation is the star of optimisation because of its guarantees. In your library, you have notes on Gradient Descent — that is the algorithm often used to minimise non-convex functions like those in deep learning. Convexity is what makes gradient descent work reliably, because you never get stuck in a local minimum. You also have notes on Least Squares Regression — fitting a line to data — which is a classic convex problem, and on the Huber function, which is a convex loss that makes regression robust to outliers. Understanding convexity will help you see why these methods are so dependable.