1
$\begingroup$

I am currently working on a research project that is trying to show that some numerical integration techniques that do well on separable convex functions will not necessarily do well on non-separable convex functions. I hope to show this using by testing these numerical integration techniques on functions of the form:

$f: \mathbb{R}^n \rightarrow \mathbb{R}$ where $f(x) = x^T Q x$

For the purposes of my test, I need $f$ to be convex and relatively "general" (in the sense that the entries of $Q$ are relatively variety and my function $f$ does not look 'special' in some kind of way). Does anyone know of a nice way to generate an $n \times n$ matrix $Q$ that will yield a convex function $f$?

3 Answers 3

2

All you need is $Q$ to be positive definite. You can do this by choosing a random full rank matrix $A$ and let $Q = AA^T$. Now $Q$ will be a symmetric positive definite matrix (provided $A$ is full rank).

If you want to ensure that the matrix you get is positive definite, generate non zero real numbers and have them as the diagonal entries of a matrix $L$. Fill the lower triangle of the matrix with random entries while the entries on the upper triangle of the matrix $L$ be zeros. Let $Q = LL^T$.

Note that the way you generate $L$ (having non-zero entries on diagonal and having $L$ as lower triangular) ensures $L$ is full rank and hence $Q$ is strictly positive definite. ($Q = LL^T$ is called the Cholesky decomposition of the matrix $Q$).

The way this is done you don't need to find out $Q$ to evaluate $f$. Just find $y=L^Tx$ (or $A^Tx$) and evaluate $y^Ty$ to give you your $f(x)$. This will work out cheaper especially for large $N$.

  • 0
    Thank you so much for this. It was exactly what I was looking for. I had a quick follow-up question if you do not mind. I was hoping to look at how my numerical integration techniques perform as the function $f(x) = x^TQx$ becomes "less separable" (meaning the factors of $x_i*x_j$ terms have less of an effect on the objective function value than the factors in $x_i^2$ terms). Is there a way to control that aspect of the matrix Q in the scheme that you proposed?2011-03-25
1

Look up positive semidefinite matrices, especially item 6.

0

The positive semidefinite idea is basic and should suffice. I would suggest also that you consider the following way. You can generate a connected graph with any of the available algorithms out there. Trivially you can create you own to generate a random geometric graph. Let $G(V,E)$ be the graph, $V$ the vertex set and $E$ the edge set. Then you can obtain the adjastency matrix $A$ by assigning $A_{ij}=1$ if the vertices $i$ and $j$ are connected by an edge in the edge set and $A_{ij}=0$ otherwise. You need to build a diagonal matrix $D$ where $D_{ii}$ is the number of connected vertices to the vertex $i$ .

Then you can obtain the laplacian matrix $L=D-A$ which is guaranteed to be a positive semidefinite matrix and the eigenvalues have some very interesting properties.

However, I am not certain how all these fit with your definition of special... ?!?