2
$\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?

Improve this question
$\endgroup$
6
  • 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, 2016 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$
    – Hari
    Apr 22, 2016 at 7:09
  • $\begingroup$ I'm unfamiliar with this distinction. How do they differ? $\endgroup$
    – Wolfgang Bangerth
    Apr 22, 2016 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$
    – Hari
    Apr 22, 2016 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, 2016 at 20:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.