# Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 11

Stanford Online2024-03-21

Stanford#Stanford Online

775 views|4 months ago

ðŸ’« Short Summary

The video covers various topics related to experimental design, statistics, and optimization problems. It discusses the incorporation of student solutions, binary hypothesis testing, randomized detectors, experiment design, matrix transpose, integer problems, probabilities, and geometric problems. The segments delve into minimizing errors, signal-to-noise ratio, and ellipsoid volume calculations. The importance of strategic decision-making, experiment optimization, and complex mathematical concepts like polyhedra intersections and convex optimization problems is emphasized. The video concludes with discussions on approximating convex sets, norms in RN, and different types of centers in mathematical problem-solving.

âœ¨ Highlights

ðŸ“Š Transcript

âœ¦

Utilizing student solutions to enhance personal work without giving credit.

02:34Validating main points in student solutions and incorporating superior ideas into own work.

Expressing gratitude to contributors of valuable insights.

Exploring binary hypothesis testing in statistics and its complexity with multiple distributions and hypotheses.

Making informed guesses based on observations and implementing a randomized detector policy.

âœ¦

Minimizing false positives and false negatives using detector optimization.

04:52Scalarization with a factor Lambda determines the weight on each type of error.

Trade-off curve illustrates the relationship between false positives and false negatives.

Analytical solution known since early 1900s with detector at top of curve having zero false positives.

Different types of errors are considered and weighted based on Lambda factor.

âœ¦

The concept of randomized detectors in experimental design.

09:06Non-deterministic detectors introduce uncertainty and potential inconsistencies.

Linear measurements and normalization in AI are crucial for accurate results, focusing on signal-to-noise ratio.

Estimation process involves least squares and covariance matrices for unbiased data analysis.

âœ¦

Importance of Experiment Design and Sensor Selection.

11:35Choosing sensors with high signal to noise ratio is crucial for accurate data collection.

A small confidence ellipsoid is desired for precise estimates in experiments.

Different methods of experiment design can lead to varying outcomes.

Optimal results in experiment design rely on selecting the best sensors available.

âœ¦

Importance of Matrix Transpose and Experiment Design in Statistics.

15:47Signal-to-noise ratio is crucial in experiment design, as well as dealing with non-invertible matrices.

Careful planning based on observations and energy budget is essential for drone operations.

Objective functions exhibit symmetric properties in specific setups.

Emphasis on the critical role of experimental design and decision-making in statistical analysis and practical applications.

âœ¦

Discussion on integer problem related to experiments and sensors.

19:20Explanation on relaxing constraints by dividing fractions to expand the feasible set.

Practical advice on selecting experiment types based on budget limitations.

Emphasis on convincing others of the sophistication of relaxation techniques, with references to quantum mechanics.

Conclusion with a focus on probabilities and the utilization of lambdas in experimentation.

âœ¦

Importance of rounding probabilities and adding them up in experiment design.

23:00Minimizing volume of confidence ellipsoid through strategic choices and constraints is crucial.

Consideration of integer constraints and their impact on volume calculations is highlighted.

Demonstrating the feasibility of achieving a specific volume outcome within constraints through strategic decision-making.

âœ¦

Importance of Experimental Design and Combinatorial Problems.

26:55Understanding invertibility is crucial for interpreting variables accurately.

Minimizing determinants and dealing with non-invertible matrices are key considerations.

D-optimal designs play a significant role in minimizing confidence ellipsoids.

Practical applications of these concepts in experimental settings are complex and require attention to detail.

âœ¦

Overview of experiment design and optimal experiments in minimizing objective functions.

30:18Relationship between experiment design and finding the minimum volume ellipsoid for desirable experiments.

Importance of high signal-to-noise ratio (SNR) options in experiment selection.

Process of shrinking an ellipsoid to choose high SNR options.

Significance of selecting measurements that are closest to orthogonal for different information.

âœ¦

Optimizing experimental design with cost and budget constraints.

34:04Linear constraints are introduced to optimize experimental design considering factors like preserving drone battery life.

Discounts for subsequent experiments are explored as a way to manage costs in experimental design.

The complexity of experimental design beyond linear measurements with Gaussian noise is emphasized, involving sequential decision-making under uncertainty.

Sophisticated approaches are needed in experimental design to address challenges beyond basic linear scenarios.

âœ¦

Determining the minimum volume of an ellipsoid involves maximizing the log determinant.

37:29The volume is a constant times the determinant of w to the power of minus one-half.

Solving geometric problems involving polyhedra includes determining their intersection and feasibility.

Finding the minimum distance between two polyhedra is classified as a quadratic programming (QP) problem.

The segment emphasizes the application of mathematical concepts in solving practical problems.

âœ¦

Basic geometric problems related to polyhedra and intersecting polyhedra are discussed.

40:45The segment covers determining distances between polyhedra and representing them by vertices.

Feasibility problems are solved through LP, emphasizing simple concepts for understanding polyhedral intersections.

The idea of minimum volume ellipsoid for covering a set in RN is introduced, highlighting the importance of these basic geometric concepts.

The relevance of these concepts in practical applications like robotics is mentioned, setting the stage for more complex geometric problems to be discussed later in the video.

âœ¦

Parameterization of ellipsoids is crucial for convexity.

44:55The log likelihood in Sigma must be concave.

Symmetric and positive definite matrices are essential for creating ellipsoids.

Invertibility is important, along with dealing with non-symmetric matrices.

Orthogonal transformations impact matrices, preserving properties like positive definiteness and symmetry.

âœ¦

Minimizing the volume of an ellipsoid to cover a given set C is an optimization problem.

51:13The problem is convex and can be transformed into a manageable form.

Example with a finite set of M points demonstrates effective solution to the convex problem.

The key takeaway is converting the ellipsoid volume minimization problem into a practical and solvable format.

âœ¦

Ellipsoidal peeling as a method for removing outliers.

53:38Involves finding the minimum volume ellipsoid covering data points and identifying outliers touching the ellipsoid.

Outliers are removed and process is repeated until desired outcome.

Removing outliers based on number of points satisfying a condition.

Importance of careful consideration in selecting candidates for removal.

âœ¦

Discussion on removing constraints in a tight scenario to optimize solutions.

56:50Ideas include removing specific outliers or constraints, such as the five tightest constraints or maximizing volume differences.

Concepts of dual variables and Duality in mathematical problem-solving are discussed.

Practical applications of minimum volume ellipsoids and convex problems are highlighted.

Importance of street fighting knowledge in problem-solving approaches is emphasized.

âœ¦

Finding the minimum volume ellipsoid to cover a polyhedron using linear inequalities.

59:57Challenges include solving in higher dimensions due to exponential increase in vertices.

Determining if an ellipsoid covers a polyhedron is NP-hard.

Introduction of the dual problem involving finding the minimum volume ellipsoid covering a set C.

Discussion on the intricacies and difficulties of these mathematical problems.

âœ¦

Finding the maximum volume ellipsoid within a set is explored, with scenarios based on the set being an ellipsoid or a polyhedron.

01:02:37The tractability of solving the problem is discussed, considering inequalities or vertices as methods.

Parameterization through an affine mapping and the significance of the determinant of B in maximizing volume are explained.

The challenges of a convex optimization problem with a complex supremum or infimum that is not easily tractable are highlighted.

âœ¦

Discussion on convex optimization problems and their tractability.

01:06:58Previously tractable problems are now shown to be false, leading to new insights.

Social setting plays a role in determining the perception of tractability, emphasizing audience knowledge.

Finding the maximum volume of a polyhedron described by inequalities has practical applications.

Convex bounded sets with non-empty interiors have intriguing implications in mathematics.

âœ¦

Approximating Convex Sets with Ellipsoids.

01:11:58Any convex set can be approximated within a factor by an ellipsoid.

Shrinking or expanding the ellipsoid around the set by a certain factor accurately approximates the set.

The concept is demonstrated using the example of a triangle and its Ler John ellipsoid.

All convex sets can be approximated by ellipsoids within a factor, with Simplex in R being the hardest to approximate.

âœ¦

Approximating Norms in RN with Ellipsoids and Quadratic Norms.

01:14:21Replacing any norm in RN with a quadratic norm symmetric with error no more than the fourth root of n is discussed.

Importance of approximating norms with quadratic norms, particularly in control systems for airplanes, is emphasized.

Linear quadratic control and its relation to quadratic norms are explored.

Centering in linear programming and finding the largest ball within a polyhedron, known as the Chebyshev Center, is briefly mentioned.

âœ¦

The segment introduces various types of centers in mathematics, including yield center and probability center.

01:18:34It also explains the concept of the analytic center, which involves maximizing the product of margins in a set of inequalities.

The analytic center is not a center of a geometrical object but of a set of inequalities.

Future lessons will cover the computation of the analytic center, with viewers expected to write code for it in about two weeks.

00:05okay we'll go ahead and start so I guess

00:08congratulations for uh surviving the

00:10midterm I suppose that was last week but

00:12still um I I should probably uh say that

00:16um oh I was also uh gonna let people

00:20know that um like for examp on on on

00:24things like the midterm and other times

00:26too we are not proud and we steal

00:29student solution just just to let you

00:31know right so we we go into it I think

00:33there was one where we asked for some

00:35DCP representation of like what inverse

00:38product or something um we' figured out

00:40two or three of them and actually

00:42amongst you you found several others and

00:44we just happily put them into the

00:45solutions just just so you know so so we

00:49sometimes we give a heads up like you'll

00:51see that if you look at a homework

00:52solution because the homework problem

00:54started life as maybe a final exam

00:56problem and we sometimes we'll say

00:58here's our solution and you say here's a

00:59far better solution submitted by a

01:01student so we'll sometimes say that but

01:03I just want to make it public that we we

01:06just we steal your Solutions if they're

01:07better than ours happily what's that do

01:10we get paid no not really no no it's an

01:12honor right if you if you look at the

01:14solutions and you go like whoa that

01:17that's my Sol and just think of it right

01:19students generations of other students

01:21will look read their homework solution

01:22and look down there and they're like

