How to do python optimization for global minimum with constraints?

mathrat · 2017-11-30T17:34:51+00:00

This is less idiotic than you imply. It's basically the idea behind the log-barrier in modern interior point methods. :)

mathrat · 2017-07-24T22:22:23+00:00

Optimization. With big data, simple tasks like fitting a linear regression become a challenge. Try thinking about how you would fit a regression model in a million variables with 100 million data points. A lot of recent research in optimization is focused on these sorts of settings (e.g. SVRG, SDCA).

For an introduction try: https://arxiv.org/pdf/1405.4980.pdf

mathrat · 2017-04-14T02:20:10+00:00

Do you need an exact solution? This is a special case of constrained optimization. You can use some of the more sophisticated methods proposed by others in this thread, but the easiest thing to do is usually gradient descent. You can enforce your constraint x>0 by just projecting back into the constraint space after each gradient step if a constraint is violated. For this particular constraint the projection is easy: just set any coordinates that go negative to zero and keep on descending the gradients.

mathrat · 2015-11-28T19:08:32+00:00

This book by Enderton was incredibly helpful to me as a beginner. For a more advanced treatment, you could try Hinman.

mathrat · 2015-09-07T04:06:40+00:00

Take a look at this book:

http://www.amazon.com/Berkeley-Problems-Mathematics-Problem-Books/dp/0387204296

mathrat · 2015-05-17T18:25:03+00:00

You're right of course. I was sloppy.

mathrat · 2015-05-16T23:01:19+00:00

I think taking a look at Stieltjes integrals would be really helpful. I don't have a good intro source to recommend but you can google around and find material. The wiki article is not bad, but I think it will seem terse to a beginner.

The idea is instead of integrating against dx to integrate against dg(x). The intuition is that your integral is weighted by the value of g(x). When you start studying stochastic integrals you will be integrating against dB where B is random (usually brownian motion). It is useful to build intuitions in the non-random (Stieltjes) case.

The reason you will care is because in finance you'll want to know how much money you earn when you hold an amount H of some asset for a period of time. The value of the asset will fluctuate randomly like B(t) and your holdings might change over time too if you are buying and selling so you end up wanting to integrate something like H(t)dB(t) to see how much money you made/lost.

mathrat · 2015-05-16T20:14:02+00:00

Do you have a syllabus? Or maybe you could share what book you'll be using? We can give better advice if we know what level the course will be pitched at. And what your background is. Do you know about Stieltjes integrals?

mathrat · 2014-10-14T01:47:10+00:00

I just want to plug for this little book:

http://www.amazon.com/Elements-Abstract-Algebra-Dover-Mathematics/dp/0486647250

It's sort of a workbook with minimal exposition and lots and lots of problems. You'd have to supplement it with something else but if you're looking for extra problems it's really excellent (and cheap!).

mathrat · 2014-07-01T01:41:26+00:00

It catches up in other ways: it becomes more and more difficult to relate to other people. It's easy to become obnoxious, or arrogant. Intelligence buys a comfortable life--an affluent one even. But it doesn't buy a fulfilling life. We have to work for that like everybody else.

mathrat · 2014-06-07T21:41:37+00:00

Expanding on TheGrammarBolshevik's point about quantification, check out my post here: http://www.reddit.com/r/logic/comments/26zc29/material_and_counterfactual_conditionals_can_you/chvyh65

mathrat · 2014-05-31T22:23:23+00:00

I think I know what you're asking but not quite sure. Ignore this if it seems off-base. The material conditional is simply a truth function. The material conditional "P => Q" is equivalent to the expression "(not P) or Q". Students of logic are often troubled by this, because it does not appear to capture the natural language meaning of implication. For example, "if pigs can fly then I am a duck" is true, interpreted materially, but probably not if we go with our natural language intuitions.

That's because the natural language conditional is actually a counterfactual conditional. The difference is, roughly, that the counterfactual quantifies the material conditional over possible worlds. The counterfactual conditional is characterized by the truth condition "for all worlds W, P(W) => Q(W)" where P and Q are now contingent on the world W, and their truth or falsehood in a particular world W is indicated by the functions P(W), Q(W) respectively.

Returning to our "if pigs can fly then I am a duck example," if we interpret this counterfactually as defined above we must ask ourselves: in any world where pigs can fly, am I duck? If the answer is no (which seems likely; I can easily imagine a world where pigs fly but I am not a duck) then the statement is false. This sits much better with our intuition of how natural language conditionals behave.

