Prev: Extracting a surface in a binary volume
Next: hough
From: Mostafa on 7 May 2010 20:02

Hello,

I have a non-linear optimization problem as the following:

Find x1, x2, x3,.......xK that maximize the function f(x1, x2, x3,.......xK)
where K is unknown, subject to the constraint x1+x2+x3+........xK =1 (actually they represent probabilities), and other constraints.
I also have the information that:
Increasing K will increase f till reaching a certain value Kmax, after which any increase in K will not affect f.
In other words, if Kmax = 5, then if we try to solve with K = 6, we get x6 = 0.

Actually what I did is straight forward:
Start with K = 2, and find x1, x2 that maximize f.
then K = 3, then 4, then 5 till certain the value of K = Kmax, then f does not increase anymore.

My question:

Is it possible to make the number of variables K as one of my optimization variables, and solve the problem as a MIP problem?
That means at the beginning I do not know exactly the number of variables, which will be (K+1), where K itself is unknown.

Thanks
From: Bruno Luong on 8 May 2010 03:18
"Mostafa " <aymanmmmm(a)yahoo.com> wrote in message <hs29lu$e0p$1(a)fred.mathworks.com>...
>
> Hello,
>
> I have a non-linear optimization problem as the following:
>
> Find x1, x2, x3,.......xK that maximize the function f(x1, x2, x3,.......xK)
> where K is unknown, subject to the constraint x1+x2+x3+........xK =1 (actually they represent probabilities), and other constraints.
> I also have the information that:
> Increasing K will increase f till reaching a certain value Kmax, after which any increase in K will not affect f.
> In other words, if Kmax = 5, then if we try to solve with K = 6, we get x6 = 0.
>
> Actually what I did is straight forward:
> Start with K = 2, and find x1, x2 that maximize f.
> then K = 3, then 4, then 5 till certain the value of K = Kmax, then f does not increase anymore.
>
> My question:
>
> Is it possible to make the number of variables K as one of my optimization variables, and solve the problem as a MIP problem?
> That means at the beginning I do not know exactly the number of variables, which will be (K+1), where K itself is unknown.

You seem to over complicate the problem. The "space" the full vector
x1, x2, ..., xkmax
it can also embed all "shorter" vectors, because any of xi can be zero.

Just optimize your problem with kmax length vector, no need to loop on K. If you have preference of obtaining solution having small number of non-zero elements, you can add the total variation constraint, i.e., maximize

f(x1, ..., xkmax)

such that sum |x_(j+1)-x_j| <= TV

The sum is carried over j, and x is sorted. TV is a constant "well" selected.

Bruno
 | 
Pages: 1
Prev: Extracting a surface in a binary volume
Next: hough