01:25whoa that's like who would have thought

01:27of that have my name on uh ah yeah no I

01:31we we haven't we don't attribute yeah

01:33yeah we don't we don't we we

01:35theoretically we know right because it's

01:37some somewhere in some email it's it's

01:39like AATA for the book right oh by the

01:42way and actually we've people in the

01:43class have

01:44found several things that were just like

01:47wrong so I mean they're they don't the

01:50main points are still valid but uh we're

01:53I think we're at two and growing so

01:55that's pretty good too because people

01:56have been looking at it pretty carefully

01:57for a long time so and they just so

02:00anyway so thanks to those people as well

02:04so okay um let's see any other were

02:08there any other announcements that that

02:10that was it good um let's see any any

02:13questions about uh midterm finals where

02:17we are what we're doing all that kind of

02:21stuff okay that's a that's that's a

02:23that's a no so okay good we'll continue

02:28um so uh we'll we'll continue last time

02:30we looked at this uh B binary hypothesis

02:34testing right which is I mean in some

02:36ways it's the essence of kind of like

02:38all of Statistics right it's it's you

02:41you have uh in this case you have just

02:42two distributions You observe one sample

02:45and the question is you know which

02:47distribution generated it one or the

02:48other um and if you make that more

02:51complicated uh and have distributions

02:53not on a finite number of points but you

02:55know on you know RN or something like

02:57that or more complicated things and you

03:00have more than two hypotheses then you

03:02know that's kind of most of Statistics

03:04right there but anyway so this is a very

03:06simple uh uh

03:08setting and so the question was to make

03:12a guess about whether an observation

03:15right and an observation is is like a

03:17number like three that's an observation

03:19right that's that's what happened and

03:22then your goal is to try to figure out

03:24did it come or guess in some intelligent

03:25way did it come from this distribution

03:27or this one right and um we looked at

03:31that you you end up with you have this

03:33idea of a of a a randomized detector

03:36it's a policy that says When You observe

03:39this outcome which distribution do you

03:42attribute it to right and if it's and

03:45that you do with a you know a 2 by uh n

03:49Matrix where the columns give you the

03:51probabilities that you announce it came

03:53from you know P or Q the two different

03:56distributions right so that that's how

03:58that works um

04:00if those are all zeros and ones then

04:02it's deterministic and you end up you

04:04write this down as a by Criterion

04:08optimization problem that you there's

04:10two things you care about uh the

04:12probability of a false positive and

04:14that's pfp and the probability of a

04:17false negative right and so and these

04:19are just you just get these from matrix

04:21multiplication and the point is that

04:22each of these is a linear function in t

04:25t is what describes your detector right

04:30um anyway so this this problem it turns

04:33out is actually really uh quite

04:36straightforward uh to solve if you

04:38scalarized it so you say that Lambda now

04:41is the the amount is the factor that

04:44relates how much I care about you know

04:46false positive versus false negatives or

04:48something like that then it turns out it

04:50just has a super simple solution that

04:52looks like this um Lambda is that

04:55waiting factor for example if it's one

04:57it says I it says actually I just just

04:59want to minimize the number of Errors

05:02period that would be Lambda equals 1 and

05:04then the solution is like analytic and

05:06it's been known since I don't know

05:07probably 1900 or something and it

05:09basically says in that case and it's

05:12completely reasonable it says if Lambda

05:14is one and you want to minimize say the

05:16total number of Errors you would say

05:19well uh what what I would do is if I

05:22will choose the distribution which had

05:24higher likelihood and we'll see that in

05:26another context or we've already seen it

05:27in the context of Maximum likelihood so

05:29that's an example of

05:31that and the Lambda allows you to put

05:33weights on the two different types of

05:35Errors which I think are called type one

05:37and type two error but I can never

05:38remember which is which and just look it

05:40up every time I need to know actually

05:42usually I try to avoid situations where

05:44people are saying things like type one

05:46and type two error so I usually walk out

05:48of the room but if I am forced to I will

05:50I will just look it up to figure out

05:51what it is okay um now what's

05:55interesting is even at this like super

05:57simple problem you can get into weird

05:59things very interesting stuff like this

06:01suppose you say I want to I want to

06:02minimize the maximum of my false

06:05probability and my f false positive and

06:07false negative errors right um that will

06:11get you something that's Pito optimal

06:12because Max is a monotone function of of

06:16the two it's a monotone mapping from the

06:18two criteria into one so that's a that

06:20is a scalarization it's not a linear

06:23scalarization which is what's normally

06:24employed but it's a scalarization right

06:28um and

06:30this that's a that turns out that's an

06:32LP and the solution is usually not

06:35deterministic right so here's an example

06:38um so here we go uh let's see here

06:42here's the trade-off curve of false

06:44positive versus false negative that's

06:46this thing this curve here and oh yeah

06:49um Somebody explain uh the point at the

06:52top first of all let's talk about what's

06:54really good about that

06:56detector what what's the probability if

06:59we use the detector up there at one uh

07:01that this this point right here this one

07:03um first let's let's let's say the good

07:06part about it what's the good what what

07:07is the probability of a false positive

07:09for that

07:10detector zero right okay fine right by

07:14the way what does that detector

07:15do it just returns like negative every

07:19time right so it's kind of silly um but

07:21the good news is it does have a very

07:22very low false positive

07:24rate okay so um you know and that's

07:29anyway each of these uh correspond the

07:32these correspond to uh likelihood ratios

07:36um between the entries there right it

07:38it's what is your what what what if in

07:41fact you can even take Lambda and and

07:43put Lambda around here and ask what

07:45happens if you have a certain Lambda

07:47like that the optimal Point you're going

07:49to find is going to be like here or here

07:51or here right um the minax one is one

07:56you can you can figure out what that is

07:57this is the x equals y line

07:59and the Minimax one you find by simply

08:01taking this rectangle or square if this

08:04was done correctly with axes which it

08:06was not um and you simply grow it until

08:09it touches this curve and that's going

08:11to be right here and so it turns out if

08:13you wanted to minimize the maximum of

08:15your false probability false

08:17positive and your false negative you

08:20would do you number one you'd have a

08:22deter you'd have a non-deterministic

08:24detector which is weird because you'd

08:25say oh the outcome was you know uh I

08:28don't know let say a two and you'd go oh

08:31yeah okay well then that's definitely

08:32like P right and then you'd then you

08:35come back later and say the outcome was

08:36two and you'd say I don't know let me

08:38check just a minute oh it's Q everybody

08:40got this so it's a little bit odd that

08:43you would have a randomized detector but

08:45uh this comes up in a bunch of things by

08:47the way a randomized detector you can

08:48think of as a

08:50relaxation of the original the original

08:52sensible problem is to say no if there's

08:55an outcome you have to commit to one of

08:59these two distributions you can't do

09:01something weird and and have an

09:03inconsistent weird probabilistic thing

09:05that's right

09:06so okay so all right so that's very baby

09:10example um okay last Topic in in this

09:14section is going to be experiment design

09:16um this is actually super interesting

09:19also like super useful um so it's the

09:22setting is we have a bunch of linear

09:24measurements here so we have linear

09:25measurements um and AI you can think of

09:29as the measurement Vector um wi uh we're

09:34going to normalize those to be to have

09:36all the same uh standard deviation which

09:39is one right and so what it means you

09:42know roughly speaking the size of a is

09:45something like and this is dialect but

09:47signal to noise ratio okay so uh right

09:51because of if a is gigantic right then

09:54it says that the AI transpose X is tells

09:57you a lot and then I add this noise it's

09:59like plusus one like who cares right if

10:02AI is small it means that's a pretty

10:04crappy

10:05measurement so that that's the idea

10:07there

10:09um now if I actually take if I get a

10:12bunch of these measurements these Yi and

10:14I ask I asked someone to guess X and you

10:17know the maximum likelihood which is

10:19just nothing but least squares the

10:21estimate it's just least squares so you

10:23just get this right it's the sum of ai

10:25ai transpose that's this thing inverse

10:28time this right and the error which is X

10:32hatus x as zero mean uh so that's an

10:35unbiased um that's an unbiased estimate

10:38um and has a covariance which is given

10:41by this Matrix here okay and if you

10:43wanted to work out a confidence

10:45ellipsoid for that again assuming

10:47because these are all gaussian this is

10:49gaussian the G it would look like this

10:51it would say it's a set of X which are

10:53centered at your estimate X hat and the

10:56shape is given by this this uh this

11:00Matrix here and so for example I don't

11:03know so that would be the that would

11:04give you and beta is going to be

11:06determined by you know uh actually it

11:08would be something like the inverse

11:10distribution of a Ki squar random

11:12variable with some number with the

11:13appropriate number of degrees it doesn't

11:15matter though because that's that's how

11:17you would get beta and that would say

11:19the thank you for the measurements this

11:22tells you you know with 90% probability

11:24you're in this uh you're in this

11:27ellipsoid right and if I say 99% of

11:31thing then beta just gets bigger here so

11:33that that's all that happens right

11:35okay so experiment design is this

11:38problem uh so I have a bunch of

11:41candidates V1 through VP you should

11:43think of these as possible measurements

11:46or experiments you can you can make

11:50right so that that's what they are um

11:53and then I want to choose

11:55M

11:57AIS which are among this pallet of of

12:02possible experiments I can carry out

12:04right so in other words I have a bunch

12:05of sensors and uh and what I can do is

12:10you'd say pick pick which sensors you

12:13should use in fact even pick the

12:15sequence right which you should use to

12:18to to actually get the best estimate the

12:21best estimate is a bit tricky because

12:23we're going to measure everything in

12:24terms of this this ellipsoid right and

12:27we want this sorry this positive

12:29definite Matrix right and what we really

12:31want is this positive definite Matrix to

12:33be small which by the way is the same as

12:35saying that the sorry yeah we want this

12:37to be small which is saying that the

12:39confidence ellipsoid is small right so

12:42that's what you do so in other words now

12:44the problem with that is this is exactly

12:46an ordering the positive semi-definite

12:48matrices which is not linear right so

