2
$\begingroup$

I encountered a minimization problem involving the following function:

$f(\mathbf{x})=\|\mathbf{x}\|_q^p$

Here, $q>1$ and $0<p<1$. Naturally, each entry of $\mathbf{x}$ is greater than $0$.

I would like to determine the convexity (or concavity) of $f$, but I'm uncertain about how to do it. In my previous experience, I could demonstrate convexity by checking the definition or using rules of convexity, such as the convexity of the sum of two functions or certain composition rules. Or, I could prove the positive semi-definiteness of the Hessian. However, I haven't been able to apply any of these techniques to analyze $f$.

$\endgroup$

1 Answer 1

3
$\begingroup$

Assuming $q > 1, 0 <p < 1$, as per the question:

If $x$ is a nonnegative scalar, $f(\mathbf{x})=\|\mathbf{x}\|_q^p$ is concave, not convex.

For non-scalar $x$, $f(\mathbf{x})=\|\mathbf{x}\|_q^p$ is neither convex nor concave. For instance, for p = 0.5, q = 2, in 2D at $x = [1, 1]^T$, the Hessian of $f(x)$ has eigenvalues of 0.297 and -0.149; so the Hessian is indefinite there, and therefore $f(x)$ is neither convex nor concave.

$\endgroup$
6
  • $\begingroup$ What value of $p$ are you using in your example? For $p=1$ (granted just outside the specified scope) and $q=2$, $f$ would be the euclidean 2 norm. $\endgroup$
    – prubin
    Dec 8, 2023 at 18:54
  • $\begingroup$ @Mark L. Stone, would you please, where can we find a material to learn about the norms and their specifications? (I know there are some books, but I appreciate if it has been dense with focus on only norms). $\endgroup$
    – A.Omidi
    Dec 8, 2023 at 19:22
  • $\begingroup$ @ptubin Sorry. I forgot to include the value of p used in my example, which is 0.5. I just edited my answer to include that. It wasn't hard fr me to find a "counterexample". The set of values in my answer was the first ones I tried. I come up with such counterexamples to convexity or concavity very frequently over at ask.cvxr.com . $\endgroup$ Dec 8, 2023 at 21:06
  • $\begingroup$ @A.Omidi Read and solve some exercises in at least the first 4 or 5 chapters of "Convex Optimization" by Boyd and Vandenberghe web.stanford.edu/~boyd/cvxbook to learn something about convex optimization, and determining convexity and concavity. You can pick up something about norms from Appendix A and supplement that with en.wikipedia.org/wiki/Norm_(mathematics) . $\endgroup$ Dec 8, 2023 at 21:11
  • $\begingroup$ @prubin, with $q = 2$, and $x = [1,1]^T, p = 1-10^{-9}$ is not convex (nor concave). With other values of $x$, perhaps $p = 1 - \epsilon$ is sufficient for non-convexity. Even though q = 2 is not on the edge of convexity for a norm (which is at q = 1), there's no room to spare for allowing $0 < p < 1$ $\endgroup$ Dec 8, 2023 at 21:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.