1.1.1 Problem 1

Minimize \(f(x)=x_1+x_2\) subject to \(g(x)=x_1^2+x_2^2-2=0.\)

Solution. Note that \[(f(x))^2=(x_1+x_2)^2\leq2(x_1^2+x_2^2)=2\cdot2=4,\] hence \(f(x)\geq-2,\forall x\in\left\{g=0\right\}.\) Since \(f((-1,-1))=-2,\) the global minimum of \(f\) is \(-2,\) attained at \((-1,-1).\)

1.1.2 Problem 2

Minimize \(f(x)=x_1+x_2\) subject to \(h(x)=x_1^2+x_2^2-2\leq0.\)

Solution. Note that \[(f(x))^2=(x_1+x_2)^2\leq2(x_1^2+x_2^2)\leq2\cdot2=4,\] hence \(f(x)\geq-2,\forall x\in\left\{h\leq0\right\}.\) Since \(f((-1,-1))=-2,\) the global minimum of \(f\) is \(-2,\) attained at \((-1,-1).\)

1.1.3 Problem 3

Minimize \(f(x)=x_1+x_2\) subject to \(h_1(x)=x_1^2+x_2^2-2\leq0\) and \(h_2(x)=x_2\geq0.\)

Solution. Note that \[x_1^2\leq2-x_2^2\leq2\Rightarrow x_1\geq-\sqrt{2}\] hence \(f(x)\geq-\sqrt{2},\forall x\in\left\{h_1\leq0\right\}\cap\left\{h_2\geq0\right\}.\) Since \(f((-\sqrt{2},0))=-\sqrt{2},\) the global minimum of \(f\) is \(-\sqrt{2},\) attained at \((-\sqrt{2},0).\)

1.1.4 Problem 4

Minimize \(f(x)=x_1+x_2\) subject to \(h_1(x)=-x_1^3+x_2\leq0,h_2(x)=x_2\geq0\) and \(h_3(x)=x_1^5-x_2\geq0.\)

Solution. Note that \[-x_1^3+x_2\leq0\Rightarrow x_1^3\geq x_2\geq0\Rightarrow x_1\geq0\] so \(f(x)\geq0,\forall x\in\left\{h_1\leq0\right\}\cap\left\{h_2\geq0\right\}\cap\left\{h_3\geq0\right\}.\) Since \(f(0,0)=0,\) the global minimum of \(f\) is \(0,\) attained at \((0,0).\)

1.1.5 Problem 5

Maximize \(f(x,y)=xy\) subject to \(x+y^2\leq2,x\geq0,y\geq0.\)

Solution. We have the inequalities \[(f(x,y))^2=x^2y^2=\frac{1}{2}\cdot x\cdot x\cdot 2y^2\leq\frac{1}{2}\cdot\frac{1}{27}\cdot\left(x+x+2y^2\right)^3\leq\frac{32}{27}\] so the global maximum of \(f\) is \(\sqrt{32/27},\) attained at \(\left(4/3,\sqrt{2/3}\right).\)

1.1.6 Problem 6

Minimize \(f(x)=x_1^2+x_2^2\) subject to \(g(x)=x_1^2+x_2^2\leq1.\)

Solution. Clearly \(f\geq0,\) so the global minimum of \(f\) is \(0,\) attained at \((0,0).\)

1.1.7 Problem 7

Minimize \(f(x)=x_1^2+x_2^2+60x_1\) subject to \(h_1(x)=x_1\geq80\) and \(h_2(x)=x_1+x_2\geq120.\)

Solution. Note that \[\begin{align*}f(x) &= x_1^2-160x_1+x_2^2+80x_1+140x_1\\ &\geq x_1^2-160x_1+x_2^2+80(120-x_2)+140\cdot80\\ &= (x_1-80)^2+x_2^2-80x_2+14400\\ &= (x_1-80)^2+(x_2-40)^2+12800\geq12800\end{align*}\] so the global minimum of \(f\) is \(12800,\) attained at \((80,40).\)

1.2.1 Equality Constraints

We assume that \[\Omega=\bigcap_{i=1}^m\left\{h_i(x)=0\right\}.\] Notations:

