A lower bound on complexity of optimization on the Wiener space

James M. Calvin

doi:10.1016/j.tcs.2007.04.016

A lower bound on complexity of optimization on the Wiener space

James M. Calvin

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.

Original language	English (US)
Pages (from-to)	132-139
Number of pages	8
Journal	Theoretical Computer Science
Volume	383
Issue number	2-3
DOIs	https://doi.org/10.1016/j.tcs.2007.04.016
State	Published - Sep 18 2007

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Keywords

Average-case complexity
Global optimization
Wiener measure

Access to Document

10.1016/j.tcs.2007.04.016

Cite this

@article{c29f5721e2da45169e6cbe24df8418da,

title = "A lower bound on complexity of optimization on the Wiener space",

abstract = "This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.",

keywords = "Average-case complexity, Global optimization, Wiener measure",

author = "Calvin, {James M.}",

year = "2007",

month = sep,

day = "18",

doi = "10.1016/j.tcs.2007.04.016",

language = "English (US)",

volume = "383",

pages = "132--139",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "2-3",

}

TY - JOUR

T1 - A lower bound on complexity of optimization on the Wiener space

AU - Calvin, James M.

PY - 2007/9/18

Y1 - 2007/9/18

N2 - This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.

AB - This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.

KW - Average-case complexity

KW - Global optimization

KW - Wiener measure

UR - http://www.scopus.com/inward/record.url?scp=34548130697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34548130697&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2007.04.016

DO - 10.1016/j.tcs.2007.04.016

M3 - Article

AN - SCOPUS:34548130697

SN - 0304-3975

VL - 383

SP - 132

EP - 139

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3

ER -

A lower bound on complexity of optimization on the Wiener space

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this