# Convex Optimization

Problems where any local minimum is global, giving strong guarantees and reliable algorithms.

**Rests on:** KKT Conditions, Lagrange Multipliers

**Leads to:** Carlini-Wagner Attack, Inverse Problems, Nonsmooth Optimization

*Mathematical Foundations · Optimization*


## Why learn this

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.


## The intuition

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.


## An analogy

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.


## Definition

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.


## How it connects

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.


## The mathematics

Optimization is the process of finding the best input to a function so that the output is as small as possible (or as large as possible). In this text, we focus on minimization: finding the input that gives the lowest output.

To understand optimization, we first need to understand what a function is. A function takes an input number and produces an output number. We write this as f(x), which is read "f of x". The letter x represents the input, and f(x) represents the result. For example, if f(x) = x squared, then f(2) means we put 2 into the function, square it, and get 4.

In optimization, we look at the graph of the function. A local minimum is a point on the graph that is lower than all the points immediately next to it. It looks like the bottom of a small valley. A global minimum is the single lowest point on the entire graph. In many complicated functions, there can be many local minima (many small valleys), but only one global minimum (the deepest valley).

Convex optimization deals with a special class of functions called convex functions. A function is convex if its graph has no "dents" or "hills" between any two points. More precisely, if you pick any two points on the graph and draw a straight line connecting them, that entire line segment will lie above or exactly on the graph. It never dips below the curve.

This geometric property has a powerful consequence for optimization: for a convex function, every local minimum is also the global minimum. There are no false valleys. If you find a point where the function stops going down (a local minimum), you have found the absolute best solution. This allows algorithms like gradient descent to work reliably; they simply walk downhill and are guaranteed to reach the bottom.

Mathematically, convexity is defined using three numbers: two input points x1 and x2, and a mixing weight t that is between 0 and 1 (inclusive). The expression t times x1 plus (1 minus t) times x2 creates a new point somewhere on the straight line segment between x1 and x2. The definition of convexity states that the value of the function at this new point must be less than or equal to the weighted average of the function values at x1 and x2.

In symbols:
f(t * x1 + (1 - t) * x2) <= t * f(x1) + (1 - t) * f(x2)

Here, the left side is the height of the graph at the intermediate point. The right side is the height of the straight line connecting the two original points at that same horizontal position. The inequality means the graph is below or touching the line.


## A worked example

Let us verify the convexity of the function f(x) = x squared using specific numbers.

We choose two input points: x1 = 1 and x2 = 3.
First, we calculate the output of the function at these points:
f(1) = 1 * 1 = 1.
f(3) = 3 * 3 = 9.

Next, we pick a point halfway between x1 and x2. We do this by setting t = 0.5 (which is between 0 and 1).
The intermediate input point is:
x_mid = 0.5 * 1 + (1 - 0.5) * 3
x_mid = 0.5 * 1 + 0.5 * 3
x_mid = 0.5 + 1.5
x_mid = 2.

Now we compare the height of the graph at x_mid with the height of the straight line connecting (1, f(1)) and (3, f(3)).

Step 1: Calculate the function value at the intermediate point.
f(x_mid) = f(2) = 2 * 2 = 4.
This is the actual height of the curve at x=2.

Step 2: Calculate the weighted average of the function values at the endpoints. This represents the height of the straight line at x=2.
Line_height = t * f(x1) + (1 - t) * f(x2)
Line_height = 0.5 * 1 + 0.5 * 9
Line_height = 0.5 + 4.5
Line_height = 5.

Step 3: Compare the two heights.
The definition of convexity requires that:
f(x_mid) <= Line_height.
Substituting our numbers:
4 <= 5.

The inequality holds true. The graph (height 4) is below the straight line (height 5). This confirms that for these points, the function behaves as a convex function. Because this property holds for any pair of points, f(x) = x squared is a convex function. Its minimum occurs at x=0, where f(0)=0. Since it is convex, this local minimum is also the global minimum.


## From scratch, in Python

```python
def is_convex(f, x1, x2, steps=100):
    for i in range(steps + 1):
        t = i / steps
        x_mid = t * x1 + (1 - t) * x2
        line_value = t * f(x1) + (1 - t) * f(x2)
        function_value = f(x_mid)
        if function_value > line_value:
            return False
    return True

def square(x):
    return x ** 2

print(is_convex(square, -10, 10))  # True
```


