[SciPy-user] constrained optimization

[Ondrej Certik]

On Mon, Apr 28, 2008 at 8:57 PM, Robert Kern <robert.kern at gmail.com> wrote:
> On Mon, Apr 28, 2008 at 1:34 PM, John Hunter <jdh2358 at gmail.com> wrote:
>  > I need to do a N dimensional constrained optimization over a weight w
>  >  vector with the constraints:
>  >
>  >   * w[i] >=0
>  >
>  >   * w.sum() == 1.0
>  >
>  >  Scanning through the scipy.optimize docs, I see a number of examples
>  >  where parameters can be bounded by a bracketing interval, but none
>  >  where constraints can be placed on combinations of the parameters, eg
>  >  the sum of them.  One approach I am considering is doing a bracketed
>  >  [0,1] constrained optimization over N-1 weights (assigning the last
>  >  weight to be 1-sum others) and modifying my cost function to punish
>  >  the optimizer when the N-1 input weights sum  to more than one.
>  >
>  >  Is there a better approach?
>
>  Transform the coordinates to an unconstrained N-1-dimensional space.
>  One such transformation is the Aitchison (or "additive log-ratio")
>  transform:
>
>   y = log(x[:-1] / x[-1])
>
>  And to go back:
>
>   tmp = hstack([exp(y), 1.0])
>   x = tmp / tmp.sum()
>
>  Searching for "compositional data analysis" should yield similar
>  transformations, but this one should be sufficient for maintaining
>  constraints. For doing statistics, the other have better properties.

Wow, that is very clever. Just today I was thinking how to do it and
it didn't occur to me I should read scipy-user. :)

The exp/log transform is clear, but I didn't figure out that in order
to maintain
the norm, I can maintain it in the last element, so it's enough to do:

y = x[:-1]/x[-1]

tmp = hstack([y, 1.0])
x = tmp / tmp.sum()

Very cool, thanks. However, the transform is not one to one, e.g. both

x = [1, 2, 1, 4]
x = [2, 4, 2, 8]

represent the same thing:

y = [0.25, 0.5, 0.25]

and


Ondrej