Timeline for How to solve simple bilinear equations under extra linear constraints
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 27, 2011 at 5:34 | comment | added | Woland | Oh, and by extra linear constraints I mean additional constraints of the form $c_i(x) \geq 0$, $d_i(y) \geq 0$, $e_i(x) = 0$, $f_i(y) = 0$, where $c,d,e,f$ are linear. These are in addition to the bilinear constraints $y^T x = 0$. | |
| Dec 27, 2011 at 5:30 | comment | added | Woland | Thanks Gilead. Unfortunately I can't just assume that $u_{ij} \geq 0$. There is a way to reformulate this problem so that $u_{ij} \geq 0$, but then the bilinear constraints would become $u_{ij}^T \lambda_i = \alpha_{ij}$ for some $\alpha_{ij} \geq 0$, and this would no longer be a complementarity problem. I'm not sure if that formulation would be easier. Alos, I understand NPC != unsolvable, but I am trying to understand the complexity of the problem these equations encode. So I am looking either for a polytime algorithm or an NPC proof. | |
| Dec 24, 2011 at 16:33 | comment | added | Gilead | It looks like this could be reformulated into a (mixed) linear complementarity problem (if $u_{ij}$ can be made to be non-negative). There may exist complexity proofs in the LCP literature. | |
| Dec 24, 2011 at 16:28 | comment | added | Gilead | Not sure what you mean about "extra linear constraints". You mean the inequality constraints? Also, just a comment: a system being NP-hard does not preclude one from finding a solution. Those statements are not mutually exclusive. A worst-case complexity bound is just that: a bound. The simplex method is NP-hard, but its average performance is extremely good. | |
| Dec 24, 2011 at 8:04 | history | edited | Woland | CC BY-SA 3.0 |
edited title
|
| Dec 24, 2011 at 7:35 | history | edited | Woland | CC BY-SA 3.0 |
added 125 characters in body
|
| Dec 24, 2011 at 7:25 | history | asked | Woland | CC BY-SA 3.0 |