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