@article{Sagnol2013, author = {Sagnol, Guillaume}, title = {On the semidefinite representation of real functions applied to symmetric matrices}, volume = {439}, journal = {Linear Algebra and its Applications}, number = {10}, doi = {10.1016/j.laa.2013.08.021}, pages = {2829 -- 2843}, year = {2013}, abstract = {We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10.}, language = {en} } @article{Sagnol2013, author = {Sagnol, Guillaume}, title = {Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs}, volume = {161}, journal = {Discrete Applied Mathematics}, number = {1-2}, doi = {10.1016/j.dam.2012.07.016}, pages = {258 -- 276}, year = {2013}, abstract = {We study a family of combinatorial optimization problems defined by a parameter \$p\in[0,1]\$, which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as \$p\$ goes to \$0\$, and to a trivial instance of the knapsack problem as \$p\$ goes to \$1\$. In this article, we establish a matrix inequality which shows that the objective function is submodular for all \$p\in[0,1]\$, from which it follows that the greedy approach, which has often been used for this problem, always gives a design within \$1-1/e\$ of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to \$1\$ as \$p\$ goes to \$1\$.}, language = {en} } @misc{SagnolHarman2013, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Computing exact D-optimal designs by mixed integer second order cone programming}, issn = {1438-0064}, doi = {10.1214/15-AOS1339}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41932}, year = {2013}, abstract = {Let the design of an experiment be represented by an \$s\$-dimensional vector \$\vec{w}\$ of weights with non-negative components. Let the quality of \$\vec{w}\$ for the estimation of the parameters of the statistical model be measured by the criterion of \$D\$-optimality defined as the \$m\$-th root of the determinant of the information matrix \$M(\vec{w})=\sum_{i=1}^s w_iA_iA_i^T\$, where \$A_i\$, \$i=1,...,s\$, are known matrices with \$m\$ rows. In the paper, we show that the criterion of \$D\$-optimality is second-order cone representable. As a result, the method of second order cone programming can be used to compute an approximate \$D\$-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an \emph{exact} \$D\$-optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second order cone problems. We prove that some other widely used criteria are also second order cone representable, for instance the criteria of \$A\$-, and \$G\$-optimality, as well as the criteria of \$D_K\$- and \$A_K\$-optimality, which are extensions of \$D\$-, and \$A\$-optimality used in the case when only a specific system of linear combinations of parameters is of interest. We present several numerical examples demonstrating the efficiency and universality of the proposed method. We show that in many cases the mixed integer second order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.}, language = {en} }