Isotonic Regression

Given a sequence A of n integers, design an algorithm to find an non-decreasing sequence B of n integers, such that is minimized.

Solution:

This problem can be solved by minimum cost flow. Here we use dynamic programming.

Let F(k, z) be the optimal objective value for the first k elements with B[k] = z. Then, we have a recurrence relation: F(k, z) = min F(k-1, x) + |z – A[k]|. Thus, the problem becomes how to efficiently find the z minimizing F(k, z) for all fixed k. It can be showed that F(k, z) is a piecewise linear convex function in z and the minimizing value must be in A. Thus, the dynamic programming can be speed up by using slope optimization and find the solution in O(n lg n) time.

解法：

令 F(k, z) 為前 k 個元素且  B[k] = z 時的最佳解之值。當給定 k ，我們可得一遞回關係式：F(k, z) = min F(k-1, x) + |z – A[k]|。因此問題就變成如何快速的找出最小化 F(k, z) 的 z 值。我們可以證明 F(k, z) 對於 z 是一個 piecewise linear convex 函數 ，而且可以最小化 F 的 z 值必定在 A 中。因此使用動態規劃加上斜率最佳化可以在O(n lg n)時間內找到答案。

Reference: Stackoverflow, Stackoverflow

Günter Rote, “Isotonic Regression by Dynamic Programming”