Lecture 1

Author

Xiaoqian Liu

Optimization

Optimization is the science of making better decisions in unclear environments. — Patrick L. Combettes.

Overview

In this lecture, we introduce the Euclidean space, some concepts in it, and some basic identities and inequalities.

Euclidean space

The Euclidean space \(\mathcal{H}\) is a real finite dimensional vector space equipped with a scalar product \(\langle \cdot, \cdot \rangle: \mathcal{H} \times \mathcal{H} \to \mathbb{R}\), \((x, y) \mapsto \langle x\mid y \rangle\).

  • Properties of the scalar product

    • \(\forall (x, y) \in \mathcal{H}^2, \langle x\mid y \rangle=\langle y\mid x \rangle\)
    • \(\forall \alpha \in \mathbb{R}, \forall (x, y, z) \in \mathcal{H}^3, \langle \alpha x+y \mid z \rangle=\alpha \langle x \mid z \rangle + \langle y \mid z \rangle\)
    • \(\forall x \in \mathcal{H}\setminus\{0\}, \langle x \mid x \rangle>0\)

A norm on \(\mathcal{H}\) is a function \(\lVert \cdot \lVert: \mathcal{H} \to \mathbb{R}\), \(x \mapsto \lVert x \lVert\) such that

  1. \(\forall (x, y) \in \mathcal{H}^2, \lVert x + y \rVert \leq \lVert x \rVert + \lVert y \rVert\)

  2. \(\forall \alpha \in \mathbb{R}, \forall x \in \mathcal{H}, \lVert \alpha x \rVert = \alpha \lVert x \rVert\)

  3. \(\\forall x \in \mathcal{H}, x=0 \iff \lVert x \rVert=0_{\mathcal{H}}\)

The default norm of \(\mathcal{H}\) is the one associated with the scalar product: \[ \forall x \in \mathcal{H}, \lVert x \rVert = \sqrt{\langle x \mid x \rangle}, \tag{1}\] which also gives rise to a distance \[ \forall (x, y) \in \mathcal{H}^2, d(x, y)= \lVert x-y \rVert = \sqrt{\langle x-y \mid x-y \rangle}. \tag{2}\]

Basic identities and inequalities

  • Cauchy–Schwarz: \(\forall (x, y) \in \mathcal{H}^2, |\langle x\mid y \rangle| \leq \lVert x \rVert \lVert y \lVert\). Moreover, \(|\langle x\mid y \rangle| = \lVert x \rVert \lVert y \lVert \iff \exists \alpha \in \mathbb{R}_+, x = \alpha y\)

  • \(\forall (x, y) \in \mathcal{H}^2, \lVert x+y \rVert^2 = \lVert x \lVert^2 + 2\langle x\mid y \rangle + \lVert x \lVert^2\).

  • Parallelogram identity: \(\lVert x+y \rVert^2 + \lVert x-y \rVert^2 = 2\rVert x \lVert^2 + 2\rVert \lVert y \lVert^2\)

  • Polarization identity: \(\langle x\mid y \rangle = \frac{1}{4}\left[\lVert x+y \rVert^2 - \lVert x-y \rVert^2\right]\)

  • Let \(\alpha \in \mathbb{R}\), then \(\lVert \alpha x+(1-\alpha)y \rVert^2 = \alpha \lVert x \rVert^2+ (1-\alpha) \lVert y \rVert^2- \alpha(1-\alpha)\lVert x-y \rVert^2\)

  • \(\langle x\mid y \rangle \leq 0 \iff \forall \alpha\in [0, +\infty), \lVert x \rVert \leq \lVert x -\alpha y\rVert \iff \forall \alpha\in [0, 1], \lVert x \rVert \leq \lVert x -\alpha y\rVert\)

Basic concepts

  • Let \(x \in \mathcal{H}\) and \(\rho \in (0, +\infty)\), the ball with center \(x\) and radius \(\rho\) is \(B(x; \rho) = \{y\in \mathcal{H} \mid \lVert x-y \rVert \leq \rho\}\).

  • Let \(C \in \mathcal{H}\), then \(C\) is an open set if \(\forall x \in \mathcal{H}, \exists \rho \in (0, +\infty), B(x; \rho) \in C\). \(C\) is a closed set if \(\mathcal{H} \setminus C\) is open.

  • Take a sequence \((x_n)_{n \in \mathbb{N}}\) in \(\mathcal{H}\) and a point \(x\in \mathcal{H}\), then \(x_n\) converges to \(x\) if \(\lVert x_n -x \rVert \to 0\) as \(n \to \infty.\) In other words, \(\forall \rho \in (0, \infty), \exists N \in \mathbb{N}, \forall n \in \mathbb{N}, n \geq N \Rightarrow x_n \in B(x; \rho)\).

  • \(C\) is closed means that for every sequence \((x_n)_{n \in \mathbb{N}}\) in \(C\) that converges, say \(x_n \to x\), then \(x \in C.\)

\(~~~~~~\)Ex. Let \(\mathcal{H} = \mathbb{R}, C = (0, 1), x_n=\frac{1}{1+n}\), then \(x_n \to 0\) which is not in \(C\), so \(C\) is not closed.

  • A sequence \((x_n)_{n \in \mathbb{N}}\) in \(\mathcal{H}\) converges if and only if it is a Cauchy sequence: \(\lVert x_n - x_m \rVert \to 0\), as \(n, m \to \infty\).