Filtern
Erscheinungsjahr
- 2015 (2) (entfernen)
Dokumenttyp
- Artikel (2) (entfernen)
Sprache
- Englisch (2)
Volltext vorhanden
- nein (2)
Gehört zur Bibliographie
- nein (2)
Institut
Let the design of an experiment be represented by an $s-$dimensional vector $w$ of weights with nonnegative components. Let the quality of $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(w)=\sum_{i=1}^s w_i A_i A_i^T$, where $A_i$,$i=1,\ldots,s$ are known matrices with $m$ rows.
In this 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 exact $D-$optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of $D_K-$optimality, which measures the quality of $w$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix $K$.
We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of $A-$, $A_K$-, $G-$ and $I-$optimality.
We present several numerical examples demonstrating the efficiency and general applicability 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.
Network spot-checking games: Theory and application to toll enforcing in transportation networks
(2015)
We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.