\section{Introduction}

In \cite{aos19} the problem of optimal design of statistical experiments was revisited in the broad framework of polynomial regressions on semi-algebraic domains. A numerical solution was proposed, based on the so-called moment-SOS (sums of squares) hierarchy of semidefinite programming relaxations \cite{l10}. While optimality arguments were used in \cite{aos19} to derive many of the results, the dual to the problem of optimal experimental design was not explicitly constructed and studied. It is the purpose of this note to clarify this point in a self-contained and direct way. \new{We believe that a significantly shorter, separate, elementary derivation of the dual is welcome, and its interpretation is informative.} 
	
We use elementary arguments of convex analysis to show how the Christoffel-Darboux polynomial, ubiquitous in approximation theory and data science \cite{lp19}, arises naturally in the dual to the D-optimal design problem.

\section{\new{Primal formulation of the approximate design problem}}

Let  $\S^n$ denote the set of symmetric real matrices of size $n$. Given a vector $\v_d(\mathbf{x})$ whose elements form a basis of the vector space of real polynomials of degree up to $d$ in the vector indeterminate $\mathbf{x} \in \mathbb{R}^n$, let
\[
\mathscr{M}_d(\Spt):=\left\{\mathbf{y} \in \mathbb{R}^{n_d} : \mathbf{y} = \int_\Spt \v_d(\mathbf{x})d\mu(\mathbf{x}) \:\text{for some positive Borel measure $\mu$ on $\Spt$}\right\}
\]
denote the convex cone of moments of degree up to $d$ on a given compact semi-algebraic set
$\Spt \in \mathbb{R}^n$ with non-empty interior. This cone has dimension
\[
n_d:=\frac{(n+d)!}{n!\:d!}.
\]
Given a measure $\mu$ and its moment vector $\mathbf{y} \in \mathscr{M}_{2d}(\Spt)$, define the moment matrix
\[
\mathbf{M}_d(\mathbf{y}):=\int_\Spt \v_d(\mathbf{x})\v^\star_d(\mathbf{x})d\mu(\mathbf{x}) \in \S^{n_d}
\]
where the star denotes transposition. Each entry of the above matrix $\v_d(\mathbf{x})\v^\star_d(\mathbf{x})$ is a polynomial of degree up to $2d$, and hence it is a linear combination of elements in basis vector $\v_{2d}(\mathbf{x})$. Consequently, each entry of $\mathbf{M}_d(\mathbf{y})$ is a linear combination of entries of the moment vector $\mathbf{y}$, whose dimension is $n_{2d}$. It follows that $\mathbf{M}_d$ can be interpreted as a linear map from $\mathbb{R}^{n_{2d}}$ to $\S^{n_d}$, 
and let $\mathbf{M}^\star_d$ denote its adjoint map from $\S^{n_d}$ to $\mathbb{R}^{n_{2d}}$, defined such that
\begin{equation}\label{adjoint}
\text{trace}(\mathbf{M}_d(\mathbf{y})\mathbf{X}) = \mathbf{M}^\star_d(\mathbf{X})\mathbf{y}
\end{equation}
holds for all $\mathbf{X} \in \S^{n_d}$ and $\mathbf{y} \in \mathbb{R}^{n_{2d}}$.

Given a matrix $\mathbf{A} \in \mathbb{R}^{m\times n_d}$, a vector $\b \in \mathbb{R}^m$, a vector $\c \in \mathbb{R}^{n_d}$ and a strictly concave function $\phi$ from $\S^{n_d}$ to $\mathbb{R}$, consider the primal optimal design problem
\begin{equation}\label{primal}
\begin{array}{ll}
\inf_{\mathbf{y}} & \c^\star  \mathbf{y} - \phi(\mathbf{M}_d(\mathbf{y}))\\
\text{s.t.} & \mathbf{A}\mathbf{y} = \b \\
& \mathbf{y} \in \mathscr{M}_{\new{2}d}(\Spt)
\end{array}
\end{equation}
where the infimum is with respect to vectors $\mathbf{y} \in \mathbb{R}^{n_d}$.

\section{\new{Dual formulation of the approximate design problem}}

