[go: up one dir, main page]
Scribd
Upload
12 views10 pages

Optimization - Introduction - Part - 2

The document discusses various methods for solving linear programming (LP) problems, including the Simplex method, ADMM, and the Interior Point method. It outlines the formulation of the Lagrangian function, KKT conditions, and provides a practical example using CVX to maximize a function subject to constraints. Additionally, it details the steps to verify the solution and ensure all constraints are satisfied.

Uploaded by

rohanrtron
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
12 views10 pages

Optimization - Introduction - Part - 2

The document discusses various methods for solving linear programming (LP) problems, including the Simplex method, ADMM, and the Interior Point method. It outlines the formulation of the Lagrangian function, KKT conditions, and provides a practical example using CVX to maximize a function subject to constraints. Additionally, it details the steps to verify the solution and ensure all constraints are satisfied.

Uploaded by

rohanrtron
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Methods for Solving LP

Simplex- The classical method


ADMM-Most Modern Method
IP-Interior Point method.
(An Indian mathematician ‘Narendra Karmarkar’ pioneered research in this area)

We learn only this. The method can solve a wide variety of problems
Solve Example problems from +2
Using CVX
Feasible Region

Using CVX
% problem 1
cvx_begin quiet
variables x y
maximize 4*x+y
subject to
x+y<=50
3*x+y<=90
x>=0
y>=0
cvx_end
sprintf('x=%0.2f y=%0.2f maxvalue=
%0.2f',x,y,4*x+y)
Simple rule for Writing Lagrangian function
1. Express all inequality in the form g(x) >=0
2. In minimization, subtract from objective function after
multiplication with lagrangian
3. In maximization, add to objective function after
multiplication with lagrangian
What is Lagrangian function?.
What are KKT Conditions
First order condition of Lagrangian function is
KKT Conditions of constrained optimization problem

What is a Lagrangian Function?


Given an objective function and a set of constraints (in primal variables), a new
function which is an algebraic sum of objective function and scalar (dual
variables) multiples of constraint functions such that the new function’s first
order optimality conditions wrt to primal and dual variables are same as the
KKT condition of original problem with objective function and constraints .
Reframe in Std Format
Maximize f  x  4 x1  x2
Constra int s in standard form is
g1 ( x) : 50  x1  x2 0
g 2 ( x) : 90  3 x1  x2 0
x1 0; x2 0
f  x  4 x1  x2
Constra int s in standard form is
Write KKT conditions
All >=0
g1 ( x) : 50  x1  x2 0
g 2 ( x) : 90  3 x1  x2 0
Add b) Compementarity conditions
x1 0; x2 0
1 50  x1  x2  0
Lagrangian for maximization is:
L( x1 , x2 , 1 , 2 , u1 , u2 ) 4 x1  x2  1 50  x1  x2   2 90  3 x1  x2   u1 x1  u 2 x2 2 90  3 x1  x2  0
KKT conditions are u1 x1 0
 L  u2 x2 0
  c) constraints
L  x1   4  1  32  u1   0 
a ) gradient condition:     
x  L   1  1  2  u2   0  50  x1  x2 0
 x  90  3 x1  x2 0
 2
 4  u1  x1 0; x2 0
or f  x     1g1  x   2g 2  x   u 
 1  2
 4   1   3  u 
   1    2     1 
 1   1   1   u2 
Are complementarity condition
satisfied

𝑏¿ Compementarity condit ons


b) Compementarity conditions
1 50  x1  x2  0
Solution
2 90  3 x1  x2  0 x1 = 30.00
u1 x1 0 x2 = 0.00
L1 = 0.00
u2 x2 0 L2 = 1.33 = 4/3
u1 = 0.00
u2 = 0.33 = 1/3
Are all constraints satisfied?.
Solution
c) constraints x1 = 30.00 c) constraints
x2 = 0.00 50  30  0 20 0
50  x1  x2 0 L1 = 0.00
90  3 x1  x2 0 L2 = 1.33 = 4/3 90  3 x1  x2 90  90  0 0
u1 = 0.00 x1 30 0; x2 0
x1 0; x2 0 u2 = 0.33 = 1/3

You might also like