Factoring out common functionality of cvxpy and
convex.jl: The goal of this project is to create an LLVM for CVXlike 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 CVXlike systems and could also provide novel
functionality such as algebraic simplification of optimization
problems. Contact Steven Diamond <stevend2@stanford.edu> if interested.
Optimization over the union of convex sets (i.e., optimization over a disjunction):
even though NPhard in general, these 'disjunctive programs’ can be converted into
a mixedinteger conic programs (MICP) and solved using MILP and MISOCP solvers.
Contact Nick Moehle <moehle@stanford.edu> and Steven Diamond
<stevend2@stanford.edu> if interested.
POGSrelated 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 510 lines of
JuliaPython versus 5060 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 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 matrixvector 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 nonconvex
losses, with substantial focus on binary classification. This project will extend these
results to multiclass 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; FrankWolfe 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.
