\documentclass[12pt]{article}

\usepackage[dvips]{graphicx}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{eucal}
\usepackage{hhline}
\usepackage{natbib}
%\usepackage{mathabx}


%\renewcommand{\baselinestretch}{2}
%\linespread{1.6}
\setlength{\oddsidemargin}{0.1cm}
\setlength{\evensidemargin}{0.1cm}
\setlength{\topmargin}{0cm}
\setlength{\textwidth}{6.2in}
\setlength{\textheight}{9in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}

% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
%\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
%\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
%\numberwithin{equation}{section}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
\newcommand{\corr}{\twoheadrightarrow}
% ----------------------------------------------------------------
\begin{document}

\textbf{ECON 4113. SOLUTION TO HOMEWORK 2}

\begin{enumerate}
\item (30 points) Solve using the Lagrange Theorem
\begin{eqnarray*}
\max_{x,y,z\in\Real} &&xyz+ z\\
\mathrm{s.t.}&& x^2+y^2+z \leq 6\\
&& x,y,z \geq 0
\end{eqnarray*}

Lagrangean is
$$L=xyz + z -\mu_1(x^2+y^2+z-6)+\mu_2x+\mu_3y+\mu_4z$$

First Order Conditions:
\begin{eqnarray}
yz-2x\mu_1+\mu_2&=&0\\
xz-2y\mu_1+\mu_3&=&0\\
yx+1-\mu_1+\mu_4&=&0\\
\mu_1(x^2+y^2+z-6)&=&0\\
\mu_2x=\mu_3y=\mu_4z&=&0\\
\mu_{1,2,3,4}&=&0\\
x^2+y^2+z &\leq& 6\\
x,y,z &\geq& 0
\end{eqnarray}

Cases:
\begin{description}
\item[$\mathbf{\mu_1 > 0}$] It follows from (4) that $x^2+y^2+z=6$
\begin{description}
\item[$\mathbf{z=0;\ x,y>0}$] It follows from (5) that $\mu_2=\mu_3=0$. Then from (1-2) we get $-2x\mu_1=-2y\mu_1=0\ \Rightarrow\ \mu_1=0$. Contradiction.
\item[$\mathbf{z,y>0;\ x=0}$] It follows from (5) that $\mu_4=\mu_3=0$. Then from (1-2) we get $yz+\mu_2=-2y\mu_1$. LHS is positive, RHS is not positive. Contradiction. The same works for the case $z,x>0;\ y=0$.
\item[$\mathbf{z=x=0;\ y>0}$] It follows from (5) that $\mu_3=0$, from (1) $\mu_2=0$. Then from (2) we get $-2y\mu_1=0\ \Rightarrow\ \mu_1=0$. Contradiction.
\item[$\mathbf{z>0;\ x=y=0}$] It follows from (5) that $\mu_4=0$. From (3) then $\mu_1=1$, which agrees with the assumption. From (1-2) $\mu_2=\mu_3$, from (4) $z=6$. All conditions are satisfied. We have 3 binding equations: (7) and $x=y=0$, so Constraint Qualification says that
\begin{displaymath}
\left(\begin{array}{c c c}
2x& 2y & 1\\
-1 & 0 & 0\\
0 & -1 & 0
\end{array}\right) = 
\left(\begin{array}{c c c}
0& 0 & 1\\
-1 & 0 & 0\\
0 & -1 & 0
\end{array}\right)
\end{displaymath}
should be full rank, which it is. Therefore, $(0,0,6)$ is a candidate solution.
\item[$\mathbf{x,y,z>0}$] So (5) implies $\mu_2=\mu_3=\mu_4=0$. Then (1-2,8) says $x=y$, (4) says $z=6-2x^2$, (3) implies $x=y=1$, $z=4$. Constraint Qualification:
\begin{displaymath}
\left(\begin{array}{c c c}
2x& 2y & 1
\end{array}\right) =
\left(\begin{array}{c c c}
2& 2 & 1\\
\end{array}\right)
\end{displaymath}
is full rank, so another candidate solution: (1,1,4).
\end{description}
\item[$\mathbf{\mu_1 = 0}$] (3) implies $xy+1+\mu_4=0$, which cannot be true since $x,y,\mu_4\geq 0$. Contradiction.
\end{description}

