MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

RE: Question - Karmarkar's Algorithm

  • To: mathgroup at smc.vnet.net
  • Subject: [mg33732] RE: [mg33719] Question - Karmarkar's Algorithm
  • From: "Ingolf Dahl" <f9aid at fy.chalmers.se>
  • Date: Wed, 10 Apr 2002 00:49:16 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

Without knowing too much about either your problem or cluster analysis, to
me they sound as similar problems, also similar to the "posterize" operation
in Photoshop for image analysis. Check the following web addresses:
http://www.eigenvector.com for Principal Component Analysis (PCA) and
cluster analysis, and
http://www.ae.utexas.edu/courses/ase389p/gao/analysis.html. Maybe also
http://discover.nci.nih.gov/nature2000/tools/cluster.html could be a
starting point. There was an article in Scientific American, see
http://www.sciam.com/2001/0801issue/0801hargrove.html, where they used a
cluster of PC:s to do cluster analysis of weather data, also a similar
problem.
Another approach is to use neural networks, which should be able to handle
this kind of problems. Or, as I see it, that is what nature designed them
for.
I am not an expert on Karmarkar, either, but as I have understood it, the
idea with Karmarkars algorithm for linear programming is the following: In
linear programming, you should optimise a linear function of several
variables, restricted by a number of inequalities. These inequalities define
a polytope in a multidimensional space. The optimisation methods before
Karmarkar (i.e. the simplex method) usually followed the edges on the
surface of the polytope, while Karmarkar followed paths through interior
points. See http://citeseer.nj.nec.com/kranich91interior.html and
http://mathworld.wolfram.com/LinearProgramming.html. It should be possible
to rewrite your problem as an optimisation problem, but other methods that
give approximate solutions might be faster, which may be important for your
application, if you have not a supercomputing cluster available.

Please inform anything is coming out from your investigations. I also wonder
if there is something useful in Mathematica for these applications.

Ingolf Dahl
Chalmers University, Sweden



-----Original Message-----
From: Mark Van Noy [mailto:mvannoy at mac.com]
To: mathgroup at smc.vnet.net
Subject: [mg33732] [mg33719] [mg33719] Question - Karmarkar's Algorithm


I am working on an AI project and have been looking for a computer
application of "Karmarkar's Algorithm."  I had half expected that
Mathematica would contain this application.  However, the information on
Wolfram's website doesn't mention it.  Is there an available application
of Mathematica that implements Karmarkar's Algorithm?

BACKGROUND:
Mr. Karmarkar's algorithm was highlighted in a scientific publication
around 1989.  At that time it was very new.  The story is basically
this:  Mr. Karmarkar is (was?) a mathematician working for AT&T (Bell
Labs?).  He came up with an optimization algorithm that far exceeds the
ability of linear algebra.  Its advantage is that it can work with a
very large number of variables and still quickly calculate an accurate
solution, using a reasonable amount of computing power.  The "secret" of
the algorithm is that it uses vectors.  AT&T's application was/is rapid
optimization of phone call routing during heavy calling periods.
Another obvious application is 'real-time' scheduling of airline
equipment, crews, gates, times, and routes.  The ability to do this on
the fly (so to speak), using desktop computing rather than mainframes,
has significant implications.

According to the article, AT&T would not let Mr. Karmarkar discuss it or
publish his findings, due to obvious commercial considerations.  When
AT&T had completed implementation, they allowed him to present them in a
professional forum.  After he made his presentation, there was
discussion of whether it actually worked, and some challenged his
assertions.  In defense of his professional standing, Mr. Karmarkar
found it necessary to meet with doubters on an individual basis to
explain his algorithm.

Right now, this project is wholly my personal creation (i.e., I am not
doing this for a company, as part of my job or something), so it's slow
work.  I am developing an AI concept based on the machine-formation of
"opinions" from assimilation and correlation of real-time raw data
streams and existing opinions.  The idea is to correlate data to form
symbols, associate knowledge and opinions with those symbols, and enable
formation of layers of opinions through integration.  I have a construct
of opinions as vectors and need a computer application that rapidly
considers a vast array of loosely associated opinions and either selects
existing opinions, or forms new opinions, upon which to base selection
and execution of a set of "learned" output sequences that become
real-time response (e.g., conversational robotic speech).  I believe Mr.
Karmarkar's algorithm holds promise.

OK, that's the basic situation.  If anyone has useful information about
this admittedly esoteric application, I would appreciate it if they
could provide a helping hand.

Thanks,
Mark Van Noy





  • Prev by Date: RE: Different Methods inside one package
  • Next by Date: RE: Different Methods inside one package
  • Previous by thread: Question - Karmarkar's Algorithm
  • Next by thread: combination of two ContourPlots - impossible?