# Is there any obvious way to enforce a minimum amount of "positive definiteness" on a matrix?

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?

• People write $A \ge \alpha I$ meaning $x^TAx \ge \alpha x^Tx$ for all $x$. May 7, 2020 at 23:00
• @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? May 7, 2020 at 23:03
• Or use a trust region approach? May 7, 2020 at 23:04
• @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? May 7, 2020 at 23:23
• This looked like a nice presentation: people.maths.ox.ac.uk/hauser/hauser_lecture3.pdf May 8, 2020 at 2:16

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

• 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. May 8, 2020 at 14:49

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.

• 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]$. May 8, 2020 at 14:07
• 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
– lcv
May 8, 2020 at 23:02