Convex Optimization

Cones and generalized inequalities

Affine set, convex set and cone

  • A set \(C\) is affine if \(\forall x_1, x_2 \in C\) and \(\forall \theta\), we have \(\theta x_1 + (1-\theta) x_2 \in C\).
    • subspace: If \(C\) is an affine set and \(x_0 \in C\), then \(V = C - x_0 = \{x-x_0\,|x \in C\}\) is a subspace.
    • \(\mathbf{aff}\,C = \{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \sum_i \theta_i = 1\}\), the affine hull of \(C\).
  • A set \(C\) is convex if \(\forall x_1, x_2 \in C\) and \(\forall \theta\) satisfying \(0 \leq \theta \leq 1\), we have \(\theta x_1 + (1 - \theta) x_2 \in C\).
    • \(\mathbf{conv}\,C = \{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \theta_i \geq 0, \sum_i \theta_i = 1\}\), the convex hull of \(C\).
  • A set \(C\) is a cone if \(\forall x \in C\) and \(\forall \theta \geq 0\), we have \(\theta x \in C\).
    • convex cone \(C\): \(\forall x_1, x_2 \in C\) and \(\forall \theta_1, \theta_2 \geq 0\), we have \(\theta_1 x_1 + \theta_2 x_2 \in C\).
    • proper cone \(K\):
      • \(K\) is convex.
      • \(K\) is closed.
      • \(K\) is solid, that is, having nonempty interior.
      • \(K\) is pointed, that is, \(x \in K, -x \in K \implies x = 0\).
    • conic hull of \(C\): \(\{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \theta_i \geq 0\}\)

Some examples of proper cones:

  • \(\mathbf{S}^n\), the set of all positive semidefinite matrix, is a convex cone.

Separating and supporting hyperplanes

  • separating hyperplane: For nonempty convex sets \(C\) and \(D\) satisfying \(C \cap D=\varnothing\), there exist \(a \neq 0\) and \(b\) such that \(a^T x \leq b, \, \forall x \in C\) and \(a^T y \geq b, \, \forall y \in D\). The hyperplane \(\{x\,|\,a^T x=b\}\) is a separating hyperplane for \(C\) and \(D\).
  • supporting hyperplane: For \(C \subseteq \mathbb{R}^n\) and \(x_0 \in \mathbf{bd}\,C = \mathbf{cl}\,C \setminus \mathbf{int}\,C\), if \(a \neq 0\) satisfies \(a^T x \leq a^T x_0, \, \forall x \in C\), then the hyperplane \(\{x\,|\,a^T x = a^T x_0\}\) is a supporting hyperplane to \(C\) at \(x_0\). For any nonempty convex set \(C\) and any \(x_0 \in \mathbf{bd}\,C\), there exists a supporting hyperplane to \(C\) at \(x_0\).
    • strict supporting hyperplane: if the hyperplane is a supporting hyperplane to \(S\) at \(x_0\), and intersects \(S\) only at \(x_0\).
    • If a set is closed, has nonempty interior, and has a supporting hyperplane at every point in its boundary, then it is convex.

Dual cone

The dual cone of a cone \(K\) is defined as: \[ K^* = \{y\,|\,x^T y \geq 0, \, \forall x \in K\} \] Geometrically, \(y \in K^* \Longleftrightarrow -y\) is the normal of a hyperplane that supports K at the origin.

Dual cone can be also defined for an arbitrary set \(S\). For example:

  • The dual cone of subspace \(V \subseteq \mathbb{R}^n\) is its orthogonal complement \(V^\perp=\{y\,|\,v^Ty=0, \, \forall v \in V\}\)

The properties of dual cones (given a cone \(K\)):

  • \(K^*\) is closed and convex.
  • \(K_1 \subseteq K_2 \implies K_2^* \subseteq K_1^*\).
  • \(K\) has nonempty interior \(\implies K^*\) is pointed.
  • \(\mathbf{cl}\,K\) is pointed \(\implies K^*\) as nonempty interior.
  • \(K^{**} = \mathbf{cl}\left(\mathbf{conv}\,K\right)\). This implies if \(K\) is a proper cone, then \(K^{**} = K\).

