We introduce and study the problem of optimizing arbitrary functions over
degree sequences of hypergraphs and multihypergraphs. We show that over
multihypergraphs the problem can be solved in polynomial time. For hypergraphs,
we show that deciding if a given sequence is the degree sequence of a
3-hypergraph is NP-complete, thereby solving a 30 year long open problem. This
implies that optimization over hypergraphs is hard already for simple concave
functions. In contrast, we show that for graphs, if the functions at vertices
are the same, then the problem is polynomial time solvable. We also provide
positive results for convex optimization over multihypergraphs and graphs and
exploit connections to degree sequence polytopes and threshold graphs. We then
elaborate on connections to the emerging theory of shifted combinatorial
optimization.