Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Linear Programming: Data FittingSteve GuMar 21, 2008Outline•Data fitting (Ref: pp 250)•Data fitting using LPData fittingX 1 2 3Y 2 5 8XYData fitting•How to fit the model to the following data set using Chebyshev criterion? •Chebyshev’s criterion: minimize the largest absolute deviation: y cx=X 1 2 3Y 2 5 8( )i i ir y y x= -Chebyshev Criterionmax ( ): minimize i i iy y xGoalee= -A min max problem!More Formal StatementX 1 2 3Y 2 5 8max: min ri i ir y cxGoal= -subject to:(2 ) 0(2 ) 0(5 2 ) 0(5 2 ) 0(8 3 ) 0(8 3 ) 0r cr cr cr cr cr c- - �+ - �- - �+ - �- - �+ - �Interpret Geometrically1 2 3 4 5cr2468(2 ) 0(2 ) 0(5 2 ) 0(5 2 ) 0(8 3 ) 0(8 3 ) 0r cr cr cr cr cr c- - �+ - �- - �+ - �- - �+ - �Feasible regionInterpret Geometrically1 2 3 4 5cr2468Feasible regionOptimal solution(8 3 ) 0(2 ) 02.5, 0.5r cr cc r- - =+ - == =Therefore, 2.5 is the optimal value of c and the residual error is 0.5More general problem•Given N points (X1,Y1),(X2,Y2),…,(XN,YN), How to fit the model y=cx using Chebyshev criterion?max ( ): minimize i i iy y xGoalee= -Data fitting using Linear Programmingmin r, where r= maxi i iy cx-•What’s the Goal?•What are the Unknowns?–r and c•What are the constraints?–Compare to 3-points case:(2 ) 0(2 ) 0(5 2 ) 0(5 2 ) 0(8 3 ) 0(8 3 ) 0r cr cr cr cr cr c- - �+ - �- - �+ - �- - �+ - �Data fitting using Linear Programming1 11 12 22 21 11 1( ) 0( ) 0( ) 0( ) 0...( ) 0( ) 0( ) 0( ) 0N NN NN NN Nr y cxr y cxr y cxr y cxr y cxr y cxr y cxr y cx- -- -- - �+ - �- - �+ - �- - �+ - �- - �+ - �1 11 12 22 21 11 1...N NN NN NN Nr x c yr x c yr x c yr x c yr x c yr x c yr x c yr x c y- -- -- - �-- + �- - �-- + �- - �-- + �- - �-- + �Data fitting using Linear Programming1 11 12 22 21 11 1...N NN NN NN Nr cx yr cx yr cx yr cx yr cx yr cx yr cx yr cx y- -- -- - �-- + �- - �-- + �- - �-- + �- - �-- + �1 11 11111N NN Nx yx yrcx yx y- - -� � � �� � � �-� � � �� � � ����� � � ������ � � �� � � �- - -� � � �� � � �-� � � �M M MM M MAx b�Data fitting using Linear Programming1 11 111, ,111: 0N NN Nx yx yrA b xcx yx yDefine f- - -� � � �� � � �-� � � �� � � ���= = =� � � ������ � � �� � � �- - -� � � �� � � �-� � � ���=����M M MM M Mconstraints: objective: maxTAx bf 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 <= bLP in MATLABResults: Fitting data using LPResults: Fitting data using LPc=1.0039r=18.1304End: