11.8 Appendix: Review of Optimization and Constrained Optimization

Consider the function of a single variable: \[ y=f(x)=x^{2}. \] Clearly the minimum of this function occurs at the point \(x=0\). Using calculus, we find the minimum by solving: \[ \min_{x}~y=x^{2}. \] The first order (necessary) condition for a minimum is: \[ 0=\frac{d}{dx}f(x)=\frac{d}{dx}x^{2}=2x \] and solving for \(x\) gives \(x=0\). The second order condition for a minimum is, \[ 0<\frac{d^{2}}{dx}f(x), \] and this condition is clearly satisfied for \(f(x)=x^{2}\).

Next, consider the function of two variables: \[\begin{equation} y=f(x,z)=x^{2}+z^{2}\tag{11.19} \end{equation}\] This function looks like a salad bowl whose bottom is at \(x=0\) and \(z=0\). To find the minimum of (11.19), we solve: \[ \min_{x,z}y=x^{2}+z^{2}, \] and the first order necessary conditions are, \[\begin{align*} 0 & =\frac{\partial y}{\partial x}=2x,\\ 0 & =\frac{\partial y}{\partial z}=2z. \end{align*}\] Solving these two linear equations gives \(x=0\) and \(z=0\).

Now suppose we want to minimize (11.19) subject to the linear constraint: \[\begin{equation} x+z=1.\tag{11.20} \end{equation}\] The minimization problem is now a * constrained minimization*: \[\begin{align*} \min_{x,z}y & =x^{2}+z^{2}\textrm{ subject to }(s.t.)\\ x+z & =1. \end{align*}\] Given the constraint \(x+z=1\), the function (11.19) is no longer minimized at the point \((x,z)=(0,0)\) because this point does not satisfy \(x+z=1\). One simple way to solve this problem is to substitute the restriction (11.20) into the function (11.19) and reduce the problem to a minimization over one variable. To illustrate, use the restriction (11.20) to solve for \(z\) as: \[\begin{equation} z=1-x.\tag{11.21} \end{equation}\] Now substitute (11.21) into (11.19) giving: \[\begin{equation} y=f(x,z)=f(x,1-x)=x^{2}+(1-x)^{2}.\tag{11.22} \end{equation}\] The function (11.22) satisfies the restriction (11.20) by construction. The constrained minimization problem now becomes: \[ \min_{x}y=x^{2}+(1-x)^{2}. \] The first order conditions for a minimum are: \[ 0=\frac{d}{dx}(x^{2}+(1-x)^{2})=2x-2(1-x)=4x-2, \] and solving for \(x\) gives \(x=1/2\). To solve for \(z\), use (11.21) to give \(z=1-(1/2)=1/2\). Hence, the solution to the constrained minimization problem is \((x,z)=(1/2,1/2)\).

Another way to solve the constrained minimization is to use the method of Lagrange multipliers. This method augments the function to be minimized with a linear function of the constraint in homogeneous form. The constraint (11.20) in homogenous form is: \[ x+z-1=0. \] The augmented function to be minimized is called the Lagrangian and is given by: \[ L(x,z,\lambda)=x^{2}+z^{2}-\lambda(x+z-1). \] The coefficient on the constraint in homogeneous form, \(\lambda\), is called the Lagrange multiplier. It measures the cost, or shadow price, of imposing the constraint relative to the unconstrained problem. The constrained minimization problem to be solved is now: \[ \min_{x,z,\lambda}~L(x,z,\lambda)=x^{2}+z^{2}+\lambda(x+z-1). \] The first order conditions for a minimum are: \[\begin{align*} 0 & =\frac{\partial L(x,z,\lambda)}{\partial x}=2x+\lambda,\\ 0 & =\frac{\partial L(x,z,\lambda)}{\partial z}=2z+\lambda,\\ 0 & =\frac{\partial L(x,z,\lambda)}{\partial\lambda}=x+z-1. \end{align*}\] The first order conditions give three linear equations in three unknowns. Notice that the first order condition with respect to \(\lambda\) imposes the constraint. The first two conditions give: \[ 2x=2z=-\lambda, \] or, \[ x=z. \] Substituting \(x=z\) into the third condition gives: \[ 2z-1=0 \] or, \[ z=1/2. \] The final solution is \((x,y,\lambda)=(1/2,1/2,-1)\).

The Lagrange multiplier, \(\lambda\), measures the marginal cost, in terms of the value of the objective function, of imposing the constraint. Here, \(\lambda=-1\) which indicates that imposing the constraint \(x+z=1\) reduces the objective function. To understand the role of the Lagrange multiplier better, consider imposing the constraint \(x+z=0\). Notice that the unconstrained minimum achieved at \(x=0,z=0\) satisfies this constraint. Hence, imposing \(x+z=0\) does not cost anything and so the Lagrange multiplier associated with this constraint should be zero. To confirm this, we solve the problem: \[ \min_{x,z,\lambda}~L(x,z,\lambda)=x^{2}+z^{2}+\lambda(x+z-0). \] The first order conditions for a minimum are: \[\begin{align*} 0 & =\frac{\partial L(x,z,\lambda)}{\partial x}=2x-\lambda,\\ 0 & =\frac{\partial L(x,z,\lambda)}{\partial z}=2z-\lambda,\\ 0 & =\frac{\partial L(x,z,\lambda)}{\partial\lambda}=x+z. \end{align*}\] The first two conditions give: \[ 2x=2z=-\lambda \] or, \[ x=z. \] Substituting \(x=z\) into the third condition gives: \[ 2z=0, \] or, \[ z=0. \] The final solution is \((x,y,\lambda)=(0,0,0)\). Notice that the Lagrange multiplier, \(\lambda\), is equal to zero in this case.