<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">
Hi Toby,
<div><br class="">
<blockquote type="cite" class="">
<div class="">On Jan 25, 2019, at 12:11 PM, Isaac, Tobin G <<a href="mailto:tisaac@cc.gatech.edu" class="">tisaac@cc.gatech.edu</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">On
Fri, Jan 25, 2019 at 04:29:11PM +0000, Dener, Alp via petsc-users wrote:</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
Hi Hansol,<br class="">
<br class="">
We don’t have a Levenberg-Marquardt method available, and if the PETSc/TAO manual says otherwise, that may be misleading. Let me know where you saw that and I can take a look and fix it.<br class="">
<br class="">
In the meantime, if you want to solve a least-squares problem, the master branch of PETSc on Bitbucket has a bound-constrained regularized Gauss-Newton (TAOBRGN) method available. The only available regularization right now is an L2 proximal point Tikhonov
regularizer. There are ongoing efforts to support an L1 regularizer, and also the ability for users to define their own, but these have not made it into the master branch yet. We’re working on it and should be in for the next major PETSc release in the Spring.<br class="">
<br class="">
If you’d like to use that method, you need to set the Tao type to TAOBRGN and then go through the TaoSetResidualRoutine() and TaoSetJacobianResidualRoutine() interfaces to define your problem.<br class="">
<br class="">
In general, you can use other TAO algorithms (e.g.: BNLS, BQNLS, etc.) with your own regularization term by embedding it into the objective, gradient and Hessian (if applicable) evaluation callbacks. The caveat is that your regularizer needs to be C1 continuous
for first-order methods and C2 continuous for second order methods. This typically limits you to L2-norm regularizers. There is no support yet for L1-norm regularizers, but as I said, we’re working on it right now and it should be available in a couple of
months.<br class="">
</blockquote>
<br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">Is
there a feature branch yet where we could see what is being</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">prepared?</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
</div>
</blockquote>
<div><br class="">
</div>
<div>Xiang has been working on it here: <a href="https://bitbucket.org/petsc/petsc/branch/xhuang/tao-feature-L1" class="">https://bitbucket.org/petsc/petsc/branch/xhuang/tao-feature-L1</a></div>
<div><br class="">
</div>
<div>Currently it’s a complete replacement of the L2 regularizer in BRGN, but we will merge and combine with the old regularizer, and make some interface changes to support user-provided regularizers before it’s ready for a pull request.</div>
<br class="">
<blockquote type="cite" class="">
<div class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">While
I think it is nice as a convenience for Tao to support adding l1</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">regularization
for people, my two cents is that this should call on a</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">deeper
structure that supports separable objectives.</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
</div>
</blockquote>
<div><br class="">
</div>
<div>The Gauss-Newton code (BRGN) is a very simple wrapper around the existing Newton Line-Search (BNLS) algorithm. It constructs the problem from the provided residual and Jacobian, tacks on an L2 regularizer, and feeds it into BNLS underneath.</div>
<div><br class="">
</div>
<div>I’m not intimately familiar with the L1 regularizer that Xiang has been working on for some tomography problems but I’m reasonably sure that it does not take advantage of any kind of a structure in the objective function because it’s built on top of the
same BRGN infrastructure.</div>
<div><br class="">
</div>
<div>I wasn’t aiming for a very sophisticated least squares solver when I put together BRGN. It’s more of a low-hanging fruit case, where we could write a very small amount of code that saves the user some time in constructing the same Gauss-Newton problem
that they could actually have also constructed themselves manually if they defined the FormFunctionAndGradient() and FormHessian() routines appropriately for existing Newton solvers.</div>
<div><br class="">
</div>
<div>I agree that a more sophisticated and serious approach to least-squares problems would benefit from separable objective functions and algorithms that take advantage of structure, but we don’t have any solvers in Tao that do this yet. I personally wouldn’t
mind adding other features to BRGN or adding other L-S solvers, but we don’t really have applications or use-cases in front of us so it’s hasn’t risen high up on the priority list. If you have a problem you want to solve or a particular algorithm to add to
Tao, we can talk altogether with Todd and see what we have to do with Tao interfaces and other things to support those efforts and collaborate.</div>
<div><br class="">
</div>
<div>Best,</div>
<div>
<div>——<br class="">
<b class="">Alp Dener</b></div>
<div>Argonne National Laboratory</div>
<div><a href="https://www.anl.gov/profile/alp-dener" class="">https://www.anl.gov/profile/alp-dener</a></div>
</div>
<div><br class="">
</div>
<blockquote type="cite" class="">
<div class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">For
example, an implementation of total variation regularization would</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">apply
l1 to some operator applied to the control variables, and</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">instead
of creating a complete TV implementation in Tao, a user should</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">be
able to express "This part (misfit) is smooth" and "This part is</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">not,
but it is convex".</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class=""> Toby</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">
<br class="">
Hope that helps,<br class="">
——<br class="">
Alp Dener<br class="">
Argonne National Laboratory<br class="">
<a href="https://www.anl.gov/profile/alp-dener" class="">https://www.anl.gov/profile/alp-dener</a><br class="">
<br class="">
<br class="">
<br class="">
On Jan 24, 2019, at 2:57 PM, David via petsc-users <<a href="mailto:petsc-users@mcs.anl.gov" class="">petsc-users@mcs.anl.gov</a><<a href="mailto:petsc-users@mcs.anl.gov" class="">mailto:petsc-users@mcs.anl.gov</a>>> wrote:<br class="">
<br class="">
Hi. I was wondering whether there was some kind of general consensus about<br class="">
<br class="">
the currently-best-implemented L1, L2 norm regularization for petsc/tao<br class="">
that has been implemented.<br class="">
<br class="">
Naively, I would shoot for Levenberg-Marquardt for some kind of random<br class="">
matrix, or even generic<br class="">
<br class="">
finite-difference stencil problem. (but it seems like LM is yet to be<br class="">
implemented, but only on petsc manual pdf?)<br class="">
<br class="">
Or perhaps, of the implemented ones, LMVM seems to work well, at least<br class="">
on my local machine.<br class="">
<br class="">
In any due case, I would highly appreciate the input and opinion about<br class="">
these matters.<br class="">
<br class="">
<br class="">
Thanks.<br class="">
<br class="">
<br class="">
<br class="">
Hansol Suh,<br class="">
<br class="">
PhD Student<br class="">
<br class="">
<br class="">
Georgia Institute of Technology</blockquote>
</div>
</blockquote>
</div>
<br class="">
</body>
</html>