4
$\begingroup$

Let $f(A,F)=\max(A,F)$ where $A\in\mathbb{R}$ is a variable and $F\in\mathbb{R}$ is a constant representing a "floor" below which the result should not be permitted to go.

Is there any obvious expression (algorithm) for a generalized version of $f$ for square matrices $A\in\mathbb{R}^{n\times n}$ and $F $ representing a minimum amount of "positive-definiteness" required in the result?

Background (if needed)

I'm not sure what exactly I mean by "amount of positive-definiteness" but hoping there is some elegant/obvious quantification. My goal is to limit the step size in Quasi-Newton optimization by enforcing a minimum concave-up curvature / positive-definiteness of the estimated Hessian matrix.

I could resort to adding a scalar multiple of the identity matrix to it, but that would be analogous to $f(A,F)=A+F$ in the real case, which is less ideal than $f(A,F)=\max(A,F)$ because it would shorten steps that are already short enough.

Edit:

Do I have to find the smallest eigenvalue $\lambda_{min}$ and evaluate $A+I(F-\lambda_{min})$ i.e. "add enough $I$ to $A$ to make it's smallest eigenvalue $F$"? Is there any way to get an approximate result (even if slightly more positive-definite than required) without having to evaluate the eigenvectors?

$\endgroup$
9
  • 1
    $\begingroup$ People write $A \ge \alpha I$ meaning $x^TAx \ge \alpha x^Tx$ for all $x$. $\endgroup$
    – copper.hat
    May 7, 2020 at 23:00
  • $\begingroup$ @copper.hat So I suppose I need to add "enough $I$" to $A$ for that to become true. So the question becomes how much $I$ is enough? $\endgroup$
    – Museful
    May 7, 2020 at 23:03
  • $\begingroup$ Or use a trust region approach? $\endgroup$
    – copper.hat
    May 7, 2020 at 23:04
  • $\begingroup$ @copper.hat What I have available is an exact algorithm to evaluate the gradient ($\in\mathbb{R}^8$) and an approximate/noisy algorithm to evaluate the objective function. The Hessian ($\in\mathbb{R}^{8x8}$) is estimated from step changes in the gradient. Are trust region approaches appropriate if only the gradient is available? $\endgroup$
    – Museful
    May 7, 2020 at 23:23
  • 1
    $\begingroup$ This looked like a nice presentation: people.maths.ox.ac.uk/hauser/hauser_lecture3.pdf $\endgroup$
    – copper.hat
    May 8, 2020 at 2:16

2 Answers 2

5
$\begingroup$

I'm responding first to your background comment, but it will lead to an approach to your original question. A quasi-Newton method minimizes a smooth function $f:\mathbb R^n \to \mathbb R$ using the iteration $$ \tag{1} x_{k+1} = \arg \min_x f(x_k) + \nabla f(x_k)^T(x - x_k) + \frac12 (x - x_k)^T B_k (x - x_k). $$ Quasi-Newton methods differ in the choice of the matrix $B_k$. (If $B_k = \nabla^2 f(x_k)$, then the above iteration is Newton's method. In quasi-Newton methods, $B_k$ is an approximation to $\nabla^2 f(x_k)$ that can be computed inexpensively.)

The approximation in (1) is good when $x$ is close to $x_k$. It would be natural to add a penalty term to the objective function in (1) to discourage $x$ from straying too far from $x_k$: $$ \tag{2} x_{k+1} = \arg \min_x f(x_k) + \nabla f(x_k)^T(x - x_k) + \frac12 (x - x_k)^T B_k (x - x_k) + \frac1{2t} \|x - x_k \|_2^2. $$ The parameter $t > 0$ can be thought of as a "step size" that controls how severely we are penalized for moving away from $x_k$. Including such a penalty term is a common trick in optimization; for example, the proximal gradient method and the Levenberg-Marquardt algorithm can both be interpreted as using this trick.

