1

I was reading the well-known convex optimization PDF lesson by Boyd and Vandenberghe (more specifically chapter 3), and ran into a problem which I haven't been to solve.

On slide 3-20, the perspective function of a function f is defined as : $$g(x,t) = t f({x \over t})$$ assuming $$f : {\rm I\!R}^n → {\rm I\!R}$$ so that $$g : {\rm I\!R}^{n+1} → {\rm I\!R}$$ and also $${x \over t} \in dom f, t > 0$$

The slide says the perspective g of the function f is convex is f is itself convex, before naming 3 examples of functions of which convexity can be proven using this theorem. The first 2 examples seem rather straightforward to me ; however the 3rd example : $$g(x) = (c^T x + d) f ({{Ax + b} \over {c^T x + d}})$$ surprised me a bit ; the slide says this function is convex if f is convex.

It appears the $$g(x,t) = t f({x \over t})$$ function is used here : $$g(Ax + b, c^T x + d) = (c^T x + d) f ({{Ax + b} \over {c^T x + d}})$$ However, I don't quite understand why composing the g function with the function mapping x to Ax + b, and restricting the t variable to have $$t = c^T x + d$$ wouldn't break the g function's convexity ; isn't such function composition subject to the function composition rules defined in slide 3-18 (Vector Composition) ?

Any idea about what I'm missing here ? Thanks in advance for your valuable help guys !

Starkiller7
  • 41

1 Answers1

3

I think I figured out the answer by myself… from what I understood, the reasoning here consists in using a very simple theorem mentioned in slide 3-14 :

f (Ax + b) is convex if f is convex

noting that g(x,t) can be expressed as g(xa) where xa is an "augmented vector variable" :

$$x_a = (x,t) = (x_1, …, x_n, t)$$

and also that :

$$(Ax + b, c^T x + d) = \left( \begin{array}{}A & 0 \\ c^T & 0 \\ \end{array} \right) \cdot \left( \begin{array}{}x \\ t \\ \end{array} \right) + \left( \begin{array}{}b \\ d \\ \end{array} \right) = A_a \cdot x_a + b_a $$

with : $$A_a = \left( \begin{array}{}A & 0 \\ c^T & 0 \\ \end{array} \right), b_a = \left( \begin{array}{}b \\ d \\ \end{array} \right)$$

so we have : $$g (Ax + b, c^T x + d) = g(A_a x_a + b_a)$$

We know that f(x) is convex so g (xa) = g (x, t) is convex too (see theorem about the perspective of functions in my original post), and using the theorem mentioned above in this post, we can deduce that g (Aa xa + ba) is convex as well, hence :

$$h(x) = (c^T x + d) f ({{Ax + b} \over {c^T x + d}})$$ is convex if f is convex.

Starkiller7
  • 41