In problem (\ref{primal}) we introduce the matrix variable $\mathbf{Y} \in \S^{n_d}$ and equality constraint $\mathbf{Y}=\mathbf{M}_d(\mathbf{y})$, the Lagrange multipliers $\mathbf{X}$, $\mathbf{z}$, $\mathbf{p}$ and the Lagrangian
\[
f(\mathbf{X},\mathbf{z},\mathbf{p},\mathbf{Y},\mathbf{y}):=\c^\star \mathbf{y} - \phi(\mathbf{Y}) + \text{trace}\left\{\mathbf{X}(\mathbf{Y}-\mathbf{M}_d(\mathbf{y}))\right\} + \mathbf{z}^\star (\b-\mathbf{A}\mathbf{y}) - \mathbf{p}^\star \mathbf{y}
\]
where $\mathbf{X} \in \S^{n_d}$, $\mathbf{z} \in \mathbb{R}^m$ and $\mathbf{p}$ belongs to $\mathscr{P}_{\new{2}d}(\Spt)$, the convex cone of polynomials \new{of degree at most $2d$} that are positive on $\mathbf{X}$, which is dual to the moment cone $\mathscr{M}_{\new{2}d}(\Spt)$ according to the Riesz-Haviland Theorem \cite[Theorem 3.1]{l10}.
Use \eqref{adjoint} to rearrange terms as follows
\[
f(\mathbf{X},\mathbf{z},\mathbf{p},\mathbf{Y},\mathbf{y}) = \b^\star  \mathbf{z} + \left\{\text{trace}(\mathbf{X}\mathbf{Y})-\phi(\mathbf{Y})\right\} +  \{\c^\star  - \mathbf{z}^\star \mathbf{A} - \mathbf{M}^\star_d(\mathbf{X}) -\mathbf{p}^\star\}\mathbf{y}.
\]
The dual problem to \eqref{primal} is obtained by minimizing the dual function
\[
g(\mathbf{X},\mathbf{z},\mathbf{p}):=\inf_{\mathbf{Y}\in \S^{n_d},\:\mathbf{y}\in\mathbb{R}^{n_{\new{2}d}}} f(\mathbf{X},\mathbf{z},\mathbf{p},\mathbf{Y},\mathbf{y}).
\]
First observe that this function is bounded below only if
\begin{equation}\label{poly}
\mathbf{p}^\star = \c^\star  - \mathbf{z}^\star \mathbf{A} - \mathbf{M}^\star_d(\mathbf{X}).
\end{equation}
Defining
\[
\phi^\star(\mathbf{X}) := \inf_{\mathbf{Y}\in\S^{n_d}} \left\{\text{trace}(\mathbf{X}\mathbf{Y})-\phi(\mathbf{Y})\right\}
\]
as the concave conjugate function to $\phi$, the problem of maximizing the dual function becomes
\begin{equation}\label{dual}
\begin{array}{ll}
\sup_{\mathbf{X},\mathbf{z}} & \b^\star \mathbf{z} + \phi^\star(\mathbf{X}) \\
\text{s.t.} & \c^\star - \mathbf{z}^\star \mathbf{A} - \mathbf{M}^\star_d(\mathbf{X}) \in \mathscr{P}_{\new{2}d}(\Spt)
\end{array}
\end{equation}
where the supremum is with respect to matrices $\mathbf{X} \in \S^{n_d}$ and vector $\mathbf{z} \in \mathbb{R}^m$.
\new{Letting $p(x):= \mathbf{M}^\star_d(\mathbf{X})\v_{2d}(\mathbf{x}) = \v_d(\mathbf{x})^\star \mathbf{X} \v_d(\mathbf{x})$},
the conic constraint in dual problem \eqref{dual} can be formulated
as a polynomial positivity constraint
\[
(\c^\star-\mathbf{z}^\star \mathbf{A})\v_{2d}(\mathbf{x}) \geq p(\mathbf{x})
\]
satisfied for all $\mathbf{x} \in \Spt$.

\begin{theorem}[Duality for optimal design]\label{duality}
Problems \eqref{primal} and \eqref{dual} are in strong duality, i.e. their values coincide.
\end{theorem}

{\bf Proof:}
Weak duality, i.e. the value of primal problem \eqref{primal} is greater than or equal to the value of dual problem \eqref{dual}, follows from the inequality
\[
\phi^\star(\mathbf{X})+\phi(\mathbf{Y}) \leq \text{trace}(\mathbf{X}\mathbf{Y})
\]
which holds by definition of $\phi^\star$ for every positive semidefinite pair $\mathbf{X}$, $\mathbf{Y}$.
Indeed, for any feasible $\mathbf{X}$, $\mathbf{y}$, $\mathbf{z}$ it holds
\[
0 \leq (\c^\star  - \mathbf{z}^\star\mathbf{A} - \mathbf{M}^\star_d(\mathbf{X}))\mathbf{y} = \c^\star\mathbf{y} -\b^\star\mathbf{z} - \text{trace}(\mathbf{X}\mathbf{M}_d(\mathbf{y}))
\leq \c^\star\mathbf{y}  - \b^\star\mathbf{z} - \phi^\star(\mathbf{X}) - \phi(\mathbf{M}_d(\mathbf{y}))
\]
and hence
\[
\c^\star\mathbf{y} - \phi(\mathbf{M}_d(\mathbf{y})) \geq \b^\star\mathbf{z} + \phi^\star(\mathbf{X}).
\]
Strong duality, i.e. the above inequality is an equality for any optimal values $\hat{\mathbf{X}}$, $\hat{\mathbf{y}}$, $\hat{\mathbf{z}}$ follows from concavity of function $\phi$ and the so-called Slater qualification constraint \cite[Section C.1]{l10}, i.e. the existence of an interior point for primal problem \eqref{primal}: choose e.g. the vector of moments of an atomic measure supported on $\Spt$ with more than $n_d$ distinct atoms. Then the moment matrix $\mathbf{M}_d(\mathbf{y})$ is positive definite. Equivalently, the complementarity condition
\begin{equation}\label{comp}
\hat{\mathbf{p}}^\star \hat{\mathbf{y}} = 0
\end{equation}
holds for $\hat{\mathbf{p}}^\star:=\c^\star  - \hat{\mathbf{z}}^\star\mathbf{A} - \mathbf{M}^\star_d(\hat{\mathbf{X}})$ as in \eqref{poly}.
$\Box$

