File:Karmarkar.svg

Original file(SVG file, nominally 720 × 540 pixels, file size: 43 KB)

Summary

 Description English: Solution of example LP in Karmarkar's algorithm. Blue lines show the constraints, Red shows each iteration of the algorithm. Date 3 May 2015 Source Own work Author Gjacquenot

Licensing

I, the copyright holder of this work, hereby publish it under the following license:
 This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license. You are free: to share – to copy, distribute and transmit the work to remix – to adapt the work Under the following conditions: attribution – You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). share alike – If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.

Source code (Python)

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Python script to illustrate the convergence of Karmarkar's algorithm on
# a linear programming problem.
#
# http://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
#
# Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984
# for solving linear programming problems. It was the first reasonably efficient
# algorithm that solves these problems in polynomial time.
#
# Karmarkar's algorithm falls within the class of interior point methods: the
# current guess for the solution does not follow the boundary of the feasible
# set as in the simplex method, but it moves through the interior of the feasible
# region, improving the approximation of the optimal solution by a definite
# fraction with every iteration, and converging to an optimal solution with
# rational data.
#
# Guillaume Jacquenot
# 2015-05-03
# CC-BY-SA

import numpy as np
import matplotlib
from matplotlib.pyplot import figure, show, rc, grid

class ProblemInstance():
def __init__(self):
n = 2
m = 11
self.A = np.zeros((m,n))
self.B = np.zeros((m,1))
self.C = np.array([[1],[1]])
self.A[:,1] = 1
for i in range(11):
p = 0.1*i
self.A[i,0] = 2.0*p
self.B[i,0] = p*p + 1.0

class KarmarkarAlgorithm():
def __init__(self,A,B,C):
self.maxIterations = 100
self.A = np.copy(A)
self.B = np.copy(B)
self.C = np.copy(C)
self.n = len(C)
self.m = len(B)
self.AT = A.transpose()
self.XT = None

def isConvergeCriteronSatisfied(self, epsilon = 1e-8):
if np.size(self.XT,1)<2:
return False
if np.linalg.norm(self.XT[:,-1]-self.XT[:,-2],2) < epsilon:
return True

def solve(self, X0=None):
# No check is made for unbounded problem
if X0 is None:
X0 = np.zeros((self.n,1))
k = 0
X = np.copy(X0)
self.XT = np.copy(X0)
gamma = 0.5
for _ in range(self.maxIterations):
if self.isConvergeCriteronSatisfied():
break
V = self.B-np.dot(self.A,X)
VM2 = np.linalg.matrix_power(np.diagflat(V),-2)
hx = np.dot(np.linalg.matrix_power(np.dot(np.dot(self.AT,VM2),self.A),-1),self.C)
hv = -np.dot(self.A,hx)
coeff = np.infty
for p in range(self.m):
if hv[p,0]<0:
coeff = np.min((coeff,-V[p,0]/hv[p,0]))
alpha = gamma * coeff
X += alpha*hx
self.XT = np.concatenate((self.XT,X),axis=1)

def makePlot(self,outputFilename = r'Karmarkar.svg', xs=-0.05, xe=+1.05):
rc('grid', linewidth = 1, linestyle = '-', color = '#a0a0a0')
rc('xtick', labelsize = 15)
rc('ytick', labelsize = 15)
rc('font',**{'family':'serif','serif':['Palatino'],'size':15})
rc('text', usetex=True)

fig = figure()
ax = fig.add_axes([0.12, 0.12, 0.76, 0.76])
grid(True)
ylimMin = -0.05
ylimMax = +1.05
xsOri = xs
xeOri = xe
for i in range(np.size(self.A,0)):
xs = xsOri
xe = xeOri
a = -self.A[i,0]/self.A[i,1]
b = +self.B[i,0]/self.A[i,1]
ys = a*xs+b
ye = a*xe+b
if ys>ylimMax:
ys = ylimMax
xs = (ylimMax-b)/a
if ye<ylimMin:
ye = ylimMin
xe = (ylimMin-b)/a
ax.plot([xs,xe], [ys,ye], \
lw = 1, ls = '--', color = 'b')
ax.set_xlim((xs,xe))
ax.plot(self.XT[0,:], self.XT[1,:], \
lw = 1, ls = '-', color = 'r', marker = '.')
ax.plot(self.XT[0,-1], self.XT[1,-1], \
lw = 1, ls = '-', color = 'r', marker = 'o')
ax.set_xlim((ylimMin,ylimMax))
ax.set_ylim((ylimMin,ylimMax))
ax.set_aspect('equal')
ax.set_xlabel('$x_1$',rotation = 0)
ax.set_ylabel('$x_2$',rotation = 0)
ax.set_title(r'$\max x_1+x_2\textrm{ s.t. }2px_1+x_2\le p^2+1\textrm{, }\forall p \in [0.0,0.1,...,1.0]$',
fontsize=15)
fig.savefig(outputFilename)
fig.show()

if __name__ == "__main__":
p = ProblemInstance()
k = KarmarkarAlgorithm(p.A,p.B,p.C)
k.solve(X0 = np.zeros((2,1)))
k.makePlot(outputFilename = r'Karmarkar.svg', xs=-0.05, xe=+1.05)


File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current15:34, 22 November 2017720 × 540 (43 KB)DutchCanadian (talk | contribs)The right hand side for the constraints appears to be p<sup>2</sup>+1, rather than p<sup>2</sup>, going by both the plot and the code (note the line <tt>self.B[i,0] = p*p + 1.0</tt>). Updated the header line.
19:29, 3 May 2015720 × 540 (41 KB)Gjacquenot (talk | contribs)Updated constraint display
19:26, 3 May 2015720 × 540 (41 KB)Gjacquenot (talk | contribs)Updated constraint display
19:17, 3 May 2015720 × 540 (41 KB)Gjacquenot (talk | contribs)Updated constraint display
18:54, 3 May 2015720 × 540 (41 KB)Gjacquenot (talk | contribs)User created page with UploadWizard
• You cannot overwrite this file.

The following page uses this file:

File usage on other wikis

The following other wikis use this file:

• Usage on en.wikipedia.org
• Usage on fr.wikipedia.org
• Usage on pt.wikipedia.org
• Usage on ru.wikipedia.org