I have implemented a program to solve primal and dual problem defined by:
A)
Primal is:
maximize $cx$ subject to $Ax=b$ and $x>=0$
corresponding dual is:
minimize $kb$ subject to $kA-z=c$
In the above $A$ is a matrix all all other variable is vector.
Now I want to solve the minimization problem:
B)
minimize $(norm(A*x-b)+norm(x,1))$
Where norm(.) is usual L2 norm and norm(x,1) means L1 norm
Can I solve B using the same solving method of A ? If so how can I change the variables of B similar to A? Any guidance would be appreciated.
Here is a more complete answer about the problem dual (since that is what you asked about originally):
We start with the primal problem, an L1-regularized LLS
$\min ||Ax-b||_2^2 + \lambda||x||_1$
Now, let us define $z$ s.t. $z := Ax - b$. Thus, our problem can be written as
$\min z^Tz + \lambda ||x||_1$ s.t. $z = Ax-b$.
Associate $\mu_i$ with the $i$th constaint, thus we have the Langrangian is simply
$L(x,z,\mu) = z^Tz + \lambda||x||_1 + \mu^T(Ax-b-z)$.
Therefore, the dual function is then given by
$\displaystyle g(\mu) = \inf_{x,z}\left\{L(x,z,\mu)\right\}$.
Now, we want to find $\max_{\mu}g(\mu)$, and so first we note that if, for some $i$, $|\sum_j a_{ji}\mu_j| > \lambda_i$, then we have a direction of unboundedness this is because the only terms in the numerator with $x_i$ are
$\displaystyle \left(\sum_ja_{ji}\mu_j\right)x_i$ and $\displaystyle \lambda_i|x_i|$.
Thus for any such $\mu$ we have $g(\mu) = -\infty$. Therefore, we can restrict our attention to $\mu$ s.t. $|(A^T\mu)_i| \leq \lambda_i \forall i$. Now, for each such $\mu$ it can be seen that the $x$ that minimizes $g(\mu)$ is $x=0$.Thus, for all $\mu$ of interest, we have that
$\displaystyle g(\mu) = \inf_{x,z}\{L(x,z,\mu)\} = \inf_z\left\{z^Tz - \mu^Tz - \mu^Tb\right\}$.
Fortunately, we can differentiate this, set it to zero, to see that in optimality, $z_i = \mu_i/2.$
Hence, for all $\mu$ s.t. $|(A^T\mu)_i| \leq \lambda_i \forall i$ we have that
$\displaystyle g(\mu) = -\frac{1}{4}\mu^T\mu-\mu^Tb$.
Therefore, the Lagrangian Dual is given by
$\displaystyle \max_\mu -\frac{1}{4}\mu^T\mu-\mu^Tb$ s.t.$|(A^T\mu)_i| \leq \lambda_i \forall i$.
Therefore, the dual is a convex optimization problem in $\mu$ and because the primal problem satisfies Slater's condition, we have that the duality gap is zero.