Let $f$ be a $C^2$ convex function with Hessian $H$ such that $lI\mathcal\le H(x)\le LI,\ \forall x\in\mathbb{R}^n$. Then using Taylor's theorem it follows that $$f(x)-f(y)+\frac{l}{2}\|y-x\|_2^2\le-\langle y-x,\nabla f(x)\rangle\le f(x)-f(y)+\frac{L}{2}\|y-x\|_2^2$$ where $\|\cdot\|_2$ is the $l_2$ norm. I need to find an upper bound on the following expression $$-\left\langle B(y-x),\nabla f(A x)\right\rangle$$ where $A,B$ are $n\times n$ matrices. Note that here the notation $\nabla f(Ax)$ means evaluating $\nabla f$ at $Ax$.

Using the preceding inequalities I could derive the following bound:$$-\left\langle B(y-x),\nabla f(A x)\right\rangle\le f(Bx)-f(By)+\frac{L}{2}\|By-Ax\|_2^2-\frac{l}{2}\|Bx-Ax\|_2^2$$ However, though the LHS of the inequality beocmes $0$ when $x=y$, the RHS doesn not, in general, which makes me conclude that this must be a loose inequality.

Can anybody help refer me to any existing technique that might help me finding the tightest inequality? Basically, I need the convex function-type inequality as in the first inequalities, and Cauchy-Scwartz type inequality is not useful to me.

Please do not provide a full answer, and give only suggestions, or references to useful techniques. Thanks in advance.

I asked this question here in math.stackexchange too, but nobody responded.


If $A$ is invertible and $BA^{-1}$ is, by any chance, symmetric positive definite, then you could write $$ \langle B(y-x),\nabla f(Ax)\rangle = \langle BA^{-1}A(y-x),\nabla f(Ax)\rangle $$ and use that $\langle BA^{-1}y,x\rangle =: \langle y,x\rangle_{BA^-1}$ defines an inner product. Use your first inequality in this new inner product and norm to get $$ -\langle B(y-x),\nabla f(Ax)\rangle \leq f(Ax)-f(Ay) + \frac{L}2\|A(y-x)\|_{BA^{-1}}^2. $$

| cite | improve this answer | |
  • $\begingroup$ Yes, I have thought about that case, and also got something like that, but thanks anyway. But I am really interested in the case where A, B are both singular. Is there any technique for that? $\endgroup$ – Samrat Mukhopadhyay Aug 4 '17 at 12:11
  • $\begingroup$ Also, as a special case, is it possible to say anything, when B is identity, and A is singular? $\endgroup$ – Samrat Mukhopadhyay Aug 4 '17 at 12:18

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.