Transcript MULTILEVEL PLACEMENT ALGORITHM

Easy Optimization
Problems,
Relaxation,
Local Processing
for a small subset of
variables
Different types of relaxation
 Variable by variable relaxation – strict
minimization
 Changing a small subset of variables
simultaneously – Window strict
minimization relaxation
 Stochastic relaxation – may increase the
energy – should be followed by strict
minimization
Easy to solve problems
 Quadratic functional and linear constraints
Solve a linear system of equations
Quadratization of the functional: P=1, P>2
Linearization of the constraints: P=2
Inequality constraints: active set method
Data structure
For each node in the graph keep
1. A list of all the graph’s neighbors: for each neighbor
keep a pair of index and weight
2. …
3. …
4. Its current placement
5. The unique square in the grid the node belongs to
For each square in the grid keep
1. A list of all the nodes which are mostly within
 Defines the current physical neighborhood
2. The total amount of material within the square
Graph drawing
Most graph
drawing
algorithms
Graph drawing
Most graph
drawing
algorithms
With space
utilization
The error of the compressed
32x32 grid graph
Start the equi-density with
a 2x2 grid
Continue the equi-density with
a 4x4 grid
8x8 grid
The final results was obtained after
equi-density in a 32x32 grid
5-level binary tree with
non-uniform vertices
Inequality constraints
Given E(x) subject to m inequality constraints:
gk(x)<=0 , k=1,…,m , construct the Lagrangian
while taking into account only the unsatisfied
constraints. This is the active set A, i.e., for k in A
L(x,l) = E(x) + Sk lk gk(x) and solve the system
of n+|A| equations as with equality constraints.
At the solution gk(x)=0 for k in A
Should probably take only a of the solution
Should consider constraints only when lk >0
these are the binding constraints
Iterate
Exc#5: Lagrange multipliers
inequality constraints
minimize x2+y2
subject to x+2y<1 and 1/2-y<0
starting at (1,1/4)
1)Find the minimum
2)Calculate the Lagrange multipliers
3)Which constraint is binding, explain
Easy to solve problems
 Quadratic functional and linear constraints
Solve a linear system of equations
Quadratization of the functional: P=1, P>2
Linearization of the constraints: P=2
Inequality constraints: active set method
 Linear functional and linear constraints
Linearization of the quadratic functional
Linear programming
minimize/maximize a linear function
under equality/inequality linear constraints
 Standard form:
maximize
Z ( x )  a' x  a01 x0  ...  a0 N x N
subject to A1 x  b , b  0 ,
A2 x  c , c  0 ,
A1  R
m1  N
A2  R
m2  N
x  0 , a , b, c , x  R N , m1  m 2  M
The region satisfying all the constraints is the
feasible region and it is convex
Linear programming (cont.)
The optimum of a convex function in a convex
polyhedron region is at its extreme, corner points
Convex set (region) and function
convex
non-convex
convex polyhedron
A convex function F(x) satisfies:
F (a x1  (1  a ) x2 )  aF ( x1 )  (1  a )F ( x2 ) , a [0,1]
F(x2)
F(x1)
x1
x2
The basic mechanism of the
simplex method: A simple example
maximize Z ( x )  15 x1  10 x 2
s.t.
x1  2
x2  3
x1  x 2  4
x1  0
,
x2  0
Linear programming (cont.)
The optimum of a linear function in a convex
polyhedron region is at its extreme, corner points
 The maximum of a linear function cannot be in
the interior since there is always a positive
gradient direction
 Follow this direction until hitting the boundary
 Keep on going over the exterior until hitting a
corner point
 Go from one corner point to another
 At one of the corner points the global maximum
Linear programming (cont.)
N M




N


The number of corner points is finite
The global maximum is at the corner point in
which Z(x) is greater or equal to the value of Z
at all adjacent corner points
The simplex method (Dantzig 1948) starts at a
feasible corner point and visited a sequence of
corner points until a maximum is obtained
#of iterations is almost always O(M) or O(N)
whichever is larger, but can become exponential
for pathological cases