## What the code does

First, we define a function is_convex that takes a function f and two points x1, x2. It checks along many points on the line between them (using steps=100) that the line is always above or on the graph. We start with t=0 (which is x1) and go to t=1 (which is x2). For each t, we compute the midpoint x_mid. The line_value is the weighted average of f(x1) and f(x2). The function_value is f(x_mid). If function_value is ever greater than line_value, then the line dips below the graph, so the function is not convex, and we return False. If we finish the loop without finding a violation, we return True. Then we define a simple function square(x) = x², and test it. The output is True because square is convex. This code uses a loop, a function, and an if statement — all standard Python. You don't need any libraries.


## Common misconceptions

**Convex means the function is bowl-shaped** — Convex means the function looks like a U or a bowl, and that's all there is to it.

Bowl-shaped is one example, but convex functions can also be flat, like f(x)=0, or piecewise linear, like f(x)=|x|, which has a V shape. The definition is about the line segment always lying above the graph, not about a particular shape. In fact: A function is convex if the line segment between any two points on its graph lies above or on the graph. This includes many shapes beyond a simple bowl.

**Every local minimum is global only if the function is smooth** — Convexity requires the function to be smooth and continuous.

Convexity is a property about the line segment, not about differentiability. A function can have corners (like |x|) and still be convex. Even non-continuous functions can be convex in an extended sense, but in practice we deal with continuous ones. In fact: Convex functions can have sharp corners, like the absolute value function. They do not need to be smooth.

**Convex optimization always solves problems quickly** — Since convex problems have a unique optimum, the algorithm will always be fast.

Convexity guarantees that any local min is global, but the time to reach it depends on the algorithm and the problem size. Some convex problems can still take a long time to solve if they are large or if the function is flat. In fact: Convexity gives reliability, not necessarily speed. Algorithms have convergence rates, and a very large convex problem might still require many iterations.

**Bias means the model is unfair** — In optimization, the bias term in a model is a source of unfairness.

The word 'bias' has a specific meaning in machine learning: it's an additive constant that shifts the model. It has nothing to do with fairness. Fairness bias is a separate concern entirely. In fact: In a linear model, bias is a learned parameter that shifts the prediction. It's a mathematical offset, not a moral judgment.


## In short

Convexity is the guarantee that a local minimum is the global minimum. It applies to functions where the line between any two points on the graph lies above the graph. This property makes optimization reliable and is the foundation for many machine learning algorithms like linear and logistic regression. When a problem is convex, you can trust the result; when it's not, you have to be more careful. Remember: convex → one valley, no false bottoms.


## Where this is used

In practice, convex optimization is used whenever you need a guaranteed optimum. In machine learning, many classic models are convex: linear regression (least squares), logistic regression, and support vector machines. When you fit a line to data, the loss function (like squared error) is convex, so gradient descent or other algorithms will always find the best line. In large language models, the training objective is non-convex, so convex optimization as a guarantee does not apply. However, convex optimization is used in parts of the pipeline: for example, in the fine-tuning of some layers or in the projection steps in constrained optimization. In small models on devices, the same applies — if the model is a convex model like logistic regression, you can train it efficiently on-device with guarantees. In retrieval-augmented generation, embeddings are learned, and the embedding space is optimized, but the objective is non-convex. However, the similarity metric (like cosine similarity) is used with a convex objective when training embeddings? Actually, embeddings are typically trained with non-convex objectives. In agentic systems, planning can involve solving convex optimization problems for resource allocation or path planning, where you have constraints and guarantee optimality. In everyday applied ML, whenever you use scikit-learn's LinearRegression or LogisticRegression, you are using a convex solver underneath. A developer writes `model.fit(X, y)` and trusts that the solution is the best possible. The Huber function from your library is a convex loss that is used in robust regression — it makes the regression less sensitive to outliers while keeping the problem convex, so you still get guarantees. If convexity breaks, you lose those guarantees and have to rely on heuristics like random restarts or careful tuning. What breaks when done badly: if you assume convexity when it's non-convex, you might get stuck in a local minimum and report a suboptimal solution without knowing it. So recognising convexity is crucial.


---

Read this on the web: https://basavapurushottam.com/learn-ai/convex-optimization
