Figure 6.7:

Cost contours for a two-player, nonconvex game.

Code for Figure 6.7

Text of the GNU GPL.

stackcontours.py

 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
36
37
# points = stackcontours(c)
#
# Takes the output of contourc and stacks it into a single data table with NaNs
# inserted for line breaks. This allows the contours to be plotted using the
# standard plot() function.
import numpy as np

def stackcontours(c):
    """
    points = stackcontours(c)

    Takes the output of contourc and stacks it into a single data table with NaNs
    inserted for line breaks. This allows the contours to be plotted using the
    standard plot() function.
    """
    if not isinstance(c, np.ndarray):
        raise TypeError("Input must be numpy array")

    # First have to figure out how many chunks there are, then save each chunk
    # to a cell array, and finally concatenate.
    nchunks = 0
    offset = 0  # Convert to 0-based indexing
    while offset < c.shape[1]:
        nchunks += 1
        offset = offset + int(c[1,offset]) + 1

    chunks = [None] * nchunks
    offset = 0
    for i in range(len(chunks)):
        chunk_size = int(c[1,offset])
        chunk = c[:,(offset + 1):(offset + chunk_size + 1)]
        chunks[i] = np.hstack((chunk, np.full((2,1), np.nan)))
        offset = offset + 1 + chunk_size

    points = np.hstack(chunks).T

    return points

main.py

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Example of nonconvex optmization in which the convex combination of
# one-variable-at-a-time optimizations is not decreasing.
# [depends] functions/stackcontours.py
import sys
import os
import matplotlib.pyplot as plt
import numpy as np
from scipy import optimize

sys.path.append('functions/')
from stackcontours import stackcontours
from misc import gnuplotsave

def V(x, y):
    a = 1.1
    b = 0.4
    return (np.exp(-2*x) - 2*np.exp(-x) + np.exp(-2*y) - 2*np.exp(-y)
            + a*np.exp(-b*((x + 0.2)**2 + (y + 0.2)**2)))

# Grid setup
nxy = 221
xvec = np.linspace(-0.5, 5, nxy)
yvec = np.linspace(-0.5, 5, nxy)
ncont = 15

xgrid, ygrid = np.meshgrid(xvec, yvec)
Vgrid = V(xgrid, ygrid)

# Initial points
x0 = 0
y0 = 0

xguess = 2.5
yguess = 2.5

# One variable at a time minimization
xp = optimize.fmin(lambda x: V(x, y0), xguess, disp=False)[0]
yp = optimize.fmin(lambda y: V(x0, y), yguess, disp=False)[0]

# Midpoint
xw = (x0 + xp)/2
yw = (y0 + yp)/2

# Plotting
if not os.getenv('OMIT_PLOTS') == 'true':
    plt.figure()
cs = plt.contour(xvec, yvec, Vgrid, ncont)
if not os.getenv('OMIT_PLOTS') == 'true':
    plt.plot(x0, y0, 'ok', xp, y0, '+k', x0, yp, '+k', xw, yw, 'ok',
             [xp, x0], [y0, yp], '-k', [x0, xw], [y0, yw], '-k')

# Build MATLAB-format contour matrix from matplotlib output, then stackcontours
c_cols = []
for level, segs in zip(cs.levels, cs.allsegs):
    for seg in segs:
        npts = seg.shape[0]
        header = np.array([[level], [npts]])
        c_cols.append(np.hstack([header, seg.T]))
c = np.hstack(c_cols)

# Save data
data = {}
data['points'] = np.array([[x0, y0], [xp, y0], [x0, yp], [xw, yw]])
data['lines']  = np.array([[x0, y0], [xw, yw], [np.nan, np.nan], [xp, y0], [x0, yp]])
data['contours'] = stackcontours(c)
gnuplotsave('nonconvex.dat', data)