9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is the norm a black box as well? Or is it the usual norm for Banach spaces, $\|\cdot\|_\infty$? $\endgroup$
    – Jack Poulson
    Commented Apr 18, 2012 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
    Commented Apr 18, 2012 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
    Commented Apr 18, 2012 at 8:03
  • $\begingroup$ @Jed: $F$ is linear, so it is already differentiable. $\endgroup$
    – shuhalo
    Commented Apr 18, 2012 at 8:03

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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