directed graph

Special cases of the quadratic shortest path problem

  • Hao Hu
  • Renata Sotirov
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Network Optimization Tags , ,

    The quadratic shortest path problem (QSPP) is the problem of finding a path in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was … Read more

    ExtraPush for Convex Smooth Decentralized Optimization over Directed Networks

  • Wotao Yin
  • Jinshan Zeng
    • Categories Network Optimization, Nonlinear Optimization Tags , , , ,

    In this note, we extend the existing algorithms Extra and subgradient-push to a new algorithm ExtraPush for convex consensus optimization over a directed network. When the network is stationary, we propose a simplified algorithm called Normalized ExtraPush. These algorithms use a fixed step size like in Extra and accept the column-stochastic mixing matrices like in … Read more