12:51it's completely reasonable if you came

12:53up with an experiment design and you

12:54came up with one we looked at your your

12:57your e like E1 1 and E2 and they were

13:01not comparable so in some directions

13:03you're better and in other directions

13:05you're better that that can and does

13:07happen everybody got it so so we're

13:09going to have to

13:12scalarized definite Matrix being small

13:15and and there's lots of different ways

13:16to do it each one is going to lead to a

13:18certain named type of experiment design

13:21so let me discuss a couple of things

13:23quickly um earlier I said that uh the

13:27size of a is something like like let's

13:29say the torm that's something like a

13:31signal to noise ratio right if AI is

13:33gigantic that's really good that's a

13:35good measurement right so let me ask a

13:38question here I if fact have a

13:40proposal here's my experiment design

13:42method ready um I will find the largest

13:45the largest VI in magnitude someone says

13:48why are you choosing that and you go of

13:51the of the sensors or the experiments

13:53I've been offered that's the one with

13:55the highest signal to noise ratio make

13:57sense okay and then they'd say ready

13:59ready for my experiment design just do

14:02that use suppose V7 is the largest in

14:05magnitude of these then you just do that

14:07the whole way all way and someone says

14:08why are you doing that and you go why

14:10would I use anything other than the

14:13experiment that has the highest signal

14:15to noise

14:16ratio everybody got that okay it's I

14:21well okay you're probably not going to

14:23fool for it but I I'm actually pretty

14:25good at making up a good I could tell

14:27stories around that and all sorts of

14:29other stuff I bet I could get some

14:31people to go for that okay any

14:35comments you want the worst situation

14:38not the best

14:42situation well I mean uh no I just told

14:45you my policy my my policy is I'm going

14:47to take V7 over here because it's the

14:49one with the largest magnitude right and

14:53then I'm just going to all my AIS are

14:54going to be that you have a suggestion

14:57any comment on it

14:59would there be some like bias in One

15:02Direction no you know all of these are

15:05kind of unbi yeah um let me ask one

15:09question uh what is let's talk about

15:12this Matrix if all the AIS were the

15:16same what's that Matrix look

15:21like what is

15:25it identity it's what the whatever A7

15:30and then A7 square and an identity

15:32Matrix I don't see any identity M what's

15:36that no yeah so I just this this thing

15:38would become sum from IAL 1 to M V7 V7

15:42transpose otherwise known as M times V7

15:46V7

15:47transpose anybody got a comment about

15:50the Matrix V7 V7

15:52transpose it's what it's rank one right

15:56okay so if I just always use the the

15:59experiment with the high if I always

16:00make a measurement which is the highest

16:01signal to noise

16:02ratio then uh we got we got a kind of a

16:06problem here because this Matrix is is

16:09not invertible it's singular right and

16:12so I mean we could talk about e inverse

16:15if you like it's kind of silly I can

16:16tell you what it would be it's our error

16:18Co variance it'd be really good in the

16:21direction V7 because I blew my entire

16:24every experiment I ever did was was the

16:26same experiment right but in

16:29What In N minus one Dimensions if yeah

16:31okay in N minus one Dimensions I got no

16:33information of any kind whatsoever and

16:35so my confidence ellipsoid is like

16:37infinite in those directions everybody

16:39make

16:41sense yep okay so that's it okay um all

16:46right so uh oh the first thing to to

16:50there's another thing we can observe

16:51here right um here we don't have to

16:55choose the sequence right because the

16:57outcome doesn't depend on the sequencing

17:00right so in other words now this there

17:03no difference if someone says please do

17:05the following use V1 four times then V3

17:10and then here's the trick switch back to

17:11V1 four more times and then V4 everybody

17:14got what I just said okay so it turns

17:16out doesn't matter if you look at our

17:19objective function here it's symmetric

17:21you can permute them any way you like

17:23right by the way this is

17:25completely false except in this inedibly

17:28simple gaussian setup right in in other

17:32cases you want to do design of

17:33experiments it's it's a it's a whole

17:36sequence and it depends on Al it depends

17:38on what you've observed so far right in

17:41other words the best if you're if we're

17:43flying a drone and someone says which uh

17:46we have an energy budget which sensor

17:49are we going to use right it depends on

17:52all sorts of stuff um but in this

17:54gaussian model actually it doesn't so

17:57okay so it it really only depends I only

17:59have to tell you how many of my my total

18:01budget is M experiments I just have to

18:03divide M up across these the the pallet

18:06of potential experiments that I've been

18:08offered okay so I if I had 22 I could

18:11say I want to do four of these seven of

18:13those three of these and blah blah blah

18:15and my numbers better add up to 22

18:17that's all we have to do

18:19okay so we'll write it this way um and

18:23here we have an integer problem right

18:25because the M's are integers actually

18:28here MK is the number of times I'm going

18:30to I'm going to use experiment K or

18:33sensor K right that that's what it is um

18:37and then this thing just looks like this

18:38right uh okay so this is all all cool um

18:43let's see this is even what this is

18:47actually if M were if M were not an

18:49integer but a real number positive real

18:51number this thing would actually be uh K

18:54convex where K is the PSD cone right so

18:58so this is this would be cool right um

19:02but it's not m is an integer okay and

19:04now by the way this comes up in lots and

19:06lots of settings where there's an in

19:08there's an integer or something like

19:09that and then so you do I mean it's kind

19:11of one of the themes is you do uh

19:13relaxation right so the relaxation is

19:17you know what uh I divide the M's by

19:20capital M so so instead of working with

19:23M1 I'm going to work with M1 / capital M

19:26and then you're saying what is the fr

19:28fraction of the total number of

19:29experiments you're going to do that are

19:31going to use in fact M1 m is the what is

19:34the fraction when you use experiment

19:35number

19:36onebody make sense okay so um now if I

19:42do that we still have the constraint

19:44that those fractions are integer

19:46multiples of 1/ M okay so now what we're

19:50going to do is we're going to relax it

19:52right so we're going to Simply ignore

19:55that last constraint that's that's

19:57that's a typical relax ation right

19:59relaxation in general just means you

20:01made the feasible set bigger right that

20:05that's all it means right uh and so we

20:07do that um okay now this this is

20:10actually it's kind of cool if you know

20:12so we're going to relax it like this um

20:15and then there's all sorts of things you

20:17can do with this so we'll we'll talk

20:18about solving it but what's going to

20:20come up is you say actually what I'm

20:22really going to do is I'm going to I'm

20:23going to choose for you the fractions of

20:27each of the experiment types that you

20:29should use whatever your budget is right

20:33now maybe it's not going to fit into the

20:34integers but if m is big I don't think

20:36this is a problem right and then so and

20:38then I'll I'll I'll give you lots of

20:40hints about what you could do

20:42um what you can do first you go back to

20:45the person who said do the experiment

20:47design and you'd say yeah okay what's

20:49your budget and they'd say 57 and they

20:50go great you should do you should use

20:53experiment number two 6.45 times and

20:57they would go like

20:58what does that mean like that means

21:00nothing I can't use exper I can I every

21:03time I I'm allowed to choose one of the

21:05experiments and I can't do it 6.4 five

21:07times everybody see that okay this point

21:09and this is just like very practical

21:10advice for all of you as when you uh

21:13when you become part of the 364a

21:16diaspora uh here here's here's what

21:18you're G the first thing you do is you

21:20try to convince the person that your

21:23relaxation is actually much more

21:25sophisticated and you'd say oh yeah look

21:28you don't tell me about six or seven I I

21:30don't care about that this is much more

21:32sophisticated you can drop things like

21:34you can make reference to quantum

21:35mechanics that sometimes helps right

21:37because you'd say like look it's not

21:39like you just choose an experiment each

21:42time you know anyway you could say this

21:44is really like a probability these are

21:45in fact the lambdas are going to be

21:46probabilities and then it says here's

21:48what you should do every time you should

21:49roll the dice with probability Lambda

21:52and if 13 comes up congratulations you

21:56should do Experiment 13 everybody

21:58following what I'm saying anyway some

22:00people actually like fall for this it's

22:02actually kind of amazing right and you

22:04you mention you know and you you Mumble

22:07about quantum mechanics and things like

22:08that it's much more sophisticated it's a

22:09probabilistic thing and you can hint at

22:12other things like Hey do you remember

22:13like Matrix Games do you remember how

22:15there's like not generally not an

22:17equilibrium and so you have to have a

22:19what do you call it a a uh what's it

22:21called a randomized policy and they

22:24would go yeah and you go well it's just

22:26like that right anyway then anyway

22:29that's fine um but supposing in fact you

22:32really had to do uh someone said no dude

22:36you're the Drone is flying and you have

22:39a a budget of 120 experiments so I need

22:42integers right so someone tell me what

22:46would you

22:51do what would you do FR thing R yeah do

22:55you mean rounding yeah yeah you yeah

22:58here's what You' do you'd find your

22:59lambdas they're going to be it's going

23:00to be sort of the it's a continuous you

23:03know probability that you choose

23:04experiment or a fraction right and you

23:06just round them right by the way if you

23:08round them and then you add up the

23:10rounded things and they come up to 121

23:12what do you do

23:13then just reduce one okay that's what

23:17you do everybody following this and I'm

23:18not kidding with this and you say that's

23:20my experiment design and they would say

23:22awesome and they would say is that is

23:26that actually the one that is going to

23:28minimize the is that going to give me

23:31the is that going to be the best one is

23:32it going to minimize this uh confidence

23:36ellipsoid what's your what's the honest

23:38answer to

23:40that

23:42no probably would work that's that's

23:45fair that's that's one way to say no but

23:47yeah so you'd say you'd say does it

23:49solve the they'd say does it actually

23:50solve this problem and you'd say I don't

23:52really know um but what can you what can

23:55you do to give some evidence that your

23:58rounded one is not so

24:04bad we do the Dual problem yeah yeah you

24:08don't even need the Dual because this

24:09was a relaxation so what you do is we'll

24:12wait until this will make more sense

24:14when we scalarized this right so let's

24:16say for example what happens is you end

