6 ms·

Nice book on convex optimization techniques

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

carterschonwald 18y ago
Do any folks on HN have any interesting optimization stories or unusual application domains?
- Rod 18y ago
  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 http://www.stanford.edu/~boyd/papers/int_est.html
- dcminter 18y ago
  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!
  - carterschonwald 18y ago
    Could you elaborate on the modeling that needs that machinery?
    - dcminter 18y ago
      I don't think it's of general interest, but I can drop you an email with a precis if you like.
      - carterschonwald 18y ago
        sure, that'd be dandy
Rod 18y ago
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-39d1-4fdb-90e8-364129597c87 http://see.stanford.edu/SEE/courseinfo.aspx?coll=2db7ced4-39... http://see.stanford.edu/SEE/courseinfo.aspx?coll=523bbab2-dcc1-4b5a-b78f-4c9dc8c7cf7a 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://abel.ee.ucla.edu/cvxopt http://cvxmod.net http://cvxmod.net
- pz 18y ago
  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.
  - Rod 18y ago
    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.
  - maximilian 18y ago
    It seems to be available for free online as well: http://www.inference.phy.cam.ac.uk/mackay/itila/book.html http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
wwalker3 18y ago
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 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.
- carterschonwald 18y ago
  I take it that this is referring to a (listening) bug detector?
  - wwalker3 18y ago
    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.
    - IgorCarron 18y ago
      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.
globalrev 18y ago
Could someone give a very simple example of a problem to solve with this?
- IgorCarron 18y ago
  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 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 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 http://igorcarron.googlepages.com/cs Cheers, Igor.
- pz 18y ago
  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!
IgorCarron 18y ago
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=stephen+boyd+optimiization&aq=f 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-lecture01.html 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.

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

carterschonwald 18y ago

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

Rod 18y ago
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 http://www.stanford.edu/~boyd/papers/int_est.html
dcminter 18y ago
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!
- carterschonwald 18y ago
  Could you elaborate on the modeling that needs that machinery?
  - dcminter 18y ago
    I don't think it's of general interest, but I can drop you an email with a precis if you like.
    - carterschonwald 18y ago
      sure, that'd be dandy

Rod 18y ago

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-39d1-4fdb-90e8-364129597c87 http://see.stanford.edu/SEE/courseinfo.aspx?coll=2db7ced4-39... http://see.stanford.edu/SEE/courseinfo.aspx?coll=523bbab2-dcc1-4b5a-b78f-4c9dc8c7cf7a 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://abel.ee.ucla.edu/cvxopt http://cvxmod.net http://cvxmod.net

pz 18y ago
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.
- Rod 18y ago
  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.
- maximilian 18y ago
  It seems to be available for free online as well: http://www.inference.phy.cam.ac.uk/mackay/itila/book.html http://www.inference.phy.cam.ac.uk/mackay/itila/book.html

wwalker3 18y ago

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 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.

carterschonwald 18y ago
I take it that this is referring to a (listening) bug detector?
- wwalker3 18y ago
  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.
  - IgorCarron 18y ago
    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.

globalrev 18y ago

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

IgorCarron 18y ago
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 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 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 http://igorcarron.googlepages.com/cs Cheers, Igor.
pz 18y ago
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!

IgorCarron 18y ago

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=stephen+boyd+optimiization&aq=f 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-lecture01.html 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.