2
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ You may wish to try out the CCCP Procedure (more generally, d.c. programming) $\endgroup$
    – Suvrit
    Commented Feb 19, 2015 at 14:18
  • $\begingroup$ @Suvrit Is it possible to approximate the local minima with some constant factor with guaranteed polynomial time? $\endgroup$
    – Yushi Xiao
    Commented Feb 19, 2015 at 14:50
  • $\begingroup$ without additional structure, I don't think it will be possible in general to guarantee even reasonable non-constant factor approximations...; perhaps you could ask a more specific separate question with the exact $F_1$ and $F_2$ that you care about? $\endgroup$
    – Suvrit
    Commented Feb 19, 2015 at 15:44
  • $\begingroup$ @Suvrit I updated my questions. Thx for advice. $\endgroup$
    – Yushi Xiao
    Commented Feb 19, 2015 at 16:37

1 Answer 1

Reset to default
2
$\begingroup$

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,

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Are you answering just the title or also the body of the question? $\endgroup$
    – usul
    Commented Feb 19, 2015 at 14:05
  • $\begingroup$ @usul I think for a specific choice of functions that the OP has, you can construct from the theory of the cited papers an example for which it is NP-complete to check local optimality (unless it is a priori somehow easy to prove that the Hessian is strictly positive definite at a stationary point that is a candidate for a local min) $\endgroup$
    – Suvrit
    Commented Feb 19, 2015 at 14:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .