Signomial Programming!

[pgkirsch]

...as per discussion with @whoburg and @cjk12.

It's as though Santa Claus, the easter bunny, and the tooth fairy jointly raised a child and called it signomial programming and then, when it was mature enough to be a competent member of society, dropped it off at the MIT Convex Optimization Group's front door.

[whoburg]

Ha, great ticket.

Here's a specific idea to get started: how hard/nice/elegant/impractical/etc would it be to create the Signomial class, and have Posynomial inherit from it?

[whoburg]

Background reading:

section 9.1 of this paper: http://stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf

slides 25 and 26 of this lecture: http://stanford.edu/class/ee364b/lectures/seq_slides.pdf

[pgkirsch]

I think this might make @bqpd cry given that posynomial is such a fundamental building block of the code at the moment...but surely Posynomial should inherit from Signomial not the other way around. This would be consistent with the current hierarchy between Posynomial and Monomial (the latter inherits from the former).

[bqpd]

Hehe. Wellll, there's no reason not to just implement Signomial as a Posynomial with some cs less than 0, right? There's actually already an "allow_negative" flag in Posynomial that does this.

[bqpd]

(or vice versa, make Posynomial be a Signomial with "positive_only=True".

[bqpd]

(note mostly to self) Hmm, let's make the monomial approximation m of posynomial 1+p(x) at x_k:

d ln(1+p(x))/d ln(x_i) = d p(x)/dx_i  * x_i * 1/(1+p) at x_k
=> m = (prod x_i^(x_i * d p(x)/dx_i at x_k))^(1/1+p(x_k))

We could also accept arbitrary nonconvex functions, as long as they gave us their local monomial.

Could we get trust regions automatically for posynomials in a nice way? Perhaps by thresholding the ratio of their derivatives?

[bqpd]

We can threshold x such that (1+p)/m >= c1 \forall x in X. Conservatively this would just involve holding each value constant and solving for the root (polynomial root-finding n times, where n is the length of x; use newton and take advantage of a posynomial diff function).

Since dp/dm is also a posynomial, we can easily do the same for dp/dm >= c2. This gives us two thresholds to set per constraint; experimentation will be needed to determine reasonable defaults. So far it seems that a threshold of c1 = 1 (which is conservative) and c2 = 1.5 are reasonable starting points.

[bqpd]

@whoburg: what's the priority of this? Definitely possible to implement, but it's not convex...

[codykarcher]

@bqpd I have a large number of uses for this. I don't want to set priorities, but I'd vote for this very enthusiastically to happen soonish.

[bqpd]

@cjk12: I'm worried about it being kinda obnoxious to use, since: you won't be guaranteed a global optimum, and you'll have to set some threshold values for each signomial constraint, which values might drastically change the solution or runtime. It definitely seems like it's edging towards MDO...

[raddy]

Would the plan be for automatically detecting the log-convex regions? And then return a nice sweep with each of the regions at their optimum? (Which is perhaps not really that useful...)

[whoburg]

I'm willing to be shown I'm wrong, but I just sketched out an easy way to convert any signomial programming problem directly to a 'difference-of-convex' programming problem. This implies that we do not need any trust regions, and the process will still converge. (The result would still only be locally optimal though, unlike the globally optimal answers for a GP).

@bqpd - we should talk about this -- I can write up a short document showing how it would work -- it's slightly different than the formulation given in the gptutorial paper.

[whoburg]

@raddy - re: automatically detecting log-convex regions, this ticket isn't quite directed at exactly that, but wanted to point you to a working paper we have on automatically fitting GP models to log-convex data: http://web.mit.edu/~whoburg/www/papers/gp_fitting.pdf. It might be of interest.

We're also developing a separate software package to go along with the fitting paper -- still under active development, to be released later this spring: https://github.com/convexopt/gpfit

[whoburg]

@bqpd, I prefer the option for Posynomial to inherit from Signomial (and just set positive_only=True). Makes more mathematical sense than inheriting the other way around.

[whoburg]

Making a simple use case here: https://github.com/convexopt/gpkit/issues/176

[bqpd]

@whoburg: Posynomial now inherits from Signomial.

[bqpd]

Latest commit implements Signomial solving; please break it!

[bqpd]

The only thing we discussed that's not implemented is allowing the zeroing of particular monomial terms for the solver's starting position.

[bqpd]

Closing this issue; open new issues for specific bugs?