Lecture 4: �Optimization

André E. Lazzaretti

UTFPR/CPGEI

Optimization

• Why optimization?
• In pattern recognition, the goal is often to optimize (maximize or minimize) a specific mathematical function (cost function, loss function, objective function).

​

• For example:
• Least squares

​

• General framework: formulate the function and perform the optimization

​

• Optimization:
• Unconstrained
• Constrained

​

​

Unconstrained Optimization

​

​

• g(x) → cost/loss function
• x = [x₁, x₂, ... , x_n] → variables to be optimized

Unconstrained Optimization

​

​

• ∇g(x) → gradient of g(x)
• Provides the direction of the greatest slope (variation) of g(x)
• Negative Direction of ∇g(x): Direction of steepest descent

Unconstrained Optimization

• Global Minimum
• x^* is a global minimum if

Unconstrained Optimization

• Local minimum:

​

• Optimality conditions:
• Necessary condition: if g(x) is continuously differentiable (first-order condition):

​

​

​

​

​

Unconstrained Optimization

• Sufficient condition: if every element of ∇²g(x) is a continuous function, ∇²g(x) evaluated for x = x^* must be positive definite for x* to be a local minimum point (second-order condition):

​

​

​

​

​

​

• A matrix Ω is positive definite if all eigenvalues λ_i, i = 1, 2, ..., n, of Ω Ω are positive.
• Null gradient: saddle point, maximum, or minimum.
• Negative definite – maximum
• Positive and negative eigenvalues: saddle point

Unconstrained Optimization

• Necessary and sufficient conditions for x* to be a local minimum point:

​

​

• H(x) evaluated for x = x^* must be positive definite

​

• If g(x) is convex and x* satisfies the first-order condition, then x* is a global minimum point.

Convex function: all local minima are global minima(*).

Non-convex function

How to solve it?

• Normally: ∇g(x)=0

​

• This solution is viable when ∇g(x)=0 forms a linear system of equations;

​

• If this is not possible (nonlinear system of equations) → alternatives;

​

• Alternative – Iterative methods:
• Gradient descent;
• Newton's method.

​

​

​

​

Optimization using Gradient

Example

(x₁)² + x₁x₂ + 10(x₂)² – 5x₁ – 3x₂

​

1) Calculate the gradient.

​

2) Write in the following form:

​

​

​

​

3) Calculate the gradient using:

​

​

​

4) Write it as:

​

A

b

C

d

Example

Example

Example

Example

Example

Problems with gradient

Newton’s method

• Use the following:

​

​

​

• This method is derived by assuming a second-order approximation (via a Taylor series) of the function at the point in question:

​

• Exercise – verify!

​

​

or