  We consider maximizing a continuous convex function over the assignment
polytope. Such problems arise in Graph Matching (the optimization version of
Graph Isomorphism) and Quadratic Assignment problems. In the typical case of
maximizing a convex function over a polytope the problem can be solved by using
a simplicial algorithm such as Tuy's method or the Falk-Hoffman method, but
these algorithms require that the underlying polytope be non-degenerate, which
is not the case for the assignment polytope. In this note we show how a simple
perturbation scheme can be used to create a "surrogate problem" that is both
non-degenerate and combinatorially equivalent to the original problem. We
further provide an explicit construction of a surrogate problem that is
non-degenerate and combinatorially equivalent to the Graph Matching problem,
when the latter is posed as a convex maximization problem. By constructing a
surrogate problem that is known a priori to be non-degenerate and
combinatorially equivalent to Graph Matching we resolve an "open issue" of
solving Graph Matching via convex maximization first raised by Maciel.
