ENGN3301_Quadratic_Programming_2024.pptx

Quadratic programming

1. ENGN3301 Operations Research NONLINEAR PROGRAMMING QUADRATIC PROGRAMING 

2. 2 ANU SCHOOL OF ENGINEERING   |   EB4 QUADRATIC PROGRAMMING  Linear Programming (LP) Recall the anatomy of a linear program Decision variables: (with lower and upper bounds) Objective function (linear): ( minimise / maximise ) Constraints: (inequality, equality) In matrix form ( Matlab -preferred formulation): For a LP problem, the optimal solution is always at one of the vertices of the feasibility region.   Objective function: a plane in space (for a problem with 2 decision variables) “house with a flat roof”

3. 3 Non-Linear Programming ANU SCHOOL OF Engineering   |   EB4 Quadratic PROGRAMMING  Objective function:  Minimise : Constraints:         If the function or one of the constraints or is non-linear, that is a case of non-linear programming . The optimal solution is no longer guaranteed to be at the feasibility region boundary / vertex Quadratic Programming is a special case of non-linear programming   A nonlinear objective function, also plotted as contours superimposed on the feasibility region

4. 4 ANU SCHOOL OF ENGINEERING   |   EB4 QUADRATIC PROGRAMMING  Quadratic Programming (QP) Objective function has degree 2, e.g., All the constraints and are linear (same as LP) Any QP can be defined as:   Such that: : number of decision variables : number of equality constraints : number of inequality constraints        

5. DD MMM YY Investment decisions across collection of financial assets ( eg.  stocks) Machine learning: Least squares Satellite Slew Control Minimising manufacturing cost (problems with economies/diseconomies of scale) Many other problems with quadratic formulation. 5 Applications of QPs Photo by  Callum Wale  on  Unsplash ANU SCHOOL OF ENGINEERING   |   EB4 QUADRATIC PROGRAMMING 

6. 6 Matlab solution of Quadratic Problem ANU SCHOOL OF ENGINEERING   |   EB4 QUADRATIC PROGRAMMING  Minimize:  Such that:  Bounds   H = 2*[1/2 -1/8;       -1/8   1];  %H matrix standard form f = [0.1; -3]; % same for f A = [1 1;      -1 2;      2 1]; b = [2; 2; 3]; lb = zeros(2,1); ub = [10, 10]; Aeq = []; beq = []; [ x,fval ] = quadprog ( H,f,A,b,Aeq,beq,lb,ub ); x = [ 0.5200 1.2600] // optimal solution  

7. ANU SCHOOL OF LAW | PRESENTATION NAME GOES HERE 7 DD MMM YY Solution visualisation Note: solution not at vertex!

8. ANU SCHOOL OF LAW | PRESENTATION NAME GOES HERE 8 DD MMM YY Equation to matrix form for solution     H = 2*[1/2 -1/8;       -1/8   1];   half of coefficient   coefficient for   coefficient for   2x scaling factor as the Matlab formulation expects a ½ fraction in front f = [0.1; -3]; half of coefficient (symmetric matrix)   coefficients for  

9. DD MMM YY Interior Point Active set Augmented Lagrangian Conjugate gradient Gradient Projection Various methods depending on nature of the problem (e.g., dense vs sparse H), precision vs speed trade-offs etc. 9 Different methods  to solve QP Photo by  Viswanath V Pai  on  Unsplash ANU SCHOOL OF ENGINEERING   |   EB4 QUADRATIC PROGRAMMING 

10. Assume two warehouses and two stores, with transport between them. ANU SCHOOL OF LAW | PRESENTATION NAME GOES HERE 10 DD MMM YY Example: transport with congestion        

11. Thank you