<p>Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.</p>

<p>Is there a survey/lecture notes describing generalizations of LP that can be solved in poly time?</p>

<p>This is related to <a href="https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in">this question</a>, but the questions in that post are quite different and most of the questions have not been answered.</p>

CC BY-SA 4.0
2019-02-26T18:19:24.883Z
I think the general rule is: (1) convex optimization problems are polynomially solvable, and (2) as soon as non-convexity pops up you hit NP-hardness.
Gamow
CC BY-SA 4.0
2019-02-27T13:17:35.240Z
I think that is a good rule of thumb, however, there are polynomial time solvable nonconvex programs and NP-hard convex problems
user2316602
<ds.algorithms><optimization><linear-programming><polynomial-time><semidefinite-programming>
Generalizations of linear programming
user2316602
# Generalizations of linear programming

(Asked by: username_0 on 2019-02-26)

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.

Is there a survey/lecture notes describing generalizations of LP that can be solved in poly time?

This is related to [this question](https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in), but the questions in that post are quite different and most of the questions have not been answered.

**Tags:** ds.algorithms, optimization, linear-programming, polynomial-time, semidefinite-programming
> **Comments:**
> **username_1**: I think the general rule is: (1) convex optimization problems are polynomially solvable, and (2) as soon as non-convexity pops up you hit NP-hardness.  
> **username_0**: I think that is a good rule of thumb, however, there are polynomial time solvable nonconvex programs and NP-hard convex problems  

---

## 0 answers