24:18up with the volume of the confidence

24:20ellipsoid and someone says does that

24:22choice actually minimize the volume of

24:24the confidence ellipsoid you go you

24:26actually your answer was perfect

24:27probably you'd say it's very close and

24:30they'd say well how do you know that you

24:31go well because when I remove the

24:34constraint that these things are

24:35integers and I solved this problem I

24:37found that the log of the volume was

24:3912.6 and you'd say nobody could do

24:42better than that that's if we ignore

24:44this silly constraint that these things

24:45are integers and you say my volume my

24:49log volume was 12.7 when I rounded

24:53everybody got that then it's kind of

24:55it's done right then then you're just

24:57done because you just say I I can show

24:59nobody can have a volume did I get that

25:01right I did get it right no one can have

25:02a volume less than 12.6 that's something

25:06you can but but we got one that has

25:07volume log volume 12.7 okay ever make

25:10sense okay all right so this is relax

25:14experiment design um actually we will

25:16get to the Dual of this very soon

25:19yes of M be much than the number of

25:22experiments sorry where here M much

25:25mucher than P the Assumption assume what

25:28why why the experiment design say assume

25:31M much much than p and then using Lambda

25:34K isal MK by uh you mean over here yeah

25:38why is that there uh let yeah let's let

25:42let's see why oh the idea is I wanted I

25:44I wanted these numbers to be reasonably

25:48uh to be not too grainy I I want if I

25:50round it I want to be able to get

25:52something that's close to an integer I

25:54mean you you don't even need this right

25:55the the first one that doesn't matter

25:57right um yeah now when you get down when

26:01went to a well okay let's let's try this

26:04what if I said you have three

26:07experiments

26:09period can we solve that

26:13problem I mean it depends how big

26:16whatever it is p is Right p is the

26:18number of p is the number of options

26:21right let's suppose p is 20 or something

26:23and I tell you no you have three

26:25experiments tell me what to do

26:28can we solve that just try all the

26:31combination yeah you try all it's like P

26:32cubed you just do you try all

26:35combinations or whatever it's not even P

26:36cubed it's less a lot less than that

26:38right P cubed over six right or

26:40something like that right you try all of

26:41them you find out okay so that's so for

26:44small ones we can actually solve the

26:45actual you know and that's actually when

26:48you get into things like design of

26:49experiments these are like grainy and um

26:52you know they're kind of combinatorial

26:53right and these are these are tricky

26:55yeah so Professor perhaps I didn't

26:57understand and what you me before about

26:59like e not being invertible but doesn't

27:02this not require that e is invertible

27:05like because you can make a solution

27:07where M1 is equal to M yeah yeah so uh

27:11yeah so there's you're going to have a

27:13problem though let me show you what the

27:14problem is um that when this is non

27:17invertible we we're going to interpret e

27:20as being basically infinite in those

27:24directions and we've asked you to

27:26minimize it now by the way when we

27:27scalarized it we're going to be cool

27:29right because we're going to have a log

27:30of determinant or a trace and all that

27:32kind of stuff and the problem is then

27:34you'd say if you if you do that you're

27:35going to come up with plus infinity yeah

27:38and we'll so we'll get to that in a

27:39minute yeah but

27:44that's is making it undesirable for it

27:47to be yes in fact in this case uh

27:49infinitely undesirable so what we'll do

27:51is we'll say that if this thing is in is

27:54invertible uh we'll say then e is

27:56infinitely undesired by the way when we

27:58scalar that's going to happen

27:59automatically in a minute okay so okay

28:04um okay so now you have different na

28:06names right uh and these are like famous

28:09names so D optimal you know you know duh

28:12is going to be the determinant right so

28:15if you minimize the log determinant and

28:17that's actually beautiful basically it

28:19says minimize the volume of any of a

28:23confidence ellipsoid at some level right

28:25because that's what it means right and

28:27by the way here your question we can be

28:29very specific um if I choose let's say

28:32Lambda equals

28:33E1 that means I'm simply only going to

28:36do experiment one then uh this Matrix is

28:40you know not invertible I can take the

28:41the minus one and put it out here but

28:43then log determinant of a of a non-

28:47singular Matrix is going to be minus

28:49infinity of a singular matrix it's going

28:51to be minus infinity and when I make it

28:53when I flip the sign I get plus infinity

28:56and it's like nice choice of experiment

28:58design but your objective is infinity

29:01and given that we're minimizing it I

29:02would call that a rather poor design

29:05right so I don't know if that explained

29:07that but okay all right um so that this

29:10is called de optimal experiment you G

29:12have there's whole books on this which

29:13is kind of cool I think but that's okay

29:16um so uh all right um You can actually

29:21work out the Dual problem of this which

29:23is actually a a dual right um and it

29:26turns out out to be something uh that

29:28we're going to talk about uh possibly

29:30even later today but it looks like this

29:32you're going to end up with a maximize

29:34of the log determinant of w w is going

29:36to be like a dual variable um plus a

29:38constant um and then you're going to

29:40have subject to this constant here and

29:43this thing let's just check that that is

29:45in fact a convex optimization problem

29:47with variable capital W right um this is

29:52concave log determinant of a positive

29:54definite Matrix is concave that's a

29:56constant doesn't make any any difference

29:58uh what kind of uh what kind of

29:59inequality is this as a function of

30:03w what is it it's linear it's just

30:06linear inequalities on W it's quadratic

30:09in V's but the v's are given to us those

30:11are the th those are the options for

30:13experiments that we carry out right so

30:16okay and we can actually interpret it

30:18really well this is cool this is an

30:20ellipsoid uh and it's it's centered at

30:23the origin right and this simply says

30:26this thing here says that uh all the v's

30:30are in the ellipsoid right um and so

30:33what this says is here's how you find

30:37this this tells you that there's a

30:38relation between this experiment design

30:40and actually you take your V's uh then

30:44find the minimum volume ellipsoid send

30:45it to the origin that covers them and

30:48there's a close relation to that in fact

30:50there's weird complimentary slackness

30:51would tell you this that the one it

30:53touches when you find this minimum

30:54volume ellipsoid it touches some of the

30:56points those are the experiments that

30:57are desirable we we'll look at some

30:59pictures of that in a minute um here's

31:03one okay so uh so here's here's the

31:07origin right and then here are the

31:10experiments you've been offered I don't

31:11know maybe there's 20 of them like 10

31:13here and 10 here right um and let's see

31:16let me ask a couple of questions

31:20um okay clearly these are more desirable

31:24than these um how come and just roughly

31:30why would why would these why would

31:32these experiments be more powerful than

31:36these have more SNR yeah yeah they're

31:39they're farther from the origin that

31:40means that means VI is bigger it means

31:42the signal noise ratio is higher right

31:44okay um now uh here so here's this is

31:49the minimum volume ellipsoid you take it

31:50an ellipsoid shrink it we'll see how to

31:52do that very shortly you shrink it until

31:54it just touches two and that's this one

31:56and this one and it says that you should

31:58use the high SNR options I mean I'm

32:03right that's what it says and why does

32:04it pick this one and that

32:08one it's in two Dimensions right how

32:12come yeah that's right they're they're

32:15they're you take the two measurement the

32:16two high signal noise measurements which

32:19are closest to orthogonal or they kind

32:22of give you different information right

32:24if you're saying these this is this is

32:26the way you should your radar it says

32:28yeah I would I mean ideally I would love

32:31to have like you know this shot and then

32:33one 90Â° like that right that hasn't been

32:36offered me here right um let me ask a

32:38question what if I shrunk these down to

32:41just a little tiny uh

32:44Arc someone guess what what do you think

32:47actually and I'd put it somewhere else I

32:49mean not not it shouldn't reflect this

32:51thing right but uh suppose I put these

32:55things like up up way up like over here

32:58and I shrunk them down to just a

33:01few what do you think would

33:05happen at some point you probably

33:07wouldn't take two because they don't

33:08have enough different of a view right

33:11and that means that they're not going to

33:13give you so you'd end up picking one of

33:14these you don't want to but you'd pick

33:16it because you need this kind of

33:17diversity to be able to see what it is

33:19okay everybody all all this make

33:22sense okay um so this is this is the the

33:27optimal experiment design it says you

33:29should make these both. five I mean who

33:30knows why because maybe it's symmetric

33:33um but there's a ton of super fun things

33:36you can add to this right so here I just

33:39said these are your measurements right I

33:41could attach to each measurement a cost

33:45and I would say I could give you a

33:48budget in cost right the the cost could

33:51be let's say the energy you use to carry

33:53out that experiment and you had and you

33:56want to you want to preserve your drone

33:58battery life everybody following

34:01this um and that's actually how would I

34:04change the convex optimization problem

34:06to uh adjust how would I change this for

34:10that what would I

34:12do to include a budget there then you

34:17could have all sorts of interesting

34:18stuff you could have you could have

34:20really high signal noise measurements

34:22but they cost a lot of

34:24jewels okay and I'm I mean these are not

34:27made up this is exactly how kind of

34:29things work but um

34:33any yeah would that be a linear

34:36constraint yeah this is a linear it's C

34:38transposed Lambda is less than a budget

34:41it's nothing more right um you could do

34:45other weird stuff um here's one just for

34:48fun let's suppose this is actually like

34:50a drone or something suppose it turns

34:52out that you get a that it's free once

34:54you do one experiment of one type

34:58you get like you get a discount on like

35:00two

35:01others right because you know once you

35:03fly to that place you might as well turn

35:05on your liar and blah blah blah and all

35:07these other things right or something

35:08like that and we can just talk briefly

35:10about that how would you express

35:15that any

35:19uh how would you do that okay put it

35:21this way I'll leave it for you to think

35:23about those are convex constraints and

35:25they start getting really sophisticated

35:28and quite interesting everybody

35:30understood what I just said yeah so so

35:33yeah no you get a it's a weird thing

35:36where you say well if you if you use

35:37that sensor you might as well also use

35:39this one you get a discount could even

35:40be free right so okay I'll just leave it

35:44this way for now um that that yeah okay

