Convex optimization problems
Các bài toán phổ biến nhất (linear programming, quadratic programming, geometric programming)
Sử dụng thư viện cvxopt cho bài toán linear programming
Ví dụ 1 (tối ưu hàm min)
(x, y, z, t) = argmin (5x + 10y + 15z + 4t)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
(x, y, z, t) = argmin (5x + 10y + 15z + 4t)
subject to:
x + z = 600 --> -x - 0y - z - 0t <= -600
y + t = 400 --> -0x - y - 0z - t <= -400
x + y <= 800 --> x + y + 0z + 0t <= 800
z + t <= 700 --> 0x + 0y + z + t <= 700
x, y, z, t >= 0
-->
-x - 0y - 0z - 0t <= 0
-0x - y - 0z - 0t <= 0
-0x - 0y - z - 0t <= 0
-0x - 0y - 0z - t <= 0
'''
import cvxopt as opt
c = opt.matrix([5.0, 10.0, 15.0, 4.0])
G = opt.matrix([
[-1.0, 0.0, 1.0, 0.0, -1.0, 0.0, 0.0, 0.0],
[0.0, -1.0, 1.0, 0.0, 0.0, -1.0, 0.0, 0.0],
[-1.0, 0.0, 0.0, 1.0, 0.0, 0.0, -1.0, 0.0],
[0.0, -1.0, 0.0, 1.0, 0.0, 0.0, 0.0, -1.0]
])
h = opt.matrix([
-600.0, -400.0, 800.0, 700.0, 0.0, 0.0, 0.0, 0.0
])
opt.solvers.options['show_progress'] = False
sol = opt.solvers.lp(c, G, h)
print(sol['x'])
print(sol['primal objective'])
Ví dụ 2 (Ax = b)
(x, y, z, t) = argmin (5x + 10y + 15z + 4t)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
'''
(x, y, z, t) = argmin (5x + 10y + 15z + 4t)
subject to:
x + y <= 800 --> x + y + 0z + 0t <= 800
z + t <= 700 --> 0x + 0y + z + t <= 700
x, y, z, t >= 0
-->
-x - 0y - 0z - 0t <= 0
-0x - y - 0z - 0t <= 0
-0x - 0y - z - 0t <= 0
-0x - 0y - 0z - t <= 0
'''
import cvxopt as opt
c = opt.matrix([5.0, 10.0, 15.0, 4.0])
G = opt.matrix([
[1.0, 0.0, -1.0, 0.0, 0.0, 0.0],
[1.0, 0.0, 0.0, -1.0, 0.0, 0.0],
[0.0, 1.0, 0.0, 0.0, -1.0, 0.0],
[0.0, 1.0, 0.0, 0.0, 0.0, -1.0]
])
h = opt.matrix([
800.0, 700.0, 0.0, 0.0, 0.0, 0.0
])
A = opt.matrix(
[1.0, 0.0, 1.0, 0.0, 0.0, 1.0, 0.0, 1.0],
(2, 4)
)
b = opt.matrix([600.0, 400])
#Ax = b
opt.solvers.options['show_progress'] = False
sol = opt.solvers.lp(c, G, h, A, b)
print(sol['x'])
Ví dụ 3 (tối ưu hàm max)
(x, y) = argmax (5x + 3y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
(x, y) = argmax (5x + 3y)
subject to:
x + y <= 10
2x + y <= 16
x + 4y <= 32
x, y >= 0 --> -x, -y <= 0
'''
''' vector cot'''
#Gx <= h
import cvxopt as opt
c = opt.matrix([-5.0, -3.0])
G = opt.matrix([
[1.0, 2.0, 1.0, -1.0, 0.0],
[1.0, 1.0, 4.0, 0.0, -1.0]
])
h = opt.matrix([10.0, 16.0, 32.0, 0.0, 0.0])
opt.solvers.options['show_progress'] = False
sol = opt.solvers.lp(c, G, h)
print(sol['x'])
print('solving a linear program with argmax')
Ví dụ 4 (cách biến đổi điều kiện)
argmin (2x1 + x2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
argmin (2x1 + x2)
subject to:
-x1 + x2 <= 1
x1 + x2 >= 2 --> -x1 - x2 <= -2
x2 >= 0 --> -x2 <= 0
x1 - 2x2 <= 4
'''
import cvxopt as opt
G = opt.matrix([
[-1.0, -1.0, 0.0, 1.0],
[1.0, -1.0, -1.0, -2.0]
])
h = opt.matrix([1.0, -2.0, 0.0, 4.0])
c = opt.matrix([2.0, 1.0])
opt.solvers.options['show_progress'] = False
sol = opt.solvers.lp(c, G, h)
print(sol['x'])
print(sol['primal objective']) # in ket qua nhan duoc)
Sử dụng thư viện cvxopt cho bài toán quadratic programming
Ví dụ 1
argmin (0.5 * x^2 + 3x + 4y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
argmin (0.5 * x^2 + 3x + 4y)
x, y >= 0 --> -x <= 0, -y <= 0
x + 3y >= 15 --> -x - 3y <= -15
2x + 5y <= 100
3x + 4y <= 80
'''
import cvxopt as opt
h = opt.matrix([0.0, 0.0, -15.0, 100.0, 80.0])
G = opt.matrix([
[-1.0, 0.0, -1.0, 2.0, 3.0],
[0.0, -1.0, -3.0, 5.0, 4.0]
])
'''
format:
1/2 * [x, y] * [[t1, t2], [t3, t4]] * [x, y].T + [t5, t6].T * [x, y].T
--> tim t1, t2, t3, t4, t5, t6
--> P = [[t1, t2], [t3, t4]]
--> q = [t5, t6].T
'''
P = opt.matrix([ # ma tran vector cot.
[1.0, 0.0],
[0.0, 0.0]
])
q = opt.matrix([3.0, 4.0]) # ma tran cua vector cot.
opt.solvers.options['show_progress'] = False
sol = opt.solvers.qp(P, q, G, h)
print(sol['x'])
print(sol['primal objective'])
Ví dụ 2
argmin = 2x^2 + y^2 + xy + x + y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
'''
argmin = 2x^2 + y^2 + xy + x + y
x >= 0
y >= 0
x + y = 1
'''
import cvxopt as opt
A = opt.matrix([1.0, 1.0], (1, 2)) # 1 hang, 2 cot [x + y = 1]
b = opt.matrix(1.0)
h = opt.matrix([0.0, 0.0])
G = opt.matrix([
[-1.0, 0.0],
[0.0, -1.0]
])
'''
format:
1/2 * [x, y] * [[t1, t2], [t3, t4]] * [x, y].T + [t5, t6].T * [x, y].T
--> tim t1, t2, t3, t4, t5, t6
--> P = [[t1, t2], [t3, t4]]
--> q = [t5, t6].T
'''
P = opt.matrix([ # ma tran vector cot.
[4.0, 1.0],
[1.0, 2.0]
])
q = opt.matrix([1.0, 1.0]) # ma tran cua vector cot.
opt.solvers.options['show_progress'] = False
sol = opt.solvers.qp(P, q, G, h, A, b)
print(sol['x'])
print(sol['primal objective'])
Sử dụng thư viện cvxopt cho bài toán geometric programming
f(x, y, z) = argmin(40/xyz + 2(xy + yz + zx))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
'''
f(x, y, z) = argmin(40/xyz + 2(xy + yz + zx))
subject to:
x, y, z > 0
'''
import numpy as np
import cvxopt as opt
K = [4]
F = opt.matrix([
[-1.0, 1.0, 1.0, 0.0],
[-1.0, 1.0, 0.0, 1.0],
[-1.0, 0.0, 1.0, 1.0]
])
g = opt.matrix([
np.log(40.),
np.log(2.),
np.log(2.),
np.log(2.)
])
opt.solvers.options['show_progress'] = False
sol = opt.solvers.gp(K, F, g)
print(sol['x'])
print(np.exp(np.array(sol['x'])))
print(sol['primal objective'])
Link tham khảo
Tài liệu tham khảo
Machine learning cơ bản
Hết.
