Timeline for Minimize a strictly convex quadratic function subject to linearly equality and nonnegativity constraints in finite time?
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16, 2014 at 4:32 | vote | accept | XiMS | ||
| Apr 15, 2014 at 6:02 | comment | added | XiMS | @Suvrit, thanks a lot! I really appreciate this. I am reading:) | |
| Apr 13, 2014 at 22:57 | answer | added | Cristóbal Guzmán | timeline score: 4 | |
| Apr 13, 2014 at 19:40 | comment | added | Suvrit | @Xims: you'll benefit greatly by reading the book: Introductory lectures on convex optimization by Yurii Nesterov --- that books a very nice introduction to oracle based complexity (upper and lower bounds); you can also have a look at Lecture 23 of my course: cs.cmu.edu/~suvrit/teach/aopt.html | |
| Apr 13, 2014 at 17:09 | comment | added | XiMS | @Suvrit, thank you so much! I see. I think I am talking about the oracle model. I was reading the book "Convex Optimization" by Professor Stephen Boyd yesterday. I think many ϵ-accuracy solutions mentioned (like Newton's step in that book) are actually based on the oracle model. | |
| Apr 13, 2014 at 11:32 | comment | added | Suvrit | @XiMS: As Brian asked: "what model of computation are you using?" Complexity analysis depends on the model of computation----the term "polynomial time" too, so it would be good to know what model. But in the commonly used oracle model, the runtimes are polynomial in the problem size for $\epsilon$-accuracy solution (depending on stuff like $1/\epsilon$, $\log(1/\epsilon)$, etc.) | |
| Apr 12, 2014 at 21:19 | comment | added | XiMS | Thanks Brian. Yes, I am asking this from a theoretical perspective. I am wondering if it is possible to use convex optimization techniques to solve this one in polynomial time or finite time (if polynomial is not achievable). | |
| Apr 12, 2014 at 20:00 | comment | added | Brian Borchers | As a practical matter, such problems are relatively easy to solve numerically to within reasonable tolerances. However, it sounds as though you're asking a more theoretical question about exactly solving the problem within some model of computation. What computational model are you interested in? | |
| Apr 12, 2014 at 19:02 | history | asked | XiMS | CC BY-SA 3.0 |