  We present two matrix-free methods for approximately solving exact penalty
subproblems that arise when solving large-scale optimization problems. The
first approach is a novel iterative re-weighting algorithm (IRWA), which
iteratively minimizes quadratic models of relaxed subproblems while
automatically updating a relaxation vector. The second approach is based on
alternating direction augmented Lagrangian (ADAL) technology applied to our
setting. The main computational costs of each algorithm are the repeated
minimizations of convex quadratic functions which can be performed matrix-free.
We prove that both algorithms are globally convergent under loose assumptions,
and that each requires at most $O(1/\varepsilon^2)$ iterations to reach
$\varepsilon$-optimality of the objective function.
  Numerical experiments exhibit the ability of both algorithms to efficiently
find inexact solutions. Moreover, in certain cases, IRWA is shown to be more
reliable than ADAL.