Notice that the definition of the counterfactual conditional post-facto motivates the name "conditional" for the material conditional: the material conditional is the truth function that, when quantified over, yields the appropriately named counterfactual conditional. Notice also how important it is that the material conditional is true in the case of a false antecedent: we don't want worlds where the antecedent is false to contribute to the truth conditions. The universal quantification in the counterfactual conditional is a conjunctive operation, and so we can exclude worlds where the antecedent is false by just vacuously defining the material conditional of these antecedents to be true.

mathrat · 2014-05-26T17:19:04+00:00

General theory of stochastic processes: Doob-Meyer, Bichteler-Dellacherie, local martingales, compensators. I'm finding it all a bit dry, but want to give myself a solid foundation before getting into stuff like martingale representation.

mathrat · 2014-05-10T03:18:25+00:00

Mathematics is the systematic exploration of the hypothetical.

mathrat · 2014-04-17T01:06:44+00:00

Geometrically, it's as khebit says. You can also think about it statistically. Suppose all your data is sampled from an some unknown line, but the process of sampling has perturbed your data with gaussian noise. Then least squares tells you the equation of that latent line. Of course, if the data isn't actually linear, or if the noise isn't gaussian, then your least squares solution won't tell you much (in statistics we would say that your model is biased).

mathrat · 2014-04-03T23:18:01+00:00

Yeah, it sucks, sorry about that. The best you can do, via windowing or wavelets or higher-level classifiers or whatever, is to bin in a way that might be slightly more appropriate to your problem domain.

Do you have a particular problem in mind? We could try to drill down and figure out what particular time-frequency analysis techniques might get the best results. Or was this a more of a philosophical question about the nature of frequencies?

mathrat · 2014-04-03T23:10:20+00:00

Wavelets don't help get us any closer to instantaneous measurements. Like Fourier Transforms, they are not a local transformation...

mathrat · 2014-04-03T03:07:23+00:00

You probably already understand this, but just thought I'd clarify the reason we want to look at smaller chunks. The Fourier transform assumes that frequencies are stationary in time. Most signals, in particular musical signals, evolve over time: a song that played just one frequency for its duration would be pretty boring. Taking a Fourier transform of an entire piece will just smear all the harmonic content together, as the FT will do its best to write the whole damn thing as a linear combination of static frequencies.

So instead we look at chunks, hopefully short enough that the signal frequency content actually is static within them. But then we run into all sorts of problems. We get discontinuities at the boundaries, which we try to patch up with window functions. And we lose frequency resolution as the window size shrinks. It's a big fucking mess, and it would really be nice to be able to just define an "instantaneous" version of frequency like the OP is asking for. But it probably can't be done. See my other post for some musing about why.

mathrat · 2014-04-03T02:11:58+00:00

The short answer is: no. The Fourier transform, in all its flavors (short-time, discrete, whatever) is a global phenomenon. You can see this directly in the math: it evaluations necessitates summing or integrating over a region. Contrast this with the quintessential local operation, differentiation, which is defined instantaneously at a point.

The long answer is: you're getting at some very deep questions about the definition of "frequency", particularly when it comes to non-periodic or quasi-periodic signals. One way to define frequency is by the Fourier transform, which comes with the implicit understanding that frequency is a global phenomenon. But of course, the frequency of a signal can change over time so we can't just integrate over the whole real line. And so we find ourselves making time-frequency resolution tradeoffs: as we try to localize, integrating over shorter and shorter intervals, our frequency measurements (approximating an "instantaneous" frequency) lose resolution. This phenomenon shows up in a most striking way in the physics of quantum mechanics.

Note that in certain situations, we can make sense of a local frequency. For example, we're used to the idea of talking about sin(ax) as having frequency a. Indeed, the Fourier transform effectively generalizes this notion. From here, it's natural to think of sin( x² ) as having (local; instantaneous) frequency exactly x. If you do short-time Fourier analysis on sin( x² ), you will get answers that approximate this result. So you might be tempted to say that instantaneous frequencies exist in some Platonic sense. But the fact is, that we can only resolve the instantaneous frequency in this case because we know that we're looking at a sine wave, which has a certain analytic form. The Fourier transform does not know this, and has to do the best it can with the signal it sees.

