Karmarkar Algorithm презентация

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

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

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

Simplex vs Interior Point

Linear Programming

Karmarkar’s Algorithm

Step 2.1

Step 2.2

Big Picture

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

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 Overview Projective transformation Orthogonal projection Complexity analysis Transformation to Karmarkar’s canonical form

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)

# 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 Overview Transformation to Karmarkar’s canonical form Projective transformation Orthogonal projection Complexity analysis

Transform to canonical form

Step 1:Convert LP to a feasibility problem Combine primal and dual problems LP becomes a feasibility problem

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

Step 3: Convert feasibility problem to LP

Step 3: Convert feasibility problem to LP Change of notation

Step 5: Get the minimum value of Canonical form

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

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.

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.

Q&A