Optimization: Dual for L1 norm minimization with equality constraint

[Master1022]

Homework Statement

Find the dual problem of the L1 norm minimization problem with an equality constraint

Relevant Equations

Epigraphic reformulation

Hi,

I was reading through some notes on standard problems and their corresponding dual problems. I came across the L2 norm minimization for an equality constraint, and then I thought how one might formulate the dual problem if we had an L1-norm instead.

Question:
Consider the following optimization problem:
$\text{minimize}_{x}$ $|| x ||_{1}$
subject to: $Ax = b$.
where $x \in \mathbb{R}^{n}$, $b \in \mathbb{R}^{n}$, and $A \in \mathbb{R}^{n \times n}$

Attempt at finding the dual:
This is the attempt I have made, but I don't know how to proceed much further

1. Make an epigraphic reformulation of the objective function
We get:
$\text{minimize}_{t, x}$ $\sum_{j = 1}^{n} t_{j}$
subject to: $Ax = b$
$-x_{j} \leq t_{j}$ and $x_{j} \leq t_{j}$ for $j = 1, ..., n$

2. Write the Lagrangian
I realized that I don't fully understand what to do here when there are two separate optimization variables.

Would the Lagrangian look like?
$$L(x, t, \lambda, \nu) = \vec{1}^{T} \vec{t} + \vec{\nu}^{T} \left( A \vec{x} - \vec{b} \right) + \vec{\lambda}^{T} \left( \vec{x} - \vec{t} \right) + \vec{\lambda}^{T} \left( -\vec{x} - \vec{t} \right)$$

I included vector symbols just to (try to) be clear.

Thanks in advance

 

[mighty2000]

Thank you for your post. It's great to see that you are delving into the topic of standard and dual problems.

To answer your question, your attempt at finding the dual problem is on the right track. Here are a few suggestions to help you proceed further:

1. It is not necessary to make an epigraphic reformulation of the objective function. The L1-norm can be written as a sum of absolute values, which can then be reformulated as a linear program. This will make the Lagrangian easier to work with.

2. Your Lagrangian looks correct, but you have some extra terms in it. The Lagrangian should only have one set of Lagrange multipliers (in this case, \lambda) for the equality constraint and another set (in this case, \nu) for the inequality constraints. So your Lagrangian should look like this:

L(x, t, \lambda, \nu) = \vec{1}^{T} \vec{t} + \vec{\nu}^{T} \left( A \vec{x} - \vec{b} \right) + \vec{\lambda}^{T} \left( \vec{x} - \vec{t} \right)

3. To proceed further, you can differentiate the Lagrangian with respect to x and t, set the derivatives to zero, and solve for x and t in terms of \lambda and \nu. This will give you the dual function, which you can then maximize with respect to \lambda and \nu to obtain the dual problem.

I hope this helps. Good luck with your research!