Reading List 2015.3.12

“Alternative Distributed Algorithms for Network Utility Maximization”

Decomposition techniques: primal decomposition & dual decomposition methods

subproblems (separable) & master problem (update coupling variable)

Solve coupling variable: primal method
Solve coupling constraint: dual method

- Direct Primal and Direct Dual Decompositions
- Indirect Primal and Indirect Dual Decompositions (transform coupling constraint into coupling variable)
- Multilevel Primal and Dual Decompositions
  In problem (17): two sets of constraints (similar to my problem). dual-primal / dual-dual decomposition
- Gradient/Subgradient Methods
  choices of stepsize[33][34][36].
- Standard Dual-Based Algorithm for Basic NUM (Network Utility Maximization)

Application:
- Power-Constrained Rate Allocation
- QoS Rate Allocation
- Hybrid Rate-Based and Price-Based Rate Allocation
- Multipath-Routing Rate Allocation

Reading List 2015.3.11

“Distributed Methods for Constrained Nonconvex Multi-Agent  Optimization - Part I: Theory”

Comparison of some methods: 

1) Feasible Sequential Quadratic Programming (FSQP) methods [2];  --- maintain feasibility but centralized.

2) Parallel Variable Distribution (PVD) methods [3]-[5]; --- parallel but an amount of info exchange/knowledge & convergence only for convex or non convex but block separable constraints.

3) SCA algorithms [6]-[11].

    --- [6][7][11]: centralized; [8]-[10]: distributed methods but convex and separable constraints.

Reading List 2015.3.11 - Parallel variable distribution

• “Parallel variable distribution”

- Unconstrained parallel variable distribution;

- PVD with block separable constraints;

- PVD with general constraints: min f(x) such that g(x) <= 0;

  Handling inseparable constraints: exterior penalty[8], augmented Lagrangian methods[17], [3]. Avoid both of difficulties of above: the dual differentiable exact penalty function[10].

• “Parallel variable distribution for constrained optimization”

In parallel algorithms, an iteration consists of two steps: parallelization & synchronization[2].

Some methods: Block-Jacobi[2], updated conjugate subspaces[10], coordinate descent[21], parallel gradient distribution[14], PVD.

- Nonconvex separable constraints
- Convex inseparable constraints

• “On the Convergence of Constrained Parallel Variable Distribution Algorithms”

Also mentioned some methods: block Jacobi[2], coordinate descent[26], parallel gradient distribution algorithms[16].
Mainly prove the convergence of optimization problems with general convex constraints.