So we have found two candidate solutions. What's left to do is to check that there are no points at which Constraint Qualification does not hold (if there are such points, Lagrange Theorem cannot tell us anything about them, but if there are no such points then we know that the candidate solutions we found are the only ones worth looking at). We need to look at different cases to make sure that CQ always holds.

Cases:
\begin{description}
\item[$\mathbf{x=y=z=0}$] Three equations bind. CQ:
\begin{displaymath}
\left(\begin{array}{c c c}
-1 & 0 & 0\\
0 & -1 & 0\\
0 & 0 & -1\\
\end{array}\right)
\end{displaymath}
is full rank.
\item[$\mathbf{z>0;\ x=y=0}$] Three equations bind. Checked above.
\item[$\mathbf{x,y,z>0}$] One equation binds. Checked above.
\item[$\mathbf{z=x=0;\ y>0}$] Three equations bind. CQ:
\begin{displaymath}
\left(\begin{array}{c c c}
0& 2y & 1\\
-1 & 0 & 0\\
0 & 0 & -1
\end{array}\right)
Determinant is $2y>0$, so full rank. The same works for $z=y=0;\ x>0$
\item[$\mathbf{z,x>0;\ y=0}$] Two equations bind. CQ:
\begin{displaymath}
\left(\begin{array}{c c c}
2x& 0 & 1\\
0 & -1 & 0
\end{array}\right)
\end{displaymath}
There is a $2\times 2$ submatrix with determinant $1\neq 0$, so, rank is 2. The same works for $z,y>0;\ x=0$
\item[$\mathbf{x,y>0;\ z=0}$] Two equations bind. CQ:
\begin{displaymath}
\left(\begin{array}{c c c}
2x& 2y & 1\\
0 &  0& -1
\end{array}\right)
\end{displaymath}
There is a $2\times 2$ submatrix with determinant $-2y\neq 0$, so, rank is 2.
\end{description}

These are all possible cases. In all of them CQ holds. Therefore Lagrange theorem says that the only $(x,y,z)$ which can possibly be the solutions are those satisfying FOC. 






\item (30 points) Solve using the Lagrange Theorem
\begin{eqnarray*}
\max_{x,y\in\Real} &&3xy-x^3\\
\mathrm{s.t.}&& 2x-y = -5\\
&& 5x+2y \geq 37\\
&& x,y\geq 0
\end{eqnarray*}

\item (40 points) Facts: if $f:\Real^n\to\Real$ is continuous, then the set $\{x\in\Real^n: f(x)\leq 0\}$ is closed and $\{x\in\Real^n: f(x) < 0\}$ is open. Also for any finite number of sets $S_1,...,S_k$ it is true that: 1) if all $S_i$ are closed then the intersection $\cap_{i=1..k} S_i$ is closed; 2) if all $S_i$ are open then the intersection $\cap_{i=1..k} S_i$ is open.


Call $f:\Real^n\to\Real$ \textit{strictly increasing} if
$$\forall x,y\in\Real^n\ \ \  \Big[x\geq y \Rightarrow f(x)>f(y)\Big]$$
where $x\geq y$ means that $x_i\geq y_i$ for all $i=1..n$ and $x_j > y_j$ for at least one $j=1..n$.

Consider the problem
\begin{eqnarray*}
\max_{x\in\Real^n} &&F(x)\\
\mathrm{s.t.}&& G(x) \leq 0\\
\end{eqnarray*}
where $F:\Real^n\to\Real$, $G:\Real^n\to\Real^m$, $F$ is continuous and strictly increasing. Prove rigorously that if $\Gamma = \{x\in\Real^n: G(x) \leq 0\}$ is bounded then 1) the solution exists and 2) any solution $\bar x$ is such that $G^i(\bar x)=0$ for at least one $i\in\{1,...,m\}$ (the same as saying that $\bar x$ is not \textit{interior} solution).
\end{enumerate}
% ----------------------------------------------------------------
%\bibliographystyle{amsplain}
%\bibliography{}
\end{document}
% ----------------------------------------------------------------
