Nice book on convex optimization techniques | Hacker News Reader

Nice book on convex optimization techniques

stanford.edu

Hey all, here's a nice text on the theory and algorithmics of solving problems which can be described as max/minimizing some function subject to some feasibility constraints

Open articleView on HN

This book is truly wonderful. Probably my favorite math book.

Those of you who may be interested in convex optimization may want to take a look at these "MIT OCW-like" pages:

http://see.stanford.edu/SEE/courseinfo.aspx?coll=2db7ced4-39... http://see.stanford.edu/SEE/courseinfo.aspx?coll=523bbab2-dc...

and those who are interested in convex optimization and Python programming, might want to take a look at these:

http://abel.ee.ucla.edu/cvxopt http://cvxmod.net

i second this. this is probably my favorite text book behind Mackay's "Information Theory, Inference, and Learning Algorithms".

if you take the time to honestly follow the text you come away with a great understanding of convex optimization... both the theory and the methods.

Now that you've reminded me of Mackay's equally wonderful book, I can't decide which of these two is my favorite ;-) All math books should be like these two gems. I never get tired of reading them.

It seems to be available for free online as well: http://www.inference.phy.cam.ac.uk/mackay/itila/book.html

I know a guy who's using convex optimization as part of a project to sample an ultra-wide range of frequencies looking for a hidden narrowband signal (I leave it up to you to guess who would need that kind of device).

Apparently they use "compressive sampling" (http://en.wikipedia.org/wiki/Compressed_sensing) in conjunction with the convex optimization so they can avoid building the superfast A-to-D that you'd normally need to cover such a frequency range.

You can apparently prove that it'll always find the narrowband signal, as long as it's narrow enough.

I take it that this is referring to a (listening) bug detector?

It sounded like a broad-spectrum communications monitor.

If you want to know who's broadcasting anywhere in the range from 1MHz to 10GHz (example only -- I don't know the real range for this device), that's a bandwidth of 9.999 GHz.

You could scan freqencies sequentially, but it's slow and you might miss something. You can't afford to build a 20 GHz A-to-D converter, and even if you could, you don't want to build a computer big enough to process the resulting 80 GB/s data stream (assuming a 40 GHz sample rate with 16-bit samples).

The compressive sampling process is what allows you to sample at a lower rate (as long as you can assume that the signal you're looking for doesn't use too much of the total bandwidth). The convex optimization is apparently used to decide how to do the sampling in a way that's guaranteed to recover your signal.

The convex optimization is used to reconstruct the original signal.

The underlying compressive sensing theory says that if you do a measurement of a sparse signal, then convex optimization should allow you to recover that signal with high to overwhelming probability. The reason compressive sensing is interesting is that: - the process of taking measurement is linear (no iteration a la JPEG), thereby allowing one to foresee very low powered sensors. - the number of measurements is expected to be much smaller than what the Nyquist-Shannon theorem says (Nyquist is just a sufficient condition, not a necessary one), thereby realizing a de-facto compression of the signal with no a priori on the shape of that signal (except the knowledge that it is sparse) - the measurements are automatically encrypted.

In the case of the broad-spectrum communications monitor, the message is known to be sparsely located all over the frequencies.

Igor.

Thanks for the clarification, Igor -- my knowledge of this is second-hand, from a friend's description of an interesting project he's working on. I had never heard of compressive sampling or convex optimization before that, and it was eye-opening to see what's possible.

Minor nit: you usually can't prove it will always find the narrowband signal. All you can prove is that it will do so with high probability.

Do any folks on HN have any interesting optimization stories or unusual application domains?

Using Mixed-Integer Quadratic Optimization to process real-time GPS data. Perhaps the coolest project I ever worked on. More info: http://www.stanford.edu/~boyd/papers/int_est.html

I did a MIQP package for the DeBeers Trading Company to help them decide who to sell to. A very odd project in many ways!

Could you elaborate on the modeling that needs that machinery?

I don't think it's of general interest, but I can drop you an email with a precis if you like.

sure, that'd be dandy

One more thing, Stephen Boyd's class on convex optimization (he is one of the co-author of the book) can be found on Youtube:

http://www.youtube.com/results?search_type=&search_query...

a person has pit all the videos in notes and put the said notes on a blog:

http://minhva.blogspot.com/2009/02/convexoptimizationii-lect...

so you can watch the video and read the text of the video at the same time.

Igor.

Could someone give a very simple example of a problem to solve with this?

As it turns out, convex optimization is being seen by a few folks as the new least square. As wwalker mentioned, convex optimization is currently being used in solving for measurements taken with hardware implementing compressive sensing (or compressed sensing or compressive sampling). The A/D converter is just one of the application of compressive sensing. One of the most well known example is that of the single pixel camera at rice but there are many others. I have listed most of the known hardware implementing compressive sensing here:

http://igorcarron.googlepages.com/compressedsensinghardware

One should note that while convex optimization has given some real impetus to the field (by providing theoretical bounds), signal reconstruction is also using speedier techniques nowadays even though linear programming techniques remains some sort of gold standard. For those of you interested in the subject, I write a small blog on the subject of CS:

http://nuit-blanche.blogspot.com/search/label/CS

and have written a page trying to summarize our current understanding in this page(it is a bit technical):

http://igorcarron.googlepages.com/cs

Cheers,

Igor.

convex optimization covers a lot of different problem types. in general, you are trying to minimize (or maximize) some function (the objective function) over a set of variables subject to a set of constraints on those variables. 'convex optimization' deals specifically with optimization problems where the objective function is... convex. this essentially means you can efficiently find the global minimum (or maximum if the function is concave)

ok, so a simple example: lets say you're on a hacker's budget and you want to maximize your caloric intake given your limited funds. This is your objective function. BUT, if you're like me, you can't live on ramen and mountain dew... i have a basic set of nutritional requirements. These are your constraints. For example, sodium has to be less than A and protein greater than B and so on and so forth. So you are essentially optimizing over ALL possible diets.

My guess is you'd end getting back: kale, potatoes and beans. Now that's a real hacker's diet!

At my day job, we use linear programming to calculate virtual capacities on airplanes, i.e. overbooking. There's a few other optimization techniques involved, such as dynamic progamming, but if you've ever been asked to take a different plane, chances are an LP was involved.

Reply on news.ycombinator.com