[SciPy-user] constrained optimization
dmitrey
dmitrey.kroshko@scipy....
Tue Apr 29 03:04:48 CDT 2008
Robert Kern wrote:
> On Mon, Apr 28, 2008 at 3:03 PM, Ondrej Certik <ondrej@certik.cz> wrote:
>
>> On Mon, Apr 28, 2008 at 8:57 PM, Robert Kern <robert.kern@gmail.com> wrote:
>> > On Mon, Apr 28, 2008 at 1:34 PM, John Hunter <jdh2358@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]
>>
>
> Yes, that is by design. With compositional data, only the ratios
> between components matter. They are unique only up to a scaling
> factor, and typically, you normalize them such that they sum to 1.
>
>
I guess the real problems for using this and/or almost any other
coordinate transformation could be possible yielding ill-condition
problem (or increasing ill-condition, if former problem is already
ill-conditioned), for example when coord x[-1] is close to zero either
in optimal point or during moving along trajectory. This makes
optimization solvers to work unstable, unpredictable and maybe stop far
from optimum.
Regards, D.
More information about the SciPy-user
mailing list