More precisely, The setting could be formulated as,


$min. F\_{\lambda}(p)$ over permutation matrices $P$


Here $F\_{\lambda}(p)$=$\lambda \*F\_{0}(p)+(1-\lambda)F\_{1}(p)$ 


where both $F\_{0}(p)$ and $F\_{1}(p)$ are **quadratic** (*Frobineous norm*) and $F\_{0}(p)$ is convex, $F\_{1}(p)$ is concave. Thus their combination can be neither convex nor concave.


The objective function comes from the paper ***A Path Following Algorithm for the Graph Matching Problem***, the ultimate goal is to find a good permutation matrix $P$ for the graph matching problem. 


The idea of the author is briefly as follows, 


1. relax the domain of the $F\_{0},F\_{1}$ to double stochastic matrices $D$
2. set $\lambda$ to 1. Since $F\_{0}$ is convex, we can minimize $F\_{0}$ efficiently to get the minimum $X^{cur}$
3. increase $\lambda$ iteratively to 1. In each iteration, optimize this $F\_{\lambda}$ to a local minima using $X^{cur}$ as starting point.
4. update $X^{cur}$ to the newly local minima in step 3
5. when $\lambda=1$, since $F\_{1}$ is concave, the local minima must be a permutation matrix.


In a theoretical perspective, the algorithm can be used as a way to solve the graph isomorphism problem. So I want to investigate in detail the running time of the algorithm. As the approximation graph isomorphism is NP-hard in general.


Thanks in advance.


[Link to the paper](http://www.di.ens.fr/~fbach/path_following_pami.pdf)



Is there any algorithm can find local minima of nonconvex objective function in guaranteed polynomial time?
In general, without additional assumptions this will not be possible (barring P=NP).


In particular, from the (slightly edited) abstract of: K. G. Murty, S. K. Kabadi. [**Some NP-Complete problems in quadratic and nonlinear programming**, *Mathematical Programming*, 39(1987), 117-129](http://link.springer.com/content/pdf/10.1007/BF02592948.pdf), 



> 
> In continuous variable, smooth, nonconvex nonlinear programming, we analyze the complexity of checking whether
> 
> 
> 1. a given feasible solution is not a local minimum, and
> 2. the objective function is not bounded below on the set of feasible solutions.
> 
> 
> We construct a special class of indefinite quadratic programs, with simple constraints and integer data, and show that checking (1) or (2) on this class is NP-complete. As a corollary, we show that checking whether a given integer square matrix is not copositive, is NP-complete.
> 
> 
> 


