| forum.alglib.net http://forum.alglib.net/ |
|
| Optimize: linear constraints including several absolute val. http://forum.alglib.net/viewtopic.php?f=2&t=737 |
Page 1 of 1 |
| Author: | Hugo81 [ Mon Nov 26, 2012 2:48 pm ] |
| Post subject: | Optimize: linear constraints including several absolute val. |
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 |
|
| Author: | Sergey.Bochkanov [ Tue Nov 27, 2012 10:35 am ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
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). |
|
| Author: | Hugo81 [ Tue Nov 27, 2012 11:37 am ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
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! |
|
| Author: | Sergey.Bochkanov [ Tue Nov 27, 2012 1:06 pm ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
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. |
|
| Author: | Sergey.Bochkanov [ Tue Nov 27, 2012 1:07 pm ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
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. |
|
| Author: | Hugo81 [ Tue Nov 27, 2012 2:04 pm ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
OK, I will try this... thanks a lot for your input!!! |
|
| Author: | Sergey.Bochkanov [ Tue Nov 27, 2012 5:45 pm ] |
| Post subject: | Re: Optimize: linear constraints including several absolute |
BTW, can you post your findings here? it would be interesting to hear anything about algorithm behavior :) |
|
| Page 1 of 1 | All times are UTC |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|