Convex Network Optimization

Implementation in Adaptor High Performance Fortran
Aleksandar Donev, working with Dr. Phil Duxbury

Graphs and Networks

Graph: G=(V,E)
Nodes: V={i, i=1..n}, n=|V|
Arcs: E={e_(i,j) | i,j in V}, m=|E|

Network: N=(G,C)
Cost functional: C={c_(i,j)}
Cost on each arc: c_(i,j)(f_(i,j))

A few examples of directed and undirected graphs

Fig 1. A few examples of directed and undirected graphs

Min-cost Network Flow Problem

Constraints--Combinatorial (Descrete) Optimization Aspect

D_i=S_{e_(i,j)}f_(i,j)-S_{e_(j,i)}f_(i,j)+b_i=0

Flow conservation: Af=b
Node-arc incidence matrix A:
+1 in row i and -1 in row j for the column corresponding to arc e_(i,j)

Minimizing the Cost--Continuous Optimization Aspect

Convex separable total cost:
g(f)=S_{e_(j,i)}c_(i,j)(f_(i,j))
Min-cost network flow problem:

min_f g(f) | Af=b

Disordered Physical Systems Modeled as Networks

Graphs

Disordered systems of interest:

Porous materials--oil extraction
Superconducting materials--grainboundary effects
Varistors--semiconductor technology

Fig 1. A two dimensional grid-based network
Fundamental properties of networks in physics:

Very large--10⁷ nodes and arcs
Very sparse--nearest neighbour
Disordered--randomly diluted

Cost

Potential P -- flow f characteristic
Cost function--related to the dissipation of power:

c(f)=Integrate( P(x)dx, x=0..f)

Fig 2. Highly non-linear potential-flow characteristics of certain conducting elements
Fundamental properties of P(f) (or f(P)):

Stationary initial behaviour--no flow or no potential
Highly non-linear transition--critical potential or flow
Linear asymptotic behavior--easy asymptotic problem

Numerical Algorithm

The full mathematical definition of the problem:
Large-scale sparse convex separable min-cost network optimization

Studied extensively by:

Applied mathematicians--large-scale linear network optimization (simplex algorithm)
Economics-large-scale dense linear and non-linear
Engineers (electrical)--small-scale non-linear
Physicists (???)--large-scale non-linear optimization--most difficult

Algorithm: Truncated Dual Newton Method
Newton linear system of equations in x:

Hx=-G

(AH^*A^T)x=-(A^TG^*-b)

Conjugate gradient:

Combinatorial optimization aspects contained in A:
- Matrix-vector multiplication with AH^*A^T
- Preconditioning based on minimal spanning forests
Continuous optimization aspects contained in H^*
- Convex-cost function difficult to calculate numerically
- The system is ill-conditioned in the asymptotic regions

Computational Implementation

We need large computers--parallel distributed computing:

Implementation language: High Perfomance Fortran with Adaptor compilation system
Test platform: Beowulf Linux Cluster of 11 PC's
Ultimate platform: The Intel Paragon
Key points about parallel programming:
1. Minimize communication costs
2. Distribute all data structures accross processors
3. Minimize waiting/sleep time

The initial graph connectivity and distribution

Fig 3. Initial labeling and distribution of the graph.
The example was executed on 3 processors and was a 2D grid of size 7x7 with 70% of the arcs present
Steps in algorithm:

Generate a hypercube lattice in 2D or 3D
Randomly dilute some of the arcs with a given probability d
Extract a single pure graph using connected-components labeling algorithm:
- Implemented in parallel--fully memory distributed
- Possibly remove danging edges for large dilutions
- This is a neccessary combinatorial (graph) algorithm Fig 4. The graph labeling after the connected component extraction
Assign random values to arc parameters--disorded systems
Use maximum-flow or shorthest path to find critical total current or potential--more combinatorial optimization
Find a good initial guess for the flow--it helps convergence
Start the Dual Newton Method
- Use Conjugate Gradient to solve Newton's system--preconditioning??? Fig 5. Convergence of CG for the coefficient matrix AH^*A^T
  An almost positive-semidefinite and a nice positive-definite case are shown. Diagonal preconditioning seems to help some in the former case, but not much in general.
- Use Truncated Newton Algorithm to perform the continiuos optimization
- ...

Results and Conclusion

Graph and network algorithms are important in physics
Convex network optimization can model complex disordered systems
There are both combinatorial and continious aspects to the algorithm
We need to implement a scalable parallel algorithm
The algorithm can later be used by many for different purposes
Preliminary scaling tests very promissing--much more work to be done