0

Suppose I have a function $f(x)=||Ax-b||_2^2$. So, its hessian is as follows $\nabla^2(x)=2A^TA$ which is positive definite if $A\ge0$ which means $f(x)$ is convex. But how to determine its convexity if there is additional restriction like $f(x) = ||Ax-b||_2^2/(1-x^Tx)$ where $||x||_2\le1$. My understanding is as $x^Tx$ is a scalar we can take $(1-x^Tx)=c$, where $c$ is also scalar. So, $f(x)=c||Ax-b||_2^2$ is convex given $c$ is defined. But the retriction on $x$ makes me confused. As $||x||_2$ can be equal to 1, so $c\to\infty$ in which case $f(x)$ is no longer convex?

Update: As pointed out the comment, in the 1d case, we have $f(x)=(ax-b)^2/(1-x^2)$, taking $a=1$ and $b=0$, and plotting for the value for the valid range of $|x|\le1$, it looks like a convex function to me!

enter image description here

Getting pretty confused. I am also pretty new to this topic and so I can make some silly mistakes. But I'll be really grateful if someone can clarify. Thanks.

user3086871
  • 287
  • $x^Tx=||x||_2^2$, so why is it a scalar? And in 1D your $f(x) = \frac{(ax-b)^2}{1-x^2}$, which is certainly not convex. – Conifold Jan 31 '20 at 08:07
  • If I understand correctly, $x\in R^n$ and has shape of $n\times1$, and so $x^Tx$ has $1\times n\times{n\times 1}$. And I think it is equal to the 2norm squared which is still a scalar as $||x||2^2=\sum{i=1}^n(x_i)^2$. – user3086871 Jan 31 '20 at 08:16
  • $||Ax-b||_2^2$ is also a "scalar" in this sense. But they both depend on $x$, so the Hessian of $c||Ax-b||_2^2$ is not a constant times the Hessian of $||Ax-b||_2^2$. – Conifold Jan 31 '20 at 08:23
  • Thanks for pointing that out @Conifold. But I was trying to use the convexity preserving property that if f(x) is convex than cf(x) is also convex if c is a constant. But maybe I am missing out on the fact that here $(1-x^Tx)$ may be a scalar but not a constant. – user3086871 Jan 31 '20 at 08:35
  • The formula for the Hessian of the product is $H(fg) = (Hf)g + (\nabla f)^T\nabla g + (\nabla g)^T\nabla f + f(Hg)$ with $f=||Ax-b||_2^2$ and $g=\frac1{1-x^Tx}$ in your case. You'd have to compute it and show that the result is positive definite for $||x||_2<1$. It looks like it might be true in 1D at least. – Conifold Jan 31 '20 at 09:14
  • That's what crossed my mind at first, but given that $g=1/(1-x^T*x)$ is inverse of a term, the Hessian of the whole product becomes rather long and gets out of hand. Hence I was thinking there must be an easier way to do this, and thought of this solution. But it has flaws as you have pointed out. – user3086871 Jan 31 '20 at 09:27
  • Are you sure that you need this? Typically one minimizes $||Ax-b||_2^2$ on $||x||_2\le1$, which would be a convex function on a convex set, or on $||x||_2=1$, which can be done using Lagrange multipliers. – Conifold Jan 31 '20 at 09:39
  • See Rayleigh quotients. – Conifold Jan 31 '20 at 09:49

0 Answers0