Repository navigation
Correct bib review and proven algorithms #380
Description
Folks,
The full theory for this type of algorithm was developed here:
https://link.springer.com/article/10.1007/s10107-020-01582-2
"A regularized smoothing method for fully parameterized convex problems
with applications to convex and nonconvex two-stage stochastic programming"
https://link.springer.com/article/10.1007/s10589-020-00257-0
"Decomposition Algorithms for Some Deterministic and
Two-Stage Stochastic Single-Leader Multi-Follower Games"
Kolter and Amos were the first to publish something, but it was a simultaneous invention.
There are registers of myself publishing about it as early as 2018, but review times at MathProg
are way too high, so it took a while until the work was out there.
Regards,
Activity
[-]Proven algorithms[/-][+]Correct bib review and proven algorithms[/+]joaquimg commentedon Oct 19, 2026
Thanks for the suggestion @pedroborgesmelo !
We do not intend to track the originality of ideas in this repo nor provide a detailed bibliographic review. Sensitivity analysis is a classic topic, and many works developed similar ideas long before Kolter and Amos.
If there is a particular sentence in the documentation that you find imprecise, I'd be happy to review.
The current references merely reflect the works (mainly software-backed) that the authors considered good reads and used during the software's development.
Your work looks very interesting and seems like a great contribution to the literature. If anything in your papers could improve the code in this repository, I'd be thrilled to learn more and get some pointers.
pedroborgesmelo commentedon Oct 19, 2026
Hello @joaquimg,
The whole question is centered around the existence (or not) of derivatives of solution mappings and value functions.
Most optimization problems, even linear ones satisfying all standard assumptions, will have multiple optimal
solutions at some parameters and non smooth value functions.
The question we solve there is how to build a proven (exact in the limit) approximation that always has
derivatives, without the need to resort to heuristics, and with such approximations, we can leverage standard
algorithms for smooth optimization, preserving convergence properties, and reusing the software stack.
With this in mind, the raw application of the implicit function theorem will result in eventual failure modes for
DiffOpt, in my opinion, most frequently when the upper problems involve solution mappings, as set-valuedness will hinder convergence in the upper level, and no heuristic will clearly work in this setting.
The eventual changes for DiffOpt would be to incorporate the regularization proposed in the paper and the associated strategies to manage the regularization parameter (an epsilon going to zero).
The regularization strategies are actually very simple: just stop Mehrotra early and employ Tikhonov.
However, this would require a custom implementation of Mehrotra. The last time I checked a couple years ago, no
LP solver gives you the option to drive the Mehrotra centering to a positive value, instead of driving it to zero.
I would like to congratulate you and the team on this great initiative.
Best regards,
blegat commentedon Oct 19, 2026
Did you check with MadIPM ?
pedroborgesmelo commentedon Oct 19, 2026
Hello @blegat,
No, at the time we used Ipopt, but as you may suspect, it is not as fast and reliable for LPs.
Regards,
joaquimg commentedon Oct 19, 2026
I think I understand.
The goals of DiffOpt are:
Therefore, a solver with the functionality you mention would be very welcome and would definitely use the DiffOpt API. However, I do not see DiffOpt managing the solver internals.
Indeed, MadIPM might be the place to explore those ideas.
I am closing this since there is no action for now. Please reopen this or open a new one if you find an issue we can tackle under the current scope of the package.