OvercomingtheConvexBarrierforSimplexInputs: SupplementaryMaterial

Equivalently,ifwe demonstrate that anylinear function obtains the same maximum value overS asoverCH,theproofiscomplete. Figure 1inourmain paper compares thetightness between different relaxations. For using the Anderson relaxation, we need to replace the input simplex with the unit hypercube. The relaxation first uses Kuhn triangulation of[0,1]n [Todd, 1976], which is used to describe the collection of simplices whose union is[0,1]n. Then constraintsr1 andr2 are constructed using these two triangles. In contrast, our relaxation works directly with the input simplex and only requires one upper constraint.