Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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$.

share|improve this answer
    
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? –  Elements Mar 25 '11 at 22:22

Look up positive semidefinite matrices, especially item 6.

share|improve this answer

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... ?!?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.