# Linear Programming: Data Fitting Linear Programming: Data Fitting Steve Gu Mar 21, 2008 Outline Data fitting (Ref: pp 250) Data fitting using LP Data fitting X Y 1 2 2

5 3 8 Y X Data fitting How to fit the model y cx to the following data set using Chebyshev criterion? X Y 1

2 2 5 3 8 Chebyshevs criterion: minimize the largest absolute deviation: ri yi y ( xi ) Chebyshev Criterion max i yi y ( xi ) Goal : minimize A min max problem!

More Formal Statement X 1 2 3 Y 2 5 8 subject to: r max i yi cxi Goal : min r r (2 c) 0 r (2 c) 0 r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 Interpret Geometrically r (2 c) 0 r (2 c) 0

r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 r 8 6 Feasible region 4 2 1 2

3 4 5 c Interpret Geometrically r r (8 3c) 0 r (2 c) 0 c 2.5, r 0.5 Therefore, 2.5 is the

optimal value of c and the residual error is 0.5 8 6 Feasible region 4 2 Optimal solution 1 2 3

4 5 c More general problem Given N points (X1,Y1),(X2,Y2),,(XN,YN), How to fit the model y=cx using Chebyshev criterion? max i yi y ( xi ) Goal : minimize Data fitting using Linear Programming Whats the Goal? min r, where r= max i yi cxi What are the Unknowns?

r and c What are the constraints? Compare to 3-points case: r (2 c) 0 r (2 c) 0 r (5 2c) 0 r (5 2c) 0 r (8 3c) 0 r (8 3c) 0 Data fitting using Linear Programming r ( y1 cx1 ) 0 r x1c y1

r ( y1 cx1 ) 0 r x1c y1 r ( y2 cx2 ) 0 r x2 c y2 r ( y2 cx2 ) 0 r x2 c y2 ... r ( yN 1 cxN 1 ) 0 ... r xN 1c y N 1

r ( y N 1 cxN 1 ) 0 r xN 1c y N 1 r ( yN cxN ) 0 r xN c y N r ( y N cxN ) 0 r xN c y N Data fitting using Linear Programming r cx1 y1 r cx1 y1 r cx2 y2

r cx2 y2 ... r cxN 1 y N 1 1 x1 y1 1 x1 y1 r

c 1 xN yN 1 xN yN r cxN 1 y N 1 r cxN yN r cxN yN Ax b

Data fitting using Linear Programming 1 x1 y1 1 x y 1 1

r A , b , x c 1 xN yN 1 xN yN

Define : 1 f 0 constraints: Ax b objective: T max f x LP in MATLAB Use command: linprog Do type help linprog !

Example: X=linprog(f,A,b) solves the linear programming problem: min f'*x subject to: A*x <= b LP in MATLAB Results: Fitting data using LP Results: Fitting data using LP c=1.0039 r=18.1304 End: Q&A Thanks