Dual Subgradient Step

Problem

Take one projected subgradient ascent step on the dual multipliers.

Return max(0, lam[i] + lr * g[i]) for every coordinate, where g is the constraint violation subgradient. Projection keeps the multipliers non-negative.

Hint

The dual is maximized, so a violated constraint increases its multiplier.

Test cases

case 1

in: [[0.5,0.2],[1,-1],0.1]

expected: [0.6,0.1]

case 2

in: [[0,0],[-1,0.5],0.5]

expected: [0,0.25]

case 3

in: [[1],[2],0.25]

expected: [1.5]

Starter codePython

def dual_subgradient_step(lam, g, lr):
    # Your code here
    pass

3 test cases · run your code against them in the editor