利用GEKKO中非零元素的L0范数/个数约束混合整数非线性优化问题
利用GEKKO中非零元素的L0范数/个数约束混合整数非线性优化问题
提问于 2021-01-23 20:01:41
我想把实现给定的非负整数值b的代价降到最小，它是从GEKKO中的两组非负整数变量x，y线性计算出来的。如果用某种方式说明了我的问题，那么b是x& y上的约束。我的代价函数是非线性的:使用条件/最小的二次函数。除了这些标准约束外，我还有一个约束，要求x中的非零元素的数量至少与x中的最大元素一样大(例如，L0-范数等于LInifity-范数)。
我现在的困难是双重的，因为我对优化和GEKKO的新手相当陌生。
- 我看到GEKKO支持numpy数组，这会使问题陈述更加简洁，但我很难让它发挥作用--导致大量的列表理解，而不是向量化操作。
- 我成功地定义了L0范数约束，GEKKO实际上与它一起运行，但是它没有找到解决方案。我认识到L0问题确实很难解决(例如组合问题)，但不知何故，通过“手工”就可以很容易地找到解决方案。我只是觉得我做错了什么。
我很感激你的帮助！以下是我迄今所做的工作：
from gekko import GEKKO
import numpy as np
# Setup gekko (taken from their MINLP tutorial with more iterations).
m = GEKKO()
m.options.SOLVER = 1 # APOPT is an MINLP solver
m.solver_options = ('minlp_maximum_iterations 500',
'minlp_max_iter_with_int_sol 10',
'minlp_as_nlp 0',
'nlp_maximum_iterations 50',
'minlp_branch_method 1',
'minlp_integer_tol 0.05',
'minlp_gap_tol 0.01')
# Define variables as arrays.
y = m.Array(m.Var, (7), value=1, lb=1, ub=12, integer=True)
x = m.Array(m.Var, (18), value=0, lb=0, ub=8, integer=True)
# Example of the user-defined target values b as constraints (actually input args).
m.Equation(x[2] + y[1] == 7)
m.Equation(x[12] + y[2] == 5)
# This is the L0 constraint.
# I thought using m.Array would make this a nice definition like
# m.Equation(np.count_nonzero(x) >= np.max(x))
# but it didn't, since these numpy functions are not supported in GEKKO.
# So I defined the following , which feels wrong:
m.Equation(m.sum([int(x_i.value > 0) for x_i in x]) >= max(x_i.value for x_i in x))
# Finally, the objective function (intermediates for readability).
k = np.array([m.min2(y_i, 3) for y_i in y])
x_cost = m.Intermediate(m.sum(x * (x + 1)))
y_cost = m.Intermediate(m.sum((k - 1) * (k + 2) + 2.5 * (y - k) * (y + k - 3)))
m.Obj(x_cost + y_cost)
# Solve.
m.solve(disp=True, debug=True)回答 1
Stack Overflow用户
回答已采纳
发布于 2021-01-24 15:18:40
Gekko使用基于梯度的求解器，因此方程不应该改变迭代到迭代。有一种方法可以得到与基于梯度的求解器兼容的非零变量的计数。下面是给出x向量的计数和最大值的另一种形式。它使用if3、max3和min3，就像在关于具有逻辑条件的建模功能的文档中发现的那样。
from gekko import GEKKO
import numpy as np
# Setup gekko (taken from their MINLP tutorial with more iterations).
m = GEKKO(remote=False)
# Define variables as arrays.
y = m.Array(m.Var, (7), value=1, lb=1, ub=12, integer=True)
x = m.Array(m.Var, (18), value=0, lb=0, ub=8, integer=True)
# Example of the user-defined target values b as constraints (actually input args).
m.Equation(x[2] + y[1] == 7)
m.Equation(x[12] + y[2] == 5)
# This is the L0 constraint.
# m.Equation(np.count_nonzero(x) >= np.max(x))
eps = 0.05 # decision point for a "zero" value
count = m.sum([m.if3(x_i-eps,0,1) for x_i in x])
max_x = 0
for x_i in x:
max_x = m.Intermediate(m.max3(max_x,x_i))
m.Equation(count >= max_x)
# Finally, the objective function (intermediates for readability).
k = np.array([m.min3(y_i, 3) for y_i in y])
x_cost = m.Intermediate(m.sum(x * (x + 1)))
y_cost = m.Intermediate(m.sum((k - 1) * (k + 2) + 2.5 * (y - k) * (y + k - 3)))
m.Minimize(x_cost + y_cost)
# Solve.
m.options.SOLVER = 3 # Initialize with IPOPT
m.solve(disp=True)
m.options.SOLVER = 1 # APOPT is an MINLP solver
m.solver_options = ('minlp_maximum_iterations 500',
'minlp_max_iter_with_int_sol 10',
'minlp_as_nlp 0',
'nlp_maximum_iterations 50',
'minlp_branch_method 1',
'minlp_integer_tol 0.05',
'minlp_gap_tol 0.01')
m.solve(disp=True)我用IPOPT给出了初始化的非整数解，然后用APOPT找到了最优的整数解。这种方法使用x生成一个成功的解决方案。
>>> x
array([[0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0],
[0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0]],
dtype=object)和y
>>> y
array([[1.0], [7.0], [5.0], [1.0], [1.0], [1.0], [1.0]], dtype=object)您可能并不打算为x提供零的解决方案，因此您可能需要添加诸如m.Equation(count>=n)或更改eps=0.05之类的约束来查找非零值，或者在局部最小值时将求解器从零推开。使用m.Equation(count>=n)和eps=0.5，它找到了一个更好的解决方案：
n=3, obj=63
n=5, obj=52下面是x和y的解决方案，obj=52 (最佳解决方案)。
>>> x
array([[0.0], [1.0], [4.0], [0.0], [0.0], [0.0], [0.0], [0.0], [0.0],
[0.0], [1.0], [0.0], [2.0], [0.0], [0.0], [0.0], [1.0], [0.0]],
dtype=object)
>>> y
array([[1.0], [3.0], [3.0], [1.0], [1.0], [1.0], [1.0]], dtype=object)当一个值被计算为非零时，您可能需要调整if3中使用的minlp_integer_tol 0.05来调整值，或者需要调整作为求解器选项的minlp_integer_tol 0.05来确定整数公差。下面是带有附加不等式约束的最后一个脚本，它提供了最好的解决方案。
from gekko import GEKKO
import numpy as np
# Setup gekko (taken from their MINLP tutorial with more iterations).
m = GEKKO(remote=False)
# Define variables as arrays.
y = m.Array(m.Var, (7), value=1, lb=1, ub=12, integer=True)
x = m.Array(m.Var, (18), value=0, lb=0, ub=8, integer=True)
# Example of the user-defined target values b as constraints (actually input args).
m.Equation(x[2] + y[1] == 7)
m.Equation(x[12] + y[2] == 5)
# This is the L0 constraint.
# m.Equation(np.count_nonzero(x) >= np.max(x))
eps = 0.5 # threshold for a "zero" value
count = m.sum([m.if3(x_i-eps,0,1) for x_i in x])
max_x = 0
for x_i in x:
max_x = m.Intermediate(m.max3(max_x,x_i))
m.Equation(count >= max_x)
# Finally, the objective function (intermediates for readability).
k = np.array([m.min3(y_i, 3) for y_i in y])
x_cost = m.Intermediate(m.sum(x * (x + 1)))
y_cost = m.Intermediate(m.sum((k - 1) * (k + 2) + 2.5 * (y - k) * (y + k - 3)))
m.Minimize(x_cost + y_cost)
m.Equation(count>=5)
# Solve.
m.options.SOLVER = 3 # Initialize with IPOPT
m.solve(disp=True)
m.options.SOLVER = 1 # APOPT is an MINLP solver
m.solver_options = ('minlp_maximum_iterations 500',
'minlp_max_iter_with_int_sol 10',
'minlp_as_nlp 0',
'nlp_maximum_iterations 50',
'minlp_branch_method 1',
'minlp_integer_tol 0.05',
'minlp_gap_tol 0.01')
m.solve(disp=True)您可以调整n或一些求解器选项，以获得更好的解决方案。我希望这能帮你找到正确的方向。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65863807
复制相关文章
相似问题
腾讯云开发者
