最小化高阶多元函数的数学方法

Question

我有一个 12×12 矩阵，其元素是 4 个变量的函数（阶数 1）。如果我对矩阵 进行对角化，那么我会得到 12 个不同的函数（最大阶数为 12）作为特征值。为了获得变量范围内的最小特征值（比如说 -5 到 5），我必须最小化所有函数并比较每个函数的最小值。我被困在这一点上，因为我找不到任何合适的最小化方法。

最初我尝试使用 LLAPACK（因为如果我分配参数值，它会按升序排序）子程序扫描给定范围内变量的 4 维网格中的所有点，但需要很长时间才能覆盖所有点并且比较一下。

然后我检查了梯度下降（和共轭梯度）方法，但这些方法是为二次函数精心设计的，随着阶数的增加，会出现收敛问题，并且最小化变得不可能。

概率方法对我不起作用，因为我需要特定的最低点，并且这些方法可能/可能无法达到它。

可能有一些软件包在不同的编程语言或软件中可用，但我需要知道执行此操作的实际过程。

所以请建议我任何可行的数学方法或技术。

Answer 1

事实上，你有一个对角矩阵与解决方案无关。构造一个线性规划问题，在其中最小化 12 个函数值的最小值，每个函数值都是四个决策变量的线性函数：

import numpy as np
from scipy.optimize import linprog
from numpy.random import default_rng

rand = default_rng(seed=0)

# Function coefficients for all 12 functions and all 4 variables
functions = rand.integers(low=-2, high=2, size=(12, 4), endpoint=True)

# Decision variables: minimum function value, function variables, function assignments
c = np.zeros(1 + 4 + 12)
c[0] = 1  # Only the minimum function value is minimized
integrality = np.zeros(1 + 4 + 12, dtype=bool)
integrality[-12:] = True  # Function assignments are binary

bounds = np.empty((1 + 4 + 12, 2))
bounds[0, :] = -np.inf, np.inf  # Minimum function value is unbounded
bounds[1:5, :] = -5, 5          # Function variables are bounded
bounds[-12:, :] = 0, 1          # Assignments are binary

# Exactly one function must be selected as the minimum
A_eq = np.block([
    [0, np.zeros(4), np.ones(12)],
])

# Big-M for last constraint > the biggest magnitude of f
buffer = 2 * (np.abs(functions) @ np.full(shape=4, fill_value=5)).max()

A_ub = np.block([
    # For each function, it must be >= the minimum m. xf >= m  ->  m - xf <= 0
    [np.ones((12, 1)), -functions, np.zeros((12, 12))],
    # For each function, if it is selected, it must also be <= m.
    # xf <= m + buffer(1-s)  ->  -m + xf + buffer*s <= buffer
    [-np.ones((12, 1)), functions, buffer*np.eye(12)],
])
b_ub = np.zeros(12 + 12)
b_ub[-12:] = buffer

result = linprog(
    c=c, integrality=integrality, bounds=bounds,
    A_eq=A_eq, b_eq=[1],
    A_ub=A_ub, b_ub=b_ub,
)
assert result.success, result.message
m = result.x[0]
x = result.x[1:5]
assigns = result.x[-12:]

print(f'Minimum function i={(assigns > 0.5).nonzero()[0][0]} at value {m}')
print('x =', x)
print('Function values:')
print(functions @ x)

Minimum function i=2 at value -35.000000000000014
x = [ 5. -5. -5. -5.]
Function values:
[ 10.  25. -35. -20.  -5. -10.  -5.   0. -10.  -5.  30. -20.]

Answer 2

IIUC 您有某个域的矩阵值函数，并且想要在该域上优化该矩阵的最低特征值。这实际上不容易通过使用 @Reinderien 建议的线性程序来解决。此外，你的问题是非线性的，但其目标没有连续的二阶导数。

赶时间的你可以尝试

COBYLA

，可以通过

scipy.optimize

获得。

您还应该检查矩阵的所有特征值是否都是真实的，如果不是，则重新表述问题。