Презентация Lemkes Algorithm: The Hammer in Your Math Toolbox? онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Lemkes Algorithm: The Hammer in Your Math Toolbox? абсолютно бесплатно. Урок-презентация на эту тему содержит всего 35 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Математика » Lemkes Algorithm: The Hammer in Your Math Toolbox?
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:35 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:326.50 kB
- Просмотров:59
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![First, a Word About Hammers](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img1.jpg)
Содержание слайда: 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,](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img2.jpg)
Содержание слайда: 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](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img3.jpg)
Содержание слайда: 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)
№14 слайд
![Specific Examples b Cubic](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img13.jpg)
Содержание слайда: 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
№16 слайд
![Specific Examples Minimum](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img15.jpg)
Содержание слайда: 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
№23 слайд
![Specific Examples Joint](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img22.jpg)
Содержание слайда: 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
№26 слайд
![Karush-Kuhn-Tucker Optimality](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img25.jpg)
Содержание слайда: 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
№30 слайд
![Solving MLCPs where I hope I](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img29.jpg)
Содержание слайда: 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](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img30.jpg)
Содержание слайда: 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.](/documents_6/0cbe80cd8a75d871042b3b9a6998aad1/img31.jpg)
Содержание слайда: 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!
Скачать все slide презентации Lemkes Algorithm: The Hammer in Your Math Toolbox? одним архивом:
Похожие презентации
-
Extracurricular study in mathematics, 7th grade
-
General problem of mathematical programming
-
Discrete mathematics. Sets
-
Mathematical Induction
-
The Gilbert-Johnson-Keerthi (GJK) Algorithm
-
Методы и системы компьютерной математики. Преобразование Фурье и Лапласса в системе Mathematica,maple,mathcad
-
Russian mathematician. Sofia Kovalevskaya
-
Discrete mathematics. Probability
-
Mathematics for Computing. Lecture 2: Logarithms and indices
-
Mathematics for Computing 2016-2017. Lecture 1: Course Introduction and Numerical Representation