  We consider a new and general online resource allocation problem, where the
goal is to maximize a function of a positive semidefinite (PSD) matrix with a
scalar budget constraint. The problem data arrives online, and the algorithm
needs to make an irrevocable decision at each step. Of particular interest are
classic experiment design problems in the online setting, with the algorithm
deciding whether to allocate budget to each experiment as new experiments
become available sequentially.
  We analyze two greedy primal-dual algorithms and provide bounds on their
competitive ratios. Our analysis relies on a smooth surrogate of the objective
function that needs to satisfy a new diminishing returns (PSD-DR) property
(that its gradient is order-reversing with respect to the PSD cone). Using the
representation for monotone maps on the PSD cone given by L\"owner's theorem,
we obtain a convex parametrization of the family of functions satisfying
PSD-DR. We then formulate a convex optimization problem to directly optimize
our competitive ratio bound over this set. This design problem can be solved
offline before the data start arriving. The online algorithm that uses the
designed smoothing is tailored to the given cost function, and enjoys a
competitive ratio at least as good as our optimized bound. We provide examples
of computing the smooth surrogate for D-optimal and A-optimal experiment
design, and demonstrate the performance of the custom-designed algorithm.

Optimization and Control;Data Structures and Algorithms