It is natural human desire to find the best solution among all possibilities, though it is usually subject to certain constraints.
Types of Optimization Problems
Optimization problems can be either continuous or discrete.
Discrete
- domain is a discrete set
- Without clever strategies, we need
amount of time to solve it - sometimes clever strategy (e.g. MST)
- more often, NP-hard (e.g. travelling salesman problem)
Continuous
- domain is continuous
- still many NP-hard problems, but also large classes of “easy problems” (e.g. convex optimization)
Standard Form
We can formulate most continuous optimization problems this way:
given functions
The optimal solution
We can usually reduce other problems into this form.
For example, if we have equality constraint, we can just use two constraints (
Note here:
Methods to Solve Optimization Problems
- finding derivatives and performing second derivative test
- Lagrange multiplier
- iterative methods
Local Vs Global Minima
Global minimum is the absolute best among all possibilities, and the local minimum is best “among immediate neighbors”. Depending on the problem, sometimes local minima is a good enough answer. For example, a lot of times, structure in nature is local minimum (e.g. protein structure). Another example is machine learning (which is often local minimum)
Existence & Uniqueness of Minimizers
The minimizer may not exist. And if it exist, it may not be unique. For example, the problem above does not have a unique minima.
Feasibility
Consider
The value of objective doesn’t depend on
Even Bounded below is not Enough
Consider
Existence
Sufficient Conditions for a Solution to Exist
- extreme value theorem: continuous objective & compact domain
- coercivity: objective goes to
as we travel (far) in any direction
Optimality Conditions
- In general, our objective is
- How do we test for a local minimum?
- In 1D we can use derivative test (
and )
- In 1D we can use derivative test (
- 1st derivative becomes gradient (
); 2nd derivative becomes Hessian ( )
The optimal condition is
Note here the
With Constraints
When we have constraints, we will probably find a minimizer that is not a optimality condition (since optimality conditions may not satisfy constraints).
In general, any (local or global) minimizer must at least satisfy the Karush-Kuhn-Tucker conditions.