1. \(x=(x_1,x_2,...,x_n)\) and \(\nabla f(x)=(\partial f/\partial x_1,\partial f/\partial x_2,...,\partial f/\partial x_n).\)
2. \(h=(h_1,h_2,...,h_m),\) i.e. \(h:\mathbb{R}^n\rightarrow\mathbb{R}^m\) and \(h(x)=(h_1(x),h_2(x),...,h_m(x)).\) Also, \[\nabla h(x)=\begin{pmatrix}\nabla h_1(x)\\\nabla h_2(x)\\...\\\nabla h_m(x)\end{pmatrix}.\]
3. \(f\in\mathcal{C}^k\) is continuously differentiable of order \(k,\) i.e. its \(k^{\textrm{th}}\) derivative exists and is continuous.
4. A point \(x\in\Omega\) is called regular if the vectors \[\nabla h_1(x),\nabla h_2(x),...,\nabla h_m(x)\] are linearly independent. If \(h=h_1,\) then \(x\) is regular if \(\nabla h_1(x)\neq0.\)
5. For a vector \(\lambda\in\mathbb{R}^m,\) the Lagragian function is given by \[\mathcal{L}(x,\lambda)=f(x)+\lambda^Th(x)=f(x)+\sum_{i=1}^m\lambda_ih_i(x).\] Note that \(\nabla_{\lambda}\mathcal{L}(x,\lambda)=h(x).\)

Theorem 1 (Simplified Karush-Kun-Tucker Theorem). If \(x\) is a regular, extremum point of the provided problem, then there is a \(\lambda\in\mathbb{R}^m\) such that \[\nabla_x\mathcal{L}(x,\lambda)=\nabla f(x)+\lambda^T\nabla h(x)=0.\]

1.2.2 Inequality Constraints

We assume that \[\Omega=\left(\bigcap_{i=1}^m\left\{h_i(x)=0\right\}\right)\cap\left(\bigcap_{j=1}^p\left\{g_j(x)\leq0\right\}\right).\]

Notations:

1. For each \(x\in\Omega,\) set \(J_x=\left\{j:g_j(x)=0\right\}.\) Then \(x\) is called regular if the vectors \[\nabla h_i(x):i=\overline{1,m},\nabla g_j(x):j\in J_x\] are linearly independent.
2. For vectors \(\lambda\in\mathbb{R}^m\) and \(\mu\in\mathbb{R}^p,\) the Lagragian function is given by \[\mathcal{L}(x,\lambda,\mu)=f(x)+\lambda^Th(x)+\mu^Tg(x)=f(x)+\sum_{i=1}^m\lambda_ih_i(x)+\sum_{j=1}^p\mu_jg_j(x).\] Note that \(\nabla_{\lambda}\mathcal{L}(x,\lambda)=h(x)\) and \(\nabla_{\mu}\mathcal{L}(x,\lambda)=g(x).\)

Theorem 2 (Karush-Kun-Tucker Theorem). If \(x\) is a regular, extremum point of the provided problem, then there is a \(\lambda\in\mathbb{R}^m\) and \(\mu\in\mathbb{R}^p,\mu\geq\textbf{0}\) such that \[\nabla_x\mathcal{L}(x,\lambda)=\nabla f(x)+\lambda^T\nabla h(x)+\mu^T\nabla g(x)=0\] and \(\mu^Tg(x)=(\mu_1g_1(x),\mu_2g_2(x),...,\mu_pg_p(x))=\textbf{0}.\)

1.2.3 Problem 1

Minimize \(f(x)=x_1+x_2\) subject to \(g(x)=x_1^2+x_2^2-2=0.\)

Solution. The feasible region \(\Omega=\left\{g=0\right\}\) is compact while the objective function \(f\) is continuous, so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(1,1)\textrm{ and }\nabla g(x)=(2x_1,2x_2),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\lambda\in\mathbb{R}\) such that \[(0,0)=\nabla f(m)+\lambda\cdot\nabla g(m)=(1,1)+(2\lambda m_1,2\lambda m_2)\] or equivalently, \[\left\{\begin{matrix}1+2\lambda m_1=0\\1+2\lambda m_2=0\\m_1^2+m_2^2-2=0\end{matrix}\right.\Rightarrow(m_1,m_2,\lambda)\in\left\{(1,1,-0.5),(-1,-1,0.5)\right\}.\] There is no irregular point. Note that \(f((1,1))=2,f((-1,-1))=-2,\) so the global minimum of \(f\) is \(-2,\) attained at \((-1,-1).\)

1.2.4 Problem 2

Minimize \(f(x)=x_1+x_2\) subject to \(h(x)=x_1^2+x_2^2-2\leq0.\)

Solution. The feasible region \(\Omega=\left\{h\leq0\right\}\) is compact while the objective function \(f\) is continuous, so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(1,1)\textrm{ and }\nabla h(x)=(2x_1,2x_2),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\mu\in\mathbb{R}\) such that \(\mu\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f(m)+\mu\cdot\nabla h(m)=(1,1)+(2\mu m_1,2\mu m_2)\\0=\mu\cdot h(m)=\mu\cdot(m_1^2+m_2^2-2)\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}1+2\mu m_1=0\\1+2\mu m_2=0\\\mu\cdot(m_1^2+m_2^2-2)=0\end{matrix}\right.\Rightarrow(m_1,m_2,\mu)=(-1,-1,0.5).\] There is no irregular point. The global minimum of \(f\) is \(-2,\) attained at \((-1,-1).\)

