Skip to main content

My research is in convex programming, especially in semidefinite programming, and conic linear programming. A few years back I also did research in integer programming. I also have several papers on applications of optimization.

My main research area, which is closest to my heart, is on Semidefinite Programs (SDPs), some of the most exciting, and useful class of optimization problems of the last few decades.

The goal is to produce easy-to-verify, combinatorial certificates for SDPs: for example, to verify

  • infeasibility,
  • weak infeasibility: when an SDP is infeasible, but within zero distance to the set of feasible instances. Weak infeasibility does not happen in linear programming and it leads to very challenging SDPs.
  • Pathological behavior of semidefinite systems: why essentially all “bad” SDPs in the literature look strikingly similar.
  • Positive duality gaps — again a fascinating behavior that leads to very difficult SDPs and cannot happen in linear programming.
  • Exponential size solutions — these are impossible to even write down in a reasonable amount of space.

Interestingly, we can use mostly elementary row operations (coming from Gaussian elimination) to bring SDPs (more generally, conic linear systems) into a form, so the infeasibility, weak infeasibility, etc. become easy to see.

The structural insights that we obtain can be used to preprocess SDPs and to create difficult SDP instance libraries.

An older paper, which deals with a closely related, classical problem is

The geometry of SDPs and more generally of conic LPs (extreme points, degeneracy, etc.)

Reformulating integer programs using basis reduction

These papers show how to reformulate integer programming problems (IPs) by nearly orthogonalizing the columns. The reformulation makes many hard IPs easier, and more surprisingly, it makes most integer programs solvable by just one branch-and-bound node.

Solving a hard, previously unsolved integer program