1

Assume $a\in {{R}^{d}}$ and $B\in {{R}^{d\times d}}$. Consider minimizing an objective function of the form

$\text{sgn}{{\left( a \right)}^{T}}B~\text{sgn}(a)$

wrt to $a$. Assume it is bounded below.

Is replacing the sign functions with $f(x)=2/(1+e(-x)) - 1$ (sigmoid smoothing) and doing gradient descent a good idea? Any other suggestions?

Adam I.
  • 359

1 Answers1

0

This is an NP hard problem: http://en.m.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization

Nothing so simple will work!

apt1002
  • 2,033
  • Any suggestions, approximations though? – Adam I. Nov 14 '13 at 22:42
  • 1
    Exhaustive search is not unreasonable. Special methods exist if $B$ is sparse but some exhaustive search is usually still needed. Annealing also works for some $B$ but for others it gets trapped in a local minimum. If you Google for "quadratic binary optimisation" you will find a lot of useful ideas. – apt1002 Nov 14 '13 at 22:50