Prev: Generating a parity check matrix in ldpc
Next: How to i get the wavelet coefficients of an image?
From: Matt J on 25 Jan 2010 11:14
"John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hjke6o$4qq$1(a)fred.mathworks.com>...
> "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hjkc2m$d1l$1(a)fred.mathworks.com>...
> > "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hjjhdi$t0d$1(a)fred.mathworks.com>...
> >
> > > > Perhaps the nonlinear constraint
> > > >
> > > > ( x^2 - 5.5^2 ) ^2 <= 7^2 - 4^2
> > >
> > > Bad idea, the domains are composed by two disconnected sets. Depending where the starting point is located, FMINCON will find the (local) minimum is the associated domain. Re-parametrize does not solve the composite nature of the problem.
> > >
> > > The only way is to optimize twice, one on each domain then compare the results.
> >
> > I see what you mean. Still, I wonder if it's not worthwhile if only because it expresses two bound constraints as 1 and therefore reduces the number of Lagrange multipliers that fmincon has to deal with. Then again, if that were true, I guess no one would ever use bound constraints...
>
> As Bruno says, this is a POOR solution.
>
> Suppose that fmincon starts in one of these
> disjoint sets? It can essentially never escape
> to the other piece if that is necessary.
>
> Merely because this "reduces" the complexity
> of the problem by having fewer constraints is
> not a useful gain here.
>
> Solve the problem as two disjoint problems,
> then take the better solution of the two.
===========

The two approaches aren't mutually exclusive. You can parametrize the bounds as I proposed, reducing the complexity of the constraints, but still run fmincon twice, solving the problem as 2 disjoint ones.

I think the main concern would be whether parametrizing the constraints quadratically can get you into a situation where the minima don't satisfy constraint qualifications.
You can see this in simple examples of quadratic equality constraints. For example, if you minimize f(x)=x1^2+x2^2 subject to the constraints
(x1+x2-1)=0
then you can solve the problem using Lagrange multipliers. If you formulate the constraints equivalently as
(x1+x2-1)^2=0,
there is no Lagrange multiplier solution.

Not sure if the same problem arises for inequality constraints, though...
From: Matt J on 25 Jan 2010 15:23
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hjjhdi$t0d$1(a)fred.mathworks.com>...

>
> Bad idea, the domains are composed by two disconnected sets. Depending where the starting point is located, FMINCON will find the (local) minimum is the associated domain. Re-parametrize does not solve the composite nature of the problem.
>
> The only way is to optimize twice, one on each domain then compare the results.
=================


Come to think of it, this really doesn't seem to be true. Just because the two domains are disjoint doesn't mean either one is a capture basin for points initialized inside it. At minimum, this seems quite algorithm dependent.

Take as an example, a quadratic objective function with constraints consisting of 2 disjoint sets and with one of the sets containing the unconstrained minimum (hence it will be the constrained global minimum as well). A Newton-like method would certainly cause the algorithm to jump from one disjoint domain to another, if necessary, because the Newton direction vector contains the correct distance information.
From: John D'Errico on 25 Jan 2010 15:35
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hjkg0d$40u$1(a)fred.mathworks.com>...

> The two approaches aren't mutually exclusive. You can parametrize the bounds as I proposed, reducing the complexity of the constraints, but still run fmincon twice, solving the problem as 2 disjoint ones.
>

So you would prefer to replace a simple bound
constrained problem, with a nonlinearly bounded
problem?

This is silly in the extreme.

John
From: Matt J on 25 Jan 2010 15:56
"John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hjkv9p$a37$1(a)fred.mathworks.com>...
> "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hjkg0d$40u$1(a)fred.mathworks.com>...
>
> > The two approaches aren't mutually exclusive. You can parametrize the bounds as I proposed, reducing the complexity of the constraints, but still run fmincon twice, solving the problem as 2 disjoint ones.
> >
>
> So you would prefer to replace a simple bound
> constrained problem, with a nonlinearly bounded
> problem?
>

I wouldn't advocate anything I haven't had the chance to try myself first, but I also wouldn't rule it out before someone gives me a proper explanation as to why it wouldn't work.

If successful, it would mean running fmincon once instead of twice. Also, it would consolidate every pair of upper and lower bound constraints into a single constraint, for half the total number of constraints. I don't know if any of the algorithms used by fmincon are primal-dual algorithms, but if they are, it means fewer Langrange multipliers, and hence fewer variables to iterate over.
From: John D'Errico on 25 Jan 2010 16:30
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hjl0h6$smu$1(a)fred.mathworks.com>...
> "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message <hjkv9p$a37$1(a)fred.mathworks.com>...
> > "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hjkg0d$40u$1(a)fred.mathworks.com>...
> >
> > > The two approaches aren't mutually exclusive. You can parametrize the bounds as I proposed, reducing the complexity of the constraints, but still run fmincon twice, solving the problem as 2 disjoint ones.
> > >
> >
> > So you would prefer to replace a simple bound
> > constrained problem, with a nonlinearly bounded
> > problem?
> >
>
> I wouldn't advocate anything I haven't had the chance to try myself first, but I also wouldn't rule it out before someone gives me a proper explanation as to why it wouldn't work.
>
> If successful, it would mean running fmincon once instead of twice. Also, it would consolidate every pair of upper and lower bound constraints into a single constraint, for half the total number of constraints. I don't know if any of the algorithms used by fmincon are primal-dual algorithms, but if they are, it means fewer Langrange multipliers, and hence fewer variables to iterate over.

No. It would not mean running fmincon once. It
would force fmincon to form constraint derivatives
when nothing of the sort is necessary, turning a
set of simple bound constraints into the black box
of nonlinear constraints.

As was said before, fmincon cannot jump between
discontinuous pieces of a domain, so you would
still need to run fmincon multiple times.

John
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Generating a parity check matrix in ldpc
Next: How to i get the wavelet coefficients of an image?