Minimize $ {L}_{p} $ Norm Regularized with a Linear Term (Conjugate Function of the Norm Function)

Question

The problem is given as following:

$$ \min_{x} {a}^{T} x + \lambda \left\| x \right\|_{p} $$

Namely minimizing a ${L}_{p} $ norm term regularized by a linear term.

The above form occurs repeatedly on the dual forms of convex optimization problems as it is related to the Conjugate Function.

I will add my solution as Wiki Solution.
Please add your own or validate the community solution.
I will mark as an answer other people solution.

Answer 1

The Problem

$$ \min_{x} {a}^{T} x + \lambda \left\| x \right\|_{p} $$

The Solution

First pay attention that by setting $ y = -x $ the problem can be transformed into:

$$ \min_{y} -{a}^{T} y + \lambda \left\| y \right\|_{p} $$

Defining $ q $ such that $ \frac{1}{p} + \frac{1}{q} = 1 $.
One could show that $ \left\| \cdot \right\|_{p} $ is the dual of $ \left\| \cdot \right\|_{q} $.

Case I - $ \left\| a \right\|_{q} \leq \lambda $

By Holder Inequality $ {a}^{T} y \leq \left| {a}^{T} y \right| \leq \left\| a \right\|_{q} \left\| y \right\|_{p} $ hence:

$$ \begin{align*} -{a}^{T} y + \lambda \left\| y \right\|_{p} & \geq - \left\| a \right\|_{q} \left\| y \right\|_{p} + \lambda \left\| y \right\|_{p} \\ & = \left\| y \right\|_{p} \left( \lambda - \left\| a \right\|_{q} \right) \end{align*} $$

This is a non negative term which is minimized by $ y = \boldsymbol{0} \Rightarrow x = \boldsymbol{0} $ which means the minimum value is given by $ 0 $.

Case II - $ \left\| a \right\|_{q} > \lambda $

By definition as the dual norm $ \left\| a \right\|_{q} > \lambda \Rightarrow \exists u, \, \left\| u \right\|_{p} \leq 1 : {u}^{T} a > \lambda $.
Choosing $ y = t u $ yields:

$$ \begin{align*} -t {a}^{T} u + \lambda t \left\| u \right\|_{p} & = t \left( \lambda \left\| u \right\|_{p} - {a}^{T} u \right) & \text{} \\ & = t \left( \lambda - {a}^{T} u \right) \xrightarrow[]{t \to \infty} - \infty & \text{Since $ \left\| u \right\|_{p} \leq 1 $ and $ {a}^{T} u > \lambda $ } \end{align*} $$

Summary

$$ \min_{x} {a}^{T} x + \lambda \left\| x \right\|_{p} = \begin{cases} 0 & \text{ if } \left\| a \right\|_{q} \leq \lambda \\ -\infty & \text{ if } \left\| a \right\|_{q} > \lambda \end{cases} $$

The above could be generalized to any Norm and its Dual Norm.
Basically proving the Conjugate Function of a Norm is the Indicator Function of its Dual Norm.

Please Validate This Solution (Wiki Solution)

Answer 2

I'll take $\lambda = 1$ for simplicity. Let $f(x) = \| x \|_p$. Note that \begin{equation} \inf_x \, a^T x + \|x \|_p = - \sup_x \, \langle - a, x \rangle - \| x \|_p = - f^*(-a). \end{equation} The conjugate of a norm is the indicator function for the dual norm unit ball. Moreover, the dual norm for the $p$-norm is the $q$-norm, where $q = 1 - 1/p$. Thus, $$ f^*(-a) = \begin{cases} 0 & \quad \text{if } \| a \|_q \leq 1, \\ \infty & \quad \text{otherwise.} \end{cases} $$ It follows that $$ \inf_x \, a^T x + \|x \|_p = \begin{cases} 0 & \quad \text{if } \| a \|_q \leq 1, \\ -\infty & \quad \text{otherwise.} \end{cases} $$