Karmarkar Algorithm
Contents
LP Solutions
Simplex vs Interior Point
Linear Programming
Karmarkar’s Algorithm
Step 2.1
Step 2.2
Big Picture
Contents
Karmarkar’s Algorithm
Projective Transformation
Projective transformation
Problem transformation:
Problem transformation:
Karmarkar’s Algorithm
Orthogonal Projection
Orthogonal Projection
Orthogonal Projection
Orthogonal Projection
Orthogonal Projection
Calculate step size
Movement and inverse transformation
Big Picture
Matlab Demo
Contents
Running Time
# of iterations
# of iterations
# of iterations
# of iterations
# of iterations
# of iterations
# of iterations
# of iterations
Rank-one modification
Method
Rank-one modification (cont)
Performance Analysis
Performance analysis - 2
Performance Analysis - 3
Performance Analysis - 4
Performance Analysis - 5
Contents
Transform to canonical form
Step 1:Convert LP to a feasibility problem
Step 2: Convert inequality to equality
Step 3: Convert feasibility problem to LP
Step 3: Convert feasibility problem to LP
Step4: Introduce constraint ∑▒〖〖x′〗_i=1〗
Step4: Introduce constraint A^′ x^′=0
Step 5: Get the minimum value of Canonical form
Step 5: Get the minimum value of Canonical form
References
5.48M
Category: programmingprogramming

Karmarkar Algorithm

1. Karmarkar Algorithm

Anup Das, Aissan Dalvandi, Narmada Sambaturu, Seung Min,
and Le Tuan Anh
1

2. Contents

• Overview
• Projective transformation
• Orthogonal projection
• Complexity analysis
• Transformation to Karmarkar’s canonical form
2

3. LP Solutions

• Simplex
• Dantzig 1947
• Ellipsoid
• Kachian 1979
• Interior Point
• Affine Method 1967
• Log Barrier Method 1977
• Projective Method 1984
• Narendra Karmarkar form AT&T Bell Labs
3

4. Simplex vs Interior Point

Linear Programming
General LP
Karmarkar’s Canonical Form
5

5. Linear Programming

Karmarkar’s Algorithm
6

6. Karmarkar’s Algorithm

Step 2.1
7

7. Step 2.1

Step 2.2
8

8. Step 2.2

Big Picture
9

9. Big Picture

Karmarkar’s Algorithm
11

10. Contents

Projective Transformation
Transform
12

11. Karmarkar’s Algorithm

Projective transformation
13

12. Projective Transformation

Problem transformation:
Transform
14

13. Projective transformation

Problem transformation:
Convert
15

14. Problem transformation:

Karmarkar’s Algorithm
16

15. Problem transformation:

Orthogonal Projection
17

16. Karmarkar’s Algorithm

Orthogonal Projection
18

17. Orthogonal Projection


19

18. Orthogonal Projection


20

19. Orthogonal Projection


21

20. Orthogonal Projection

Calculate step size
22

21. Orthogonal Projection

Movement and inverse
transformation
Transform
Inverse
Transform
23

22. Calculate step size

Big Picture
24

23. Movement and inverse transformation

Matlab Demo
25

24. Big Picture

Contents
• Overview
• Projective transformation
• Orthogonal projection
• Complexity analysis
• Transformation to Karmarkar’s canonical form
26

25. Matlab Demo

Running Time
• Total complexity of iterative algorithm =
(# of iterations) x (operations in each iteration)
• We will prove that the # of iterations = O(nL)
• Operations in each iteration = O(n2.5)
• Therefore running time of Karmarkar’s algorithm = O(n3.5L)

26. Contents

# of iterations

27. Running Time

# of iterations

28. # of iterations


29. # of iterations


30. # of iterations


31. # of iterations


32. # of iterations


33. # of iterations


34. # of iterations

Rank-one modification

35. # of iterations

Method

36. Rank-one modification

(cont)

37. Method

Performance Analysis

38. Rank-one modification (cont)

Performance analysis - 2

39. Performance Analysis

- 3

40. Performance analysis - 2

Performance Analysis - 4

41. Performance Analysis - 3

Performance Analysis - 5

42. Performance Analysis - 4

Contents
• Overview
• Transformation to Karmarkar’s canonical form
• Projective transformation
• Orthogonal projection
• Complexity analysis
44

43. Performance Analysis - 5

Transform to canonical form
General LP
Karmarkar’s Canonical Form
45

44. Contents

Step 1:Convert LP to a
feasibility problem
• Combine primal and dual problems
Dual
Primal
Combined
46
• LP becomes a feasibility problem

45. Transform to canonical form

Step 2: Convert inequality to
equality
• Introduce slack and surplus variable
47

46. Step 1:Convert LP to a feasibility problem

Step 3: Convert feasibility
problem to LP
48

47. Step 2: Convert inequality to equality

Step 3: Convert feasibility
problem to LP
• Change of notation
49

48. Step 3: Convert feasibility problem to LP


50

49. Step 3: Convert feasibility problem to LP


51

50. Step4: Introduce constraint ∑▒〖〖x′〗_i=1〗

Step 5: Get the minimum value
of Canonical form
52

51. Step4: Introduce constraint A^′ x^′=0

Step 5: Get the minimum value
of Canonical form
• The transformed problem is
53

52. Step 5: Get the minimum value of Canonical form

References
• Narendra Karmarkar (1984). "A New Polynomial Time
Algorithm for Linear Programming”
• Strang, Gilbert (1 June 1987). "Karmarkar’s algorithm and its
place in applied mathematics". The Mathematical Intelligencer
(New York: Springer) 9 (2): 4–10. doi:10.1007/BF03025891.
ISSN 0343-6993. MR '''883185'‘
• Robert J. Vanderbei; Meketon, Marc, Freedman, Barry (1986).
"A Modification of Karmarkar's Linear Programming
Algorithm". Algorithmica 1: 395–407.
doi:10.1007/BF01840454. ^ Kolata, Gina (1989-03-12). "IDEAS
& TRENDS; Mathematicians Are Troubled by Claims on Their
Recipes". The New York Times.
54

53. Step 5: Get the minimum value of Canonical form

References
• Gill, Philip E.; Murray, Walter, Saunders, Michael A., Tomlin, J.
A. and Wright, Margaret H. (1986). "On projected Newton
barrier methods for linear programming and an equivalence to
Karmarkar’s projective method". Mathematical Programming
36 (2): 183–209. doi:10.1007/BF02592025.
• oi:10.1007/BF02592025. ^ Anthony V. Fiacco; Garth P.
McCormick (1968). Nonlinear Programming: Sequential
Unconstrained Minimization Techniques. New York: Wiley.
ISBN 978-0-471-25810-0. Reprinted by SIAM in 1990 as ISBN
978-0-89871-254-4.
• Andrew Chin (2009). "On Abstraction and Equivalence in
Software Patent Doctrine: A Response to Bessen, Meurer and
Klemens". Journal Of Intellectual Property Law 16: 214–223.
55

54. References

Q&A
56
English     Русский Rules