[petsc-users] L1 or projection type regularization with PETSc

[Jed Brown]

Lingyun Qiu <qiu.lingyun at gmail.com> writes:

> On Thu, Apr 7, 2016 at 2:24 PM, Jed Brown <jed at jedbrown.org> wrote:
>
>> Lingyun Qiu <qiu.lingyun at gmail.com> writes:
>>
>> > Dear all,
>> >
>> > I am working an optimization problem as
>> > min_x  ||Ax - b||_2^2 + alpha ||x||_1
>> >
>> > For the fidelity term, we use L2 norm.  We use L1 norm for the
>> > regularization term. Without regularization term, i.e., alpha=0, we
>> > iteratively solve the problem as
>> > x_k+1 = KSP(x_k).
>>
>> I.e., a single KSPSolve because the optimization problem is quadratic?
>
> Yes. A single KSPSolve because of the quadratic form. k stands for the
> iteration index inside KSPSolve.

But the k+1 iterate is not a function of just the previous iterate, it
is a function of all previous iterates (sometimes via recurrence).

>> > I plan to use the split Bregman method to solve the regularized problem.
>> It
>> > reads as,
>> > y_k+1 = KSP(x_k)
>> > x_k+1 = B(y_k+1)
>> > Here B() is the function related to the Bregman method. It works as a
>> > post-processing of the iterates.
>>
>> But outside the KSPSolve, not at each iteration of the KSPSolve...
>>
> I need to modify the iterate after each iteration inside the KSPSolve. Yes,
> B is a nonlinear operation.

That nonlinear operation breaks orthogonality, so your Krylov method
won't work.  You can't just tinker willy-nilly with the vectors inside
the Krylov solver.  There are specialized Krylov methods for solving
problems with certain constraints, such as QCG for solving SPD systems
subject to trust region constraints.  But not in general.  Call KSPSolve
and then do your shrink operation, rinse and repeat, perhaps with
nonlinear acceleration.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 818 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20160407/044b4378/attachment.pgp>