35:48I'll leave it we'll just we'll move on

35:49to the next topic okay so let me just

35:52end this by saying the idea of uh this

35:56experiment design

35:57stuff is this is Extreme this is only

36:01for linear you know linear measurements

36:04with gaussian noise right all other

36:07experiment design things get

36:08unbelievably complicated they are

36:10basically sequential decision-making

36:12under uncertainty and things like that

36:14and they start getting really

36:15complicated but for this one case which

36:18is actually kind of it is weird if you

36:20think about it it's well there's a lot

36:21of weird things about gaussians and

36:22things like that but this this basically

36:25says uh it this basically says you can

36:29say ahead of time how well you're going

36:31to do if someone says there's my flight

36:34plan what's going to be how well am I

36:36going to estimate this thing you can

36:38actually say right um ahead of time

36:40before doing it right whereas for other

36:42things you you you can't do that for the

36:44distribution anyway I I won't I just

36:46want to just warn people about that

36:48okay I'm going to skip the derivation of

36:51the duel um and we'll go on to the next

36:53topic oh question yeah quick question

36:56yeah the Dual problem how do we get the

36:58minimum volumeid Oh you mean how do you

37:01mean the interpretation of it I mean it

37:04seems like a

37:05maximization yeah well uh so I have to

37:07ask you what is the volume of this

37:10ellipsoid that's going to be kind of our

37:11next topic what's the volume of this

37:14ellipsoid I mean right okay let's let's

37:17go real slow if if W is big like as a

37:22matrix what can you say about the

37:24ellipsoid there it's small

37:27right so in fact the volume I don't even

37:29remember what it is it's like it's the

37:31determinant of w I think to the minus

37:34one2 and then multiplied by the volume

37:39of a unit ball in our whatever it is in

37:42this case maybe r p or something like

37:45that right which has got some gamma

37:49function and some weird factorials and

37:52who know some probably some pies in

37:53there I'm guessing that doesn't matter

37:55right so so so the the volume of this is

37:58a is a

38:00constant times the determinant of w to

38:03the minus one2 and that says the if you

38:07make dou so minimizing that minimizing

38:11determinant of w to the minus one over

38:13the square root of that is the same as

38:16maximizing the log determinant so so

38:19that that's what that so I I didn't say

38:21that so it's kind of un yeah I forgot

38:24about like big w means the small

38:27right that's that's for this that's for

38:29this this parameterization of an

38:31ellipsoid because we're about to see

38:32some

38:34others okay now we'll do geometric

38:36problems actually um I don't even have

38:39here I'm going to mention some really

38:40simple ones they're so simple that it's

38:42almost like insulting to ask but let's

38:44just start with some really simple ones

38:46um suppose I gave you two ellipsoids uh

38:48two polyhedra like P is the set of X for

38:52which you know ax is less than b right

38:56and let's say say p TI is the set of X

38:59for which a TI X is less than b ti so

39:03these are two these are two polyedra

39:05right and suppose how would you solve

39:07the following problems right uh how

39:10would you determine if they

39:14intersect is it a convex problem and how

39:16would what what what problem is

39:20it is like a feasibility problem that

39:23satisfies both constraints that's it

39:24it's just a feasibility problem so you'd

39:26say yes you can solve that it's convex

39:28it's an LP feasibility problem okay I'll

39:30take it up a notch find me the minimum

39:32distance between the two polyedra let me

39:35explain what that means it means

39:39uh it means find me a point you know in

39:43one and a point in the other for which

39:47the distance is as small as possible

39:49what kind of problem is

39:53that squares with these strings yeah

39:56it's a it's just a it's a QP right I I

40:00would say it's going to be I would have

40:02these constraints ax less than b and I

40:04would write ax TI less than b TI and I

40:07would

40:08minimize uh simply x - x TI there any

40:12Norm any Norm you like but we'll take

40:14two Norm everybody got that so these are

40:17just unbelievably simple problems now

40:20right oh and what if the two what if the

40:22two polyhedra

40:24intersect and I ask you you find the

40:27distance between the two

40:30polyhedra yeah it's a zero and you name

40:33any point and you go W how could it be

40:35zero and you go well because this one

40:36vector is in both polyhedra and the

40:38distance between a vector and itself is

40:40zero everybody got this okay so I mean

40:41these are simple things right um so you

40:45know I we could go on and on uh what if

40:48I represented you know the polyhedra by

40:50a list of its vertices right suppose I

40:54have P hat is the convex Hull of V1 up

41:01to VN ooh now how do I determine if this

41:06intersects

41:09that any

41:13suggestions it's a different

41:15representation right so any uh

41:20suggestions is it a convex problem how

41:22would you solve

41:24it yeah like wait is your variable

41:27precisely right I would make one

41:29variable is going to be sum Theta I VI

41:33the Theta I are positive and they sum to

41:38one right that's my variable Theta right

41:42and if I want to if I want to do this I

41:44would actually write this uh equals x

41:47right and then I would also have ax less

41:50than b everybody see this and so what

41:53that is is and now I Sol

41:56that feasibility problem which is an LP

41:58feasibility problem but really who cares

42:00right I solve that problem if this is

42:03feasible then this this polyhedron

42:06described by its vertices intersects

42:08this one described by its inequality

42:10constraints right if this is not

42:12feasible they don't

42:14intersect everything so anyway the these

42:17are very basic ones you can read about

42:18them in the book but in a way like at

42:21this point in the course you know enough

42:22that these are just almost too simple to

42:24even I just I mentioned them right but

42:26that's that's the idea so um we are

42:29going to get to ones where things are

42:31not obvious at all and that's actually

42:34the first topic the these are kind of

42:36obvious right and you go on and on with

42:38different geometrical problems and and

42:40you know these things obviously come up

42:41all the time in things like you know

42:43robotics if you want to know if you have

42:45a polyhedral you know uh thing of if you

42:48have a if a polyhedron represents a

42:49vehicle and then you have a polyhedral

42:51safe space or something and you want to

42:53know where you anyway I'll I won't or an

42:55obstacle right and you want to know am I

42:57far am i what's my distance to the

42:59obstacle or something okay so all right

43:01so now we're going to look at ones that

43:03are not obvious at all and these are

43:07going to be I think these are all pretty

43:09simple right this gets very weird and

43:13cool and it's more than 100 years old so

43:15here it is um suppose I have just a set

43:18C in

43:19RN right and um what I want is I want to

43:23find the minimum volume ellipsoid that

43:26covers it

43:28okay so that's you know it that's that's

43:33a that's got a name it's called The

43:34Loner John ellipsoid of a set C and now

43:39we're going to show you how to how to

43:41pose that as a convex optimization

43:43problem and this is actually uh it's

43:46interesting now you have to be very

43:47careful because there's lots of

43:50parameterization of

43:52ellipsoids and for each of these

43:54problems we're actually going to take

43:56different

43:57parameterizations because in that

43:59parameterization it's going to be

44:02convex and in another one it will not be

44:04so you have to be completely on your

44:06toes on these things right I mean the

44:08truth is we already saw it we didn't

44:10mention it here but for example if I ask

44:12you to

44:14estimate the covariance of a zero mean

44:16Gan Vector from data right then it turns

44:20out the log likelihood is not concave in

44:25Sigma The covariance Matrix it is

44:28concave in the inverse which is the

44:30Precision Matrix okay so if you know

44:32what I'm talking about fine and if you

44:33don't that's fine too right so that's a

44:35case where there's lots of ways to say

44:37what a covariance matrix is right you

44:39could give its inverse you could give it

44:42um and it's going to turn out some

44:44things are convex in one but not the

44:46other and so on and so forth right and

44:48this is similar so here we

44:50go so we're going to do this I'm going

44:53to write the ellipsoid I'm going to

44:55parameterize it by a matrix a and a

44:58vector B and uh it's the inverse image

45:04of the unit ball under an apine mapping

45:08okay

45:09everybody got that here so that's that

45:13that's what it's going to be um okay uh

45:17and here I'm going to say that without

45:20loss in generality I'm going to assume a

45:22is symmetric and positive

45:24definite okay

45:26I mean okay so it has to be just

45:28positive semi-definite because I want it

45:30to be uh invertible here right otherwise

45:33that's not an ellipsoid it it's got like

45:35a you know whatever it's it's got some

45:38infinite it goes in it's a cylinder I

45:40think is what people call it or

45:41something like that okay um so I would

45:44like to know if someone says yeah I have

45:47a parameterization of lipoid with an A

45:48and A B but my a is not

45:50symmetric so I need someone to help me

45:53to see why we would say without loss of

45:55gener

45:56ality right this is this is a a subtlety

46:00right so uh but an important

46:05one right so I have it's a set of X for

46:09which ax uh I can't is it plus or minus

46:13B ax plus b

46:17right torm is less than one someone

46:21gives you this but a is not symmetric so

46:24or it's not symmetric in positive

46:26definite so a is invertible so any

46:28suggestions on what we can do

46:35here they give you a lower triangular

46:37Matrix I don't know what they give they

46:38give you something like that so what

46:40what do I

46:41do any uh yeah singular value

46:45decomposition yeah let's let's write U

46:48let's say is U Sigma V transpose those

46:52are all square because it's it's a it's

46:56non- singular okay

47:00um does everyone agree that if I took

47:03this vector and I put in here an

47:06orthogonal ve an orthogonal Matrix then

47:09nothing has changed I could put a q in

47:13front here which is orthogonal and this

47:16constraint is identical because if I

47:18rotate something and if I rotate the

47:20unit ball it's you still have the unit

47:22ball everybody cool with that okay

47:25someone can someone suggest a q I should

47:28apply to

47:32this and you want you want I want to

47:34apply a q which is going to have no

47:36effect whatsoever on this but it's going

47:39to render this thing when I multiply by

47:41Q on the left this thing is going to

47:43come out positive definite and symmetric

47:47so I'm open to suggestions for what Q

47:52is v u transpose yeah there you go q = v

47:57u transpose that's orthogonal these are

48:00both orthogonal these are orthogonal so

48:02if I plug that in there then a is now

