MIT 6.854 Spring 2016 Lecture 12: From Separation to Optimization and Back; Ellipsoid Method

preview_player
Показать описание
Recorded by Andrew Xia
  1. Andrew Xia
  2. 6.854
  3. mit
  4. ankur
  5. moitra
  6. ankur moitra
Рекомендации по теме
MIT 6.854 Spring 0:59:17

MIT 6.854 Spring 2016 Lecture 3: Consistent Hashing and Random Trees

University of Texas 0:19:27

University of Texas at Austin 2014 Commencement Address - Admiral William H. McRaven

MIT Hacking Medicine 0:02:38

MIT Hacking Medicine 2019 Post Hack Showcase

New Jersey are 0:01:00

New Jersey are you ready? TO RECEIVE THE MINISTRY OF PROPHET VICTOR KUSI BOATENG!

Recent Advances in 1:02:38

Recent Advances in FPT and Exact Algorithms for NP-Complete Problems

Celebration of Mike 0:37:12

Celebration of Mike Stonebraker #8 - Students (Magda Balazinska, Andy Pavlo)

Meet MCB: UIUC 0:02:59

Meet MCB: UIUC PhD student Yiquan, Biochemistry

Nmap.exe Demystified: The 0:30:32

Nmap.exe Demystified: The Ultimate Network Discovery Tool Part 1

2020_05_12_Jonathan Home: 'Quantum 0:50:07

2020_05_12_Jonathan Home: 'Quantum computing with trapped ions'

lecture 15: interior 1:15:02

lecture 15: interior point methods 1

20160913 introduction 0:57:56

20160913 introduction

NICO101 - Mac 0:03:43

NICO101 - Mac OS X Anaconda Installation

Awakening Our Democracy: 1:38:40

Awakening Our Democracy: Affirmative Action

MAX BILL, JOSEPH 1:02:36

MAX BILL, JOSEPH MARIA OLBRICH | ICARCH 2022

'Fault tolerance made 0:43:06

'Fault tolerance made easy' by Uwe Friedrichsen - Coding Serbia Conference

Physics Daily Practice 0:42:05

Physics Daily Practice Paper (DPP) Series | Physics Practice for NDA/AirforceXY/Navy 2021 | RS Jyani

Applying data science 1:03:01

Applying data science in healthcare with Muhammad Mamdani (Unity Health Toronto)

Комментарии
Автор

00:00 - 18:20 setup for ellipsoid method
18:20 - 25:20 ellipsoid method idea and definition of ellipsoid
25:20 - 35:00 ellipsoid algorithm
35:00 finding ellipsoid in (k+1)th iteration
43:30 - 49:57 claim 1 and proof
49:57 - 54:50 claim 2 and proof
55:15 - 1:11:15 general case E(a, A)
1:11:15 - 1:18:00 reduction from feasibility to optimization

aleksagordic
Автор

Great lecturer - this is a nice primer before reading the paper by Grötschel, Lovász, and Schrijver.

J-gv
Автор

For the guys out there trying to learn ellipsoid method, it being historically the first polytime method for solving LPs, let me point out a little tricky detail.
The lecturer proposes reducing optimization to feasibility via the joint feasibility LP. That seems pretty slick at first, but remember, that in the generic case, the joint feasibility LP will have a zero-dimensional polytope made of a single point (x*, y*). Do you know what happens to ellipsoid method when your polytope is zero-dimensional?

nkt
Автор

The statement of the ellipsoid algorithm starts at 20:00

starklitho