3 ms·
Simplex solves only linear systems, and finds a global optimum. Cassowary is an incremental version of simplex—it lets you efficiently add, remove, and modify
by mayoff 8y ago
Simplex solves only linear systems, and finds a global optimum.
Cassowary is an incremental version of simplex—it lets you efficiently add, remove, and modify constraints.
Gradient descent works for non-linear systems, but isn't guaranteed to find the global optimum.
- jpfr 8y agoThere is a huge class of non-linear problems where gradient descent (with line search) is guaranteed to find the global optimum: Convex optimization problems. And within convex problems there is a hierarchy of "difficulty": LP ⊂ QP ⊂ SOCP ⊂ SDP The Simplex algorithm solves only LP. And it was shown that the Simplex has an exponential worst-case runtime (in the number of constraints). Whereas interior-point methods (basically variations of Gradient Descent) have a much better worst-case runtime. See here for further reference: http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf