3
$\begingroup$

I am having an unconstrained optimization problem, where the Hessian is positive semidefinite and block diagonal. The function is strictly convex, hence, the curvature condition ($ s^{T}_{k}y_{k} > 0$) is supposed to be always satisfied. Here, $s_{k}$ and $y_{k}$ are the usual secant pairs, where $s_{k} = x_{k}-x_{k-1}$ and $y_{k}=g_{k}-g_{k-1}$, where $g_{k}$ is the gradient at iteration $k$.

I am noticing that this curvature condition is indeed getting satisfied if I take the entire variable vector and gradient vector. But I was hoping that it will be satisfied at the block level, also, for all the blocks. i.e., by restricting $s$ and $y$ to block level vectors, for all the blocks. This is not being observed for all the blocks. My intuition says that it should happen because the blocks of a PSD matrix are also PSD. Can somebody give more understanding about this?

$\endgroup$
  • 1
    $\begingroup$ If the problem is strictly convex, then the Hessian needs to actually be positive definite, not just semidefinite. As far as your intuition is concerned, it is correct that the condition needs to hold blockwise. Of course, if your Hessian is blockdiagonal, then that means that your objective function consists of two parts that you sum together, but where each of your variables appears in only one term or the other. In such cases, you could just solve the problem by solving the two sub-problems independently. $\endgroup$ – Wolfgang Bangerth Apr 21 '16 at 16:26
  • $\begingroup$ Thanks for your comments. Maybe, the positive definite condition for the Hessian holds only for strongly convex functions. My function is strictly convex but not strongly convex. $\endgroup$ – haripkannan Apr 22 '16 at 7:09
  • $\begingroup$ I'm unfamiliar with this distinction. How do they differ? $\endgroup$ – Wolfgang Bangerth Apr 22 '16 at 11:53
  • $\begingroup$ There is some information here: en.wikipedia.org/wiki/Convex_function. Positive definiteness is a sufficient but not necessary condition for strict convexity. Any strongly convex function has a hessian with strictly positive eigen values everywhere in its domain and is also, strictly convex. But a strictly convex function only satisfies the Jensen's inequality strictly, it may have hessians with zero valued eigen values in its domain. $\endgroup$ – haripkannan Apr 22 '16 at 14:14
  • $\begingroup$ Ah, I see. But Newton's method has trouble converging for functions that are not strongly convex, precisely because otherwise the Hessian may have zero eigenvalues and consequently is not invertible. $\endgroup$ – Wolfgang Bangerth Apr 22 '16 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.