无约束问题优化

• 约束是原来优化问题降维的实现方法
• 约束的构造依赖于具体的问题，每个可解的问题降维的方法不一样。

本文件用bootstrap距包估计求最小值。

基本思路

无约束问题在某个方形区域上的最小值，是其中最简单的情形。

source("~/R/optim_no_restriction.R")
n = 500
c = 5
fun = function(x) sqrt(sum(x^2))
optim.squre.bootstrap(f = fun,c = 5, n = 500) %>% head
sum(runif(n, -c, c)^2) %>% sqrt

从结果可以看出，如果没有利用到目标函数本身的信息，我们得到最优解的概率很少！如果我们拥有一些信息比如变量的L1范数很少, 优化问题变成了 \[\mathop{min} \limits_{x \in R^n} f(x) \; s.t. \; g(x) = \|x\|_{L_1} = r\]

背后的逻辑是这样的，\(X \sim F\) then \(f(X) \sim \sim F(f^{-1}(t))\), for any sample \(X_k\), we set \(Pr(f(X_k) - min(f) < \delta) = p\), then we have probability of p to get a point \(X_k\), which satisfies \(f(X_k) < min(f) + \delta\). 问题是这个概率p非常之小，通过直接抽样得到这个值是几乎可能的。例如上述优化问题得到在0处的无约束最小值，For \(\delta\) 的差距，我们对应的概率约等于 \((\frac{\delta}{c})^n\),所以直接抽样可以保证我们以概率1得到任意接近的解，但是抽样次数需要 \((\frac{c}{\delta})^n\). 这样算法复杂度就是 \(m^n\), 这样的问题在n 维数比较少的时候可以直接计算，但是维数较大的时候就没有办法计算了。

至此，我们明白了必须找到更多优化问题的信息。例如，在此问题中，我们构造 \(L_1\) 约束，发现一个简单的事实，随着r的递增，条件本质下却界的估计递增，于是我们根据数据得出规律，调整抽样分布，或者说我们适当的改变X的分布，使得抽取到足够接近最小值的概率增大。给定信息 \(g(x) < r \approx funciton(\delta)\), then we have \(f(X_k) < min(f) + \delta\)。先验信息带来的是分布的改变，我们根据改变后的分布进行抽样，使得 \(f(X)\) 的分布集中在它的最小值附近。

所以，约束的选取至关重要，它是对问题信息的提取，给定约束生成信息域的条件下，优化问题的形式是简单的。约束是原来优化问题降维的实现方法。约束的构造依赖于具体的问题。下面我们构造约束条件优化问题加快速度。

举个例子，假设我要这个时刻我的血压值，血压值一定是某种意义上最适合我和所处环境，是某个优化问题的解，那么假如我知道全世界现在每个原子的状态和运行方式，得到无穷多个变量，我计算能力无比强大，那么我一定的精确的计算我的血压值。我只能得到一部分原子的数据，然而根据这些数据我能够预测我的血压值，约束条件就是关于这些原子一种总结，是全部信息域的一个与血压值密切相关的子信息域，血压值对我们来说是不可知的，是一个随机变量，那么在给定约束子信息域下我们能得到一个关于血压值的很好的估计，那么我们称这个约束信息域包含了大量的关于血压值的信息。比如把我现在的心跳当成一个约束条件，那么在此约束下，我能够一定程度上准确估计我的心跳。还有一种情况，自己去创造一个包含血压信息的约束变量，比如我拿个血压计去测量得到一个数值Y, 那么随机变量Y包含大量的关于血压的信息，我们能根据此信息准确的预测我的血压值。这个例子的核心思想是：

• 任何量都是不完全可知的，任何量在未来某个时刻一定是个随机变量
• 任何量都是在完全信息下某个优化问题的解
• 因为不完全可知性，任何量的随机性，我只能根据当前状态一定程度上预测在未来某个时刻是什么
• 任何量是完全信息域下的某个子信息域的可测函数，因此我们预测该量，该做的就是选定合适的约束生成子信息域，然后将该量投影到此子信息域上，并且用该投影作为预测。也就是我们需要把复杂的完全信息域中的该量投影的简单的约束子信息域中来考虑。
• 子信息域的选取是非常细节的工作，依赖于该量的具体形式。

综上求解优化问题，需要对优化问题的背景有很多的了解，根据优化问题的背景，提出一些包含该量信息域中大量信息的约束量（比如优化的是GDP，那么我们就应该考虑教育约束，法制约束等等），初步选取大量约束以后，通过变量选择，选择出来与该问题真正密切相关的约束，优化量对于约束有简单的变化规律，于是我们可以采用常见的模型来估计该变化规律，最终得出具体优化问题的解。

约束化无约束问题

问题1： \(\mathop{min} \limits_{x \in R^n} f(x) \; s.t. \; g(x) = |x_1| = r\)

问题2： \(\mathop{min} \limits_{x \in R^n} f(x) \; s.t. \; g(x) = \|x\|_{L_1} = r\)

问题3： \(\mathop{min} \limits_{x \in R^n} f(x) \; s.t. \; g(x) = \|x\|_{L_0} = d\)

这三个约束，是原来优化问题的简化信息域，在此约束生成信息域下，优化问题是个简单的函数，对于简单的函数，我们就有办法来估计了！

通过估计这两个优化问题，我们得到一些关于X分布的信息, to make sure \(f(x)\) is small.

source("~/R/matrix_hull.R")
source("~/R/optim/optim_fun.R")
c = 10
n = 50
m = 1000
dat = matrix(runif(n*m, -c, c), ncol = n)
f = function(x) sqrt(sum(x^2))
g1 = function(x) abs(x[1])
g2 = function(x) sum(abs(x))
# g3 = function(x) sum(x == 0)

dat1 = f.g.gen.data(f, g1, dat) %>% as.data.frame()
dat2 = f.g.gen.data(f, g2, dat) %>% as.data.frame()
# dat3 = f.g.gen.data(f, g3, dat)

qplot(x = g_value, y = f_value, data = dat1, geom = "point")
matrix.hull(dat1[,1:2]) 
matrix.hull.plot(dat1[,1:2])

logi.fun = function(x) sum(abs(x)) < 20
contrict.uniform.sample(m = 1000, n = 10, c = 5, logi.fun)

str(.Last.value)