Constrained optimization problems
Constrained optimization problems involve finding maxima or minima of function values within a specified set of restrictions or constraints. These problems are ubiquitous in areas like economics, engineering, physics, and machine learning where various conditions must be satisfied. The constraints could be either equality or inequality in nature. Here, we only focus on constraints that can be formulated as equalities.
In two dimension, a basic form of is either \[ \begin{aligned} \text{Minimize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] or \[ \begin{aligned} \text{Maximize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] for some function \(f(x,y)\) (called objective function) and \(g(x,y)\) as well as a constant \(c\). The equation \(g(x,y)=c\) is called the constraint (or constraint equation, in this case).
In general, such problems can be formulated as maximizing or minimizing a function (objective function) subject to a set of constraints.
There are several special types of constrained optimization problems when both the objective and the contraints are given by linear functions/equations/inequalities, we call them linear programming problems. Beyond those, we have quadratic programming problems, semi-definite programming, and etc.
Level set interpretation
The form \[ \begin{aligned} \text{Minimize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] can be interpreted as the problem of of optimizaing the value of \(f(x,y)\) while restricting ourselves to a level set of \(g\) defined by \(g(x,y)=c\).
Elimination/substitution method
If in the equation \(g(x,y) = c\), we can solve one variable in terms of the other (which may not be an easy task). the constrained optimization problem in two variables can be reduced an unconstrained optimization problem in one variable. For example, if we can get \(y = h(x)\), then the problem \[ \begin{aligned} \text{Minimize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] can be reduced to \[ \text{Minimize } f(x,h(x)). \] within certain domain.
It is often the case that the relation \(g(x,y) = c\) cannot be parametrized by a single function \(y=h(x)\). Instead, we have to piece together multiple functions, say \(y = h_1(x), y=h_2(x), \ldots\) In this case, the original optimization problem is translated into several optimization problems.
Global parametrization method
In some cases, it is possible to parametrize the set defined by \(g(x,y)=c\) as the image of a function \(\mathbf{r} : \mathbb{R} \to \mathbb{R}^2\) over some interval \(I\). With that, the problem \[ \begin{aligned} \text{Minimize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] can be translated to the unconstrained optimization problem \[ \text{Minimize } f(\mathbf{r}(t)) \] over the interval \(I\).
Method of Lagrange multipliers
The method of Lagrange multipliers is a mathematical tool used for solving constrained optimization problems. The method works by transforming the constrained problem into a almost equivalent problem without constraints. In the two-variable case, it says that from the constrained optimization \[ \begin{aligned} \text{Minimize } &f(x,y) \\ \text{subject to } &g(x,y) = c \end{aligned} \] we can derive the system of equation \[ \begin{aligned} \nabla f (x,y) &= \lambda \nabla g(x,y) \\ g(x,y) &= c \end{aligned} \] in the three variables \(x,y,\lambda\). Here, \(\nabla f\) and \(\nabla g\) are the gradient vector of \(f\) and \(g\), respectively. After solving this system of equations if the solution is finite, then…
- We plug in each solution to \(f\) to identify the maxima and minima.
- We also need to check the values of \(f\) where \(g(x,y) = c\) and \(\nabla g(x,y) = 0\) to locate any maxima and minima missed by the first step.
Note that the second step is missed by many textbooks and most internet resources.
Exercises
The saddle surface
Solve the optimization problems \[ \begin{aligned} \text{Minimize } &x^2 - y^2 \\ \text{subject to } &x^2 + y^2 = 1 \end{aligned} \] and \[ \begin{aligned} \text{Maximize } &x^2 - y^2 \\ \text{subject to } &x^2 + y^2 = 1 \end{aligned} \] Note that the equation \(x^2 + y^2 = 1\) defines the unit circle, therefore, these problems ask us to find the lowest and highest function values of \(f(x,y) = x^2 - y^2\) while restrict ourself to the unit circle.
Rectangles of given perimeter
What is the maximum area of a rectangle if the perimeter is 20? Is there a minimum area?