Transcript x 1

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 with / without
linear equality 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 x1  ...  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  m2  M
The region satisfying all the constraints is the
feasible region and it is convex
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.)
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
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
 Standard form without equality constraints
 Start at the origin: always a feasible corner point
 N=2 , M=3 at most 10 corner points, but only 5
are feasible
 at (x1,x2)=(0,0) the two last constraints intersect
The basic mechanism of the
simplex method: A simple example
 Add slack variables which transform inequality
constraints to equality constraints
maximize Z ( x )  15 x1  10 x 2
s.t.
x1  s1  2
x 2  s2  3
x1  x 2  s3  4
x1  0, x 2  0, s1  0, s2  0, s3  0
 Start at the origin: (x1,x2,s1,s2,s3)=(0,0,2,3,4) , Z=0
 move to another corner point by letting, say, x1 grow
 x1 may grow until it hits another corner point, in which
a different constraint holds => setting some si=0
The basic mechanism of the
simplex method: A simple example
 Divide all variables into two groups: basic/nonbasic
 At the origin: (x1,x2,s1,s2,s3)=(0,0,2,3,4)
 Choose a nonbasic that maximizes Z: x1 , this is the
entering basic variable
 x1 is increased until it hits the constraint x1  2
 There, x1=2 => s1=0 and this is the
leaving
basic variable
 At (2,0): (x1,x2,s1,s2,s3)=(2,0,0,3,4), Z=30
 Update the equations and continue until no further
increase in Z is available
 Automatic exchange of variables: Simplex Tableau
Simplex Tableau with inequality
constraints
In proper form:
 Exactly 1 basic variable per equation
 The coefficient of each basic variable is 1 and this is
the only non zero entry in its column
 The RHS reveal the values of all basic variables
 The entering basic variable has the most negative
entry in the 0th row (for the objective Z)
 The leaving basic variable is the one that minimizes
RHS/coefficient of entering variable
 Set the pivot to 1 and use it to eliminate all other non
zeros in its column
 The maximum is achieved when the 0th row  0
nonbasic
=0
s1
s2
s3
basic
Slack variables
s1
s2
s3
entering
basic
leaving
basic
Minimum
Ratio
Test
Simplex Tableau with inequality (‘less than’),
equality and ‘greater than’ constraints
If an equality constraints are involved, e.g., x1+x2=4
 The origin is not feasible
 Add an artificial variable to each equality constraint:
x1+x2+t1=4
If a constraint is with ‘greater than’ sign: 3x1+2x2 16
 The origin is not feasible
 Add a slack variable and an artificial variable to each
‘greater than’ constraint: 3x1+2x2-s1+t1=16
 In order to find a starting feasible corner point for the
original LP, solve a Phase 1 LP in which the objective
is to minimize the sum of all artificial variables:
minimize Sti until all ti=0 => feasible for the original LP
Simplex Tableau in general
A general LP problem involves:
 N original variables
 L less than constraints
 E equality constraints
 G greater than constraints
 Add L+G slack variables
 Add E+G artificial variables
 To find a starting feasible corner point for LP,
solve a Phase 1 LP: minimize Sti (sum of artificial variables)
 INFEASIBILE: if at the end of Phase 1 Sti>0
 If Sti=0 continue to solve the original LP
 UNBOUNDED: an entering basic variable is unlimited
Linear programming
 The Simplex method: small and large problems
 Interior point methods: very large problems
(Karmarker 1984, polynomial-time algorithm)
 Within ML should not exceed 100 variables
 Many available software: MATLAB, numerical
recipes,…
 Adjust your problem to the used software
 Linearization of both the energy functional and
the constraints: the placement problem under
pair wise non-overlap constraints
Exc#6: Window relaxation for the graph drawing problem
Consider the following window W of 3x3 squares containing the
nodes m,n and p:
m is of size 1x1 located at (2,2);
n is of size 0.8x0.8 located at (3.4,3.2);
p is of size 0.5x0.5 located at (2.5,3).
Find a correction to the locations of m,n and p such that the
quadratic energy is minimized subject to inequality constraint
demands that the area of nodes at each square <= 0.3
(4,4) (5,4)
4
8
(0.5,1.5)
(1,1)
2
7
1
p
4
3
5
m
1
2
n 9
6
3
a.
b.
c.
d.
e.
f.
g.
h.
i.
j.
Calculate the current amount of nodes’ area present in
each of the 9 squares
Calculate amkx e: the change (per unit length) in the
amount of nodes’ area induced by a small change in the x
direction of node m to square k, k=1,…,9. Similarly
calculate amky , ankx , anky , apkx and apky
Write the quadratic energy E as a function of the
corrections to the variables in W
Calculate the current value of E
Write the 9 inequalities constraints associated with each
square
Choose the active set of constraints and write the
Lagrangian
Calculate the resulting system of equations and solve it
Does the solution seem to be reasonable?
Choose .25 of the solution, does E decrease at that point?
Write the linear programming formulation
Exc#6: Window relaxation for the
graph drawing problem
~, ~
 Given a graph which is initially drawn at ( x
y)
 Introduce a grid of mxm squares, each square of
size hx by hy
 Pick a window W of squares
 Define by akix (akiy) the change in the total area in
the k’th square per small change in x~i ( ~yi )
1. How should akix (akiy) be calculated
2. Write the quadratic energy minimization problem
under equidensity constraints in W
3. Write the resulting linear system of equations
4. Write a linear programming formulation