0
$\begingroup$

This is a classic question, its for a homework assignment, I have the solution but I've been breaking my head to understand how to approach the problem.

Minimize $||A\vec x - \vec b||_1$ subject to $||x||_\infty \leq1$

and the solution given is

Minimize $\textbf{1}^T$ subject to $-y \leq A\vec x - \vec b \leq y$ and $\textbf{-1} \leq x \leq \textbf{1}$

If anyone could shed some light on how to approach this problem...

$\endgroup$
3
$\begingroup$

HINT

The constraint $\|x\|_\infty \le 1$ means max of the coordinates of $x$ cannot be more than 1 in absolute value. How do you express this in terms of a regular inequality?

Also, think about what $\|Ax-b\|_1$ looks like if we have $y = Ax-b$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.