\section{Christoffel-Darboux polynomial}

In \cite{aos19} various functions $\phi$ are considered, depending on the optimal design problem of interest.
In optimal design problem \eqref{primal}, let
\begin{equation}\label{logdet}
\phi(\mathbf{Y}) := \log\det\mathbf{Y}, \quad \mathbf{A} \mathbf{y} := \int_\Spt d\mu(\mathbf{x}), \quad \b = 1, \quad \c = 0
\end{equation}
i.e. we are minimizing over probability measures supported on $\Spt$ a function $\phi$ which is
the classical barrier function used in interior point methods for semidefinite programming \cite{nn94}. The domain of $\phi$ is the cone of positive definite matrices.
This optimal design problem has the same solution as the D-optimal design problem corresponding to the positively homogeneous objective function $(\det\mathbf{Y})^{-1/n_d}$.

\begin{theorem}\label{cd}
Problem \eqref{primal} with data \eqref{logdet} has a unique solution
\[
\hat{\mathbf{y}} \in \mathscr{M}_{\new{2}d}(\{\mathbf{x} \in \Spt : p(\mathbf{x}) = n_d\})
\]
where $p(\mathbf{x}):=\v^\star_d(\mathbf{x})\mathbf{M}^{-1}_d( \hat{\mathbf{y}})\v_d(\mathbf{x})$ is the Christoffel-Darboux polynomial \new{associated to $\hat{\mathbf{y}}$.}
\end{theorem}

{\bf Proof:}
Uniqueness of the solution $\hat{\mathbf{y}}$ follows from convexity of the feasibiliy set and strict concavity of the objective function in problem \eqref{primal}.
The solution $\hat{\mathbf{y}}$ is an interior point, i.e. $\mathbf{M}_d(\hat{\mathbf{y}})$ is positive definite.  As explained in the proof of Theorem \ref{duality}, the Karush-Kuhn-Tucker (KKT) optimality conditions
are necessary and sufficient for an optimal solution, see e.g. \cite[Section C.1]{l10}: all partial derivatives of the Lagrange dual function $f$ must vanish, and this implies that
\[
\frac{\partial f}{\partial \mathbf{Y}} = \hat{\mathbf{X}}-\frac{\partial \phi}{\partial \mathbf{Y}}(\mathbf{M}_d(\hat{\mathbf{y}})) = 0
\]
and hence that
\[
\hat{\mathbf{X}} = \mathbf{M}^{-1}_d(\hat{\mathbf{y}})
\]
for an optimal primal-dual pair $\hat{\mathbf{X}}$, $\hat{\mathbf{y}}$. From the complementarity condition \eqref{comp} and property \eqref{adjoint} we deduce that the optimal $\hat\mathbf{z}$ satisfies
\[
\hat{\mathbf{z}} = -\mathbf{M}^\star_d(\mathbf{M}^{-1}_d(\hat{\mathbf{y}}))\hat{\mathbf{y}} = -\text{trace}(\mathbf{M}_d(\hat{\mathbf{y}})\mathbf{M}^{-1}_d(\hat{\mathbf{y}})) = -n_d.
\]
Complementarity condition \eqref{comp} means that an optimal vector of moments $\hat{\mathbf{y}}$ corresponds to a measure $\mu$ supported on the zero level set of the optimal
positive polynomial with coefficients $\hat{\mathbf{p}}:=\mathbf{M}^\star_d(\mathbf{M}^{-1}_d(\hat{\mathbf{y}}))-n_d$, i.e. the algebraic set $\{\mathbf{x} \in \Spt : p(\mathbf{x}) = n_d\}$.$\Box$

