0

I'm considering Problem 6.4 of Boyd's Convex Optimization.

In the problem, we're using $\phi(u) = (u^2 + \epsilon)^{1/2}$ to solve the problem $$ \min \sum_{i=1}^m \phi(a_i^Tx-b_i) $$ in place of the true $\ell_1$ minimization problem $\inf_{x \in \mathbb{R}^m} \| Ax - b \|_1$.

The solutions formulates the dual of the approximation problem as $$ \max \sum_{i=1}^m -b_i \lambda_i $$ subject to constraints $|\lambda_i| \leq 1, \sum_{i=1}^m \lambda_i a_i = 0$. I'm having trouble seeing why this is the case.

What I've tried is to rewrite the approximation problem as:

$$ \min \sum_{i=1}^m \phi(r_i) $$ subject to $Ax - b = r$. Then I can write:

$$ L(x, r, \nu) = \sum_{i=1}^m \phi(r_i) + \nu^T(Ax - b - r)$$ and the dual function $$ g(\nu) = \inf_{r_i} \sum_{i=1}^m \phi(r_i) - \nu_ir_i - \nu^Tb.$$

It seems like the solution is using $\lambda$ in place of $\nu$ in my formulation above. Reverse-engineering from the solution also suggests that somehow minimizing over $r_i$ should make the summation $0$, but I'm not able to see why that's the case.

Alex Shtoff
  • 12
  • I suppose it'll come down to finding the dual $\phi^\ast$ of the approximation function, but I can't get a clean expression for that. –  Mar 19 '18 at 07:06
  • Actually, I believe the solution's formulation for the dual is not exact. Instead, it seems to be using the fact that $\phi^\ast(r_i) \leq 0$ when $|r_i| \leq 1$. –  Mar 19 '18 at 07:32
  • 1
    I believe that the dual you have is the dual of the original problem before approximation. It cannot be the dual of the approximation, since the original and the approximate problems have different optimal values, and therefore cannot have the same duals due to strong duality. – Alex Shtoff Mar 19 '18 at 11:42
  • Alex is correct. I suspect you're misreading the text (and/or it is unclear). – Michael Grant Mar 22 '18 at 21:42

0 Answers0