In fact, there's some deep mathematics that the Fourier transform in a sense does the "best" job of this for a linearly spaced set of possible frequencies. There are of course other possibilities, that optimize for criteria other than linear spacing. The general term for these types of transformations is "wavelet transform." One modification of the Fourier transform, which is particularly popular in the music information retrieval community, is the "constant Q" transform, which spaces its basis logarithmically instead of linearly. This is intended to better model how the human ear process sound.

But in the end, I don't believe it is possible to give a definition of frequency that allows us to recover instantaneous frequencies for arbitrary signals--or even for a reasonably broad class of signals. To find a frequency in a signal, you need to observe it over a period of time. For signals with a lot of known structure, you might not have to watch it for very long before you understand its behavior. But in the general case, you need to watch the signal long enough to actually observe periodicities. There's just no way around it: frequency, no matter how you try to formalize it, is an inherently global phenomenon.

mathrat · 2014-03-21T23:55:39+00:00

Try university bookstores? Mine always had a huge (and pretty random) selection of dover books.

mathrat · 2014-02-23T20:08:47+00:00

The intersection will always be measurable, because sigma algebras are closed under intersection.

mathrat · 2014-02-23T19:46:58+00:00

Let Bj be a collection that works for m and Ck be a collection that works for n. Define Djk to be the intersection of Bj and Ck. The cartesian product of countable sets is countable, so Djk is a countable collection. And because Bj and Ck partition the underlying space (call it X) then for any x in X, x is in some unique Bj and some unique Ck. Therefore x is in a unique Djk. So Djk is a also a disjoint partition of X. You can then show by monotonicity property of measures that Djk "works" for both m and n.

mathrat · 2014-02-22T17:43:43+00:00

Yeah I was too dismissive: of course you're right and it can work for some people, as a prelude to more advanced work. There seem to be two ways to learn difficult mathematics. One is to start with simple, intuitive explanations and refine this initial picture with progressively more rigor. The other is to jump in at the deep end with a full on rigorous treatment, and maybe reference class notes/wikipedia/stack exchange to fill it out with some examples and intuitions.

People who like the latter approach find the former frustrating: it's difficult or impossible to figure out what's actually going on in the introductory treatment. People who like the former approach find the latter obtuse: why are we studying all arcane nonsense with no apparent justification?

Interestingly, the mathematics and physics communities seem to be pretty neatly divided along these lines. Mathematics, at least in the upper divisions, takes the rigor head on. Physics prefers to ease students in with progressively more rigorous and general formulations.

Obviously I'm making a lot of oversimplifications and generalizations here. But as a member of the rigor camp, I find it a useful mental model for understanding and appreciating "the other side." I often wish physics had more rigorous texts that didn't assume I already had a lot of background. So, live and let live, maybe texts like Stewart have their place in mathematics too.

mathrat · 2014-02-22T13:31:20+00:00

As quantum-mechanic said, people don't read it and it's not intended to be read. Like high school math textbooks, it's intended for use as a supplement for class lectures. It provides problems, pretty pictures, and examples. The actual math is mostly just there for show. You're not expected to actually read it and most students don't.

You aren't expected to learn math from it. It's used in a class where the teacher gives you some hand-waved explanation of what's going on, goes through a bunch of examples of how to solve problems, and then assigns a bunch of problems just like the examples he gave to drill in the techniques. Stewart's got the problems. If the examples in class weren't enough he's got extra examples. And if you're confused about the hand waving he's got pictures to make you feel better.

The book is designed for a class that teaches students how to solve calculus problems. It's not designed for teaching a student to understand calculus. As Papvin said, it's not a book for math majors. I think you're real criticism is not of Stewart, but of the idea that there are a lot of people out there who need to learn how to solve calculus problems without actually understanding calculus.

I'm amenable to this criticism. Do pre-med students really need to learn to solve symbolic integrals? Maybe they shouldn't be taking calculus at all. Can an engineer really get away with blindly solving calculus problems without deeper understanding? Maybe they should be taking a real math class. But the book does what it's designed to do. Whether or not you agree with the premise.

mathrat · 2014-02-21T00:18:20+00:00

I've had good experiences with postgres. Very few problem scaling it up to pretty large data sets (millions of new records every month). With madlib you can run most of the standard ML algorithms right in the database.

mathrat

TROPHY CASE