Functions for working with the discrete-continuous EGM (DCEGM) algorithm as described in “The endogenous grid method for discrete-continuous dynamic choice models with (or without) taste shocks” by Iskhakov et al. (2016) [https://doi.org/10.3982/QE643 and ijrsDCEGM2017 in our Zotero]

Example can be found in https://github.com/econ-ark/DemARK/blob/master/notebooks/DCEGM-Upper-Envelope.ipynb


Given a grid of x values, a matrix with the values of different line segments evaluated on the x grid, and a vector indicating the choice of a segment at each grid point, this function computes the coordinates of the crossing points that happen when the choice of segment changes.

The purpose of the function is to take (x,y) lines that are defined piece- wise, and at every gap in x where the “piece” changes, find the point where the two “pieces” involved in the change would intercept.

Adding these points to our piece-wise approximation will improve it, since it will eliminate interpolation between points that belong to different “pieces”.

  • x_grid (np.array) – Grid of x values.
  • cond_ys (2-D np.array. Must have as many rows as possible segments, and) – len(x_grid) columns. cond_ys[i,j] contains the value of segment (or “piece”) i at x_grid[j]. Entries can be nan if the segment is not defined at a particular point.
  • opt_idx (np.array of indices, must have length len(x_grid)) – Indicates what segment is to be used at each x gridpoint. The value of the piecewise function at x_grid[k] is cond_ys[opt_idx[k],k].

  • xing_points (2D np.array) – Crossing points, each in its own row as an [x, y] pair.
  • segments (np.array with two columns and as many rows as xing points.) – Each row represents a crossing point. The first column is the index of the segment used to the left, and the second, to the right.


Computes the intersection between two line segments, defined by two common x points, and the values of both segments at both x points. The intercept is only found if it happens between the two x coordinates.

  • x (np.array, length 2) – The two common x coordinates. x[0] < x[1] is assumed
  • left_y (np.array, length 2) – y values of the two segments at x[0]
  • right_y (np.array, length 2) – y values of the two segments at x[1]

  • (m_int, v_int) (a tuple with the corrdinates of the intercept.)
  • if there is no intercept in the interval [x[0],x[1]], (nan,nan)


Given a sequence of (x,y) points, this function finds the start and end indices of its largest non-decreasing segments.

A non-decreasing segment is a sub-sequence of points {(x_0, y_0),…,(x_n,y_n)} such that for all 0 <= i,j <= n, If j>=i then x_j >= x_i and y_j >= y_i

  • x (1D np.array of floats) – x coordinates of the sequence of points.
  • y (1D np.array of floats) – y coordinates of the sequence of points.

  • starts (1D np.array of ints) – Indices where a new non-decreasing segment starts.
  • ends (1D np.array of ints) – Indices where a non-decreasing segment ends.

HARK.dcegm.upper_envelope(segments, calc_crossings=True)

Finds the upper envelope of a list of non-decreasing segments

  • segments (list of segments. Segments are tuples of arrays, with item[0]) – containing the x coordninates and item[1] the y coordinates of the points that confrom the segment item.
  • calc_crossings (Bool, optional) – Indicates whether the crossing points at which the “upper” segment changes should be computed. The default is True.

  • x (np.array of floats) – x coordinates of the points that conform the upper envelope.
  • y (np.array of floats) – y coordinates of the points that conform the upper envelope.
  • env_inds (np array of ints) – Array of the same length as x and y. It indicates which of the provided segments is the “upper” one at every returned (x,y) point.