Pure Random Search with Virtual Extension of Feasible Region

E. A. Tsvetkov () and R. A. Krymov ()
Additional contact information
E. A. Tsvetkov: Lebedev Physical Institute of the Russian Academy of Sciences
R. A. Krymov: Moscow Institute of Physics and Technology

Journal of Optimization Theory and Applications, 2022, vol. 195, issue 2, No 8, 575-595

Abstract: Abstract We propose a modification of the pure random search algorithm for cases when the global optimum point can be located near the boundary of a feasible region. If the feasible region is cube-shaped, the worst case occurs when the global optimum point is located at the vertex of a cube. In these cases, the sample size for the pure random search should be increased significantly because the success probability of the single trial is decreased. The proposed modification is based on the virtual extension of the feasible region. The extended region contains $$\varepsilon $$ ε -neighbourhoods of all points of the original region. All random points that fall outside the original feasible region are mapped to the nearest points on its boundary before the values of an objective function at these points are calculated. This extension of the feasible region also leads to an increase in the sample size due to the increased volume. We compare sample sizes required to hit into the neighbourhood of the global optimum point with a given probability for the proposed method and the original pure random search algorithm with a corrected sample size. We consider ball-shaped and cube-shaped feasible regions and find the sufficient conditions for the proposed algorithm to be more efficient. We offer a practical recommendation for cases, in which the feasible region is defined by a system of linear inequalities.

Keywords: Pure random search; Stochastic optimisation; Sample size estimation; Boundary points; 65K05; 90C15 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02097-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:195:y:2022:i:2:d:10.1007_s10957-022-02097-w

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02097-w

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().