  We develop algorithms for inner approximating the cone of positive
semidefinite matrices via linear programming and second order cone programming.
Starting with an initial linear algebraic approximation suggested recently by
Ahmadi and Majumdar, we describe an iterative process through which our
approximation is improved at every step. This is done using ideas from column
generation in large-scale linear and integer programming. We then apply these
techniques to approximate the sum of squares cone in a nonconvex polynomial
optimization setting, and the copositive cone for a discrete optimization
problem.
