Hướng dẫn lagrange multiplier python - trăn lagrange nhân hệ số

Đăng ngày 03 tháng 2 năm 2013 lúc 09:00 sáng | Thể loại: Tối ưu hóa | Tags: | categories: optimization | tags:

Cập nhật ngày 27 tháng 2 năm 2013 lúc 02:43 chiều

Bài đăng Matlab (chuyển thể từ http://en.wikipedia.org/wiki/lagrange_multipliers.)

Giả sử chúng ta tìm cách tối đa hóa hàm \ (f (x, y) = x + y \) theo ràng buộc rằng \ (x^2 + y^2 = 1 \). Hàm chúng ta tìm cách tối đa hóa là một mặt phẳng không giới hạn, trong khi ràng buộc là một vòng tròn đơn vị. Chúng tôi muốn giá trị tối đa của vòng tròn, trên mặt phẳng. Chúng tôi vẽ hai chức năng này ở đây.

import numpy as np

x = np.linspace(-1.5, 1.5)

[X, Y] = np.meshgrid(x, x)

import matplotlib as mpl
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.gca(projection='3d')

ax.plot_surface(X, Y, X + Y)

theta = np.linspace(0,2*np.pi);
R = 1.0
x1 = R * np.cos(theta)
y1 = R * np.sin(theta)

ax.plot(x1, y1, x1 + y1, 'r-')
plt.savefig('images/lagrange-1.png')

1 Xây dựng chức năng tăng cường hệ số nhân Lagrange Construct the Lagrange multiplier augmented function

Để tìm mức tối đa, chúng tôi xây dựng hàm sau: \ (\ lambda (x, y; \ lambda) = f (x, y)+\ lambda g (x, y) \) trong đó \ (g (x, y) = x^2 + y^2 - 1 = 0 \), đó là hàm ràng buộc. Vì \ (g (x, y) = 0 \), chúng tôi không thực sự thay đổi chức năng ban đầu, với điều kiện là ràng buộc được đáp ứng!

import numpy as np

def func(X):
    x = X[0]
    y = X[1]
    L = X[2] # this is the multiplier. lambda is a reserved keyword in python
    return x + y + L * (x**2 + y**2 - 1)

2 Tìm các dẫn xuất một phần Finding the partial derivatives

Timea/cực đại của hàm tăng được đặt ở nơi tất cả các dẫn xuất một phần của hàm tăng cường bằng 0, tức là \ ( y = 0 \) và \ (\ partial \ lambda/\ partial \ lambda = 0 \). Quá trình giải quyết điều này thường là để phân tích các dẫn xuất một phần, và sau đó giải các phương trình kết quả không bị ràng buộc, có thể là phi tuyến.

Thay vì thực hiện sự khác biệt phân tích, ở đây chúng tôi phát triển một cách để xấp xỉ bằng số các dẫn xuất từng phần.

def dfunc(X):
    dLambda = np.zeros(len(X))
    h = 1e-3 # this is the step size used in the finite difference.
    for i in range(len(X)):
        dX = np.zeros(len(X))
        dX[i] = h
        dLambda[i] = (func(X+dX)-func(X-dX))/(2*h);
    return dLambda

3 Bây giờ chúng tôi giải quyết các số không trong các dẫn xuất một phần Now we solve for the zeros in the partial derivatives

Hàm chúng tôi xác định ở trên (DFUNC) sẽ bằng 0 ở mức tối đa hoặc tối thiểu.Hóa ra có hai giải pháp cho vấn đề này, nhưng chỉ một trong số chúng là giá trị tối đa.Giải pháp nào bạn nhận được phụ thuộc vào dự đoán ban đầu được cung cấp cho người giải quyết.Ở đây chúng ta phải sử dụng một số phán đoán để xác định mức tối đa.

from scipy.optimize import fsolve

# this is the max
X1 = fsolve(dfunc, [1, 1, 0])
print X1, func(X1)

# this is the min
X2 = fsolve(dfunc, [-1, -1, 0])
print X2, func(X2)

>>> ... >>> [ 0.70710678  0.70710678 -0.70710678] 1.41421356237
>>> ... >>> [-0.70710678 -0.70710678  0.70710678] -1.41421356237

4 Tóm tắt Summary

Các sơ đồ ba chiều trong matplotlib khó khăn hơn một chút so với trong MATLAB (trong đó mã gần giống như các ô 2D, chỉ là các lệnh khác nhau, ví dụ: Plot Vs Plot3).Trong matplotlib, bạn phải nhập các mô -đun bổ sung theo đúng thứ tự và sử dụng phương pháp định hướng đối tượng để vẽ đồ thị như được hiển thị ở đây.

Bản quyền (c) 2013 của John Kitchin.Xem giấy phép để biết thông tin về sao chép.

Nguồn chế độ org