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

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 has smallest value of among all feasible .

We can usually reduce other problems into this form. For example, if we have equality constraint, we can just use two constraints ()

Note here: is the function to minimize and other are used for constraints. For example:

Methods to Solve Optimization Problems

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 (all feasible solutions are equally good). But it can totally happen that where no points can satisfy this constraint (no feasible points)

Even Bounded below is not Enough

Consider It is bounded at . No matter how big is, we never achieve the bound.

Existence

Sufficient Conditions for a Solution to Exist

Optimality Conditions

  • In general, our objective is
  • How do we test for a local minimum?
  • 1st derivative becomes gradient (); 2nd derivative becomes Hessian ()

The optimal condition is

Note here the symbol means positive-semidefinite ( )

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.