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}$