CARVIEW |
Select Language
HTTP/2 200
date: Wed, 23 Jul 2025 16:28:21 GMT
content-type: text/html; charset=utf-8
cache-control: max-age=0, private, must-revalidate
content-security-policy: default-src 'none'; base-uri 'self'; child-src github.githubassets.com github.com/assets-cdn/worker/ github.com/assets/ gist.github.com/assets-cdn/worker/; connect-src 'self' uploads.github.com www.githubstatus.com collector.github.com raw.githubusercontent.com api.github.com github-cloud.s3.amazonaws.com github-production-repository-file-5c1aeb.s3.amazonaws.com github-production-upload-manifest-file-7fdce7.s3.amazonaws.com github-production-user-asset-6210df.s3.amazonaws.com *.rel.tunnels.api.visualstudio.com wss://*.rel.tunnels.api.visualstudio.com objects-origin.githubusercontent.com copilot-proxy.githubusercontent.com proxy.individual.githubcopilot.com proxy.business.githubcopilot.com proxy.enterprise.githubcopilot.com *.actions.githubusercontent.com wss://*.actions.githubusercontent.com productionresultssa0.blob.core.windows.net/ productionresultssa1.blob.core.windows.net/ productionresultssa2.blob.core.windows.net/ productionresultssa3.blob.core.windows.net/ productionresultssa4.blob.core.windows.net/ productionresultssa5.blob.core.windows.net/ productionresultssa6.blob.core.windows.net/ productionresultssa7.blob.core.windows.net/ productionresultssa8.blob.core.windows.net/ productionresultssa9.blob.core.windows.net/ productionresultssa10.blob.core.windows.net/ productionresultssa11.blob.core.windows.net/ productionresultssa12.blob.core.windows.net/ productionresultssa13.blob.core.windows.net/ productionresultssa14.blob.core.windows.net/ productionresultssa15.blob.core.windows.net/ productionresultssa16.blob.core.windows.net/ productionresultssa17.blob.core.windows.net/ productionresultssa18.blob.core.windows.net/ productionresultssa19.blob.core.windows.net/ github-production-repository-image-32fea6.s3.amazonaws.com github-production-release-asset-2e65be.s3.amazonaws.com insights.github.com wss://alive.github.com api.githubcopilot.com api.individual.githubcopilot.com api.business.githubcopilot.com api.enterprise.githubcopilot.com; font-src github.githubassets.com; form-action 'self' github.com gist.github.com copilot-workspace.githubnext.com objects-origin.githubusercontent.com; frame-ancestors 'none'; frame-src viewscreen.githubusercontent.com notebooks.githubusercontent.com; img-src 'self' data: blob: github.githubassets.com media.githubusercontent.com camo.githubusercontent.com identicons.github.com avatars.githubusercontent.com private-avatars.githubusercontent.com github-cloud.s3.amazonaws.com objects.githubusercontent.com release-assets.githubusercontent.com secured-user-images.githubusercontent.com/ user-images.githubusercontent.com/ private-user-images.githubusercontent.com opengraph.githubassets.com copilotprodattachments.blob.core.windows.net/github-production-copilot-attachments/ github-production-user-asset-6210df.s3.amazonaws.com customer-stories-feed.github.com spotlights-feed.github.com objects-origin.githubusercontent.com *.githubusercontent.com; manifest-src 'self'; media-src github.com user-images.githubusercontent.com/ secured-user-images.githubusercontent.com/ private-user-images.githubusercontent.com github-production-user-asset-6210df.s3.amazonaws.com gist.github.com; script-src github.githubassets.com; style-src 'unsafe-inline' github.githubassets.com; upgrade-insecure-requests; worker-src github.githubassets.com github.com/assets-cdn/worker/ github.com/assets/ gist.github.com/assets-cdn/worker/
referrer-policy: no-referrer-when-downgrade
server-timing: discussion_layout-fragment;desc="discussion_layout fragment";dur=159.505343,content_1-fragment;desc="content_1 fragment";dur=126.763745,content_2-fragment;desc="content_2 fragment";dur=59.021511,sidebar_content-fragment;desc="sidebar_content fragment";dur=80.114758,nginx;desc="NGINX";dur=1.013143,glb;desc="GLB";dur=100.977038
strict-transport-security: max-age=31536000; includeSubdomains; preload
vary: X-PJAX, X-PJAX-Container, Turbo-Visit, Turbo-Frame, X-Requested-With,Accept-Encoding, Accept, X-Requested-With
x-content-type-options: nosniff
x-frame-options: deny
x-voltron-version: fd8fbbc
x-xss-protection: 0
server: github.com
content-encoding: gzip
accept-ranges: bytes
set-cookie: _gh_sess=oxdCi4Jqp9uTgUHrZx5DxO96Ce98t4cKsPnXQ0b7iiO4%2BKZdQ%2FVw%2FRgo2cXEcSrOvA1nhA8mlND%2Fvtftpe8X7Tf1Xj%2FuE7Ih%2FYfBLXkOdXLHsKNj6Pr4yG53VDqZTm0hHi5rZUqvV%2F3LbQrN7wE%2Fjn2xtHXzFZR6OftQpQeLviup0i3MUcQiTC3XC3pEllNh8rxH%2FjgLi7BRUoex3pHlCTYJcH9g9erfEH9BuvvKdOAZmSs%2ByeKQW46et%2BHAPDo94HbAJiDmLKUE3IZGJhYKFA%3D%3D--kYYB0KEgFoRv7q8e--fbfUKwL9rjuitc%2BDXooJYA%3D%3D; Path=/; HttpOnly; Secure; SameSite=Lax
set-cookie: _octo=GH1.1.1861406689.1753288101; Path=/; Domain=github.com; Expires=Thu, 23 Jul 2026 16:28:21 GMT; Secure; SameSite=Lax
set-cookie: logged_in=no; Path=/; Domain=github.com; Expires=Thu, 23 Jul 2026 16:28:21 GMT; HttpOnly; Secure; SameSite=Lax
x-github-request-id: 8D4C:26221E:E99665:1141B98:68810DA5
Remarks on Derivative-Free Optimization Β· libprima Β· Discussion #145 Β· GitHub
Jan 23, 2024
·
0 comments
Heading
Bold
Italic
Quote
Code
Link
Numbered list
Unordered list
Task list
Attach files
Mention
Reference
Menu
reacted with thumbs up emoji
reacted with thumbs down emoji
reacted with laugh emoji
reacted with hooray emoji
reacted with confused emoji
reacted with heart emoji
reacted with rocket emoji
reacted with eyes emoji
Skip to content
Navigation Menu
{{ message }}
Remarks on Derivative-Free Optimization #145
zaikunzhang
started this conversation in
General
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You canβt perform that action at this time.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
PRIMA is a package designed for derivative-free optimization (DFO). Below are some elaborations on DFO.
What is DFO
DFO is a branch of optimization where problems are solved based on function values (i.e., zeroth-order information) without using classical or generalized derivatives (i.e., first- or higher-order information). It is also known as zeroth-order optimization or gradient-free optimization.
Why DFO
Traditional optimization algorithms often depend on first- or higher-order information of the problem. Yet, numerous applications lack access to such data. For instance, the objective function may not have an explicit formula but instead is determined by a complex black-box process involving sophisticated simulations, leading to the phrases "black-box optimization" and "simulation-based optimization". This situation is common in industry, engineering, and increasingly in machine learning and AI. These functions might stem from computations without closed-form formulations, such as solving partial differential equations (PDEs) or training neural networks.
When to use DFO algorithms
Employ DFO algorithms only if your problem includes at least one black-box component that cannot be modeled with an explicit formula.
Even if the explicit formulation of your problem is complex and approximate, it is typically more advantageous to exploit the formulation than treat it as a black box, which neglects all problem structures. It is crucial to investigate and leverage any existing information available.
DFO should not be mistaken for nonsmooth optimization. In DFO, the reason for not using the first-order information is not the nonsmoothness of the problem, but the unavailability of such information. If you have an explicitly formulated but nonsmooth problem, you should utilize available first-order information like subgradients instead of approaching it as a black box. Although DFO algorithms can handle nonsmooth problems, they will probably not perform as well as specialized nonsmooth optimization algorithms.
How to compare DFO solvers
In DFO, the cost is often dominated by function evaluations, which typically involve time-intensive and costly simulations. For example, a problem might require solving PDEs, taking seconds to minutes, or training neural networks, which could extend to hours or even months.
The main expense of using a DFO solver thus exists outside the solver itself. The computational effort within the solver is usually minor compared to the function evaluations.
Therefore, in developing a DFO package like PRIMA, the goal is to minimize function evaluations, even at the expense of increased internal computational effort. If a single function evaluation demands several minutes, optimizing the internal computation to save mere milliseconds per iteration is counterproductive.
Hence, benchmarking DFO solvers typically focuses on comparing the number of function evaluations and the resulting solution quality. If function evaluations vastly outweigh the computational cost of numerical operations within the solver, the number of function evaluations accurately reflects the problem-solving expense.
This rationale underpins our focus on function evaluation counts when assessing PRIMA against its Fortran 77 (F77) predecessors.
Indeed, PRIMA does consume more floating-point operations (flops) and memory inside the solvers. This is the price of modernization and modularization. The F77 implementation contains many tricks to save flops and memory, which can obscure code understanding and maintenance. Moreover, significant overhead can occur when a nontrivial F77 subroutine is partitioned into smaller subroutines and organized into modules, particularly if those subroutines are invoked multiple times by the solver.
My aim with PRIMA is to offer a modernized, modular, and reference implementation for Powell's DFO solvers. Code simplicity and clarity are prioritized in this context. When faced with a choice between coding efficiency and straightforwardness, the latter prevails, assuming the algorithm dictates a consistent number of function evaluations. Given the predominating expense of function evaluations, complicating code to save milliseconds is illogical.
Nevertheless, PRIMA's disregard for internal solver costs is not absolute. Prioritization is key:
Reducing function evaluations >> enhancing code simplicity & clarity >> economizing solver's internal costs.
We should focus on internal costs only after ensuring the first two priorities remain intact.
What if function evaluations are quick?
If function evaluations are indeed cheap in your problem, DFO solvers are still viable, but alternative methods like metaheuristics or population-based algorithms might be more suitable. If you decide to adopt Powell's solvers while concerned about the internal cost of the solvers, then there are two possibilities.
matprod
,inprod
, etc; you only need to consider the procedures in fortran/common/linalg.f90). However, I am not sure whether such a version will be much more efficient (in terms of internal cost of the solvers) than the current one.References
For a comprehensive overview of DFO, consider the introductory sections of relevant monographs, theses, and surveys.
[1] A. R. Conn, K. Scheinberg, and L. N. Vicente. Introduction to Derivative-Free Optimization, volume 8 of MOS-SIAM Ser. Optim. SIAM, Philadelphia, 2009
[2] Z. Zhang. Derivative-free Optimization Methods (in Chinese), PhD thesis, The Chinese Academy of Sciences, Beijing, 2012
[3] C. Audet and W. Hare. Derivative-Free and Blackbox Optimization. Springer, 2017
[4] J. Larson, M. Menickelly, and S. M. Wild. Derivative-free optimization methods. Acta Numer., 28:287β404, 2019
[5] T. M. Ragonneau. Model-Based Derivative-Free Optimization Methods and Software. PhD thesis, The Hong Kong Polytechnic University, Hong Kong, 2022
Beta Was this translation helpful? Give feedback.
All reactions