Optimization focuses on finding the best solution within a given set of constraints. Stationary points, where the gradient of the objective function equals zero, are crucial in identifying potential optimal solutions. These include local minima, maxima, and saddle points.

First and second-order optimality conditions help determine the nature of stationary points. Understanding local versus global optimality is essential, especially in non-convex problems where multiple local optima may exist. Convexity plays a significant role in optimization, guaranteeing unique global optima and efficient problem-solving.

Stationary Points and Optimality Conditions

Stationary points in optimization

• Stationary points occur when gradient of objective function equals zero $\nabla f(x^) = 0$
• Three types: local minima, local maxima, saddle points (horse saddle shape)
• Represent potential optimal solutions requiring further analysis
• Critical for identifying candidates for global optima in non-convex problems

First and second-order optimality conditions

• First-order necessary condition: gradient must equal zero $\nabla f(x^) = 0$
• Second-order necessary condition: Hessian matrix positive semidefinite $\nabla^2 f(x^) \succeq 0$ for local minimum
• Sufficient conditions: first-order satisfied and Hessian positive definite $\nabla^2 f(x^) \succ 0$ for local minimum
• Help determine nature of stationary points (minimum, maximum, saddle point)
• Used in optimization algorithms to check convergence and optimality

Optimality and Convexity

Local vs global optimality

• Local optimality: best solution within neighborhood, not necessarily overall best
• Global optimality: best solution over entire feasible region
• All global optima are local optima, but not vice versa
• Distinguish using multiple starting points or global optimization techniques (simulated annealing, genetic algorithms)
• Critical in non-convex problems where multiple local optima may exist

Convexity and optimization implications

• Convex functions: $f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)$, unique global minimum
• Concave functions: negative of convex, unique global maximum
• Convex problems guarantee unique global optimum, local optimum is global
• Test convexity: second derivative (univariate), Hessian matrix (multivariate)
• Convexity ensures convergence and efficiency in finding global optima
• Examples: quadratic functions (convex), logarithmic functions (concave)