Readings in Optimization

DISCLAIMER : The bunch of scandalous opinions expressed on this webpage are solely the authors. (and Pink Floyd, Oscar Wilde!)

They do not express the opinion of the other participants, nor that of the Math department.

"No dark sarcasm in the classroom" --- Pink Floyd (The Wall)

"Everyone who is incapable of learning has taken to teaching" --- Oscar Wilde (The Decay of Lying)

Introduction

A weekly seminar on Optimization (Theory and Applications). ALL ARE WELCOME!.

The seminar should be of interest to both optimizers (and pessimizers! ) (Thanks to Henry Wolkowicz from whom this quote was shamelessly stolen). Are the "others" listening???

Check the webpage regularly for updates.

Your comments and suggestions are most welcome.

Please inform me about missing links and necessary updates by sending email to kartis@rpi.edu

Current News

  • Kartik's thesis defense on the 5th of July 2002, Amos Eaton 411, 10.00 am.
  • Dr. Angelia Nedic will be talking on Subgradient Methods for Convex Minimization on the 1st of April 2002, Amos Eaton 214, 4.00-5.00 pm.
  • Dr. Nello Cristianini will be talking on Advances in Kernel Based Learning Methods and their Applications on the 26th of March 2002, Amos Eaton 214, 4.00-5.00 pm.
  • Prof. Michael Overton will be talking on Optimization of Spectral and Pseudo-Spectral Functions by a Gradient Bundle Scheme on the 18th of March 2002, Amos Eaton 214, 4.00-5.00 pm.
  • Prof. Jean-Louis Goffin will be talking on Analytic centers methods, mixed integer programming and variational inequalities on the 31st of January 2002, Amos Eaton 214, 4.00-5.00 pm.

    • Check out Mathematical Sciences Seminar webpage for more details. Hope you can all make it then.

  • 1st Columbia Optimization Day, 28th November 2001

    • Participant List (starring in alphabetical order)

  • Lucian Basescu
  • Prof. Kristin Bennett
  • Jinbo Bi
  • Steve Braun (oops, that should be Dr. Steve Braun!)
  • Sava Dediu
  • Xiaoyun (Sharron) Ji
  • Kartik Krishnan
  • Abigail Michaels
  • Michinari Momma
  • Jufeng Peng

    • Next meeting

    3rd May (Friday) at 11.00 AM in AE 402 (Kartik Krishnan)

    Topics

    CAVEAT : Talks are tentative, and subject to change.

  • Talk 1 (9/14/01) : Introduction to semidefinite programming (Kartik Krishnan)(Pointers)
  • Talk 2 (9/21/01) : Randomized Approximation algorithms for MAX SAT and MAX CUT (Lucian Basescu) (Pointers)
  • Talk 3 (9/28/01) : Branch and Price : Column Generation for Solving Huge Integer Programs (Xiaoyun Ji) (Pointers)
  • Talk 4 (10/5/01) : Modeling issues in semidefinite programming (Steve Braun)
  • Talk 5 (10/12/01) : Krylov subspace methods :- A technique for partial least squares regression?(Jinbo Bi)
  • Talk 6 (10/19/01) : The GRASP approach to Job Shop Scheduling (Jufeng Peng)(Pointers)
  • Talk 7 (10/26/01) : The maximum stable set problem : Copositive programming and semidefinite relaxations(Kartik Krishnan) (Pointers)
  • Talk 8 (11/2/01) : Analytic center cutting plane methods (ACCPM) for convex optimization (Luc Basescu)(Pointers)
  • Talk 9 (11/9/01) : Searching for superconductors? : An application of support vector machines (Abigail Michaels)
  • Talk 10 (11/16/01) : Column generation approaches to data mining (Prof. Kristin Bennett)(Pointers)
  • Talk 11 (11/23/01) : Thanksgiving break! (No talk :-))
  • Talk 12 (11/30/01) : Duality in Support Vector Machines (Jinbo Bi)(Pointers)
  • Talk 13 (12/7/01) : Linear Programming approaches to semidefinite programming problems (Kartik Krishnan)(Pointers)
  • Talk 14 (01/18/02) : Nonlinear Programming approaches to semidefinite programming problems (Kartik Krishnan)(Pointers)
  • Talk 15 (01/25/02) : A Mixed Integer Nonlinear Programming Model for Multiple robots coordination (Jufeng Peng)
  • Talk 16 (02/01/02) : No talk
  • Talk 17 (02/08/02) : Using ACCPM to solving linear programming problems (Luc Basescu)
  • Talk 18 (02/15/02) : Rank two relaxation heuristics for max cut and stable set problems (Kartik Krishnan) (Pointers)
  • Talk 19 (02/22/02) : The clique partitioning problem and related graph problems (Xiaoyun Ji)
  • Talk 20 (03/29/02) : Communicating without errors, Lovasz theta function and the sandwich theorem (Kartik Krishnan)(Pointers)
  • Talk 21 (04/05/02) : A Pattern Search Method for Model Selection of Support Vector Regression (Michinari Momma)
  • Talk 22 (04/12/02) : Techniques for model step regression (Abigail Michaels)
  • Talk 23 (04/19/02) : Focusing and imaging using eigenfunctions of the scattering operator (Sava Dediu) (Pointers)
  • Talk 24 (04/26/02) : An SDP cutting plane approach for the maxcut problem : Part I Preliminaries (Kartik Krishnan)(Pointers)
  • Talk 25 (05/03/02) : An SDP cutting plane approach for the maxcut problem : Part II Can we do it only solving LP's? (Kartik Krishnan)(Pointers)
  • Talk 26 : Second Order Cone Programming (Kartik Krishnan)(Pointers)
  • Talk 27 : Solving Convex Programs using Random Walks (Kartik Krishnan)( Pointers)

    • Mathematical Programming resources on the web

  • Michael Trick's Operations Research Page
  • e-Optimization.com
  • Linear Programming FAQ
  • Nonlinear Programming FAQ
  • Christoph Helmberg's Semidefinite Programming homepage (a comprehensive site on the SDP)
  • Optimization Online
  • Interior Points Online
  • Bibliography on Semidefinite Programming : Maintained by Henry Wolkowicz
  • Bibliography on Interior Point Optimization : Maintained by John Mitchell
  • Farid Alizadeh's SDP course at IEOR, Columbia University (Fall 2001)
  • Branch Cut and Price Resource Page (Maintained by Ted Ralphs at Lehigh University)
  • Decision Tree for Optimization Software(great for Optimization Software)
  • Kartik's Optimization links
  • John Mitchell's OR sites
  • Kristin Bennett's webpage
  • A compendium of NP optimization problems
  • MathSciNet : Mathematical Reviews on the web
    • (great for digging up papers)
  • ACCPM's homepage : The analytic center cutting plane method for solving large scale convex optimization problems

    • Survey articles on semidefinite programming (Pointers for Kartik's talk)

  • L. Vandenberghe and S. Boyd
    "Semidefinite Programming",
    SIAM Review 38(1996), pp. 49-95
    ps file
  • M. Todd
    "Semidefinite Optimization",
    Survey paper, School Of Operations Research and Industrial Engineering
    Cornell University, February 2001
    ps file
  • C. Helmberg
    "Semidefinite Programming for Combinatorial Optimization",
    Habilitation Thesis, TU Berlin, January 2000
    ZIB-REPORT ZR-00-34, Konrad-Zuse-Zentrum Berlin, October 2000
    ps file

    • Semidefinite Programming in Combinatorial Optimization (Pointers for Luc's talk)

  • M. Goemans and D.P. Williamson
    "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming",
    J. ACM 42(1995), pp. 1115-1145
    pdf file
  • D.P. Williamson
    "Lecture Notes on Approximation Algorithms, Fall 1998", IBM Research Report RC 21409, February 1999
    ps file (Lectures 6 and 7 on the max cut problem and the GW algorithm)

    • Solving Large Scale Integer Programs (Pointers for Sharron's talk)

  • C. Barnhart, E. Johnson, G. Nemhauser, M. Savelsbergh and P. Vance
    "Branch and Price : Column Generation for solving huge Integer Programs", January 1996
    ps file

    • Using GRASP for Job Shop Scheduling (Pointers for Jufeng's talk)

  • L.S. Pitsoulis and M.G.C. Resende
    "Greedy Randomized adaptive search procedures", AT&T Labs Technical Report, January 2001
    pdf file
  • S. Binato, W.J. Hery, D.M. Loewenstern and M.G.C. Resende
    "A greedy randomized adaptive search procedure for job shop scheduling", AT&T Labs Technical Report, March 2000.
    pdf file

    • Copositive Programming : Linear and Semidefinite Relaxations for the copositive cone (Pointers for Kartik's 2nd talk)

  • E. De Klerk and D.V. Pasechnik
    "Approximating the stability number of a graph via copositive programming", Technical Report, Delft University of Technology, January 2001.
    ps file
  • Pablo Parrilo
    "SDP tests for higher order quadratic programming relaxations and matrix copositivity", 7th DIMACS Implementation Challenge, Rutgers University, October 2000.
    ps file
  • Pablo Parrilo
    "Semidefinite programming relaxations for semialgebraic problems", Technical Report, Control and Dynamical Systems, Caltech.
    ps file
  • I. Bomze and E. De Klerk
    "Solving standard quadratic optimization problems via semidefinite and copositive programming", Technical report TR 2001-03, ISDS, University of Vienna, Austria, September 2001.
    ps file
  • Martin Aigner and Gunter Ziegler
    "Turan's graph theorem", Chapter 27, Proofs from the book, Springer 1999

    • Analytic center cutting plane methods for convex optimization (Pointers for Luc's 2nd talk)

  • John Mitchell
    "Polynomial interior point cutting plane methods", Technical report, Dept. of Mathematical Sciences, RPI, July 2001.
    ps file

    • Column generation in Data Mining (Pointers for Kristin Bennett's talk)

  • Kristin Bennett, A. Demiriz and G. Raetsch
    "Sparse regression ensembles in infinite and finite hypothesis spaces", NeuroCOLT2 technical report, Royal Holloway College, London, September 2000. (to appear in Machine Learning)
    ps file
  • Kristin Bennett, A. Demiriz and J. Shawe-Taylor
    "Linear Programming Boosting via Column Generation". (to appear in Machine Learning)
    ps file

    • Duality in Support Vector Machines (Pointers for Jinbo's 2nd talk)

  • Jinbo Bi and Kristin Bennett
    "Duality, Geometry, and Support Vector Regression", to appear in Advances in Neural Information Processing Systems, 2002.
    ps file
  • Kristin Bennett and Erin Bredensteiner
    "Duality and Geometry in SVM Classifiers", Proceedings of the 17th International Conference on Machine Learning, Pat Langley Editor, Morgan Kaufmann, San Francisco, 2000, pp. 57-64.
    ps file

    • LP approaches to the SDP (Pointers for Kartik's 3rd talk)

  • Kartik Krishnan and John Mitchell
    "Linear Programming approaches to semidefinite programming problems", Talk at Courant Institute of Mathematical Sciences, New York University, 27th November 2001.
    ps file
  • Kartik Krishnan and John Mitchell
    "Linear Programming approaches to semidefinite programming problems", Technical Report, Dept. of Mathematical Sciences, RPI, May 2001.
    ps file
  • Kartik Krishnan and John Mitchell
    "Semi-infinite linear programming approaches to semidefinite programming problems", Technical Report, Dept. of Mathematical Sciences, RPI, August 2001.
    ps file

    • Nonlinear Programming techniques for semidefinite programming problems (Pointers for Kartik's 4th talk)

  • Sam Burer, Renato Monteiro and Yin Zhang
    "Solving a Class of Semidefinite Programs via Nonlinear Programming", working paper, Department of Computational and Applied Mathematics, Rice University, May 2001
    ps file
  • Sam Burer, Renato Monteiro and Yin Zhang
    "A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDP's", working paper, School of ISyE, Georgia Tech, May 2001
    ps file

    • Rank two relaxation heuristics for max cut and stable set problems (Pointers for Kartik's 5th talk)

  • S. Burer, R.D.C. Monteiro and Y. Zhang
    "Maximum Stable Set Formulations and Heuristics Based on Continuous Optimization", TR00-34, Computational and Applied Mathematics, Rice University, Dec 2000.
    ps file
  • S. Burer, R.D.C. Monteiro and Y. Zhang
    "Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs, TR00-33, Computational and Applied Mathematics, Rice University
    ps file

    • Communicating without errors, Lovasz theta function and the Sandwich theorem (Pointers for Kartik's 6th talk)

  • Martin Aigner and Gunter Ziegler
    "Communicating without errors", Chapter 28, Proofs from the book, Springer 1999
  • Don Knuth
    "The Sandwich Theorem", ps file
  • Farid Alizadeh
    "The Lovasz theta function", Lecture Notes 5, Semidefinite Programming, Fall 2001, Columbia University, pdf file

    • Second Order Cone Programming

  • Farid Alizadeh and Donald Goldfarb
    "Second Order Cone Programming", RUTCOR RRR Report number 51-2001, Rutgers University.
    ps file
  • L.S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret
    "Second Order Cone Programming", Linear Algebra and Its Applications (284), pp. 193-228, 1998.
    ps file

    • Focusing and imaging using eigenfunctions of the scattering operator

  • T. Douglas Mast, Adrian I. Nachman and Robert C. Waag
    "Focusing and imaging using eigenfunctions of the scattering operator"
    pdf file

    • An SDP cutting plane approach for the maxcut problem

  • Kartik Krishnan
    "A cutting plane LP approach for the maxcut problem"
    Weekly Optimization Seminar, RPI, Troy, April 26th, 2002
    ps file
  • Christoph Helmberg
    "Semidefinite Programming for Combinatorial Optimization" (especially chapter 6)
    Habilitation Thesis, TU Berlin, January 2000
    ZIB-REPORT ZR-00-34, Konrad-Zuse-Zentrum Berlin, October 2000
    ps file
  • John Mitchell
    "Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems"
    Journal of Combinatorial Optimization, 5(2), 2001, pp. 151-166
    html reference
  • Christoph Helmberg
    "A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations",
    ZIB-Report ZR-01-26, Konrad-Zuse-Zentrum Berlin, October 2001.
    ps file
  • Christoph Helmberg
    "Fixing Variables in Semidefinite Programming",
    SIAM Journal on Matrix Analysis and Applications, Vol 21(3), 2000, pp. 952-969
    SIAM reference
  • Christoph Helmberg and Franz Rendl
    "Solving Quadratic (0,1) problems by semidefinite programs and cutting planes",
    Mathematical Programming, 82(1998), pp. 291-315
    ps file

    • A good comparison is the following interior point LP approach to maxcut.

  • John Mitchell
    "Computational experience with an interior point cutting plane algorithm",
    SIAM Journal on Optimization, Vol 10(4), 2000, pp. 1212-1227
    SIAM reference

    • Other intriguing conic optimization cutting plane approaches for maxcut.

  • Masakazu Muramatsu and Tsunehiro Suzuki
    "A New Second-Order Cone Programming Relaxation for MAX-CUT problems",
    Technical Report CS-01-01, Department of Computer Science, The University of Electro-Communications, Tokyo, May 2001
    Optimization Online
  • Garud Iyengar and Mehmet Cezik
    "Cutting planes for mixed 0-1 semidefinite programming",
    Eigth International Conference on Integer Programming and Combinatorial Optimization (IPCO)
    CORC Technical Reports (gzipped form)

    • Solving Convex Programs via Random Walks

  • Dimitris Bertsimas and Santosh Vempala
    "Solving convex programs by random walks", STOC 02, Montreal, 2002.
    ps file
  • Random Walks and Polynomial-Time Algorithms, Spring 2002 : A course taught by Santosh Vempala at MIT.
    Course schedule
    • Last Updated: 16th-June-02
        kksivara at ncsu dot edu
        Webmaster : Kartik Krishnan
    © Copyright 2002 (Y2K2)