Um Algoritmo Paralelo Simples com uma Taxa de Convergência O (1/t) para Programas Convexos Gerais

Este artigo considera programas convexos com uma função objetivo convexa geral (possivelmente não diferenciável) e funções de restrição convexa contínuas em Lipschitz. Um algoritmo simples é desenvolvido e alcança uma taxa de convergência O (1/t). Semelhante ao algoritmo clássico de subgradiente dual e ao algoritmo de método dos multiplicadores de direção alternada (ADMM), o novo algoritmo possui uma implementação paralela quando as funções objetiva e de restrição são separáveis. No entanto, o novo algoritmo tem uma taxa de convergência O (1/t) mais rápida em comparação com a melhor taxa de convergência conhecida O (1/t) para o algoritmo de subgradiente dual com média primal. Além disso, ele pode resolver programas convexos com restrições não lineares, que não podem ser tratados pelo algoritmo ADMM. O novo algoritmo é aplicado a um problema de maximização de utilidade de rede multipath e resulta em um algoritmo de controle de fluxo descentralizado com a rápida taxa de convergência O (1/t).