This question is related to the text on page 222-223 on the book Convex Optimization (By Boyd and Vandenberghe). The optimization problem is as follows $$\min. \log(\det(X^{-1}))$$ $$s.t. a_i^TXa_i\leq 1, ~for~ i\in\{1,2\cdots m\}.$$ How to show that the Lagrange dual of above problem is $$\log( \det(\sum_{i=1}^m\lambda_ia_ia_i^T))-1^T\lambda +n, ~ for \sum_{i=1}^m\lambda_ia_ia_i^T ~ being~ positive ~ definite.$$ I just do not how they obtained the term $\log( \det(\sum_{i=1}^m\lambda_ia_ia_i^T))$ in the dual function. Any help in this regard will be much appreciated.
Steps needed to arrive at the Lagrange dual function
convex optimizationlagrange multiplieroptimization
Related Solutions
As you suggested, you can define indicator functions for the sets:
$$ g_i(x) = \begin{cases} 0 & \ x \in X_i \\ +\infty & \ x \notin X_i \end{cases} $$ These are dual to the support functions of those sets: $$ g_i^*(\lambda) = \sup_{x \in X_i} x^T\lambda $$
Now you can formulate the problem like a consensus optimization problem:
$$ \begin{gathered} \inf_{x_i,y_i,z} \sum_i f_i(x_i) + g_i(y_i)\\ \text{s.t.:} \ x_i = z,\ y_i = z \end{gathered} $$
Let's form the Lagrangian for this constrained problem and minimize over the "local" variables $x_i,y_i$ to get an expression in terms of the convex conjugates: $$ \inf_{x_i,y_i,z} \sum_i f_i(x_i) + g_i(y_i) + u_i^T(z-x_i) + v_i^T(z-y_i) \\= \inf_{z} \sum_i -f_i^*(u_i) - g_i^*(v_i) + (u_i+v_i)^T z $$ Minimizing over the "consensus" variable $z$ gives an implicit equality constraint. The dual problem is thus: $$ \begin{gathered} \sup_{u_i,v_i} \sum_i -f_i^*(u_i) - g_i^*(v_i)\\ \text{s.t.:} \ \sum_i u_i + v_i = 0 \end{gathered} $$ Some caveats: this formulation is only really useful if the sets $X_i$ admit simple support functions $g_i^*$. Also, while this always gives a lower bound of the optimal value of the original problem, to get strong duality there are some technical conditions you need. (See the hypotheses of Fenchel's duality theorem in a convex analysis text.)
Convex functions are defined for convex domains; for a domain that happens to be a product space this is no different. Recall what it means for a set $A$ to be convex: for all $x,y\in A$ and $t\in [0,1]$ we must have $tx+(1-t)y\in A$. This presupposes $A$ has an additive and scalar multiplicative structure, i.e. $A$ is a vector space. The space $\mathbb{R}^{n_1}\times\cdots\times \mathbb{R}^{n_m} \simeq \mathbb{R}^{n_1\cdots n_m}$, or generally any direct product of vector spaces, inherits the obvious vector space structure from each of the multiplicands, and so the concept of convex domain/subset is well-defined.
If $A$ happens to be a product of convex sets $S_1\subset \mathbb{R}^m$ and $S_2\subset \mathbb{R}^p$, then it can be proved that $A$ is convex, but this is not a necessary condition (consider the unit disc, which is not a product space by itself, but it is a convex subset of the product space $\mathbb{R}^2$).
In any case, once the domain is convex the provided definition makes sense. For example, your Lagrange dual $g$ is a function with domain the entirety of $\mathbb{R}^{m+p}$ (as $\lambda$ and $\nu$ have no restrictions), which is trivially a convex subset of itself, so there are no problems. To be explicit, concavity of $g$ means that for any $\lambda_1,\lambda_2,\nu_1,\nu_2$, and $t\in [0,1]$, $$g(t\lambda_1+(1-t)\lambda_2,t\nu_1+(1-t)\nu_2) \geq t g(\lambda_1,\nu_1) + (1-t) g(\lambda_2,\nu_2)$$ which is just the given definition with $x=(\lambda_1,\nu_1), y=(\lambda_2,\nu_2)$ and the inequality sign reversed.
Best Answer
$a_{i}^{T}Xa_{i} \leq 1$
to:
$\mbox{tr}((a_{i}a_{i}^{T})X) \leq 1$.
This is done using a couple of standard tricks:
A. Since $\mbox{tr}(s)=s$ for any scalar,
$a_{i}^{T}Xa_{i} = \mbox{tr}(a_{i}^{T}Xa_{i}) \leq 1$.
B. By the cyclic property of the trace of a product,
$\mbox{tr}((a_{i}a_{i}^{T})X) \leq 1$.
A second issue is where $f_{0}^{*}(Y)$ comes from. This is discussed in example 3.23 on page 92 of the book.
The final step is applying (5.11) to the problem to get (5.15)
Our primal problem is problem is
$\min \log \det \left( X^{-1} \right) $
subject to
$ \mathcal{A} X \preceq 1 $
where $\mathcal{A}$ is the linear operator
$\mathcal{A}X=\left[ \begin{array}{c} \mbox{tr}((a_{1}a_{1}^{T})X) \\ \mbox{tr}((a_{2}a_{2}^{T})X) \\ \vdots \\ \mbox{tr}((a_{m}a_{m}^{T})X) \end{array} \right]. $
The transpose of $\mathcal{A}$ is
$\mathcal{A}^{T}y=\sum_{i=1}^{m} y_{i} \left( a_{i}a_{i}^{T} \right). $
We have from (5.11) that
$g(\lambda) = \inf_{x} -b^{T}\lambda - f_{0}^{*}(-\mathcal{A}^{T}\lambda)$
where I've suppressed the $\nu$ terms since there are no equality constraints.
Thus
$g(\lambda)=\inf_{x} -1^{T} \lambda -f_{0}^{*}(-\mathcal{A}^{T}\lambda)$
Then
$g(\lambda)=-1^{T}\lambda -\left( \log \det \left( -(-\mathcal{A}^{T}\lambda)^{-1} \right) -n \right)$
as long as $\mathcal{A}^{T}\lambda \succ 0$.
Since $\log \det Z^{-1} = -\log \det Z$ for postivde definite $Z$, this simplifies to
$g(\lambda)= \left\{ \begin{array}{ll} -1^{T}\lambda + \log \det \left( \mathcal{A}^{T}\lambda \right) +n & \mathcal{A}^{T}\lambda \succ 0 \\ -\infty & \mbox{otherwise.} \end{array} \right. $