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?

$\endgroup$
  • 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 Feb 13 '14 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 Feb 13 '14 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 Feb 13 '14 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 Feb 14 '14 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 Feb 14 '14 at 8:16
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

$\endgroup$
  • $\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 Feb 16 '14 at 9:38

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.