EE364b: Project Ideas

Professor John Duchi, Stanford University, Spring Quarter 2014–15
  • Factoring out common functionality of cvxpy and convex.jl: The goal of this project is to create an LLVM for CVX-like systems, i.e., a C/C library that factors out the low level operations that all such systems perform. The library will make it much easier to develop new CVX-like systems and could also provide novel functionality such as algebraic simplification of optimization problems. Contact Steven Diamond <stevend2@stanford.edu> if interested.

  • Add SDP support to ECOS: Right now there is a huge gap between the open source cone solvers available in MATLAB and those available outside of MATLAB. Adding SDP support to ECOS would close this gap. Contact Steven Diamond <stevend2@stanford.edu> if interested.

  • Implement a CVX-like system in a new language: R and Scala are the preferred targets. Contact Steven Diamond <stevend2@stanford.edu> if interested.

  • Optimization over the union of convex sets (i.e., optimization over a disjunction): even though NP-hard in general, these 'disjunctive programs’ can be converted into a mixed-integer conic programs (MICP) and solved using MILP and MISOCP solvers. Contact Nick Moehle <moehle@stanford.edu> and Steven Diamond <stevend2@stanford.edu> if interested.

  • POGS-related project: Add CHOLMOD (both CPU and GPU versions) as a solver for the linear system. This would make POGS a lot more applicable in typical cone problem settings, where large sparse systems arise. At the moment POGS only supports an indirect solver for sparse matrices. Contact Chris Fougner <fougner@stanford.edu> and Baris Ungun <ungun@stanford.edu> if interested.

  • POGS Wrapper for Python and Julia. There is already a flat C interface, so creating wrappers for those two languages should be pure CpythonPython or Julia respectively. This would allow people (eg. Baris) to specify problems in about 5-10 lines of JuliaPython versus 50-60 lines of C (not to mention the data handling overhead). Specifying a Lasso problem using the MATLAB wrapper takes 5 lines of code. Also create a cone interface for POGS. Contact Chris Fougner <fougner@stanford.edu> and Baris Ungun <ungun@stanford.edu> if interested.

  • Implement a robust solver in Julia for large-scale SDPs using ADMM by splitting variables according to a chordal decomposition of the data matrix. Contact Madeleine Udell<udell@stanford.edu> if interested.

  • Implement a number of parallel least squares solvers in a language or framework of your choice (eg C, julia, Elemental) and compare their performance on shared or distributed memory architectures. Examples of parallel least squares solvers include conjugate gradients or lsqr with parallel matrix-vector multiply; a randomized Kaczmarz algorithm; an asynchronous randomized Kaczmarz algorithm; or stochastic dual coordinate ascent (SDCA). Contact Madeleine Udell <udell@stanford.edu> if interested.

  • Hit and run should be fast and fun. Hit and run and other Markov Chain Monte Carlo (MCMC) procedures for sampling from convex bodies have seen substantial theoretical development, but their practical upside in optimization has been limited. This project will produce several reference implementations of hit and run algorithms, as well as cutting plane methods using them, in attempt to make them practically viable.

  • Classification, convexity, and detection. There has been recent work on understanding the properties of using convexity in machine learning procedures instead of non-convex losses, with substantial focus on binary classification. This project will extend these results to multi-class classification (or other settings) and make connections to distributed detection problems or other areas. Contact Khashayar Khosravi <khosravi@stanford.edu> if interested. Note: this project requires fairly sophisticated mathematical treatment.

  • Operators for convex optimization. Convex optimization algorithms are built by assuming certain small convex problems are easy to solve. For example, (projected) subgradient descent assumes it is easy to solve quadratic problems over the constraint set; ADMM assumes it is easy to minimize individual terms in an objective (plus a quadratic); Mirror Descent assumes minimizing a Bregman divergence plus linear term is easy; Frank-Wolfe or conditional gradient methods that minimizing a linear function over constraints is easy. In this project, you will propose and investigate some type of alternative operator and see what its effects are for optimization. One example might be the ability to check, in any given direction, what the closest point with higher function value than the current iterate.