How can I compute a dual norm?

Question

Suppose I have a norm ||x||. Is there an R function or method that allows me to calculate the dual norm

||y||_* = \max_{x} x^Ty : ||x|| ≤ 1

?

My initial thought is that this falls under a constrained optimization problem, so I imagine there's some useful packages to solve this, but I haven't been able to formulate how to do this.

Answer 1

Analytical Dual Norm Solution

There indeed exists an analytical dual norm representation (see Wiki page)

so we can code the dual norm function like below. It should be noted that, the code below gives a scalar value of dual norm only, rather than the solution of z that enables the supremum (as $par in the outcome of dual_norm_numeric.

dual_norm_analytic <- function(x, p) {
    if (p < 1) {
        stop("Invalide value of p: Shouldn be >= 1!")
    }
    if (p == 1) {
        return(max(abs(x)))
    }
    if (is.infinite(p)) {
        return(sum(abs(x)))
    }
    q <- 1 / (1 - 1 / p)
    sum(abs(x)^q)^(1 / q)
}

with input data

set.seed(0)
n <- 10
x <- rnorm(n, 5)

we will obtain that

> dual_norm_analytic(x, 1)
[1] 7.404653

> dual_norm_analytic(x, 2)
[1] 17.3279

> dual_norm_analytic(x, 3)
[1] 25.15705

---

Numerical Solution by fmincon Optimization

If you are working with a vector x (rather than a matrix, since matrix norm would be a different story, but you might be able to try out in a similar way as shown in a following code), probably you can try fmincon from the pracma package and define a custom dual norm function, e.g.,

library(pracma)
dual_norm_numeric <- function(x, p) {
    if (p < 1) {
        stop("Invalide value of p: Shouldn be >= 1!")
    }
    if (p == 1) {
        val <- max(abs(x))
        sign(x[abs(x) == max(abs(x))])
        return(list(value = val, par = sign(x[abs(x) == val]) * (abs(x) == val)))
    }
    if (is.infinite(p)) {
        return(list(value = sum(abs(x)), par = sign(x)))
    }
    constr <- \(y) sum(abs(y)^p)^(1 / p) - 1
    fobj <- \(y) -sum(x * y)
    out <- fmincon(x * 0, fobj, hin = constr)
    list(value = -out$value, par = out$par)
}

Output (Example)

Given x as below

> set.seed(0)

> n <- 10

> x <- rnorm(n, 5)

> set.seed(0)

> n <- 10

> x <- rnorm(n,5)

and you will see

> dual_norm_numeric(x, 1)
$value
[1] 7.404653

$par
 [1] 0 0 0 0 0 0 0 0 0 1


> dual_norm_numeric(x, 2)
$value
[1] 17.3279

$par
 [1] 0.3614374 0.2697252 0.3652950 0.3619841 0.3124811 0.1996814 0.2349643
 [8] 0.2715437 0.2882193 0.4273251


> dual_norm_numeric(x, 3)
$value
[1] 25.15705

$par
 [1] 0.4989528 0.4310259 0.5016088 0.4993309 0.4639326 0.3708614 0.4022939
 [8] 0.4324763 0.4455585 0.5425285