1.2.5 Problem 3

Minimize \(f(x)=x_1+x_2\) subject to \(h_1(x)=x_1^2+x_2^2-2\leq0\) and \(h_2(x)=-x_2\leq0.\)

Solution. The feasible region \(\Omega=\left\{h_1\leq0\right\}\cap\left\{h_2\leq0\right\}\) is compact while the objective function \(f\) is continuous, so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(1,1),\nabla h_1(x)=(2x_1,2x_2),\nabla h_2(x)=(0,-1),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\mu=(\mu_1,\mu_2)^T\in\mathbb{R}^2\) such that \(\mu_1,\mu_2\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f(m)+\mu^T\cdot\nabla h(m)=(1,1)+(2\mu_1m_1,2\mu_1m_2-\mu_2)\\(0,0)=\mu^T\cdot h(m)=(\mu_1\cdot(m_1^2+m_2^2-2),-\mu_2m_2)\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}1+2\mu_1m_1=0\\1+2\mu_1m_2-\mu_2=0\\\mu_1\cdot(m_1^2+m_2^2-2)=0\\-\mu_2m_2=0\end{matrix}\right.\Rightarrow\begin{pmatrix}m_1\\m_2\\\mu_1\\\mu_2\end{pmatrix}=\begin{pmatrix}-\sqrt{2}\\0\\\frac{1}{2\sqrt{2}}\\1\end{pmatrix}.\] There is no irregular point. The global minimum of \(f\) is \(-\sqrt{2},\) attained at \((-\sqrt{2},0).\)

1.2.6 Problem 4

Minimize \(f(x)=x_1+x_2\) subject to \(h_1(x)=-x_1^3+x_2\leq0,h_2(x)=-x_2\leq0\) and \(h_3(x)=-x_1^5+x_2\leq0.\)

Solution. The feasible region \(\Omega=\left\{h_1\leq0\right\}\cap\left\{h_2\leq0\right\}\cap\left\{h_3\leq0\right\}\) is closed while the objective function \(f\) is coercive (i.e. \(f(x)\rightarrow\infty\) as \(||x||\rightarrow\infty\)), so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(1,1),\nabla h_1(x)=(-3x_1^2,1),\] \[\nabla h_2(x)=(0,-1),\nabla h_3(x)=(-5x_1^4,1),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\mu=(\mu_1,\mu_2,\mu_3)^T\in\mathbb{R}^3\) such that \(\mu_1,\mu_2,\mu_3\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f(m)+\mu^T\cdot\nabla h(m)=(1,1)+(-3\mu_1m_1^2-5\mu_3m_1^4,\mu_1-\mu_2+\mu_3)\\(0,0,0)=\mu^T\cdot h(m)=(\mu_1\cdot(-m_1^3+m_2),-\mu_2m_2,\mu_3\cdot(-m_1^5+m_2))\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}1-3\mu_1m_1^2-5\mu_3m_1^4=0\\1+\mu_1-\mu_2+\mu_3=0\\\mu_1\cdot(-m_1^3+m_2)=0\\-\mu_2m_2=0\\\mu_3\cdot(-m_1^5+m_2)=0\end{matrix}\right.:\textrm{no solution.}\] The only irregular point is \((0,0).\) The global minimum of \(f\) is \(0,\) attained at \((0,0).\)

1.2.7 Problem 5

Maximize \(f(x,y)=xy\) (i.e. minimize \(f_1(x,y)=-xy\)) subject to \(h_1(x,y)=x+y^2-2\leq0,h_2(x,y)=-x\leq0\) and \(h_3(x,y)=-y\leq0.\)

