swi 序言中的优化
Optimisation in swi prolog
假设我想求 argmax(x,y,z) -1/2(20x^2+32xy +16y^2)+2x+2y。
受限于:
x>=0, y>=0,z>=0 且 -x-y+z =0.
我知道设置为 0 的偏导数是:
-20x-16y+2=0 和 -16x-16y+2=0
所以我们可以有 x= 0 和 y =1/8 和 z=1/8。
我如何在 Swi-prolog 中执行此操作?我看到有用于线性求解的库单纯形,但这是一个二次问题,但偏导数不是。 (我有点糊涂了!)
这是我的:
:- use_module(library(simplex)).
my_constraints(S):-
gen_state(S0),
constraint([-20*x, -16*y] = 0, S0, S1),
constraint([-16*x,-16*y] = 0, S1,S2),
constraint([x] >= 0,S2,S3),
constraint([y] >= 0,S3,S4),
constraint([z] >= 0,S4,S5),
constraint([-x-y+z] = 0,S5,S).
?- my_constraints(S), variable_value(S,x,Val1),variable_value(S,y,Val2).
false.
这里有几个问题。首先,只是为了解决这个问题:library(simplex)
只能处理 linear 约束。所以是的,它不能——至少不能直接——用来解决你的实际问题。
但是 library(simplex)
通常无论如何都是有用的,所以我想快速指出以下几点:
variable_value/3
仅适用于 已解决 画面。这意味着您必须先调用maximize/3
。
例如:
?- my_constraints(S), maximize([x,y], S, Max), variable_value(Max, x, X).
S = ...,
Max = ...,
X = 0.
注意必须将my_constraint/1
的最终目标改为constraint([-1*x, -1*y,z] = 0, S5, S)
以符合本库要求的语法
话虽如此,现在让我们进入问题的核心:有众所周知的方法迭代解决二次优化问题,使用一系列linear 关于梯度的程序和推理以更接近解决方案。因此,library(simplex)
仍然可以间接用于解决您的问题。
特别是,查看 miscellaneous programs 提供的 最速上升法 。它包括一个用 Prolog 编写的小型符号导数计算器。是的,是 "symbolic" ;-)
插入你的任务,我得到:
?- maximize(- 0.5*(20*x(1)^2 + 32*x(1)*x(2) + 16*x(2)^2) + 2*x(1) + 2*x(2),
[[-1,0,0],
[0,-1,0],
[0,0,-1],
[-1,-1,1],
[1,1,-1]],
[0,0,0,0,0],
[0,0,0], Max).
Max = [4.298588509886033e-17, 0.125, 0.12500000000000006] ;
false.
也就是说,浮点运算令人难以忍受,我希望你能使用它。
假设我想求 argmax(x,y,z) -1/2(20x^2+32xy +16y^2)+2x+2y。
受限于: x>=0, y>=0,z>=0 且 -x-y+z =0.
我知道设置为 0 的偏导数是:
-20x-16y+2=0 和 -16x-16y+2=0
所以我们可以有 x= 0 和 y =1/8 和 z=1/8。
我如何在 Swi-prolog 中执行此操作?我看到有用于线性求解的库单纯形,但这是一个二次问题,但偏导数不是。 (我有点糊涂了!)
这是我的:
:- use_module(library(simplex)).
my_constraints(S):-
gen_state(S0),
constraint([-20*x, -16*y] = 0, S0, S1),
constraint([-16*x,-16*y] = 0, S1,S2),
constraint([x] >= 0,S2,S3),
constraint([y] >= 0,S3,S4),
constraint([z] >= 0,S4,S5),
constraint([-x-y+z] = 0,S5,S).
?- my_constraints(S), variable_value(S,x,Val1),variable_value(S,y,Val2).
false.
这里有几个问题。首先,只是为了解决这个问题:library(simplex)
只能处理 linear 约束。所以是的,它不能——至少不能直接——用来解决你的实际问题。
但是 library(simplex)
通常无论如何都是有用的,所以我想快速指出以下几点:
variable_value/3
仅适用于 已解决 画面。这意味着您必须先调用maximize/3
。例如:
?- my_constraints(S), maximize([x,y], S, Max), variable_value(Max, x, X). S = ..., Max = ..., X = 0.
注意必须将
my_constraint/1
的最终目标改为constraint([-1*x, -1*y,z] = 0, S5, S)
以符合本库要求的语法
话虽如此,现在让我们进入问题的核心:有众所周知的方法迭代解决二次优化问题,使用一系列linear 关于梯度的程序和推理以更接近解决方案。因此,library(simplex)
仍然可以间接用于解决您的问题。
特别是,查看 miscellaneous programs 提供的 最速上升法 。它包括一个用 Prolog 编写的小型符号导数计算器。是的,是 "symbolic" ;-)
插入你的任务,我得到:
?- maximize(- 0.5*(20*x(1)^2 + 32*x(1)*x(2) + 16*x(2)^2) + 2*x(1) + 2*x(2), [[-1,0,0], [0,-1,0], [0,0,-1], [-1,-1,1], [1,1,-1]], [0,0,0,0,0], [0,0,0], Max). Max = [4.298588509886033e-17, 0.125, 0.12500000000000006] ; false.
也就是说,浮点运算令人难以忍受,我希望你能使用它。