So we talk about optimization today and if you have the feeling during the lecture that

this is not pattern analysis you have the right feeling.

So we do some math background today that I consider to be important to be a good expert

in pattern analysis.

So basically we do here a refresher course on optimization and on things that you should

know or that I originally expected you to know but I know that nobody knows that so

I'm summarizing that.

Yesterday I started out with a motivation and I told you there is no lecture on pattern

analysis or pattern recognition without the sectional optimization techniques.

And in pattern recognition one or in the winter semester lecture I usually say well we have

a continuous objective function we compute the gradient and the zero crossings and then

we have our optimization scheme.

That's basically the rule and in many cases we will find closed form solutions for the

zero crossings of the gradient so we get nice iteration schemes or a closed form solution

for optimizing.

But in many situations, practical situations we will not be able to find a closed form

solution and the question is what do we do that and so we need some numerical methods

for optimization and the first question we are considering is the constraint, unconstrained

optimization.

So we just have a function that accepts as input a d-dimensional feature vector or a

dimensional variable and returns a real value and returns a real value.

And what we are looking for is we look for the minimum and I assume that the function

is convex that means the epigraph is a convex set.

So we have functions like this one here.

So this is a typical convex function and here we look for the minimum and the optimal point

is denoted by x star.

Whenever I use a variable with a star I mean the optimal point, right?

I mean the optimal value and what we have to solve is minimize the function f with respect

to x and tell me at which point x the function achieves its minimum.

And in this case a necessary and sufficient condition for the minimum is that the gradient

is 0.

It is necessary and sufficient because we have the constraint that we are considering

convex functions at the beginning, okay?

Usually if you have a function like this here you might also reduce the problem to a convex

optimization problem if you are able to restrict the optimization for instance to this interval.

So let's first consider convex functions and we look for a unique minimum, a unique optimal

point of these functions.

So a necessary but sufficient condition is that the gradient is 0.

An example for instance if you have a function like that we have ax minus b and we want to

minimize the Euclidean length of the residual.

This is a function that depends on x1 to let's say xm vectors so it has m times d dimensions

and you want to compute here the minimum of that.

Usually we take the square and this is obviously a convex function that we have to minimize.

We compute the derivative and the zero crossing and basically we find out that we have to

compute the single inverse of a.

So we get some normal equations to solve this least square estimate.

So that's something that we apply quite often and I'm not talking about these things anymore.

Basically I'm saying okay we have to compute the gradient, the zero crossings and then

I do all the computations.

Usually if we cannot find a closed form solution as was the case with the residual minimization