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. 



See also: 

This math page by Martin Osborne 

This math page again by Martin Osborne 

This Math SE post by smcc


Plotting the Chebyshev polynomials of the second kind in Python

Test001