Comments (10)
Hello @andyfaff and all,
First of all, thank you very much for bringing this issue up and for proposing improvements (see also cobyqa/cobyqa#152). They are extremely important to us. We cherish your suggestions and inputs.
Meanwhile, I would like to mention that COBYQA (PRIMA as well) is primarily designed for "derivative-free optimization" (DFO), aka "black-box optimization" or "simulation-based optimization". We assume that function evaluations predominate the cost. In practice, each function evaluation can take seconds, minutes, hours, or days, because it often involves sophisticated simulations. In contrast, the costs incurred inside the solver (e.g., floating point operations, memory allocations) are assumed to be negligible. That is why we commonly use the number of function evaluations to measure the performance of DFO solvers.
However, we (Tom @ragonneau and I) always keep in mind that our assumptions can be wrong, and users may use our DFO solvers to solve non-DFO problems. Therefore, we should not ignore the internal costs of our solvers. Prioritization is key:
Reducing function evaluations >> enhancing code simplicity & clarity >> economizing solver's internal costs.
Any improvement of the code that does not increase the number of function evaluations should be integrated, just like what we have done at cobyqa/cobyqa#152 (credit goes to @andyfaff . Thank you!).
If you are interested in this topic, the following notes on DFO may be interesting to you. You are invited to make comments there:
https://github.com/orgs/libprima/discussions/145
Many thanks again!
Cheers,
Zaikun
from scipy.
Norm accepts axis keyword. No need to loop there
from scipy.
e.g. A long time is spent in Framework.get_best_index
. There is a loop in that method that calls Framework.merit
repeatedly. As part of merit
the constraint violations are calculated.
In a subsequent line in the loop the max constraint value is calculated. This maxcv calculation reevaluates the constraint violations again. i.e. duplication of calculation.
Furthermore, it's not clear why those constraint violations even need to be calculated for a system where there are no constraints or bounds.
from scipy.
Most of this loop could be vectorised.
from scipy.
Vectorize this line
from scipy.
Hi, I'm interested in helping out on this issue. Are you interested in PRs from anyone on this topic, or just the original author?
from scipy.
I've started a branch at https://github.com/andyfaff/cobyqa/tree/efficiency that's looking at various efficiency things. This is based on a jupyter notebook where I was line profiling things, https://gist.github.com/andyfaff/4cfdc554f9f520fb1a6a6f983025996f.
I'm yet to find the big prize.
It would be good to have the authors on board here, as the originators of the code they're familiar with it, and it's going to be easier for them. You're definitely more than welcome to contribute here, but it might be a slow slog through profiling country.
- There are a lot of expensive
scipy.linalg.eigh
calls. - It's annoying that the code wraps
optimize.LinearConstraint
,optimize.NonLinearConstraint
withproblem.LinearConstraints
andproblem.NonLinearConstraints
instead of using the original classes directly. - I suspect that there's a lot of linear algebra going on that doesn't need to be. e.g. if there are no constraints or bounds, then the algorithm should be designed to quickly bypass all calls to evaluation of those constraints, and the linear algebra involved with processing them to direct the minimisation.
- I suspect there's a bunch of caching that could be done, that isn't.
from scipy.
There are a lot of expensive
scipy.linalg.eigh
calls.
I found it was possible to reduce the time spent in eigh()
by 30% by passing driver="evd"
to eigh()
.
E.g.
eig_values, eig_vectors = eigh(a, driver="evd", check_finite=False)
Unfortunately, it also increased nfev by 3%, which may not be worth it.
I also tried passing overwrite_a=True
, but I did not find any speed-up from this.
from scipy.
This looks very helpful, I had a similar impression when I had a glance over COBYQA's source code. For the sake of repo hygiene, could we move the discussion to the COBYQA repo though? It must be fixed there anyway.
from scipy.
Please reassess the fail_slow
marks (gh-20699, gh-20741) when this is resolved.
from scipy.
Related Issues (20)
- Failures for new `pytest-fail-slow` check in Windows CI jobs HOT 7
- TST: my local test failures HOT 14
- BUG: ``optimize.nnls`` sometimes fails when input ``A`` is a Fortran order array HOT 4
- BUG: sparse.csgraph.minimum_spanning_tree: 64bit indices unsupported
- BUG: stats.levy_stable.rvs() ignores "S0"-parameterization
- BUG: SLSQP Inequality constraints incompatible when no constraints are present or constraints are respected HOT 7
- BUG: Numerically incorrect `scipy.signal.savgol_coeffs` (also affects `scipy.signal.savgol_filter`) HOT 4
- ENH: Add option to pass a single function to compute fun and jac in scipy.optimize.least_squares HOT 5
- query: scipy.signal.ShortTimeFFT import does not work HOT 1
- BUG: special.fdtri: inaccurate results for extreme arguments (exposed via scipy.stats.f.ppf) HOT 2
- DOC: Discourse release notes character limit HOT 2
- BUG: first shared library in scipy fails to be consumed by MSVC HOT 1
- BUG: sparse: testcase test_array_api_deprecations fails on Ubuntu 22.04 HOT 1
- DOC: update testing docs for alternative backends HOT 5
- ENH: sparse.csr_matrix: parallelize dot product HOT 1
- BUG: signal.iirfilter: returns NaNs
- MAINT/DEV: improve command line clarity of `dev.py` HOT 1
- DOC: stats.bootstrap: improve documentation multidimensional input HOT 14
- BUG: Library not loaded: @rpath/libgfortran.5.dylib for scipy v1.14.0rc1 x86 macos wheels HOT 8
- TYP: `_lib.doccer`: add type annotations HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from scipy.