I'll assume that $B_k$ is symmetric and positive semidefinite, which is typical in quasi-Newton methods. Setting the gradient of the objective function in (2) with respect to $x$ equal to $0$, we obtain $$ \nabla f(x_k) + (B_k + \frac{1}{t} I)(x - x_k) = 0. $$ Here $I$ is the identity matrix. The coefficient matrix $B_k + \frac{1}{t} I$ is guaranteed to be positive definite. The solution to this equation is $$ \tag{3} x_{k+1} = x_k - (B_k + \frac{1}{t} I)^{-1} \nabla f(x_k). $$ If $t$ is very small, then $(B_k + \frac{1}{t}I)^{-1} \approx t I$, and the update (3) is approximately a gradient descent update with step size $t$. On the other hand, if $t$ is large, then $(B_k + \frac{1}{t}I)^{-1} \approx B_k^{-1}$, and the update (3) is approximately a quasi-Newton update. So the iteration (3) is like a compromise between a quasi-Newton method and gradient descent.

The Levenberg-Marquardt algorithm chooses the parameter $t$ adaptively, as follows. If $f(x_{k+1}) < f(x_k)$, then $x_{k+1}$ is accepted and $t$ is increased by a factor of 10. Otherwise, $x_{k+1}$ is rejected and $t$ is reduced by a factor of $10$, and then $x_{k+1}$ is recomputed. We only accept $x_{k+1}$ once a reduction in the value of $f$ has been achieved. (We don't have to use a factor of 10, but that is a typical choice.)

Note: Here is an important question about the above proposed algorithm. Quasi-Newton methods rely on the fact that the inverse of $B_k$ can be computed efficiently. Otherwise, we might as well just use Newton's method. In the algorithm I proposed, can the inverse of $B_k + \frac{1}{t} I$ be computed efficiently? If not, then we might as well just take $B_k = \nabla^2 f(x_k)$.

Can the quasi-Newton strategies to update $B_{k}^{-1}$ efficiently be adapted to update $(B_k + \frac{1}{t} I)^{-1}$ efficiently?

That is a question I will need to ponder...

$\endgroup$
1
  • $\begingroup$ That's exactly it. The idea of simply using $B_k+\lambda I$ instead of $B_k$ has been growing on me, only to worry about exactly the question you ask at the end, because $B_k^{-1}$ is maintained directly. $\endgroup$
    – Museful
    May 8, 2020 at 14:49
2
$\begingroup$

If you are looking for a generalization of $\max(a,b)$ for matrices you can use the following:

$$ \max(a,b) = \frac{|a+b|}{2}+\frac{|a-b|}{2}. \ \ \ \ \ (1) $$

Now there is a generalization of absolute value for matrices given by $|A|:=\sqrt{A^T A}$ (I'm assuming your matrices are real). With this generalization Eq. (1) is valid also for square (real) matrices.

Edit

The formula above implicitly assumes $a\ge0, \ b\ge0$ which may not be necessarily satisfied (Eq. (1) is valid if $a+b\ge0$). More generally the function $\max(a,b)$ requires to check the positivity of $a-b$. This approach cannot be generalized to matrices as there are matrices which are neither positive nor negative semidefinite. However other generalizations are still possible. For example if we know that $b\ge0$ (this could be the OP's case as supposedly $F\ge0$) we can use

$$ \max'(a,b) = \theta(a) \left ( \frac{|a+b|}{2}+\frac{|a-b|}{2} \right ) + (1-\theta(a)) b $$

where $\theta(x)$ is Heaviside's function. This function can be generalized to matrices $x$ provided $x$ is diagonalizable.

$\endgroup$
2
  • $\begingroup$ Is this perhaps a generalization of $\max(|a|,|b|)$? Thinking about $a=[-1]$ and $b=[-1]$, in which case the result is $[1]$ instead of $[-1]$. $\endgroup$
    – Museful
    May 8, 2020 at 14:07
  • $\begingroup$ You're absolutely right. I assumed in your case you could assume the arguments to be positive, but perhaps you can only assume $F$ to be non-negative. The formula is valid more generally for $a+b\ge 0$. I edited the post $\endgroup$
    – lcv
    May 8, 2020 at 23:02

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.