Let $V$ be a finite-dimensional vector space with norm $\|\cdot\|$ and let $F : V \rightarrow \mathbb R$ be a bounded linear functional. It is only given as black-box.

I would like to estimate the norm of $F$ (from above and below). As $F$ is a black-box, the only way to do so is to test it with unit vectors from $V$ and, based on the result, find $v \in S^1 V$ that maximizes $|F(v)|$.

Do you know such an algorithm? In the application that I have in mind, $V$ is a finite-element space and $F$ is a complicated functional on that space.

EDIT: My first idea is to choose $v \in S^1 V$ randomly, perturb it into several directions, say, $v_1,\dots,v_k$, and then repeat the procedure with the $v_i$ that got the biggest $F(v_i)$. I do not know where to find algorithms and analysis for this problem.

  • $\begingroup$ Is the norm a black box as well? Or is it the usual norm for Banach spaces, $\|\cdot\|_\infty$? $\endgroup$ – Jack Poulson Apr 18 '12 at 3:06
  • $\begingroup$ Also, are you interested in the norm in a region (or at a point) where the function has continuous derivative? $\endgroup$ – Jed Brown Apr 18 '12 at 4:32
  • $\begingroup$ @Jack: The norm of the vector space is computable, and on a finite element space it can be computed by the mass matrix and the stiffness matrix. ($0$-th and $1$-st derivatives). $\endgroup$ – shuhalo Apr 18 '12 at 8:03
  • $\begingroup$ @Jed: $F$ is linear, so it is already differentiable. $\endgroup$ – shuhalo Apr 18 '12 at 8:03

If your space $V$ is a Hilbert space, then Riesz theorem says that you can represent $F(v)=\left< f, v \right>$ and you can compute $f$ as you mention by trying out unit vectors. If the space is higher dimensional, then this becomes impractical, but you can at least compute estimates of $f$ by computing $F(v)$ for a sequence of random vectors $v$.


Maybe you can modify Hager's condition number estimator (see, e.g., the paper http://eprints.ma.man.ac.uk/321/01/35608.pdf), which bounds $\|A^{-1}\|$ when a factorization of $A$ is known, to work for your particular case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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