index.Rmd

--- 
title: "Semidefinite Optimization and Relaxation"
author: "Heng Yang"
date: "`r Sys.Date()`"
site: bookdown::bookdown_site
output: bookdown::gitbook
documentclass: book
bibliography: [book.bib]
biblio-style: apalike
link-citations: yes
github-repo: hankyang94/Semidefinite
description: "Lecture notes for Harvard ES 257 Semidefinite Optimization and Relaxation."
---

\newcommand{\calG}{\mathcal{G}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calZ}{\mathcal{Z}}
\newcommand{\mathx}{\mathrm{x}}
\newcommand{\mathy}{\mathrm{y}}
\newcommand{\bbE}{\mathbb{E}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\tldR}{\tilde{R}}
\newcommand{\bbZ}{\mathbb{Z}}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbC}{\mathbb{C}}
\newcommand{\bbF}{\mathbb{F}}
\newcommand{\bbR}{\mathbb{R}}

\newcommand{\Real}[1]{\mathbb{R}^{#1}}
\newcommand{\Comp}[1]{\mathbb{C}^{#1}}
\newcommand{\sym}[1]{\mathbb{S}^{#1}}
\newcommand{\psd}[1]{\sym{#1}_{+}}
\newcommand{\pd}[1]{\sym{#1}_{++}}
\newcommand{\inprod}[2]{\langle #1, #2 \rangle}
\newcommand{\linprod}[2]{\left\langle #1, #2 \right\rangle}
\newcommand{\trace}{\mathrm{tr}}
\newcommand{\tran}{^\top}
<!-- \newcommand{\det}{\mathrm{det}} -->
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\Diag}{\mathrm{Diag}}
\newcommand{\BlkDiag}{\mathrm{BlkDiag}}
\newcommand{\vectorize}{\mathrm{vec}}
\newcommand{\svec}{\mathrm{svec}}
\newcommand{\mat}{\mathrm{mat}}
\newcommand{\smat}{\mathrm{smat}}
\newcommand{\norm}[1]{\Vert #1 \Vert}
\newcommand{\lnorm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\pnorm}[2]{\Vert #1 \Vert_{#2}}
\newcommand{\Fnorm}[1]{\Vert #1 \Vert_\mathrm{F}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\cone}{\mathrm{cone}}
\newcommand{\interior}{\mathrm{int}}
\newcommand{\relint}{\mathrm{ri}}
\newcommand{\poly}[1]{\mathbb{R}[#1]}
\newcommand{\SOd}{\mathrm{SO}(d)}
\newcommand{\SOthree}{\mathrm{SO}(3)}
\newcommand{\Od}{\mathrm{O}(d)}
\newcommand{\Ogroup}{\mathrm{O}}
\newcommand{\usphere}{\mathcal{S}}
\newcommand{\bmath}[1]{\boldsymbol{#1}}
\newcommand{\lbrkt}{[\![}
\newcommand{\rbrkt}{]\!]}
\newcommand{\brkt}[1]{\lbrkt #1 \rbrkt}
\newcommand{\bracket}[1]{[ #1 ]}
\newcommand{\sign}{\mathrm{sgn}}
<!-- \newcommand{\paren}[1]{(#1)}
\renewcommand{\lparen}[1]{\left( #1 \right)} -->
\newcommand{\cbrace}[1]{\{ #1 \}}
\newcommand{\lcbrace}[1]{ \left\{ #1 \right\} }
\newcommand{\aff}{\mathrm{aff}}
\newcommand{\bbN}{\mathbb{N}}
\newcommand{\dist}{\mathrm{dist}}
\newcommand{\subject}{\mathrm{s.t.}}
\newcommand{\cl}{\mathrm{cl}}
\newcommand{\eye}{\mathrm{I}}
\newcommand{\inv}{^{-1}}
\newcommand{\invtran}{^{-\top}}
\newcommand{\Range}{\mathrm{Range}}
\renewcommand{\ker}{\mathrm{ker}}
\newcommand{\face}{\mathrm{face}}
\newcommand{\lmid}{\ \middle\vert\ }
\renewcommand{\Re}{\mathrm{Re}}
\newcommand{\hatmap}[1]{[#1]_{\times}}
\newcommand{\kron}{\otimes}
\newcommand{\skron}{\kron_{\mathrm{s}}}
\newcommand{\Ideal}{\mathrm{Ideal}}
\newcommand{\lexsucc}{\succ_{\mathrm{lex}}}
\newcommand{\lexprec}{\prec_{\mathrm{lex}}}
\newcommand{\grlexsucc}{\succ_{\mathrm{grlex}}}
\newcommand{\grlexprec}{\prec_{\mathrm{grlex}}}
\newcommand{\grevlexsucc}{\succ_{\mathrm{grevlex}}}
\newcommand{\grevlexprec}{\prec_{\mathrm{grevlex}}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\initial}[1]{\mathrm{in}(#1)}
\newcommand{\NormalForm}{\mathrm{NormalForm}}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
<!-- \newcommand{\lceil}[1]{\left\lceil #1 \right\rceil} -->
\newcommand{\qmodule}{\mathrm{Qmodule}}
\newcommand{\mom}{\mathrm{mom}}
\newcommand{\loc}{\mathrm{loc}}
\newcommand{\preorder}{\mathrm{Preorder}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\New}{\mathrm{New}}
\newcommand{\myspan}{\mathrm{span}}


<!-- \newcommand{\deg}{\mathrm{deg}} -->


# Preface {-}

This is the textbook for Harvard ENG-SCI 257: Semidefinite Optimization and Relaxation. 

## Feedback {-}

I would like to invite you to provide comments to the textbook via the following two ways:

- Inline comments with Hypothesis:
    - Go to [Hypothesis](https://hypothes.is) and create an account
    - Install the [Chrome extension of Hypothesis](https://chrome.google.com/webstore/detail/hypothesis-web-pdf-annota/bjfhmglciegochdpefhhlphglcehbmek)
    - Provide public comments to textbook contents and I will try to address them 

- Blog-style comments with Disqus:
    - At the end of each Chapter, there is a Disqus module where you can leave feedback

I would recommend using Disqus for high-level and general feedback regarding the entire Chapter, but using Hypothesis for feedback and questions about the technical details.


## Offerings {-}

Information about the offerings of the class is listed below.

#### 2024 Spring {-}

**Time**: Mon/Wed 2:15 - 3:30pm

**Location**: Science and Engineering Complex, 1.413

**Instructor**: [Heng Yang](https://hankyang.seas.harvard.edu/)

**Teaching Fellow**: [Safwan Hossain](https://safwanhossain.github.io/)

[**Syllabus**](https://docs.google.com/document/d/1H6Wqht_PVw_n8Jl0kXN3HjZfHkeZJYqYWT4ayxvqRlU/edit?usp=sharing)


<!-- #### Acknowledgment {-} -->


# Notation {-}

We will use the following standard notation throughout this book.

**Basics**

|                   |          | 
| :---------------- | :------  |
| $\Real{}$        |   real numbers   |
| $\Real{}_{+}$ | nonnegative real |
| $\Real{}_{++}$| positive real |
| $\mathbb{Z}$        |   integers   |
| $\bbN$    |  nonnegative integers   |
| $\bbN_{+}$ | positive integers |
| $\Real{n}$ |  $n$-D column vector |
| $\Real{n}_{+}$| nonnegative orthant |
| $\Real{n}_{++}$| positive orthant |
| $e_i$ | standard basic vector |
| $\Delta_n := \{x \in \mathbb{R}^n_{+} \mid \sum x_i = 1 \}$ | standard simplex | 

**Matrices**

|                   |          | 
| :---------------- | :------  |
| $\mathbb{R}^{m \times n}$ | $m \times n$ real matrices |
| $\sym{n}$  | $n\times n$ symmetric matrices  |
| $\psd{n}$ | $n\times n$ positive semidefinite matrices |
| $\pd{n}$ | $n\times n$ positive definite matrices |
| $\inprod{A}{B}$ or $\bullet$  | inner product in $\Real{m \times n}$ |
| $\trace(A)$| trace of $A \in \Real{n \times n}$ |
| $A\tran$ | matrix transpose |
| $\det(A)$ | matrix determinant |
| $\rank(A)$ | rank of a matrix |
| $\diag(A)$ | diagonal of a matrix $A$ as a vector |
| $\Diag(a)$ | turning a vector into a diagonal matrix |
| $\BlkDiag(A,B,\dots)$ | block diagonal matrix with blocks $A,B,\dots$ |
| $\succeq 0$ and $\preceq 0$ | positive / negative semidefinite |
| $\succ 0$ and $\prec 0$ | positive / negative definite |
| $\lambda_{\max}$ and $\lambda_{\min}$ | maximum / minimum eigenvalue |
| $\sigma_{\max}$ and $\sigma_{\min}$ | maximum / minimum singular value |
| $\vectorize(A)$ | vectorization of $A \in \Real{m \times n}$
| $\svec(A)$| symmetric vectorization of $A \in \sym{n}$
| $\Fnorm{A}$ | Frobenius norm |
| $\Range(A)$ | span of the column vectors |
| $\ker(A)$ | right null space | 

**Geometry**

|                   |          | 
| :---------------- | :------  |
| $\pnorm{a}{p}$ | $p$-norm |
| $\norm{a}$ | $2$-norm |
| $B(o,r)$ | ball with center $o$ and radius $r$ |
| $\aff (S)$ | affine hull of set $S$ |
| $\conv(S)$ | convex hull of set $S$ |
| $\cone(S)$ | conical hull of set $S$ |
| $\interior(S)$ | interior of set $S$ | 
| $\relint(S)$ | relative interior of set $S$ |
| $\partial S$ | boundary of set $S$ |
| $P^\circ$ | polar of convex body | 
| $P^{*}$ | dual of set $P$ |
| $\Od$ | orthogonal group of dimension $d$ |
| $\SOd$ | special orthogonal group of dimension $d$ |
| $\usphere^{d-1}$ | unit sphere in $\Real{d}$ |

**Optimization**

|                   |          | 
| :---------------- | :------  |
| KKT | Karush–Kuhn–Tucker |
| LP | linear program |
| QP | quadratic program |
| SOCP | second-order cone program |
| SDP | semidefinite program |

**Algebra**

|                   |          | 
| :---------------- | :------  |
| $\poly{x}$ | polynomial ring in $x$ with real coefficients | 
| $\deg$ | degree of a monomial / polynomial |
| $\poly{x}_d$ | polynomials in $x$ of degree up to $d$ |
| $[x]_d$ | vector of monomials of degree up to $d$ |
| $\brkt{x}_d$ | vector of monomials of degree $d$ |