Calculation of the conjugate of piecewise functions

Conjugate of piecewise function

In this post, we’ll show how to calculate the conjugate of a piecewise function f(x),
such as

    \begin{align*} f(x) = \begin{cases} f_1(x) & l_1 \leq x \leq l_2 \\ f_2(x) & l_2 < x \leq l_3 \end{cases} \end{align*}

The conjugate for the above is:

    \begin{align*} f^\ast(y) & = \sup_x xy - f(x), \\ & = \max\left(\sup_{l_1 \leq x \leq l_2} xy - f_1(x), \sup_{l_2 < x \leq l_3} xy - f_2(x)\right), \\ & = \max\left(f_1^\ast(y), f_2^\ast(y) \right), \end{align*}

where f_1^\ast(y) is the conjugate of the function f_1(x) constrained to l_1 \leq x \leq l_2. So, computing the conjugate of a piecewise function is simple as long as the conjugates of the sub-functions can be computed easily.

Conjugate of constrained function

In this section, we’ll show how to calculate the convex conjugate of a function \bar{f}(x), which is the function f(x) which is constrained to a domain l \leq x \leq u.
The conjugate is defined as:

    \begin{align*} \bar{f}^\ast(y) = \sup_{l \leq x \leq u} xy - f(x). \end{align*}

For the unconstrained case, the solution would be given by:

    \begin{align*} x = \left[f' \right]^{-1}(y), \end{align*}

where f'(x) is the derivative of f(x). Since f(x) is convex, f'(x) is a monotonically increasing function. Therefore, we have

    \begin{align*} y_l' = f'(l), \quad  y_u' = f'(u). \end{align*}

The conjugate of the constrained function is therefore:

    \begin{align*} \bar{f}^\ast(y) = \begin{cases} ly - f(l) & y < y_l, \\  f^\ast(y) & y_l \leq y \leq y_u, \\ uy - f(u) & y > y_u. \end{cases} \end{align*}

The convex conjugate for the unconstrained function can be automatically calculated in Python — as described in the previous post.

Code that do the above is given below:

def calc_const_conj(fun_str, lstr='l', ustr='u', varnames='x l u', fname='plot.png'):
    # set the symbols
    vars = sp.symbols(varnames)
    x = vars[0] if isinstance(vars, tuple) else vars
    y = sp.symbols('y', real=True)

    # set the function and objective
    fun = parse_expr(fun_str)
    obj = x*y - fun
    fun_diff = sp.diff(fun, x)
    obj_diff = sp.diff(obj, x)

    l = parse_expr(lstr)
    u = parse_expr(ustr)

    # calculate yl and yu
    yl = sp.simplify(fun.subs(x, l))
    yu = sp.simplify(fun.subs(x, u))

    dyl = sp.simplify(fun_diff.subs(x, l))
    dyu = sp.simplify(fun_diff.subs(x, u))

    # calculate derivative of obj and solve for zero
    sol = solve(obj_diff, x)

    # substitute solution into objective
    solfun = sp.collect(sp.simplify(obj.subs(x, sol[0])), x)

    # print the function and conjugate:
    print('{0:45} y < {1}'.format(str(sp.simplify(l*y - yl)), dyl))
    print('{0:45} {1} <= y <= {2}'.format(str(solfun), dyl, dyu))
    print('{0:45} y > {1}'.format(str(sp.simplify(u*y - yu)), dyu))

# Example: calc_const_conj('1/2*x**2', lstr='-1', ustr='1', varnames='x')

Table of conjugates

Function Constraint Conjugate
Linear ax + b l \leq x \leq u \begin{cases} uy -ua - b & y \geq a \\ ly-la - b & y < a \end{cases}
Simple Quadratic \frac{1}{2}ax^2 l \leq x \leq u \begin{cases} \frac{l}{2}\left(2y - al \right)  & y < al, \\ \frac{1}{2a}y^2 & al \leq y \leq au, \\ \frac{u}{2}(2y - au) & y > au. \end{cases}
Quadratic a x^2 + bx + c l \leq x \leq u \begin{cases} -2al  -b + ly & y < 2al + b \\ \frac{-4ac + b^2 - 2by + y^2}{4a}  & 2al + b \leq y \leq 2au + b \\ -2au - b + uy  &  y > 2au + b \end{cases}
PE-like \frac{1}{2}(x-1)^2 0 \leq x \begin{cases} -\frac{1}{2} & y < -1, \\ \frac{1}{2}y^2 + y & -1 \leq y. \\ \end{cases}
Hinge \max\left(0, \epsilon-x \right) \begin{cases} \epsilon y & -1 \leq y \leq 0, \\ \infty & \textrm{otherwise}. \end{cases}
(scaled)Hinge a\max\left(0, \epsilon-x \right) \begin{cases} \epsilon y & -1 \leq y \leq 0, \\ \infty & \textrm{otherwise}. \end{cases}

You may also like