Simulation-Based Optimization for Convex Functions Over Discrete Sets


  •  Eunji Lim    

Abstract

We propose a new iterative algorithm for finding a minimum point of f_*:X \subset \mathbb{R}^d \rightarrow \mathbb{R}, when f_* is known to be convex, but only noisy observations of f_*(\textbf{x}) are available at  \textbf{x} \in X for a finite set X. At each iteration of the proposed algorithm, we estimate the probability of each point \textbf{x} \in X being a minimum point of f_* using the fact that f_* is convex, and sample r points from X according  to these probabilities. We then make observations at the sampled points and use these observations to update the probability of each point \textbf{x} \in X  being a minimum point of f_*. Therefore, the proposed algorithm not only estimates the minimum point of f_* but also provides the probability of each point in X being a minimum point of f_*. Numerical results indicate the proposed algorithm converges to a minimum point of f_* as the number of iterations increases and shows fast convergence, especially in the early stage of the iterations.


This work is licensed under a Creative Commons Attribution 4.0 License.
  • ISSN(Print): 1927-7032
  • ISSN(Online): 1927-7040
  • Started: 2012
  • Frequency: bimonthly

Journal Metrics

  • h-index (December 2020): 18
  • i10-index (December 2020): 36
  • h5-index (December 2020): N/A
  • h5-median(December 2020): N/A

( The data was calculated based on Google Scholar Citations. Click Here to Learn More. )

Contact