The concave conjugate function is $\phi^\star(\mathbf{X})=n_d+\phi(\mathbf{X})$, its domain is the cone of positive definite matrices, 
and from the proof of Theorem \ref{cd}, the dual design problem (\ref{dual}) has the simple form
\begin{equation}\label{dual-final}
\begin{array}{ll}
\sup_\mathbf{X} &  \log\det\mathbf{X} \\
\text{s.t.} & n_d - \v_d(\mathbf{x})^\star \mathbf{X} \v_d(\mathbf{x}) \geq 0, \quad \forall \mathbf{x} \in \Spt.
\end{array}
\end{equation}
Its solution is $\hat{\mathbf{X}}=\mathbf{M}^{-1}_d(\hat{\mathbf{y}})$ where $\hat{\mathbf{y}}$ is the unique solution of problem (\ref{primal}).
The Christoffel-Darboux polynomial $p(\mathbf{x})=\v^\star_d(\mathbf{x})\hat{\mathbf{X}}\v_d(\mathbf{x})$ is SOS since matrix $\hat{\mathbf{X}}$ is positive definite, and dual matrix $\mathbf{X}$ is such that $n_d \geq \v_d(\mathbf{x})^\star \mathbf{X} \v_d(\mathbf{x}) \geq 0$ for all $\mathbf{x} \in \Spt$.

From Theorem \ref{cd} the optimal sequence of moments $\hat{\mathbf{y}}$ in primal problem \eqref{primal} has a representing atomic measure $\mu$ whose atoms are given by  the level set of the Christoffel-Darboux polynomial. This sequence of moments is unique, but there could be another measure, atomic or not, with the same moments.

Dual problem \eqref{dual-final} has also an interpretation in computational geometry. Indeed if $d=1$ then 
$\mathbf{x}\mapsto p(\mathbf{x})=n_d-\v_d(\mathbf{x})^T\mathbf{X}\v_d(\mathbf{x})$ is a quadratic  polynomial and so the set 
$\mathcal{E}:=\{\mathbf{x} \in \mathbb{R}^n : p(\mathbf{x})\geq0\}$  is an ellipsoid that contains $\Spt$, and $\log\det\mathbf{X}$ is related to the volume of $\mathcal{E}$.
So the dual design problem is also equivalent to the problem of finding the ellipsoid of minimum volume that contains $\Spt$, which is the celebrated L\"owner-John ellipsoid problem. For $d=1$ this was already observed in \cite{t16} and therefore 
\eqref{dual-final} can be considered as a generalization to the case $d>1$ of the L\"owner-John ellipsoid problem
with set $\Spt$ and  with $\log\det \mathbf{X}$ as a proxy for the volume of $\mathcal{E}$.


\section{Conclusion}

In this note we use only elementary concepts of convex analysis to show that the Christoffel-Darboux polynomial, so useful in approximation theory and data analysis  \cite{lp19}, also arises naturally in the dual problem of D-optimal experimental design with semi-algebraic data, a standard convex optimization problem in statistics.
Numerically, problem \eqref{primal} is solved with the moment-SOS hierarchy, i.e the moment cone $\mathscr{M}_{\new{2}d}(\Spt)$ is relaxed with a hierarchy of projections of spectrahedra of increasing size.

As shown in \cite{aos19}, the Christoffel-Darboux polynomial can be used as a certificate of finite convergence of the hierarchy: the contact points of its level set at $n_d$ with $\Spt$ are the support of an optimal design. \new{An algorithmic consequence is that an optimal measure for the design problem is concentrated at the maximizers of the Christoffel-Darboux polynomial on the domain. These maximizers can be found numerically with the moment-SOS hierarchy, see \cite[Section 5.2]{aos19}.}

\new{The dual design problem has also a nice interpretation in computational geometry as an extension of the L\"owner-John ellipsopid problem to (i) semi-algebraic domains not necessarily convex and (ii) enclosing sets more general than ellipsoids.}

\new{Another interesting isssue is to study how the Christoffel-Darboux polynomial, or its maximizers, are affected when the semi-algebraic set is perturbed. It is however unclear whether our variational characterization of this polynomial can be useful for that purpose.}

The Christoffel-Darboux polynomial corresponds to a particular choice of a convex function to be minimized in the design problem, namely the logarithmic barrier function of the positive semidefinite cone. It would be \new{insightful} to study the polynomials arising in the dual design problem corresponding to other convex functions of the eigenvalues of positive semidefinite matrices \cite{lo96}.

\subsection*{Acknowledgement}
Support from the ANR-3IA Artificial and Natural Intelligence Toulouse Institute is gratefully acknowledged. \new{This work benefited from feedback from anonymous reviewers.}