48:05going to be V Sigma vpos which is

48:07symmetric and positive definite

48:09everybody got this okay so so this is

48:13It's a subtlety but it's a it's actually

48:15going to be super important okay and

48:17then it says the following oh with this

48:21parameterization the volume is

48:23proportional to the determinant of a

48:25inverse

48:26right and you can figure that out right

48:27if a gets big then the ellipsoid gets

48:30small right you can kind of see that

48:33right um and so the volume is

48:36proportional to log to to debt a inverse

48:38and in fact I think the proportionality

48:40constant is the is this magic number

48:43which is the volume of a unit ball in RN

48:47which has some gamma functions and some

48:49probably some pies in it and other stuff

48:51I don't doesn't matter it's a constant

48:52positive constant for us right so okay

48:56so uh this thing uh is is going to uh

49:01Min this is the same as minimizing the

49:03volume of

49:05e then the other thing we have is we

49:08have to have that every every element of

49:10C has to be in this ellipsoid um and the

49:13way to express that is this it says that

49:16if you maximize over C uh av+ B right in

49:23two Norm if that's more than one then

49:25you're not in you're not in uh you're

49:26not in E if it's less than or equal to

49:28one you're in E everybody got that and

49:31now we have to stare at this and you

49:33really have to concentrate let me let me

49:35give you a couple of the warnings about

49:37why you have to concentrate now because

49:39the variables in this problem are

49:41capital A and little

49:43B I mean the usual convention is that a

49:46b c d are like data they're constant

49:50right and the usual convention is we the

49:52variables are things like u v x YZ

49:55everybody following this that's usually

49:57right um but here well V is a dummy

50:01variable so has means absolutely nothing

50:03right um but here so we have to ask you

50:06know is is this thing and a is of course

50:09symmetric positive definite this is

50:12convex log determinant a inverse um what

50:16kind of constraint is this over

50:20a I mean it's convex why because for if

50:25I fix a v what kind of what kind of uh

50:28function is that of a if I for a fixed

50:34V it's convex in A and B sorry it's

50:37jointly in A and B it's convex matter of

50:40fact the argument here AV plus b is a

50:42linear function of the pair a a right

50:46not even aine it's just linear right and

50:49so this thing for a fixed V is a convex

50:53function of the pair

50:56AB that's a supremum doesn't matter what

50:59C is that the result this left hand side

51:02is a convex function here right so

51:03that's a convex function and it's less

51:05than or equal to one right so so this so

51:07whatever this is a convex optimization

51:11problem okay so this is how you would

51:13minimize the volume of an ellipsoid that

51:18covers a given set c um now we have to

51:23turn this into something reasonable at

51:26some some something that we can handle

51:28uh and we'll do that here's a super

51:29simple example a finite set and you have

51:33M Points um and you end up with a

51:37completely reasonable thing it just

51:38looks like that um and that's a that's a

51:42convex problem you can solve it and you

51:45just get it just works right it just

51:47gives you the minimum volume of lipoid

51:49so if I give you a bunch of points by

51:52the way that has a whole lot of uh

51:54applications um I'll just mention one

51:56for fun

51:58um right so here's a bunch of

52:01points like that right right and then

52:05you oh God I don't know what I'm going

52:06to do here okay so then you get some

52:08ellipsoid that looks like that right and

52:10that's going to be the minimum volume

52:12ellipsoid that covers those points

52:15everybody following this so um so here's

52:19actually an interesting way to to uh

52:22suppose I had suppose these are like not

52:24in two dimension is silly but suppose

52:26it's in high

52:27dimensions and I want to ask which of my

52:31data points here are like

52:34outliers just like that I don't have a

52:35statistical model although that would be

52:37a reasonable way so how would what would

52:39be some reasonable ways to say something

52:41is an

52:45outlier it's close to the it's what it's

52:48close no I haven't computed this yet

52:50because we let's just do like how how

52:52would you do it otherwise well you could

52:54actually find the mean here here's one

52:56you could find the mean and the

52:57covariance of of the data points right

53:01and then that you you'd look at the what

53:03so-called mahalanobis you know distance

53:05or something from the center right that

53:07that would be a reasonable weight or we

53:09could look and just say well which which

53:10of your points are really big right

53:13those are outliers right um this is a uh

53:17this is actually a quite good one right

53:19it's entirely dependent on the outliers

53:22right because it you can kind of see

53:24that if you shrinking ellipsoid down

53:25it's going to stop when actually

53:28generically n n + 1 /2 but if that's a

53:31dimension of points are are on that uh

53:33ellipsoid right um so there's a there's

53:36a method for removing outliers called

53:38ellipsoidal

53:39peeling it's a it's a first of all it's

53:42a great name and it's also a pretty good

53:44method and it works like this you say

53:46thanks for the data you find the minimum

53:48volume ellipsoid and you find the points

53:50that it

53:52touches right that's those are the ones

53:54for which

53:55this constraint here is equal to one

53:59okay then you declare those to be

54:02outliers and you remove them and you

54:05continue until you like what happens

54:08like for example you're out of sample

54:10whatever if you have some other test you

54:11can check your estimator gets better or

54:13something like that everybody following

54:15this okay that it's very cool okay let

54:18me ask one question just for

54:21fun suppose that you do that

54:26and I have you know hundreds and

54:27hundreds of points but let's say that 25

54:31have satisfi this with

54:33equality everybody following this 25 and

54:36you'd say I'm going to remove them

54:37there's 25 outliers then someone says

54:40please don't you go why because look

54:43there's no way we have 25 hour we

54:45actually only have five or or it's I

54:47couldn't imagine it being more than five

54:49everybody following this could someone

54:51please suggest how you might choose the

54:54candidates to remove

54:56remove sounds like a trick question it's

54:59actually not and it tells you if you can

55:01uh it's easy if you can use the material

55:03we've looked

55:05at I compute the minimum volume let's

55:07let's let's review I have a whole bunch

55:08of vectors I compute a minimum volume

55:10ellipsoid 20 you know 20 let's say 22 of

55:14the 22 of the points are actually on

55:16that minimum volume ellipsoid meaning

55:18that that constraint is tight for 22

55:22right I say take them all out and they

55:24go no that you're throwing way too much

55:26of my

55:30data eliminate the far edge of yeah but

55:34what's the far edge of an

55:36ellipsoid that's I no I don't yeah I

55:39don't think that works right was there

55:41another

55:42suggestion you try to maximize the

55:45difference in the volume from the

55:46original to want you remove five of the

55:49points yeah these are these are pretty

55:53that that's that something like that

55:54might happen was there another

55:56suggestion yeah just randomly throw out

56:00okay that would be fine how about the

56:02you say here you ellip soidal peeling

56:04says that the first these 20 are bad and

56:06they go they say no no no I can only

56:08have I can I can't imagine having more

56:10than five outliers and you go cool and

56:12you just remove the first five is that

56:14that's your suggestion okay no I like it

56:17that's a good street fighting thing you

56:20know you don't say it like that to the

56:21person you just go hang on a minute you

56:23go back and you pretend to

56:25change the code and stuff like that okay

56:28and then you do that okay that was

56:29another suggestion

56:30somewhere all right let me I try one

56:33more time

56:35yeah to see if I can elicit a response

56:38okay I have 20 constraints that are

56:42tight I would like to remove

56:45five in fact I'll even do I even have to

56:48say I'll even say I want to remove the

56:50five tightest constraints how about that

56:55please

56:57what oh there we go okay fine you get

57:00the dual variables which you get for

57:01free and then you remove the five with

57:05the five largest dual

57:08variables every ready cool that's that's

57:11a it's pretty sophistic I mean I'm just

57:14we're just putting ideas from the class

57:15together this is not the but things like

57:17this are actually kind of useful

57:19actually that was a good question

57:22because it's the ones we like right

57:25because I didn't say the dword which is

57:28Duality but that was a question about

57:30Duality so so what we want is we we want

57:32you to have a street fighting idea uh

57:35knowledge of Duality because it never

57:37ever works when someone comes and says

57:38oh help me help me I have a dual and

57:40you're like no it doesn't work that the

57:42way it always works is somebody has some

57:44long complicated problem and they need a

57:46suggestion and they don't they don't

57:48even know what Duality is right so okay

57:50everyone cool that was just an side but

57:51it was fun for me anyway so um okay okay

57:56so that's so this gives you the minimum

57:57volume ellipsoid

58:00um okay so then you could say okay fine

58:04can we do uh oh let me just ask I'm

58:06going to go back and and show one of so

58:09you say that's cool you can do a minimum

58:10volume ellipsoid around a point and then

58:12you might innocently ask well that's

58:14cool uh by the way this is the minimum

58:17volume ellipsoid that covers whoops uh

58:19that covers a a

58:22polyhedrin uh given by it's uh its

58:25vertices so it's that's the same problem

58:27you agree so so if someone walks up in

58:29the street and says find the minimum

58:31volume of lipoid that covers a

58:32polyhedrin described by its

58:36vertices then that's also we can do that

58:39it's it's a simple convex problem cool

58:43but now someone says oh yeah you know

58:44what though my ellipsoid is is described

58:47by not vertices but it looks like this

58:51here's my ellipsoid it's it's it's

58:53described

58:55by uh a set of linear inequalities and

58:59we we want to find the minimum volume

59:01ellipsoid that

59:03covers you know uh a that that that

59:06covers um a polyhedron described by its

59:09faces right everybody cool on this okay

59:13it sounds reasonable actually someone

59:15give a simple I me how would you what be

59:18one way to do

59:21it what would you do BR the intersection

59:24for the inequalities and then yeah so

59:27you would you would basically you'd

59:28first write a method that called you

59:31know faces to vertices right and you'd

59:35take your ellipsoid and you'd call the

59:37faces to vertices method on it right and

59:40it would give you the vertices and then

59:41you call the then you type this in it's

59:43three lines of CVX Pi that's your

59:45proposal right I like it it would work

59:48there's a one minor problem with that is

59:51how many vertices you know just order

59:53magnitude does a polyhedrin and

