Abstract

Abstract: In computational physics, mathematical equations allow us to accurately map a given physical system to its response. Conversely, inverse problems involve the task of designing a physical system that produces a target response. Inverse problems are typically cast as search problems and solved using the Monte Carlo method, which frequently encounters local minima despite using various noise strategies to escape them. FastPivot is a recent algorithm that is known to outperform the Monte Carlo method on certain kinds of inverse problems. It starts with a system state and invokes alternating forward and backward passes through the system variables. In a forward pass, it leads the current state of the system to its response. In the subsequent backward pass, a small amount of information percolates from the target response back to the system variables. In this paper, we first analyze the FastPivot algorithm and posit that its unique ability to percolate information from the target response allows it to avoid local minima by 'attaching an elastic tether' to a global minimum. We then propose a lift-and-project strategy to enhance the FastPivot algorithm. This strategy exploits the observation that, with increasing number of dimensions, the FastPivot algorithm encounters fewer local minima while the Monte Carlo method encounters more local minima. Overall, FastPivot with the lift-and-project strategy is a very promising approach: It rarely encounters local minima on the quintessential inverse problem of placing atoms in a bounded region using a scanning tunneling microscope to achieve target responses in the density of states.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.