## Search This Blog

### Optimization with one or more equality constraints

This post is based on some theory that I was reading, and on some problems/exercises that I was solving which were related to optimization (maximization/minimization) problems.

Procedure for solving a two-variable maximization problem with an equality constraint

Let $f(x,y)$ and $g(x,y)$ be real-valued functions of two variables defined on a set $S \subseteq \mathbb{R}^2$ that are continuously differentiable on the interior of $S$, and let $c \in \mathbb{R}$ be a number. If the problem $\max_{(x,y) \in S} f(x, y)$ subject to $g(x, y) = c$ has a solution, it may be found as follows.

1) Find all the values of $(x, y, \lambda)$ such that

(a) $(x, y)$ is an interior point of $S$ and

(b) $(x, y, \lambda)$ satisfies the first-order conditions and the constraint,

i.e. the points $(x, y, \lambda)$ for which $f'_{x}(x, y) - \lambda \cdot g'_{x}(x, y) = 0$, $f'_{y}(x, y) - \lambda \cdot g'_{y}(x, y) = 0$, and $g(x, y) = c$,

i.e. the points $(x, y, \lambda)$ for which $\nabla{f}(x,y) = \lambda \cdot \nabla{g}(x,y)$, and $g(x, y) = c$.

2) Find all the points $(x, y)$ that satisfy $g'_x(x, y) = 0, g'_y(x, y) = 0$, and $g(x, y) = c$. Note that usually for most problems, there are no such values of $(x, y)$. In particular, if $g$ is linear there are no such values of $(x, y)$.

3) If the set $S$ has any boundary points, find all the points that solve the problem $\max_{(x,y) \in S} f(x, y)$ subject to the two conditions $g(x, y) = c$ and $(x, y)$ is a boundary point of $S$.

The points $(x, y)$ that you have found in steps 1), 2), 3) for which $f(x, y)$ is largest are the solutions of the optimization problem.

A variant of this procedure in which the last step involves choosing the points $(x, y)$ at which $f(x, y)$ is smallest may be used to solve the analogous minimization problem.

Procedure for solving a three-variable maximization problem with an equality constraint

Let $f(x,y,z)$ and $g(x,y,z)$ be real-valued functions of three variables defined on a set $S \subseteq \mathbb{R}^3$ that are continuously differentiable on the interior of $S$, and let $c \in \mathbb{R}$ be a number. If the problem $\max_{(x,y,z) \in S} f(x, y, z)$ subject to $g(x, y, z) = c$ has a solution, it may be found as follows.

1) Find all the values of $(x, y, z, \lambda)$ such that

(a) $(x, y, z)$ is an interior point of $S$ and

(b) $(x, y, z, \lambda)$ satisfies the first-order conditions and the constraint,

i.e. the points $(x, y, z, \lambda)$ for which $f'_{x}(x, y, z) - \lambda \cdot g'_{x}(x, y, z) = 0$, $f'_{y}(x, y, z) - \lambda \cdot g'_{y}(x, y, z) = 0$, $f'_{z}(x, y, z) - \lambda \cdot g'_{z}(x, y, z) = 0$, and $g(x, y, z) = c$,

i.e. the points $(x, y, z, \lambda)$ for which $\nabla{f}(x,y, z) = \lambda \cdot \nabla{g}(x,y,z)$, and $g(x, y, z) = c$.

2) Find all the points $(x, y, z)$ that satisfy $g'_x(x, y, z) = 0, g'_y(x, y, z) = 0, g'_z(x, y, z) = 0$, and $g(x, y, z) = c$. Note that usually for most problems, there are no such values of $(x, y, z)$. In particular, if $g$ is linear there are no such values of $(x, y, z)$.

3) If the set $S$ has any boundary points, find all the points that solve the problem $\max_{(x,y,z) \in S} f(x, y, z)$ subject to the two conditions $g(x, y, z) = c$ and $(x, y, z)$ is a boundary point of $S$.

The points $(x, y, z)$ that you have found in steps 1), 2), 3) for which $f(x, y, z)$ is largest are the solutions of the optimization problem.

A variant of this procedure in which the last step involves choosing the points $(x, y, z)$ at which $f(x, y, z)$ is smallest may be used to solve the analogous minimization problem.

Procedure for solving a three-variable maximization problem with two equality constraints

Let $f(x,y,z)$, $g(x,y,z)$, $h(x,y,z)$ be real-valued functions of three variables defined on a set $S \subseteq \mathbb{R}^3$ that are continuously differentiable on the interior of $S$, and let $c_1, c_2 \in \mathbb{R}$ be two numbers. If the problem $\max_{(x,y,z) \in S} f(x, y, z)$ subject to $g(x, y, z) = c_1$ and $h(x, y, z) = c_2$ has a solution, it may be found as follows.

1) Find all the values of $(x, y, z, \lambda, \mu)$ such that

(a) $(x, y, z)$ is an interior point of $S$,

(b) $\nabla{g}(x,y,z)$ and $\nabla{h}(x,y,z)$ are linearly independent, and

(c) $(x, y, z, \lambda, \mu)$ satisfies the first-order conditions and the constraints,

i.e. the points $(x, y, z, \lambda, \mu)$ for which $\nabla{f}(x,y, z) = \lambda \cdot \nabla{g}(x,y,z) + \mu \cdot \nabla{h}(x,y,z)$, and $g(x, y, z) = c_1$, and $h(x, y, z) = c_2$.

2) Find all the points $(x, y, z)$ for which $\nabla{g}(x,y,z)$ and $\nabla{h}(x,y,z)$ are linearly dependent, and $g(x, y, z) = c_1$ and $h(x, y, z) = c_2$

i.e. the points $(x, y, z, \lambda, \mu)$ for which $\lambda \cdot \nabla{g}(x,y,z) + \mu \cdot \nabla{h}(x,y,z) = (0,0,0)$, $(\lambda, \mu) \ne (0,0)$, and $g(x, y, z) = c_1$, and $h(x, y, z) = c_2$.

3) If the set $S$ has any boundary points, find all the points that solve the problem $\max_{(x,y,z) \in S} f(x, y, z)$ subject to the conditions $g(x, y, z) = c_1$, $h(x, y, z) = c_2$, and $(x, y, z)$ is a boundary point of $S$.

The points $(x, y, z)$ that you have found in steps 1), 2), 3) for which $f(x, y, z)$ is largest are the solutions of the optimization problem.

A variant of this procedure in which the last step involves choosing the points $(x, y, z)$ at which $f(x, y, z)$ is smallest may be used to solve the analogous minimization problem.