I need to solve the following optimization problem in Luenberger's Optimization by Vector Space Methods. I believe we can find the dual but I'm having trouble here.
\begin{align}
\mathrm{minimize}\quad&||x||_2 \\
\mathrm{subject\:to}\quad&||x||_{\infty}\geq\epsilon \\
&x\in\mathrm{Lip}_L[0,1],
\end{align}
where $\mathrm{Lip}_L[0,1]$ is the space of Lipschitz continuous functions with constant $L<\infty$.
Minimum norm problem over Lipschitz functions
functional-analysisoptimizationvector analysisvector-spaces
Related Solutions
Dual Problem Solution
The Lagrangian is given by:
$$ L \left( x, \lambda, \nu \right) = {x}^{T} x + {\lambda}^{T} \left( x - a \right) + \nu \left( \boldsymbol{1}^{T} x - b \right) = {x}^{T} x + \left( \lambda + \nu \boldsymbol{1} \right)^{T} x -{\lambda}^{T} a - \nu b $$
The Dual Function is given by:
$$ g \left( \lambda, \nu \right) = \inf_{x} L \left( x, \lambda, \nu \right) $$
Looking at the term related to $ x $:
$$ \inf_{x} {x}^{T} x + \left( \lambda + \nu \boldsymbol{1} \right)^{T} x $$
Which is a quadratic form of $ x $ with its minimizer given by: $$ {x}^{\ast} = -\frac{1}{2} \left( \lambda + \nu \boldsymbol{1} \right) $$
Its minimum given by $$ {{x}^{\ast}}^{T} {x}^{\ast} + \left( \lambda + \nu \boldsymbol{1} \right)^{T} {x}^{\ast} = -\frac{1}{4} \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) $$
Hence the Dual Problem is given by:
\begin{align*} \text{maximize} & \quad & -\frac{1}{4} \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) - {\lambda}^{T} a - \nu b \\ \text{subject to} & \quad & \lambda \succeq 0 \end{align*}
The problem is Concave in $ \left( \lambda, \nu \right) $ hence it is a convex problem.
It can be solved by a Quadratic Programming as:
$$ \left( \lambda + \nu \boldsymbol{1} \right)^{T} \left( \lambda + \nu \boldsymbol{1} \right) = {\left\| E v \right\|}_{2}^{2} = {v}^{T} {E}^{T} E v = {v}^{T} H v $$
Where $ v = {\left[ \lambda, \nu \right]}^{T}, \; E = \left[ I, \boldsymbol{1} \right], \; H = {E}^{T} E $. Then the problem becomes:
$$ \begin{align*} \text{minimize} & \quad & \frac{1}{4} {v}^{T} H v + {v}^{T} f \\ \text{subject to} & \quad & A v \preceq 0 \end{align*} $$
Where $ A = - \left[ I, \boldsymbol{0} \right], \; f = {\left[ a, b \right]}^{T} $.
The above can directly solved by MATLAB's quadprog(). Then $ {x}^{\ast} = -0.5 E v $.
I'm going to define a bunch of spaces which all describe functions of "regularity $\alpha$" in some sense.
Hölder spaces: Here $\alpha$ will be in $[0,1]$. Define $Lip_{\alpha}(\Bbb T^n)$ to be the space of all functions $f:\Bbb T^n \to \Bbb R$ such that $|f(x)-f(y)| \leq C|x-y|^{\alpha}$ for some $C>0$ independent of $x,y \in \Bbb T^n$. The smallest such constant $C$ is called the Holder seminorm, denoted by $[f]_{\alpha}$. The Banach space norm on $Lip_{\alpha}(\Bbb T^n)$ is defined by $\|f\|_{L^{\infty}(\Bbb T^n)}+[f]_{\alpha}.$ Note that when $\alpha = 0$ we just get $L^{\infty}(\Bbb T^n)$. Equivalently one may describe $Lip_{\alpha}(\Bbb T^n)$ as the set of functions $f$ such that $\sup_{x\in Q}|f(x)-f_Q| \leq C|Q|^{\alpha/n},$ for all cubes $Q \subset \Bbb T^n$, where $f_{Q} := \frac1{|Q|} \int_Q f$, and $|Q|$ is the Lebesgue measure of $Q$. (Proving this equivalence is difficult.)
Besov spaces: Here $\alpha$ can be any real number. Any function $f:\Bbb T^n \to \Bbb R$ admits a canonical decomposition called the Littlewood-Paley decomposition $f = \sum_{j\ge 0} f_j$. The Besov space $B^{\alpha}_{\infty,\infty}(\Bbb T^n)$ consists of those functions $f$ such that $\|f_j\|_{L^{\infty}(\Bbb T^n)} \leq C2^{-\alpha j}$ for some $C$ which is independent of $j$. The smallest constant $C$ for which the inequality holds is called the Besov norm. This induces a Banach space structure on $B^{\alpha}_{\infty,\infty}$. The space $B^1_{\infty,\infty}$ is called the Zygmund class and is equivalently described as the set of all functions $f$ such that $$|f(x+h)+f(x-h)-2f(x)| \leq C|h|,$$ and $B^0_{\infty,\infty}$ consists of the distributional derivatives of functions from the Zygmund class.
BMO spaces: Here $\alpha$ will be in $[0,1]$. Let us define the space $BMO_{\alpha}(\Bbb T^n)$ to be the space of all functions $f:\Bbb T^n \to \Bbb R$ such that $\sup_Q \frac{1}{|Q|^{1+\alpha/n}}\int_{Q} |f-f_Q|dx <\infty$, where the sup is over all cubes $Q\subset \Bbb T^n$, and $f_{Q} := \frac1{|Q|} \int_Q f$, and $|Q|$ is the Lebesgue measure of $f$. The norm on $BMO_{\alpha}$ is defined to be that supremum, which makes it a Banach space.
Continuous function spaces: Here $\alpha=:k$ must take values in $\Bbb N$. Then $C^{k}(\Bbb T^n)$ is defined to be the set of all functions $f:\Bbb T^n \to \Bbb R$ such that all partial derivatives of order up to $k$ are continuous. The norm is defined to be sum of the uniform norms of all of the partial derivatives up to order $k$. Again, we get a Banach space.
So now the question is: how are all of these spaces related?
Theorem 1: If $\alpha \in (0,1)$ then $$ Lip_{\alpha}(\Bbb T^n) = B^{\alpha}_{\infty,\infty} (\Bbb T^n)= BMO_{\alpha}(\Bbb T^n).$$ All of the norms are equivalent.
Theorem 2: For $\alpha = 0$ we have the following inclusions: $$C^0(\Bbb T^n) \subsetneq L^{\infty}(\Bbb T^n) \subsetneq BMO_0(\Bbb T^n) \subsetneq B^0_{\infty,\infty}(\Bbb T^n).$$ So none of the norms are equivalent. For $\alpha=1$ we have the corresponding sequence of proper inclusions.
Basically the equivalences in Theorem 1 always boil down to a computation on dyadic blocks. They fail for $\alpha=0$ due to the fact that the series $\sum 2^{-\alpha n}$ diverges for $\alpha=0$.
Sorry if this was unclear. Will try to update with references.
Best Answer
First, notice that you can assume the first constraint to be an equality. That's because any sequence $f_n$ that approaches the infimum can be rescaled to meet the equality.
So now we have to solve $$\begin{align} \mathrm{minimize}\quad&||x||_2 \\ \mathrm{subject\:to}\quad&||x||_{\infty}=\epsilon \\ &x\in\mathrm{Lip}_L[0,1], \end{align}$$
Let $f\in\mathrm{Lip}_L[0,1]$ such that $\|f\|_\infty=\varepsilon$. Without loss of generality, we can assume that $\|f\|_\infty$ is the maximum of $f$ (just multiply $f$ by $-1$ if it were the minimum). Remember that $f$ is continuous and achieves that maximum, let's assume in $a\in[0,1]$: $$f(a) = \|f\|_\infty=\varepsilon$$
Let's construct $f^*\in\mathrm{Lip}_L[0,1]$ as being a triangle function with slope $L$ and that has its maximum in $a$ with value $\varepsilon$: $$f^*(x)=\left\{ \begin{split} \varepsilon+(x-a)L & \,\,\,\,\,\text{if }\max\left(0,a-\frac \varepsilon L\right)\leq x \leq a \\ \varepsilon+(a-x)L & \,\,\,\,\,\text{if }a\leq x \leq \min\left(1,a+\frac \varepsilon L \right)\\ 0 & \,\,\,\,\,\text{ otherwise.} \end{split}\right.$$
We will prove that for all functions $f\in\mathrm{Lip}_L[0,1]$ such that $f(a)=\|f\|_\infty=\varepsilon$, we have $$\|f^*\|_2\leq \|f\|_2$$ That will show that the solution of the problem is among $f^*$ and all its translated versions.
Onto the proof itself: For $|x-a| \leq \frac \varepsilon L$, it's easy to verify that $$f(x) \geq f(a) - |f(x)-f(a)|\geq \varepsilon-L|a-x|=f^*(x)$$ Thus $$\int_0^1|f(x)^2dx \geq \int_{|x-a|\leq \frac \varepsilon L}|f(x)|^2dx \geq\int_{|x-a|\leq \frac \varepsilon L}|f^*(x)|^2dx =\int_0^1|f^*(x)|^2 dx$$ Therefore the solution is to be found among $f^*$ and its shifted versions. And there are two special values where the quadratic norm is minimal, it's when $a=0$ and $a=1$, the half triangles. And in those cases $$\|f^*\|_2 = \sqrt{\frac{\varepsilon^3}{3L}}$$