New IPMs Research Group Dr.Tamás Terlaky Dr. Jiming Peng Lois Zhu Qirong Miao Dr. Michael Guoqing Zhang Dr. Bixiang Wang Xin Huang

Other members of the AdvOL Dr. Stavros Kolliopoulos Dr. George Steiner Ellen Fan Yonghua Lou Weizhong Yu Dr. Jingde Du Dr. Petra Huhn

Project

• Project description
  
  New Interior point methods and computational testing of the new IPMs for linear, quadratic and conic-linear programming.
  
  Recently a new class of proximity functions were discovered by Peng, Roos and Terlaky. This novel class of functions allow to develop classes of new Interior Point Methods (IPMs) for linear and conic linear optimization problems. some appealing features of the new proximity functions are:
     1.   allows to design families of large update and large neighborhood IPMs for classes of optimization problems;
     2.   these methods are close to the ones that occur in practical implementation;
     3.   the theoretical worst case complexity is almost identical to the best known complexity of small-step, small neighborhood methods;
     4.   this is a significant step to close the gap between the theory and computational practice of IPMs.

  In this research we will further explore the theoretical properties of self-regular functions. we will work on generalizations to conic linear and smooth convex optimization problems.

  Special attention will be paid to explore computational and implementational aspects. By implementing and benchmarking the various members of the new family of IPMs we will determine which parameter setting enjoys the best practical performance. Experimental software will be developed on the bases of modules of existing libraries of IPM software. This research should determine the practicality and computational efficiency of this new approach.

  To keep the experimental work clean and consistent, first we will restrict to use the self-dual embedding model to solve the initialization problem of IPMs.

  Computational testing and development will be carried out on Unix, on IBM RS-6000 workstations. We plan to make use of the OSL callable library and the ESSL library as well.

• Project goals
  
  1.   To develop and explore the power of the recently identified class of "self-regular proximity" functions when they are applied to design and analyze interior point algorithms for linear and conic linear programming problems.
  
  2.   A family of interior point algorithms are proposed by using the new proximity functions. We want to benchmark these IPMs by developing an experimental software based on modules of exising libraries of IPM software.

• Detailed schedule
  
  In this research group, different people has different focus and responsibilities:
  

  - Prof. Tamás Terlaky		Project Leader
  - Jiming Peng		Ph.D Thesis
  - Lois Zhu		MSc. Thesis
  - Qirong Miao		MSc. Thesis
  - Guoqing Zhang

Hardware

	IBM RS/6000 44P Model 270 Workstation Powerful symmetric processing workstations 1-4 way SMP with POWER3-II copper-based microprocessors and up to 16GB memory Choice of five graphics accelerators for 2D and 3D applications
	SUN ULTRA 10 Ultra 10 is an outstanding animation station and MCAD machine. Creative professionals and mechanical designers, alike, will appreciate the CPU performance, memory capacity and breakthrough graphics for 2D and 3D applications.
	IBM PC NEW Microsoft Windows 2000 operating system included on select models Intel® Pentium® III processors up to 866MHz with 133MHz front-side bus Great technology at an affordable price Leading edge manageability tools Wide range of models
	IBM INFOPRINT 8 COLOR LASER PRINTER Prints up to 8 pages per minute and is more reliable than high-speed personal inkjet printers. Maximum monthly duty cycle is up to 25,000 pages. Utilizing Heidelberg color technology, it produces sharp text and vibrant color images at 600 dpi.
	IBM INFOPRINT 12 LASER PRINTER This sleek, black laser printer prints up to 12 pages per minute at 1200 dpi. Has the ability to switch automatically among print languages and interfaces. Can be directly connected or networked. Small footprint.Weighs just 25 pounds.

Software

• MATLAB
  
• OSL
  
• ESSL
  
• PCX
  
• LIPSOL
  
• C for AIX
  
• VisualAge C++
  
• FORTRAN for AIX
  

Testing

• NETLIB
  
• BPMPD
  
• QPLIB
  
• SDPLIB
  
• DIMACS
  
• CUTE
  
• Bench
  

Usefull links

• CVS Home
  
• CVS Book
  
• CVS Tutorial - Concurrent Versions System

• AIX Documentation: Books
  
• Aix Version 4.3 General Programming
  
• Base Operating System and Extensions Technical Reference, Volume 1 (A-P)
  
• Base Operating System and Extensions Technical Reference, Volume 2 (Q-Z)
  

Publications

1. E. de Klerk, C. Roos and T. Terlaky, Primal--dual potential reduction methods for semidefinite programming using affine--scaling directions (1999). Applied Numerical Mathematics, 29(3) 335--360. A special issue devoted to the HPOPT-I workshop held in Delft, 19-20 September 1996.
2. Z.-Q. Luo, C. Roos and T. Terlaky, Complexity analysis of a logarithmic barrier decomposition method for semi-infinite linear programming (1999). Applied Numerical Mathematics Vol 29(3). 379--395. Special issue dedicated to the HPOPT-I workshop held in Delft, 19-20 September 1996.
3. A. NemirovskiiT, C. Roos and T. Terlaky, On maximization of quadratic forms over intersection of ellipsoids with common center. Mathematical Programming 86 (1999) 3. 463-473.
4. A.B. Berkelaar, B. Jansen, C.Roos and T. Terlaky, Basis- and tripartition identification for quadratic programming and linear complementarity problems. From an interior point solution to an optimal basis and vice versa. Mathematical Programming 86. (1999) 2, 261-282.
5. T. Koltai and T. Terlaky, The Difference between the Managerial and Mathematical Interpretation of Sensitivity Analysis Results in Linear Programming. (To appear in International Journal on Production Economics)
6. T. Terlaky, An Easy Way to Teach Interior Point Methods (2000) To appear in European Journal of Operational Research ??. ??--??.
7. J. Peng, C. Roos and T. Terlaky, New complexity analysis of the primal-dual Newton method for linear optimization. to appear in: Annal of Operations Research.[ps]
8. J. Peng, C. Roos and T. Terlaky, New complexity analysis of primal-dual Newton method for P*(k) linear complementarity problems High Performence Optimization Techniques Kluwer Academic Publishers B.V. 249-269, 1999.[ps]
9. T. Illés, J. Peng, C. Roos and T. Terlaky, A strongly polynomial rounding precedure yielding a maximally complementarity solution for P*(k) linear complementarity problems Siam J. Optimization, Vol(1), 320-340,2000. [ps]
10. E. Klerk, J. Peng, C. Roos and T. Terlaky, A Scaled Gauss-Newton Primal-Dual Search Direction for SDP, To appear in: Siam J. Optimization, [ps]
11. J. Peng, C. Roos and T. Terlaky, New anylysis of search directions for semidefinite programming, Preprint, December 1998. To appear in: J. O. T. A. , [ps]

Technical reports