Optimality and least squares · Definition

Optimization problem

continuous optimizationoptimality and least squares

Before you start you need to know

Many problems in engineering, economics, and machine learning are formulated as finding the best value of a quantity under limits. This general form lets us study all of them with the same tools.

Definition

An optimization problem consists of minimizing or maximizing an objective function \(f\) over a set of points that satisfy certain constraints.

\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{sujeto a} \quad g_i(x) \le 0\]

If \(f\) is convex and the feasible set is convex, every local minimum is also global, and the KKT conditions are necessary and sufficient under regularity conditions. Gradient descent, Newton, and interior-point methods allow solving them numerically.

Consider minimizing \(f(x,y)=x^2+y^2\) subject to \(x+y=2\). Substituting \(y=2-x\) gives \(h(x)=x^2+(2-x)^2\), whose critical point \(x=1\) yields the minimum \(f(1,1)=2\).

A typical mistake is looking for points where \(\nabla f=0\) without checking the constraints, which may give a point outside the feasible set. Also, confusing a local minimum with the global one leads to wrong conclusions in nonconvex problems.

Think about it

What would happen to a local minimum if the objective function stopped being convex?

There could be another feasible point with a smaller value, so a local minimum no longer guarantees being global.

Exercises 10

  1. What is the general form of an optimization problem with inequality constraints?
  2. What is the name of the function that is minimized in an optimization problem?
  3. What is the name of the set of points that satisfy all the constraints?
  4. What does it mean to minimize a function over a set?
  5. What kind of problem is minimizing \(f(x)=x^2\) with no constraints?
  6. Minimize \(f(x,y)=x^2+y^2\) subject to \(x+y=4\). What is the minimum value?
  7. Compute the minimum of \(f(x)=x^2-4x+7\) over all reals.
  8. Maximize \(f(x,y)=xy\) subject to \(x+y=10\). What is the maximum value?
  9. Minimize \(f(x,y)=(x-1)^2+(y-2)^2\) subject to \(x+y\le 1\). What is the optimal point?
  10. Minimize \(f(x,y)=x^2+2y^2\) subject to \(x+y=3\). Give the minimum value and verify that it is global.

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.