Презентация Lemkes Algorithm: The Hammer in Your Math Toolbox? онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Lemkes Algorithm: The Hammer in Your Math Toolbox? абсолютно бесплатно. Урок-презентация на эту тему содержит всего 35 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:35 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:326.50 kB
- Просмотров:59
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Lemke’s Algorithm:
The Hammer in Your Math Toolbox?
Chris Hecker
definition six, inc.
checker@d6.com
№2 слайд
Содержание слайда: First, a Word About Hammers
requirements for this to be a good idea
a way of transforming problems into nails (MLCPs)
a hammer (Lemke’s algorithm)
lots of advanced info + one hour = something has to give
majority of lecture is motivating you to care about the hammer by showing you how useful nails can be
make you hunger for more info post-lecture
very little on how the hammer works in this hour
№3 слайд
Содержание слайда: Hammers (cont.)
by definition, not the optimal way to solve problems, BUT
computers are very fast these days
often don’t care about optimality
prepro, prototypes, tools, not a profile hotspot, etc.
can always move to optimal solution after you verify it’s a problem you actually want to solve
№4 слайд
Содержание слайда: What are “advanced game math problems”?
problems that are ammenable to mathematical modeling
state the problem clearly
state the desired solution clearly
describe the problem with equations so a proposed solution’s quality is measurable
figure out how to solve the equations
why not hack it?
I believe better modeling is the future of game technology development (consistency, not reality)
№5 слайд
Содержание слайда: Prerequisites
linear algebra
vector, matrix symbol manipulation at least
calculus concepts
what derivatives mean
comfortable with math notation and concepts
№6 слайд
Содержание слайда: Overview of Lecture
random assortment of example problems breifly mentioned
5 specific example problems in some depth
including one that I ran into recently and how I solved it
generalize the example models
transform them all to MLCPs
solve MLCPs with Lemke’s algorithm
№7 слайд
Содержание слайда: A Look Forward
linear equations
Ax = b
linear inequalities
Ax >= b
linear programming
min cTx
s.t. Ax >= b, etc.
№8 слайд
Содержание слайда: Applications to Games
graphics, physics, ai, even ui
computational geometry
visibility
contact
curve fitting
constraints
integration
graph theory
№9 слайд
Содержание слайда: Applications to Games (cont.)
don’t forget...
The Elastohydrodynamic Lubrication Problem
Solving Optimal Ownership Structures
“The two parties establish a relationship in which they exchange feed ingredients, q, and manure, m.”
№10 слайд
Содержание слайда: Specific Examples #1a:
Ease Cubic Fitting
warm up with an ease curve cubic
x(t)=at3+bt2+ct+d
x’(t)=3at2+2bt+c
4 unknowns a,b,c,d (DOFs) we get to set, we choose:
x(0) = 0, x(1) = 1
x’(0) = 0, x’(1) = 0
№11 слайд
Содержание слайда: Specific Examples #1a:
Ease Cubic Fitting (cont.)
x(t)=at3+bt2+ct+d, x’(t)=3at2+2bt+c
x(0) = a03+b02+c0+d = d = 0
x(1) = a13+b12+c1+d = a+b+c+d = 1
x’(0) = 3a02+2b0+c = c = 0
x’(1) = 3a12+2b1+c = 3a + 2b + c = 0
№12 слайд
Содержание слайда: Specific Examples #1a:
Ease Cubic Fitting (cont.)
d = 0, a+b+c+d = 1, c = 0, 3a + 2b + c = 0
a+b=1, 3a+2b=0
a=1-b => 3(1-b)+2b = 3-3b+2b = 3-b = 0
b=3, a=-2
x(t) = 3t2 - 2t3
№13 слайд
Содержание слайда: Specific Examples #1a:
Ease Cubic Fitting (cont.)
or,
x(0) = d = 0
x(1) = a + b + c + d = 1
x’(0) = c = 0
x’(1) = 3a + 2b + c = 0
№14 слайд
Содержание слайда: Specific Examples #1b:
Cubic Spline Fitting
same technique to fit higher order polynomials, but they “wiggle”
piecewise cubic is better
“natural cubic spline”
xi(ti)=xi xi(ti+1)=xi+1
x’i(ti) - x’i-1(ti) = 0
x’’i(ti) - x’’i-1(ti) = 0
there is coupling between the splines, must solve simultaneously
№15 слайд
Содержание слайда: Specific Examples #1b:
Cubic Spline Fitting (cont.)
№16 слайд
Содержание слайда: Specific Examples #2:
Minimum Cost Network Flow
what is the cheapest flow route(s) from sources to sinks?
model, want to minimize cost
cij = cost of i to j arc
bi = i’s supply/demand, sum(bi)=0
xij = quantity shipped on i to j arc
x*k = sum(xik) = flow into k
xk* = sum(xki) = flow out of k
flow balance: x*k - xk* = -bk
one-way streets: xij >= 0
№17 слайд
Содержание слайда: Specific Examples #2:
Minimum Cost Network Flow (cont.)
min cost: minimize cTx
the sum of the costs times the quantities shipped (cTx = c ·x)
flow balance is coupling: matrix
x*k - xk* = -bk
№18 слайд
Содержание слайда: Specific Examples #3:
Points in Polys
point in convex poly defined by planes
n1 · x >= d1
n2 · x >= d2
n3 · x >= d3
farthest point in a direction in poly, c:
№19 слайд
Содержание слайда: Specific Examples #3:
Points in Polys (cont.)
closest point in two polys
min (x2-x1)2
s.t. A1x1 >= b1
A2x2 >= b2
stack ‘em in blocks, Ax >= b
№20 слайд
Содержание слайда: Specific Examples #3:
Points in Polys (cont.)
how do we stack x1,x2 into single x given
(x2-x1)2 = x22-2x2•x1+x12
№21 слайд
Содержание слайда: Specific Examples #3:
Points in Polys (cont.)
more points, more polys!
min (x2-x1)2 + (x3-x2)2 + (x3-x1)2
№22 слайд
Содержание слайда: Specific Examples #4:
Contact
model like IK constraints
a = Af + b
a >= 0, no penetrating
f >= 0, no pulling
aifi = 0, complementarity
(can’t push if leaving)
№23 слайд
Содержание слайда: Specific Examples #5:
Joint Limits in CCD IK
how to do child-child constraints in CCD?
parent-child are easy, but need a way to couple two children to limit them relative to each other
how to model this & handle all the cases?
define dn= gn - an
min (x1 - d1)2 + (x2 - d2)2
s.t. c1min <= a1+x1 - a2-x2 <= c1max
parent-child are easy in this framework: c2min <= a1+x1 <= c2max
another quadratic program:
min xTQx
s.t. Ax >= b
№24 слайд
Содержание слайда: What Unifies These Examples?
linear equations
Ax = b
linear inequalities
Ax >= b
linear programming
min cTx
s.t. Ax >= b, etc.
№25 слайд
Содержание слайда: QP is a Superset of Most
quadratic programming
min ½xTQx + cTx
s.t. Ax >= b
Dx = e
№26 слайд
Содержание слайда: Karush-Kuhn-Tucker Optimality Conditions get us to MLCP
for QP
form “Lagrangian”
L(x,u,v) = ½ xTQx + cTx - uT(Ax - b) - vT(Dx - e)
for optimality (if convex):
L/ x = 0
Ax - b >= 0
Dx - e = 0
u >= 0 ui(Ax-b)i = 0
this is related to basic calculus min/max f’(x) = 0 solve
№27 слайд
Содержание слайда: Karush-Kuhn-Tucker Optimality Conditions (cont.)
L(x,u,v) = ½ xTQx + cTx - uT(Ax - b) - vT(Dx - e)
y = L/ x = Qx + c - ATu - DTv = 0, x free
w = Ax - b >= 0, u >= 0, wiui = 0
s = Dx - e = 0, v free
№28 слайд
Содержание слайда: This is an MLCP
№29 слайд
Содержание слайда: Modeling Summary
a lot of interesting problems can be formulated as MLCPs
model the problem mathematically
transform it to an MLCP
on paper or in code with wrappers
but what about solving MLCPs?
№30 слайд
Содержание слайда: Solving MLCPs
(where I hope I made you hungry enough for homework)
Lemke’s Algorithm is only about 2x as complicated as Gaussian Elimination
Lemke will solve LCPs, which some of these problems transform into
then, doing an “advanced start” to handle the free variables gives you an MLCP solver, which is just a bit more code over plain Lemke’s Algorithm
№31 слайд
Содержание слайда: Playing Around With MLCPs
PATH, a MCP solver (superset of MLCP!)
really stoked professional solver
free version for “small” problems
matlab or C
OMatrix (Matlab clone) free trial (omatrix.com)
only LCPs, but Lemke source is in trial
not a great version, but it’s really small (two pages of code) and quite useful for learning, with debug output
good place to test out “advanced starts”
my Lemke’s + advanced start code
not great, but I’m happy to share it
it’s in Objective Caml :)
№32 слайд
Содержание слайда: References for Lemke, etc.
free pdf book by Katta Murty on LCPs, etc.
free pdf book by Vanderbei on LPs
The LCP, Cottle, Pang, Stone
Practical Optimization, Fletcher
web has tons of material, papers, complete books, etc.
email to authors
relatively new math means authors are still alive, bonus!
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда: Specific Examples #5:
Constraints for IK
compute “forces” to keep bones together
a1 = A11 f1 + b1
a1 : relative acceleration
at constraint
f1 : force at constraint
b1 : external forces converted to
accelerations at constraints
A11 : force/acceleration relation matrix
№35 слайд
Содержание слайда: Specific Examples #5:
Constraints for IK (cont.)
multiple bodies gives coupling...
Скачать все slide презентации Lemkes Algorithm: The Hammer in Your Math Toolbox? одним архивом:
