Yonsei University
Chae-Yeon Xon
Yonsei University, School of Economics
Home/Resources/Geometry, Dynamics, and Operators for Economic Models/III-17
Sets, Optimization, and Sequential Information · Chapter III-17

Matrix Optimization and Information Allocation

Information design frequently chooses a positive-semidefinite precision or retention matrix under budget and technological restrictions. Schur complements translate quadratic risk bounds into block-matrix constraints. Matrix KKT conditions and dual gaps provide certificates, while fixed spectra restrict which coordinate-wise information allocations are attainable.

Conceptual map

  1. III-17.01Positive-semidefinite order
  2. III-17.02Schur complements
  3. III-17.03Semidefinite programs
  4. III-17.04Directional optimization
  5. III-17.05Isospectral information design

1. Precision matrices live in the PSD cone

Information allocation compares positive-semidefinite matrices through their action on directions. Singular matrices require range conditions because some target directions receive zero precision.

For symmetric matrices \(A\) and \(B\), write \(A\succeq B\) when \(A-B\) is positive semidefinite. Every \(P\succeq0\) has a unique positive-semidefinite square root and a Moore–Penrose inverse \(P^{\dagger}\). The quadratic target risk \(c^{\top}P^{\dagger}c\) is finite in the information interpretation only when \(c\in \operatorname{range}(P)\).

2. Generalized Schur complement

Proposition 1 · Singular block-PSD epigraph

For \(P\succeq0\),

\[\begin{bmatrix}P & c \\ c^{\top } & t\end{bmatrix}\succeq 0 \Longleftrightarrow c\in \operatorname{range}(P) \text{and} t\ge c^{\top }P^{\dagger }c.\](1)

Proof. A vector in \(\operatorname{ker}(P)\) must be orthogonal to \(c\) for the block quadratic form to remain nonnegative under arbitrary scaling; hence \(c\) lies in \(\operatorname{range}(P)\). Write \(c=Pu\) with \(u=P^{\dagger}c\). Completing the square gives \(x^{\top}Px+2\alpha c^{\top}x+\alpha ^{2}t=(x+\alpha u)^{\top}P(x+\alpha u)+\alpha ^{2}(t-c^{\top}P^{\dagger}c)\). ∎

With \(P=\operatorname{diag}(4,0)\) and \(c=(2,0)^{\top}\), the risk is one and the block matrix is PSD exactly when \(t\ge1\). Replacing \(c\) by \((2,0.1)^{\top}\) violates the range condition; no finite \(t\) repairs the block constraint.

3. Information retention as an SDP

Suppose retained signal \(j\) contributes \(a_{j}a_{j}^{\top}\) units of precision per unit weight. With base precision \(P_{0}\), costs \(d_{j}\), and budget \(B\), a target-risk problem is

\[\begin{aligned}\text{minimize}\quad & t \\ \text{subject to}\quad & \begin{bmatrix}P_{0}+\sum_j w_{j}a_{j}a_{j}^{\top} & c \\ c^{\top} & t\end{bmatrix}\succeq0, \\ & \sum_j d_{j}w_{j}\le B,\quad w\ge0.\end{aligned}\](2)

Matrix-valued KKT conditions pair the PSD constraint with a PSD dual matrix. The inner product of primal and dual slack matrices supplies complementarity; eigenvalue feasibility and the dual gap should be reported.

4. Eigenvalues and orientation are separate choices

Proposition 2 · Orthogonal Procrustes value

If \(M=U\Sigma V^{\top}\) is a singular-value decomposition, then

\[\operatorname{max}_{Q^{\top }Q=I} \operatorname{tr}(Q^{\top }M)=\sum _{j}\sigma _{j}(M),\](3)

attained at \(Q=UV^{\top}\) when an orthogonal solution is admissible.

Proof. Write \(\operatorname{tr}(Q^{\top}M)=\operatorname{tr}(V^{\top}Q^{\top}U\Sigma)\). The diagonal entries of the orthogonal matrix \(U^{\top}QV\) are at most one, so the trace is bounded by \(\operatorname{tr}(\Sigma)\). The proposed \(Q\) attains the bound. ∎

Schur–Horn further restricts diagonals under a fixed spectrum: a feasible diagonal is majorized by the eigenvalue vector. With eigenvalues (3,1), any diagonal must sum to four and each entry lies between one and three. The proposed allocation (4,0) has the right sum and is infeasible.

Failure case · Spectrum treated as a free diagonal budget

Eigenvalues specify information along endogenous orthogonal directions. Coordinate-level precision depends on orientation and must satisfy majorization restrictions.

5. Implementation, exercises, and sources

Symmetrize computed matrices, report minimum eigenvalues of every PSD slack, verify the range residual \(\lVert (I-PP^{\dagger})c\rVert\), and compute primal and dual objectives in original units. Inspect sensitivity at singular boundaries.

Download the volume verification script →

Exercises

  1. Verify both examples following (1) by testing the block quadratic form.
  2. Solve (2) when \(P_{0}=I\), \(c=(1,1)^{\top}\), and available signals are the two coordinate directions with equal cost.
  3. List all two-dimensional diagonals feasible under eigenvalues (3,1) and construct an orthogonal rotation attaining each one.
Partial solutions

1. For \(c=(2,0)^{\top}\), completing the square leaves \((t-1)\alpha ^{2}\). For \(c=(2,0.1)^{\top}\), test a block vector whose first component lies in \(\operatorname{ker}(P)\) and scale its last coordinate to create a negative cross term. 3. Every feasible diagonal is (\(d,4-d\)) with \(1\le d\le3\). A rotation with squared cosine (\(d-1\))/2 realizes it.

  1. Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Chapters 4–5, Appendix A.5.SDPs, duality, and Schur complements.
  2. Rajendra Bhatia, Matrix Analysis, Chapters II–III.PSD order and matrix inequalities.
  3. Roger Horn and Charles Johnson, Matrix Analysis.Generalized inverses, majorization, and Schur–Horn structure.

6. Audit checkpoint

Report PSD conventions, singular range conditions, primal and dual slack eigenvalues, budget feasibility, dual gap, complementarity, target orientation, and majorization checks.

7. Scope boundary

The chapter covers PSD order, generalized Schur complements, information-allocation SDPs, orthogonal orientation, and finite-dimensional majorization. SDP complexity theory lies outside scope.

Prerequisites