../

2025-08-25

What is Optimization?

  • Put it simply it is just $\mathbf{min} f(x)$
  • That’s it. We want to find out how to minimize a function
  • Thought it fits in a single line, it is not so easy
  • This pattern comes up everywhere. It is very ubiquitous
  • In this class we will focus on continuous optimization
  • Our $x^* \in \R^N$ or a subset of $\R^N$ that is continuous

Black-box optimization

  • If we had no idea about the characteristics of a function and was just asked to optimize it then we would fare very poorly.
  • This problem is ill-formed from the start.
  • We don’t even know if a solution exists (assuming some constraints)

BUT…all hope is not lost. If just know something about the function - whether it is linear or convex - we can do a lot more

Convex optimization

  • This will be our focus. Convex optimization is well studied.
  • We will also talk about some non-convex stuff at the end
  • cvxopt book doesn’t really cover non-convex stuff. Surprise.

Formal definition

For this class we will always follow this general definition

$$f : \R^n \rightarrow \R$$

So, a possibly multivariate real valued function. We want to minimize this.

But we also have some equality/inequality constraints of the following form

$$ g_i : \R^n \rightarrow \R, g_i(x) \le 0, i = 1, \ldots, m $$ $$ h_j : \R^n \rightarrow \R, h_j(x) = 0, j = 1, \ldots, p $$

What could make this hard?

  • Lots of constraints
  • Contradicting constraints leading to no solution
  • Even without any constraints, the input space might be so big that we cannot possibly exhaust it
  • It might not be differentiable
  • We might get stuck at a local minima
    • Using just $f’(x)$ we cannot disambiguate the valleys

What is it like for machines?

You seeing this image can easily point out where the minimum might occur even if you cannot state the exact value. But poor machines cannot see this graph or any visual representation for that matter. They can only see a single point at a time.

Silly example

Imagine yourself to be a machine. You can only propose a value and get back the function value at that point. Using this you have to move to the local minimum.

Even without any constraints, fancy function shape, this is impossible.

Consider the function $f(x) = 0, x = 0.69; f(x) = 1, x \ne 0.69$

You will not be able to guess the answer even given infinite attempts

Local information can only get you so far

This propose-oracle paradigm will inherently flawed if we don’t know anything about $f$

Don’t take the black pill yet. Even some knowledge of the characteristics can get you to at least a local minimum which is good enough in many cases.

Actual formation

  • The value of $x$ is more important than what $f(x)$ is. We just care that it is minimum. So the more accurate formulation of the problem would be $$ x^* = \arg \min f(x) $$

What helps? What do we actually need to know?

  • Though differentiation helps, it is not the best.
  • Even linear/non-linear is not the best indicator of hardness
  • The best characteristic is convexity
  • It is the single best characteristic that helps us optimize