Solution. The feasible region \(\Omega=\left\{h_1\leq0\right\}\cap\left\{h_2\leq0\right\}\cap\left\{h_3\leq0\right\}\) is compact while the objective function \(f_1\) is continuous, so \(f_1\) admits a minimal value on \(\Omega.\) Since \[\nabla f_1(x,y)=(-y,-x),\nabla h_1(x,y)=(1,2y),\] \[\nabla h_2(x,y)=(-1,0),\nabla h_3(x,y)=(0,-1),\] by the Karush-Kuhn-Tucker Theorem, if \(z_0=(x_0,y_0)\) is a regular global minimum of \(f_1\) on \(\Omega\) then there exists a vector \(\mu=(\mu_1,\mu_2,\mu_3)^T\in\mathbb{R}^3\) such that \(\mu_1,\mu_2,\mu_3\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f_1(z_0)+\mu^T\cdot\nabla h(z_0)=(-y_0,-x_0)+(\mu_1-\mu_2,2y_0\mu_1-\mu_3)\\(0,0,0)=\mu^T\cdot h(z_0)=(\mu_1\cdot(x_0+y_0^2-2),-\mu_2x_0,-\mu_3y_0)\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}-y_0+\mu_1-\mu_2=0\\-x_0+2y_0\mu_1-\mu_3=0\\\mu_1\cdot(x_0+y_0^2-2)=0\\-\mu_2x_0=0\\-\mu_3y_0=0\end{matrix}\right.\Rightarrow\begin{pmatrix}x_0\\y_0\\\mu_1\\\mu_2\\\mu_3\end{pmatrix}\in\left\{\begin{pmatrix}0\\0\\0\\0\\0\end{pmatrix},\begin{pmatrix}4/3\\\sqrt{2}/\sqrt{3}\\\sqrt{2}/\sqrt{3}\\0\\0\end{pmatrix}\right\}.\] There is no irregular point. Note that \(f_1(0,0)=0,f_1\left(4/3,\sqrt{2/3}\right)=-\sqrt{32/27},\) the global minimum of \(f_1\) is \(-\sqrt{32/27}\) i.e. the global maximum of \(f\) is \(\sqrt{32/27},\) attained at \(\left(4/3,\sqrt{2/3}\right).\)

1.2.8 Problem 6

Minimize \(f(x)=x_1^2+x_2^2\) subject to \(g(x)=x_1^2+x_2^2-1\leq0.\)

Solution. The feasible region \(\Omega=\left\{g\leq0\right\}\) is compact while the objective function \(f\) is continuous, so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(2x_1,2x_2)\textrm{ and }\nabla g(x,y)=(2x_1,2x_2),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\mu\in\mathbb{R}\) such that \(\mu\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f(m)+\mu\cdot\nabla g(m)=(2m_1,2m_2)+(2\mu m_1,2\mu m_2)\\0=\mu\cdot g(m)=\mu\cdot(m_1^2+m_2^2-1)\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}2m_1+2\mu m_1=0\\2m_2+2\mu m_2=0\\\mu\cdot(m_1^2+m_2^2-1)=0\end{matrix}\right.\Rightarrow(m_1,m_2,\mu)=(0,0,0).\] There is no irregular point. The global minimum of \(f\) is \(0,\) attained at \((0,0).\)

1.2.9 Problem 7

Minimize \(f(x)=x_1^2+x_2^2+60x_1\) subject to \(h_1(x)=-x_1+80\leq0\) and \(h_2(x)=-x_1-x_2+120\leq0.\)

Solution. The feasible region \(\Omega=\left\{h_1\leq0\right\}\cap\left\{h_2\leq0\right\}\) is closed while the objective function \(f\) is coercive (i.e. \(f(x)\rightarrow\infty\) as \(||x||\rightarrow\infty\)), so \(f\) admits a minimal value on \(\Omega.\) Since \[\nabla f(x)=(2x_1+60,2x_2),\nabla h_1(x)=(-1,0),\nabla h_2(x)=(-1,-1),\] by the Karush-Kuhn-Tucker Theorem, if \(m=(m_1,m_2)\) is a regular global minimum of \(f\) on \(\Omega\) then there exists a vector \(\mu=(\mu_1,\mu_2)^T\in\mathbb{R}^2\) such that \(\mu_1,\mu_2\geq0\) and \[\left\{\begin{matrix}(0,0)=\nabla f(m)+\mu^T\cdot\nabla h(m)=(2m_1+60,2m_2)+(-\mu_1-\mu_2,-\mu_2)\\(0,0)=\mu^T\cdot h(m)=(\mu_1\cdot(-m_1+80),\mu_2\cdot(-m_1-m_2+120))\end{matrix}\right.\] or equivalently, \[\left\{\begin{matrix}2m_1+60-\mu_1-\mu_2=0\\2m_2-\mu_2=0\\\mu_1\cdot(-m_1+80)=0\\\mu_2\cdot(-m_1-m_2+120)=0\end{matrix}\right.\Rightarrow\begin{pmatrix}m_1\\m_2\\\mu_1\\\mu_2\end{pmatrix}=\begin{pmatrix}80\\40\\140\\80\end{pmatrix}.\] There is no irregular point. The global minimum of \(f\) is \(12800,\) attained at \((80,40).\)