Convex Optimization · Problem 2.19

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · linear-fractional-functions-and-convex-sets

Problem

Linear-fractional functions and convex sets. Let

f : \mathbf{R}^m \to \mathbf{R}^n

be the linear-fractional function

f(x) = (Ax + b)/(c^T x + d), \qquad \mathbf{dom}\, f = \{x \mid c^T x + d > 0\}.

In this problem we study the inverse image of a convex set

C

under

f

, i.e.,

f^{-1}(C) = \{x \in \mathbf{dom}\, f \mid f(x) \in C\}.

For each of the following sets

C \subseteq \mathbf{R}^n

, give a simple description of

f^{-1}(C)

. ((a)) The halfspace

C = \{y \mid g^T y \leq h\}

(with

g \neq 0

). ((b)) The polyhedron

C = \{y \mid Gy \preceq h\}

. ((c)) The ellipsoid

\{y \mid y^T P^{-1} y \leq 1\}

(where

P \in \mathbf{S}^n_{++}

). ((d)) The solution set of a linear matrix inequality,

C = \{y \mid y_1 A_1 + \cdots + y_n A_n \preceq B\}

, where

A_1, \ldots, A_n, B \in \mathbf{S}^p