The relevant content starts at page 17 in the script.
The chapter ends on page 25.
Note that the exercises are different ones from the listing in the script.
==== Exercise's context ====
We consider the general minimization problem
$p^{\ast} := \inf_{x \in M \subseteq X} f(x),$
where $X \subseteq \mathbb{R}^n$, $f:X\to\mathbb{R}$ is continuous,
and the feasible set $M$ is given by inequality and equality constraints
in terms of continuous functions $(g_i){i=1,\dots,m}$ and $(h_j){j=1,\dots,q}$ (see lecture/notes).
The Lagrangian is defined as
$L(x;u,v) := f(x) + \sum_{i=1}^m u_i, g_i(x) + \sum_{j=1}^q v_j, h_j(x),$
with $u \in \mathbb{R}^m_{+}$ and $v \in \mathbb{R}^q$.
The associated Lagrange dual function is
$\Theta:\mathbb{R}^m_{+}\times \mathbb{R}^q \to \mathbb{R},$
$\Theta(u,v) := \inf_{x \in X} L(x;u,v),$
and the dual problem is
$d^{\ast} := \sup_{u \in \mathbb{R}^m_{+},\ v \in \mathbb{R}^q} \Theta(u,v).$
==== Exercise 5.1 (3.a) ====
(i) Show that $L(x;u,v) \le f(x)$ for all $x \in M$, $u \in \mathbb{R}^m_{+}$, $v \in \mathbb{R}^q$.
(ii) Show that $d^{\ast} \le p^{\ast}$.
==== Solution 5.1 (3.a) ====
(i) TODO: Write down the definition for $g$ and $h$ from the script. Consider $L-f$ and I think (i) follows from this directly.
tbd.
(ii) Make an arg about infs.
tbd.
==== Exercise 5.2 (3.b) ====
Let $X=\mathbb{R}^2$, $f(x)=-|x|^2$, and the feasible set
$M={,x \in X \mid g(x)\le 0,}$ with $g(x)=|x|-1$.
(i) Determine the primal value $p^{\ast}=\inf_{x \in M} f(x)$.
(ii) Determine the Lagrangian $L(x;u)=f(x)+u,g(x)$ for $u \in \mathbb{R}{+}$ and the dual function $\Theta(u)=\inf{x \in X} L(x;u)$.
(iii) Show that $d^{\ast}=\sup_{u \ge 0}\Theta(u)=-\infty$ and hence that a duality gap is present.
==== Solution 5.2 (3.b) ====
$r := |x| \ge 0$
(i) I think just Kurvendiscussion. And probably use that norms have $|x| = 0 \Leftrightarrow x = 0$
tbd.
(ii) Just write it down, I think
tbd.
(iii) Probably some relevant function is unbounded.
tbd.
==== Exercise 5.3 (3.c) ====
We change only the boundary formulation, but keep $X=\mathbb{R}^2$ and $f(x)=-|x|^2$.
Let $M={,x \in X \mid \tilde g(x)\le 0,}$ with $\tilde g(x)=|x|^2-1$.
(i) Determine again the primal value $p^{\ast}=\inf_{x \in M} f(x)$.
(ii) Determine the Lagrangian $\tilde L(x;u)=f(x)+u,\tilde g(x)$ for $u \in \mathbb{R}{+}$ and the dual function $\tilde \Theta(u)=\inf{x \in X} \tilde L(x;u)$.
(iii) Determine $d^{\ast}=\sup_{u \ge 0}\tilde \Theta(u)$ and show that strong duality holds, i.e., $d^{\ast}=p^{\ast}$.
Give an optimal multiplier $u^{\ast}$.
==== Solution 5.3 (3.d) ====
(i) I think as above in 5.1 (i)
tbd.
(ii) I think as above in 5.2 (ii)
tbd.
(iii) As above in 5.2 (iii) except here we seemignly don't explode. More Kurvendiscussion to get to the values $d,p,u$
tbd.
==== Exercise 5.4 (3.d) ====
Visualize, for both examples (1.b and 1.c),
the Lagrangian functions for various values of the Lagrange multiplier $u$,
in particular for the (if it exists) optimal parameter $u^{\ast}$.
Hint: Reduce the problem to a one-dimensional analysis.
==== Solution 5.4 (3.d) ====
Sounds like you'd use $r := |x|$ on the x-axis, get two curves for the Lagrange potentials, and then some Kurvenschaars.
tbd.
