forum.alglib.net

Dear all,

Within my minimization problem (MINBLEIC) I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1

Since the minimization problem includes quite a lot of variables (~100) it is not feasible to implement a linear constraint for each potential +/- combination. Currently, I am using the MINBLEIC Function. Hence, I think it is also not possible to use additional 0/1 indicator variables (i) and to estimate sth. like (2*i-1)*A.

Every help is very much appreciated!
Hugo

Such constraints are impossible with BLEIC algo. It can handle only convex feasible set (intersection of several hyperplanes or half-hyperspaces), and your feasible set given by |A|+|B|+...=1 is clearly non-convex (it has large "hole" around A=B=...=0).

Hi Sergey,

Thanks a lot for the fast response and much more for your engagement for ALGLIB!

Do you have any idea on how to implement an optimization procedure with ALGLIB that allows for such kind of constraint?

Thanks and regards!

I have one idea, but a) it may be too slow, b) it is not proved to work.

1. You may start optimizing with all variables having non-negative values, which corresponds to A+B+C+...=1, A>=0, B>=0, C>=0, ...
2. After optimization is over, you may notice that some variables have zero values. It may mean that optimal values of these variables are negative. In this case you "flip sign" of one or several such variables (distinction between one and several may be important for algorithm convergence), and now you have -A+B+C+...=1, A<=0, B>=0, C>=0, ...
3. You perform optimization again, and again, and again until convergence

Open questions:
1. I do not know whether such algorithm is guaranteed to converge
2. I can not easily come up with good convergence conditions
3. You may have problems with convergence criteria when some of the variables are exactly zero at the solution (you may infinitely cycle between a>=0 and a<=0)
4. it may be good idea to perform subsequent optimization with relaxed stopping criteria (say, limited number of steps) to detect candidates for deactivation ASAP.

5. It is not clear whether you should "flip" one variable at time, or several. In case you decide to "flip" one, it is better to flip one with largest value of corresponding component of gradient.

OK, I will try this... thanks a lot for your input!!!

BTW, can you post your findings here? it would be interesting to hear anything about algorithm behavior :)