R 如何计算对偶范数

发布于12月31日

假设我有一个标准||x||.有没有一个R函数或方法可以让我计算对偶范数

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

？

我最初的 idea 是这属于一个约束优化问题，所以我想有一些有用的包来解决这个问题，但我还不能阐明如何做到这一点.

Analytical Dual Norm Solution

确实存在解析的对偶范数表示(见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)
}

使用输入数据

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

我们将获得这一点

> 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

如果你使用的是vector x(而不是矩阵，因为矩阵范数是另一回事，但你可以用类似的方式try ，如下面的代码所示)，也许你可以try pracma包中的fmincon，并定义一个自定义的对偶范数函数，例如，

library(pracma)
dual_norm_numeric <- function(x, p) {
    if (p < 1) {
        stop("Invalide value of p: Shouldn be >= 1!")
    }
    if (p == 1) {
        list(value = max(abs(x)), par = +(abs(x) == max(abs(x))))
    } else {
        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)

x如下

> set.seed(0)

> n <- 10

> x <- rnorm(n, 5)

> set.seed(0)

> n <- 10

> x <- rnorm(n,5)

你会看到

> 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