Subscribe free to our newsletters via your
. Space Industry and Business News .




ENERGY TECH
Optimizing optimization algorithms
by Staff Writers
Boston MA (SPX) Jan 23, 2015


This sequence of graphs illustrates the application of the researchers' technique to a real-world computer vision problem. The solution to each successive problem (red balls) is used to initialize (green arrows) the search for a solution to the next. Image courtesy of the researchers.

Optimization algorithms, which try to find the minimum values of mathematical functions, are everywhere in engineering. Among other things, they're used to evaluate design tradeoffs, to assess control systems, and to find patterns in data.

One way to solve a difficult optimization problem is to first reduce it to a related but much simpler problem, then gradually add complexity back in, solving each new problem in turn and using its solution as a guide to solving the next one. This approach seems to work well in practice, but it's never been characterized theoretically.

This month, at the International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, Hossein Mobahi, a postdoc at MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL), and John Fisher, a senior research scientist at CSAIL, describe a way to generate that sequence of simplified functions that guarantees the best approximation that the method can offer.

"There are some fundamental questions about this method that we answer for the first time," Mobahi says. "For example, I told you that you start from a simple problem, but I didn't tell you how you choose that simple problem. There are infinitely many functions you can start with. Which one is good? Even if I tell you what function to start with, there are infinitely many ways to transform that to your actual problem. And that transformation affects what you get at the end."

Bottoming out
To get a sense of how optimization works, suppose that you're a canned-food retailer trying to save money on steel, so you want a can design that minimizes the ratio of surface area to volume.

That ratio is a function of the can's height and radius, so if you can find the minimum value of the function, you'll know the can's optimal dimensions. If you're a car designer trying to balance the costs of components made from different materials with the car's weight and wind resistance, your function -- known in optimization as a "cost function" -- will be much more complex, but the principle is the same.

Machine-learning algorithms frequently attempt to identify features of data sets that are useful for classification tasks -- say, visual features characteristic of cars. Finding the smallest such set of features with the greatest predictive value is also an optimization problem.

"Most of the efficient algorithms that we have for solving optimization tasks work based on local search, which means you initialize them with some guess about the solution, and they try to see in which direction they can improve that, and then they take that step," Mobahi says.

"Using this technique, they can converge to something called a local minimum, which means a point that compared to its neighborhood is lower. But it may not be a global minimum. There could be a point that is much lower but farther away."

A local minimum is guaranteed to be a global minimum, however, if the function is convex, meaning that it slopes everywhere toward its minimum. The function y = x2 is convex, since it describes a parabola centered at the origin. The function y = sin x is not, since it describes a sine wave that undulates up and down.

Smooth sailing
Mobahi and Fisher's method begins by trying to find a convex approximation of an optimization problem, using a technique called Gaussian smoothing. Gaussian smoothing converts the cost function into a related function that gives not the value that the cost function would, but a weighted average of all the surrounding values. This has the effect of smoothing out any abrupt dips or ascents in the cost function's graph.

The weights assigned the surrounding values are determined by a Gaussian function, or normal distribution -- the bell curve familiar from basic statistics. Nearby values count more toward the average than distant values do.

A Gaussian function is defined by a single parameter, which determines its width. Mobahi and Fisher begin with a very wide Gaussian, which, under certain conditions, yields a convex function. Then they steadily contract the width of the Gaussian, generating a series of intermediary problems.

At each stage, they use the solution to the last problem to initialize the search for a solution to the next one. By the time the width of the distribution has shrunk to zero, they've recovered the original cost function, since every value is simply the average of itself.


Thanks for being here;
We need your help. The SpaceDaily news network continues to grow but revenues have never been harder to maintain.

With the rise of Ad Blockers, and Facebook - our traditional revenue sources via quality network advertising continues to decline. And unlike so many other news sites, we don't have a paywall - with those annoying usernames and passwords.

Our news coverage takes time and effort to publish 365 days a year.

If you find our news sites informative and useful then please consider becoming a regular supporter or for now make a one off contribution.
SpaceDaily Contributor
$5 Billed Once


credit card or paypal
SpaceDaily Monthly Supporter
$5 Billed Monthly


paypal only


.


Related Links
Massachusetts Institute of Technology
Powering The World in the 21st Century at Energy-Daily.com






Comment on this article via your Facebook, Yahoo, AOL, Hotmail login.

Share this article via these popular social media networks
del.icio.usdel.icio.us DiggDigg RedditReddit GoogleGoogle








ENERGY TECH
New method to generate arbitrary optical pulses
Southampton, UK (SPX) Jan 23, 2015
Scientists from the University of Southampton have developed a new technique to generate more powerful, more energy efficient and low-cost pulsed lasers. The technique, which was developed by researchers from the University's Optoelectronics Research Centre (ORC), has potential applications in a number of fields that use pulsed lasers including telecommunications, metrology, sensing and ma ... read more


ENERGY TECH
Scientists invent 3-D printer 'teleporter'

Breakthrough lights up metamaterials

Is glass a true solid?

Scientists 'bend' elastic waves with new metamaterials

ENERGY TECH
USAF orders addditional Boeing rescue radios

Third MUOS Satellite Launched And Responding To Commands

MUOS-3 satellite ready for launch

Marines order Harris wideband tactical radios

ENERGY TECH
SES Entrusts Arianespace With SES-12

Client Pauses Launch of Proton Rocket Carrying British Satellite

Google aboard as Musk's SpaceX gets $1 bn in funding

Soyuz Installed at Baikonur, Expected to Launch Wednesday

ENERGY TECH
Turtles use unique magnetic compass to find birth beach

W3C and OGC to Collaborate to Integrate Spatial Data on the Web

AirAsia disappearance fuels calls for real-time tracking

Four Galileo satellites at ESA test centre

ENERGY TECH
BAE Systems support contract for Typhoon fighters extended

Switzerland restricts operations of F-5E aircraft

How prepared is your pilot to deal with an emergency?

Singapore navy finds main body of crashed AirAsia jet

ENERGY TECH
Solving an organic semiconductor mystery

Rice-sized laser, powered one electron at a time, bodes well for quantum computing

Smart keyboard cleans and powers itself -- and can tell who you are

New laser for computer chips

ENERGY TECH
SPIDER Experiment Touches Down in Antarctica

Subglacial Lakes Seen Refilling in Greenland

Airbus Defence and Space, TerraNIS and ARTAL Technologies join forces

All instruments for GOES-R now integrated with spacecraft

ENERGY TECH
Simple soil mixture reverses toxic stormwater effects

China air quality dire but improving: Greenpeace

A spoonful of sugar in silver nanoparticles to regulate their toxicity

Mystery pollutant kills 200 birds in San Francisco Bay




The content herein, unless otherwise known to be public domain, are Copyright 1995-2014 - Space Media Network. All websites are published in Australia and are solely subject to Australian law and governed by Fair Use principals for news reporting and research purposes. AFP, UPI and IANS news wire stories are copyright Agence France-Presse, United Press International and Indo-Asia News Service. ESA news reports are copyright European Space Agency. All NASA sourced material is public domain. Additional copyrights may apply in whole or part to other bona fide parties. Advertising does not imply endorsement, agreement or approval of any opinions, statements or information provided by Space Media Network on any Web page published or hosted by Space Media Network. Privacy Statement All images and articles appearing on Space Media Network have been edited or digitally altered in some way. Any requests to remove copyright material will be acted upon in a timely and appropriate manner. Any attempt to extort money from Space Media Network will be ignored and reported to Australian Law Enforcement Agencies as a potential case of financial fraud involving the use of a telephonic carriage device or postal service.