Answers given will either not work in the real world versions of what you describe or are far from lowest cost.
Steven's LM2623 datasheet is a reasonable choice and will start on 1.1V and run on 0.9V but the IC costs about 60 cents.
If you genuinely want lowest cost then a properly engineered version of the Joule Thief is a good candidate. I use that name as it will lead you to many many variants but the original form is not very efficient. However, once you have the idea you can look at the options and choose one.
The "Joule Thief" is a one transistor self oscillating boost converter using an inductor main winding plus an inductor feedback winding. For DIY use you could build one for free from almost any modern scrapped electronic device or if buying new or surplus parts could build one with 10 to 20 cents of parts.
Here is a good example of a DIY Joule Thief page
The composite image below is made of 3 images from the above page:
Others - You can build boost converters with one transistor and two separate inductors - advantage is no need for two windings. And The classic Colpitts oscillator uses an untapped inductor.
A number here and
Other versions:
Wikipedia:
Added:
The basic Joule thief is not a marvellous design. It's outstanding feature is that it does work in many cases, thereby introducing energy conversions, SMPS, boost converters and more to many relatively inexperienced and uneducated electronics dabblers.
Various thoughts on regulated versions can be found by looking throiugh this collection (YMWV).
I stumbled upon a few prior stack exchange Joule Thief answers that seem to have some relevance. Searching for "Joule Thief" on this site will turn up a few more.
How can I calculate a Joule ThiefHow can I calculate a Joule Thief
alternative fix to: How can I calculate a Joule Thiefalternative fix to: How can I calculate a Joule Thief
Both December 2012
Various one cell to LED drivers here