2
$\begingroup$

Suppose that $A(x) \in \mathbb{R}^{m \times n}$ is a nonlinear matrix function of $x \in \mathbb{R}^d$. We may assume that $A(x)$ is continuously differentiable. Are there any good ways to estimate $\mathrm{argmin}_{x} \|A(x)\|_2$? Also assume that due to some growth properties of the function $A(x)$, this minimizer can only be achieved within a known compact set. There are well known methods when $A(x)$ is linear with respect to $x$, but I don't have that linearity here.

I have tried to implement a few quasi-Newton methods with varying success, and I've also tried MATLAB's fminunc command with reasonable success (stabilizing around local minima is a problem). Unfortunately I'm relatively unfamiliar with the literature on these things (and the literature is quite vast). Are there any general approaches anybody could suggest?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ The answer will probably depend more on the form of $A$ than the fact that you seek its 2-norm minimizer. Can you say more about the form of $A$? $\endgroup$
    – Bill Barth
    Commented Feb 13, 2014 at 21:52
  • $\begingroup$ Very generally, $A = B(x)^{-1} C(x)$, where $B(x)$ and $C(x)$ have entries that are analytic functions of $x$, and $B(x)$ has a bounded inverse. So there's not too much structure here. I'd like to know what are some reliable general methods, I suppose. One can easily reformulate this as minimizing the maximum eigenvalue of a symmetric positive definite matrix, but again the entries will not have much structure. $\endgroup$
    – Christopher A. Wong
    Commented Feb 13, 2014 at 22:01
  • 1
    $\begingroup$ Could you write out an example formulation? How are you characterizing the compact set? Is it box-constrained, or are there other constraints? My gut feeling with your current description is that you'd be better off minimizing the square of the norm (which is differentiable) rather than the norm itself (which is not differentiable). $\endgroup$
    – Geoff Oxberry
    Commented Feb 13, 2014 at 22:22
  • $\begingroup$ I think he's looking for the unconstrained minimum, and the part about it being in a compact set is just to help assure us that the minimum actually exists. $\endgroup$
    – Nick Alger
    Commented Feb 14, 2014 at 8:03
  • $\begingroup$ Also, is the induced 2-norm really important, or would the Frobenius norm suffice? Dealing with differentiable matrix functions becomes so much easier when using the Frobenius norm. $\endgroup$
    – Nick Alger
    Commented Feb 14, 2014 at 8:16

1 Answer 1

Reset to default
1
$\begingroup$

This seems to be exactly the problem addressed in the following paper. Just recast the problem of minimizing $||A||_2$ into a problem of minimizing the maximum eigenvalue of $A^T A$.

Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. I had already been pointed to some of Overton's works, but I appreciate your help. I had not looked at that specific paper. $\endgroup$
    – Christopher A. Wong
    Commented Feb 16, 2014 at 9:38

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.