All Questions
Tagged with convexity computational-complexity
3 questions
7
votes
2
answers
2k
views
Computational complexity of unconstrained convex optimisation
What is known about the relationship between unconstrained convex optimisation and computational complexity? For example, for which optimisation problems and which gradient descent algorithms is one ...
- 561
2
votes
0
answers
95
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 13.9k
1
vote
0
answers
88
views
On convex quadratic programming clarification
We know convex quadratic programming is in $P$.
Is it also in $P$ if the function of interest is only convex in the domain of interest?
- 13.9k