Resolvendo o problema de decisão

O método descrito na subseção anterior encontra pontos estacionários de primeira ordem (minimizadores locais) do problema. Para aumentar a probabilidade de encontrar um minimizador global, o método começa de pontos iniciais aleatórios. Com probabilidade 1, eventualmente, o método começará de um chute inicial na bacia de convergência de um minimizador global. Apesar de tudo, esse arcabouço tem dois incovenientes: (i) não queremos esperar por um tempo inifinito; e (ii) a menos que conhecemos a priori o custo ótimo do problema no minimizador global, não somos capazes de distinguir o minimizador global de um ponto estacionário.

Na prática, rodamos o método começando de N pontos iniciais diferentes. Se a solução com o custo ótimo igual a zero é encontrado então a resposta para o problema de decisão é SIM, caso contrário a resposta é ``não sabemos'' e assumimos que a resposta é NÃO. O fluxograma na Figura mostra essa estratégia.

Figure: Resolvendo o problema de decisão.