59:57r1000 with let's say 5,000 inequalities

01:00:01which by the way is a tiny thing you can

01:00:04solve on you can solve an LP or problems

01:00:06with that on your phone everybody got

01:00:07that how many vertices does that have

01:00:09about distorter

01:00:13magnitude everybody know what I'm saying

01:00:15I mean I'm not drawing a picture here on

01:00:17R2 I'm talking about r th000 or whatever

01:00:20and you've got 5,000 inequalities how

01:00:21many vertices does it

01:00:23have a lot yeah that's the answer you

01:00:26know it's order magnitude a thousand

01:00:28choose whatever 5,000 choose a thousand

01:00:31just for the record that's a super big

01:00:33number so so your method was correct it

01:00:36would work in two dimensions and three

01:00:37and blah blah blah um it it it's not

01:00:40going to it it would be absolutely

01:00:42correct it just wouldn't uh work for for

01:00:45big okay everybody got that okay so now

01:00:47I'll now I'll let you in on the secret

01:00:48turns out actually finding the minimum

01:00:51volume ellipsoid that covers a

01:00:53polyhedrin given an INE equality form is

01:00:55NP

01:00:57hard as a matter of fact the following

01:00:59is I just walk up the street and say

01:01:02Here's an ellipsoid like don't even

01:01:04optimize it here's an ellipsoid and I

01:01:06want to ask you the following innocent

01:01:07question does my ellipsoid cover this

01:01:13polyhedrin makes sense right so I mean I

01:01:15you could even imagine all sorts of you

01:01:18could imagine all sorts of things that

01:01:19people might use this for they would say

01:01:21like you know this is a this is a my

01:01:24polyhedrin is my desired region or

01:01:26something like that and I'm going to

01:01:27cover it within a lip you just want to

01:01:29ask does it cover it anyway everyone got

01:01:30the question unbelievably simple to

01:01:32State NP

01:01:34hard okay

01:01:37so it gets very these things are about

01:01:39to get very weird Okay so it depends on

01:01:42how you describe the polyhedrin and all

01:01:44that kind of stuff okay so that so yeah

01:01:48if you're confused you should be right

01:01:51uh because this is quite complicated

01:01:54okay

01:01:55now uh to confuse you if you're not yet

01:01:57confused this should do the trick uh so

01:02:01now we go to something like a dual

01:02:03problem it turns out they're not really

01:02:04duals but that's okay the Dual problem

01:02:07is I have my set C here I'll just draw a

01:02:10c here's C right and what I want to do

01:02:13now we just The Loner John ellipsoid

01:02:15covers uh is find the minimum volume

01:02:18ellipsoid that covers this thing right

01:02:21um the now this is a A variation on that

01:02:24this doesn't have a person's name

01:02:26attached to it or I guess I should say

01:02:28that's this one it says find me the

01:02:30maximum volume ellipsoid that fits

01:02:32inside your

01:02:34set okay um here's what's going to

01:02:37happen this is crazy if the set is an

01:02:40ellipso is if the set is a

01:02:41polyhedron uh we're going to be able to

01:02:43solve this one when these are given by

01:02:47inequalities totally straightforward but

01:02:49if it's given by the vertices it's going

01:02:51to be NP hard so it's just weird and

01:02:55crazy I can calculate the maximum volume

01:02:58ellipsoid that fits inside a polyhedrin

01:03:01described by

01:03:03inequalities that that's easy tractable

01:03:07I can find the minimum volume of lipoid

01:03:09that covers a polyhedron described by

01:03:11its vertices totally tractable everybody

01:03:14following but the two other problems are

01:03:17actually extremely difficult everybody

01:03:21got that so it's I mean it's interesting

01:03:24actually okay so let's see how to do

01:03:27that now to do that what we're going to

01:03:28use we're going to use a we're actually

01:03:30going to use the opposite

01:03:31parameterization we did before before to

01:03:34find the minimum volume ellipsoid we use

01:03:36the inverse image of the unit ball under

01:03:37an apine mapping here it's going to be

01:03:40the forward image of a unit bow so

01:03:44here's the unit ball and I'm going to

01:03:46make a forward image under an apine

01:03:48mapping right so here by the way the

01:03:50bigger B is the bigger e

01:03:53is right whereas the was the opposite

01:03:55was true for the previous

01:03:57parameterization so we do this

01:03:59um and here once again we can assume

01:04:02without any loss of generality that b is

01:04:05both symmetric and positive definite

01:04:07okay so B is invertible but I can do

01:04:09that I do the same trick right here if I

01:04:12put a orthogonal matrix after if I

01:04:15replace B with BQ the problem is

01:04:17identical because Q multiplies u u has

01:04:21unit is in the unit ball and if I have

01:04:23an orthogonal Matrix doesn't change

01:04:24anything at all everybody following this

01:04:27okay so uh so that's my parameterization

01:04:31and now the volume is proportional to

01:04:33the determinant of B so if we maximize

01:04:36log determinant B that's the same as

01:04:38maximizing determinant

01:04:40B and that's that's actually log

01:04:43determinant B is as you know concave and

01:04:46then we're maximizing so everything is

01:04:48cool

01:04:50everybody following this so okay now we

01:04:55have to be able to say that um we have

01:04:57to be able to say that the following is

01:04:59true um I I want to say that everything

01:05:02in this in this ellipsoid is inside um

01:05:06is inside my my um my set right because

01:05:09that my ellipsoid has to fit inside the

01:05:11set and the way you you uh test that is

01:05:14this is I'll take the indicator function

01:05:17for

01:05:18C right um and it that's just something

01:05:22that's zero if you're in uh and infinity

01:05:25otherwise and I write it this way so I

01:05:27see a bu plus D um means let's see what

01:05:31does it mean it means if this element is

01:05:34in C this is plus infinity otherwise

01:05:36this is zero

01:05:39okay um and this is silly to say soup

01:05:42you know U Less Than it just says that

01:05:43basically for all uh it says basically

01:05:46everything of the form bu plus d with

01:05:48Norm 2 lesson one is in the set that

01:05:51that's just a fancy way to write it okay

01:05:55um now this is actually this is this is

01:05:57a convex optimization problem but once

01:05:59again we have this kind of a weird

01:06:02supremum or inum in in the problem which

01:06:06we know it's convex but we have no way

01:06:08to write it down uh we it's not

01:06:10tractable and so actually this is the

01:06:11point in the course when we can start uh

01:06:13you know basically level zero is convex

01:06:18optimization problems are tractable

01:06:20that's that's like Bas if someone on the

01:06:22street asks you or whatever like you

01:06:23know hey or from a different field asks

01:06:25you who cares about that you go well

01:06:27they're tractable right um but now you

01:06:29can see that's actually false because

01:06:31this is this is an example this is an

01:06:33example of a problem where I mean you

01:06:35had just have some trackable actually

01:06:36the ones I said were NP hard before

01:06:37they're convex problems no problem they

01:06:40just have this they just they just have

01:06:42this inum or supremum in there that you

01:06:44can't represent right so yeah so so it

01:06:47depends you have to judge the social it

01:06:49depends on the social setting right if

01:06:51you're with a bunch of mathematicians

01:06:53and or people who know a lot then you

01:06:55don't have to you wouldn't say all

01:06:58convex problems are tractable right so

01:07:00okay all right um so here let's do a

01:07:05polyhedron and then I can actually then

01:07:08I can check right so with this

01:07:10parametrization if I want to know is e

01:07:13inside this polyhedron given by a set of

01:07:16inequalities that we can that's actually

01:07:18completely tractable and it looks like

01:07:19this right that's a perfectly good

01:07:21problem right here maximize the log

01:07:23determinant subject to and and let's be

01:07:26very care you have to be really on your

01:07:28toes here what are the variables in this

01:07:35problem what what are the

01:07:39variables capital B and Little D is that

01:07:42right yeah okay and then what are Ai and

01:07:46bi what are they con they're data or

01:07:50constants or parameters however you want

01:07:51to say it right um okay so then what

01:07:55kind of function is this of the

01:08:00variables it's convex it's b b b AI is

01:08:04linear and then it's a torm so that's

01:08:06convex right um what kind of function of

01:08:09the variables is

01:08:12that it's aine but it's linear right so

01:08:17uh I mean it is appline of course but

01:08:18it's it's it's it's it's it's even

01:08:20linear right and so this is a convex

01:08:22constraint because that's a convex

01:08:23function right fact it's second order

01:08:25cone representable right so um okay so

01:08:30so uh so that's it so we so this is this

01:08:33crazy thing where if I give a

01:08:35polyhedrin if I give you a polyhedron

01:08:38described uh by its INE by inequalities

01:08:41we can find the maximum volume of lipoid

01:08:43inside it everybody got and that's

01:08:45completely tractable by the way this has

01:08:47a tons of applications immediately like

01:08:51suppose I give you a polyhedron that's

01:08:52very complicated defined by inequalities

01:08:54and you say that's a safe operating

01:08:56region right if you're state or whatever

01:08:58it is if you're robot whatever if you're

01:09:00in that you're not going to hit anything

01:09:02and it's safe everybody following this

01:09:04um this allows you to do something like

01:09:07make a guaranteed the maximum volume

01:09:10safe ellipsoid and someone say why would

01:09:12you do that you say because my my

01:09:14algorithm that manipulates it uh can

01:09:16handle a an ellipsoid but not a not a

01:09:19polyhedrin with you know 80 faces or

01:09:21something like every Everybody following

01:09:23this so so this already has a lot of

01:09:25uses right that that that's one just

01:09:28right there um

01:09:31okay um now it turns out there's

01:09:33something very weird about these

01:09:35actually it's very cool um it's this uh

01:09:39this is math right but it's it's

01:09:41actually super interesting it has all

01:09:42sorts of implications so here it is um

01:09:45take any convex bounded set with

01:09:47non-empty Interior right so it's not

01:09:49flat you know it doesn't go off to

01:09:51infinity and blah blah blah that there

01:09:52there's C right right then The Loner

01:09:55John by the way I'm not this is not

