如何为整数优化任务定义 objective 函数？

Question

我需要在 [1, 10] 范围内找到 k，这是满足 binomial(k, 2)≥ m 的最小正整数，其中 m≥3 - 整数。 binomial() 函数是 the binominal coefficient.

我的尝试是：

经过一些代数步骤后，我找到了最小化任务：min k(k-1) - 2m ≥ 0、s.t。 m≥3。我已经定义了 objective 函数和渐变。在 objective 函数中，我修复了 m=3，我的问题是如何为变量 m.

定义整数域

from scipy.optimize import line_search

# objective function
def objective(k):
  m = 3
  return k*(k-1)-2*m

# gradient for the objective function
def gradient(k):
    return 2.0 * k - 1

# define range
r_min, r_max = 1, 11

# prepare inputs
inputs = arange(r_min, r_max, 1)
# compute targets
targets = [objective(k) for k in inputs]

# define the starting point
point = 1.0
# define the direction to move
direction = 1.0
# print the initial conditions
print('start=%.1f, direction=%.1f' % (point, direction))
# perform the line search
result = line_search(objective, gradient, point, direction)
print(result)

我看到了

LineSearchWarning: The line search algorithm did not converge

问题。如何在Python中定义objective函数？

Answer 1

您希望最小化 k 使得 k(k-1)-2m≥0，对 k 有额外的限制，我们稍后会回来。你可以显式地求解这个不等式，首先求解相应的方程，即求 P:=X²-X-2m 的根。二次公式给出根 (1±√(1+4m²))/2。由于 P(x)→∞ 为 x→±∞，你知道满足你的不等式的 x 是最大根之上和最小根之下的那些。由于您只对正解感兴趣，并且由于 1-√(1+m²)<0，所需的解集是 [(1+√(1+m²))/2,∞)。在这些解中，最小的整数是 (1+√(1+m²))/2 的 ceil，它严格大于 1。让 k=ceil((1+sqrt(1+m**2))/2) 成为那个整数。如果k≤10，那么你的问题有解，就是k。否则，您的问题将无解。在 Python 中，您会得到以下内容：

import math

def solve(m):
  k = math.ceil((1+math.sqrt(1+m**2))/2)
  return k if k <= 10 else None

如何为整数优化任务定义 objective 函数？

How to define the objective function for integer optimization task?

python

mathematical-optimization