where \(\mathbf{cl}\,K\) is the closure of \(K\), and \(\mathbf{conv}\,K\) is the convex hull of \(K\).

Generalized inequality

Generalized inequality is a partial ordering defined by a proper cone \(K\): \[ \begin{align} x \preceq_K y &\Longleftrightarrow y - x \in K \\ x \prec_K y &\Longleftrightarrow y - x \in \mathbf{int}\,K \end{align} \]

where \(\mathbf{int}\,K\) means the interior of \(K\). When \(K=\mathbb{R}^n_+\) (\(\mathbb{R}_+\) is the non-negative half of \(\mathbb{R}\)), the induced \(\prec_K\) and \(\preceq_K\) is the ordinary elementwise inquality in \(\mathbb{R}^n\).

\(\preceq_K\)\(\prec_K\)
if \(x \prec_K y\), then \(x \preceq _Ky\)
additiveif \(x \preceq_K y\) and \(u \preceq_K v\), then \(x+u \preceq_K y+v\)if \(x \prec_K y\) and \(u \preceq_K v\), then \(x+u \prec_K y+v\)
transitiveif \(x\preceq_K y\) and \(y \preceq _Kz\), then \(x \preceq_K z\)if \(x\prec_K y\) and \(y \prec _Kz\), then \(x \prec_K z\)
reflective\(x \preceq_K x\)\(x \not\prec_K x\)
antisymmetricif \(x \preceq_K y\) and \(y \preceq_K x\), then \(x = y\)
preserved under limitsif \(x_i \preceq_K y_i\) for \(i = 1, 2, \dots\), \(x_i \to x\) and \(y_i \to y\) as \(i \to \infty\), then \(x \preceq_K y\)
if \(x \prec_K y\), then \(\exists u, v\) small enough, s.t. \(x+u \prec_K y+v\)

Dual generalized inequalities

If \(K\) is a proper cone, then \(K^*\) is also proper. The generalized inequality \(\preceq_{K^*}\) is refered as the dual of the generalized inequality \(\preceq_K\). We further have:

  • \(x \preceq_K y \Longleftrightarrow \lambda^T x \leq \lambda^T y, \, \forall \lambda \succeq_{K^*} 0\)
  • \(x \prec_K y \Longleftrightarrow \lambda^T x < \lambda^T y, \, \forall \lambda \succeq_{K^*} 0, \lambda \neq 0\)

Minimum and minimal elements

  • \(x \in S\) is the minimum element of \(S\) (w.r.t. \(\preceq_K\)) \(\Longleftrightarrow\) any one of:
    • for every \(y \in S\), we have \(x \preceq_K y\)
    • \(S \subseteq x + K\)
  • \(x \in S\) is a minimal element of \(S\) (w.r.t. \(\preceq_K\)) \(\Longleftrightarrow\) any one of:
    • \(y \in S\), \(y \preceq_K x\) \(\implies\) \(y=x\)
    • \((x-K)\cap S = \{x\}\)

Minimum and minimal elements via dual inequalities

  • \(x \in S\) is the minimum element of \(S\) (w.r.t. \(\preceq_K\)) \(\Longleftrightarrow\) any one of:
    • \(\forall \lambda \succ_{K^*} 0\), \(x\) is the unique minimizer of \(\lambda^T z,\,\forall z \in S\).
    • \(\forall \lambda \succ_{K^*} 0\), the hyperplane \(\{y\,|\,\lambda^T(y-x)=0\}\) is a strict supporting hyperplane to \(S\) at \(x\).
  • The necessary and sufficient condition for \(x\) to be minimal in \(S\) (w.r.t \(\preceq_K\)):
    • For a particular \(\lambda \succ_{K^*} 0\), if \(x\) minimizes \(\lambda^T z, \, \forall z \in S \implies x\) is minimal.
    • If \(S\) is convex, then \(\forall\) minimal element \(x\), there \(\exists \lambda \succeq_{K^*}, \, \lambda \neq 0\), s.t. \(x\) minimizes \(\lambda^T z, \, \forall z \in S\).