01:09:58we're not talking about whether or not

01:09:59you can compute the minimum volume

01:10:01lipoid that covers something or the

01:10:02maximum volume of ellipsoid inside it

01:10:04that's a separate question this is math

01:10:06so we don't we're unbothered by the

01:10:08questions of we're just looking at

01:10:10what's true and false not how do you

01:10:12actually how how much trouble is it to

01:10:14compute it right so okay so it turns out

01:10:17that if you take the laner John

01:10:18ellipsoid so that that says take your

01:10:21Set uh you find the minimum volume

01:10:24ellipsoid that covers your set then it

01:10:27says shrink the set around shrink that

01:10:30ellipsoid around its Center by Factor n

01:10:33everybody got that that's inside the

01:10:37set okay that that's what it that's what

01:10:40it says okay and the opposite is true uh

01:10:43for the maximum volume lip lipoid if I

01:10:46have any set at all convex I find the

01:10:48maximum volume ell lipoid that fits

01:10:50inside

01:10:51it now I expand it by a factor n about

01:10:55the center that covers the set okay and

01:10:59it gets even weirder if the set is

01:11:01symmetric like if you if you if if if

01:11:03minus the set is equal to itself or

01:11:05something like that then it turns out

01:11:08you don't have to have a factor of n you

01:11:09have a factor of square root in

01:11:11everybody following this now this

01:11:13actually tells you unbelievable things

01:11:15this says that if you had a convex set

01:11:18and you approximate it with an

01:11:20ellipsoid it says you really you can't

01:11:24be too far off in fact if if I take

01:11:26let's say either The Loner John or the

01:11:27let's suppose I take the loner John

01:11:29ellipsoid and I shrink it by suppose I

01:11:31shrink it by square root

01:11:33n right then and I say that's that's the

01:11:37ellipsoidal approximation of my set and

01:11:39you go cool in which how does it

01:11:42approximate your set you go well if I

01:11:44expand it by Factor square root n it

01:11:46covers my set if I shrink it by a factor

01:11:48of square n it's inside the set

01:11:51everybody got it so so so actually it's

01:11:53kind of what it tells you is that like

01:11:55ellipsoids are Universal

01:11:58approximators of convex

01:12:01sets right now square root n in some

01:12:03practice might be like way way too much

01:12:06for you to be happy with or something

01:12:07like that but um actually let me do an

01:12:10example uh here uh let let's just do one

01:12:14here

01:12:15um here's my set ready uh it's a

01:12:20triangle like that okay um what's the

01:12:25what's the ler johon ellipsoid of that

01:12:27it's a you know equilateral or whatever

01:12:29they call it what what's the ler John

01:12:31ellipsoid this just a circle that goes

01:12:33around it okay right so it looks like

01:12:35this right what this is going to be

01:12:37terrible but okay there it is okay right

01:12:40okay shrink that by a factor of two in

01:12:42your eye and what do you

01:12:45get you get

01:12:49this right and actually this example

01:12:52shows that that that that's tight that

01:12:54inequality right so and in fact it's

01:12:57always true so you could even say

01:12:58something very weird like this um first

01:13:01you say all convex sets can be

01:13:03approximated by ellipsoids within a

01:13:05factor I you know you could say I I

01:13:07could say Square n because I'd put it in

01:13:09the middle and then both expand and

01:13:11Shrink right and you'd say yeah well

01:13:13what are the hardest sets to approximate

01:13:16by ellipsoids makes perfect sense right

01:13:20and the answer is a Simplex in R end a

01:13:23Simplex in RN if you want to approximate

01:13:26approximate it by ellipsoids it's going

01:13:28to take it's going to take the full you

01:13:30know square root n here would be my

01:13:32weird square root n thing right it would

01:13:33be something that looks like that whoops

01:13:36okay that came out very poorly but

01:13:37anyway that that would be my this would

01:13:39be my square root

01:13:40in and I would say you see that that

01:13:44ball that that disc if I increase it by

01:13:471.4 you know whatever 1.42 there you go

01:13:50I'm then I I I cover my triangle and if

01:13:54I shrink it If I multiply it by 7 then

01:13:57I'm inside everybody got that then the

01:14:00so everybody got all this so um this

01:14:04applies actually weirdly to Norms right

01:14:07it says take any Norm at all on

01:14:10RN right any Norm it says that I can

01:14:14replace it with a quadratic I can

01:14:16approximate it with a quadratic Norm

01:14:18those are symmetric with error no more

01:14:21than the fourth root of n

01:14:25okay uh so now I'll tell you an

01:14:27important thing about that uh there's

01:14:30lots of norms like here here's a norm uh

01:14:33the minimum fuel it takes you the

01:14:36minimum fuel it takes you to you know go

01:14:39from a state to zero that's a Norm

01:14:42that's actually a norm it's a crazy

01:14:44polyhedral Norm right with lots of it's

01:14:46a it's a crazy Norm but it is it is a

01:14:48norm but that might be one we really

01:14:51care about right it says I can I can

01:14:53approximate that like pretty well with a

01:14:55quadratic Norm why does that matter

01:14:57because in fact the control that people

01:14:59actually use is all based on quadratic

01:15:02stuff and so this would give you a very

01:15:04good way to uh to find those quad to to

01:15:08find the qu actually it would it would

01:15:09actually say kind of why things work so

01:15:11well right when people would say like

01:15:14yeah how do you how are you controlling

01:15:15your airplane and if they're honest

01:15:17they'll finally they'll say something

01:15:18like it's basically using something like

01:15:22you know linear quadratic basically

01:15:23least it's almost least squares

01:15:25basically it's more complicated that but

01:15:26not not too far and you go whoa you go

01:15:30that's great are the uh you know are

01:15:32your actual constraints like you know

01:15:35spherical or whatever and they're like

01:15:36no no no no they're not you know that

01:15:39kind of thing so but it works really

01:15:41well and and this is actually at least I

01:15:43like to think part of the part of the

01:15:45explanation okay so this all this make

01:15:47sense it's kind of weird and interesting

01:15:49and cool I

01:15:51think okay um next topic is something

01:15:55we've actually seen a couple of times

01:15:57before it's um so-called it's centering

01:16:00so actually very early in the course we

01:16:02encountered this it was one of our first

01:16:04examples of a linear program right it

01:16:06was like here's a polyhedrin given by

01:16:08inequalities and I said find the find

01:16:11the

01:16:12largest ball ukian ball that fits inside

01:16:15it everybody got that that's called the

01:16:17Chevy CHF Center I me it's it it's an LP

01:16:20and I said at the time it's weird

01:16:22because you know if I say things like

01:16:24ukian ball or draw a draw a circle the

01:16:28linear programming part of your brain

01:16:29should not be lighting up because that's

01:16:32you know linear programming part of your

01:16:34brain should light up when I say things

01:16:35like polyhedrin inequalities uh visually

01:16:40you should be seeing flat things with

01:16:42Corners right you should see like a

01:16:44modern uh you know fighter jet with you

01:16:47know made with like flat parts and stuff

01:16:49like that for various reasons right

01:16:50that's what you should be seeing you

01:16:52should not be seeing

01:16:53curves I mean anyway that's what you

01:16:56should be seeing right and so that was

01:16:57weird but that's it okay so that's the

01:16:59chubby CHF Center um but we have another

01:17:01one immediately oh we saw another one we

01:17:03saw the yield Center or or probability

01:17:06Center so that would be take a

01:17:10point and then that's you're Shifting

01:17:12the mean now put a zero mean

01:17:14distribution around it and with a log

01:17:16concave density and then maximize the

01:17:20pick the center that maximizes the

01:17:22probability that's another one I think

01:17:24people call that different fields they

01:17:25call it different things it's like the

01:17:26yield Center I don't know there's all

01:17:28sorts of names for it everybody or

01:17:30probabilistic Center um but here's

01:17:32another one the center for the maximum

01:17:34volume ellipsoid right um so and that's

01:17:37a that's actually a a very good one for

01:17:40reasons I could I I I'll I'll get to but

01:17:43not today um okay so this is centering

01:17:48um oh it turns out of course look

01:17:50centering let's let's let's let's talk

01:17:52about centering an R it's going to be

01:17:54very short conversation right so here's

01:17:56a convex set an R it's called an

01:17:58interval what's the center of an

01:17:59interval a bounded interval what's the

01:18:01center of the

01:18:03interval it's the center it's the middle

01:18:06of it I mean come on that's what it is

01:18:07and there's no other I mean there's no

01:18:09other reason you say no I think it

01:18:10should be a you know the one that's

01:18:11onethird of the way towards the left and

01:18:13you're like like what does that mean

01:18:14right so there's but the minute you get

01:18:17to like R2 it's act it's actually

01:18:19interesting there it turns out there's

01:18:21multiple different definitions of aent

01:18:23and uh we're going to look at some of

01:18:26them so just just to point this out

01:18:28right okay

01:18:30um one thing uh we one thing that's

01:18:34going to come up later is the so-called

01:18:35analytic Center and it's actually a

01:18:37weird thing it's it's a bit uh it's a I

01:18:40I'll I'll say why it's weird in a minute

01:18:42but it's actually not it's not a center

01:18:45of the geometrical object it's actually

01:18:48of a set of inequalities so if I have a

01:18:50set of inequalities and some equality

01:18:52constraint if I minimize the if I

01:18:56maximize the sum of the logs these are

01:18:57the margins Fi Fi should be less than

01:19:00zero so minus fi should be positive

01:19:02right or non- negative right but here

01:19:05this says basically maximize the product

01:19:07of the

01:19:09margins that that's called the analytic

01:19:11Center of these inequalities right and

01:19:14it's going to turn out that's very

01:19:15easily computed as a matter of fact you

01:19:17will be Computing it in about two weeks

01:19:19so so um you'll be writing code to do

01:19:22that

01:19:23um anyway so we'll I think what we'll do

01:19:25is we'll quit here for today and we'll

01:19:27we'll continue uh next

01:19:33time

ðŸŽ¥ Related Videos

ðŸ”¥ Recently Summarized Examples