How to write the hypograph formulation of maximization problem?

67 Views Asked by At

Given the minimization problem

$$ \begin{array}{ll} \underset {x} {\text{minimize}} & f_0 (x) \\ \text{subject to} & f_i (x) \le 0 \end{array} $$

its epigraph formulation is

$$ \begin{array}{ll} \underset {x, t} {\text{minimize}} & t\\ \text{subject to} & f_0 (x) \leq t \\ & f_i (x) \le 0 \end{array} $$

However, if the original problem is as follows

$$ \begin{array}{ll} \underset {x} {\text{maximize}} & g (x) \\ \text{subject to} & g_i (x) \le 0 \quad\text{(or maybe } g_i (x) \ge 0)\end{array} $$

what would be the corresponding hypograph formulation?


My first try is this formulation but I am not entirely sure if my intuition is correct

\begin{aligned} \underset {x, t} {\text{maximize}} \quad &t \\ \text{subject to} \quad &g_i(x) \le 0 \quad \text{(or maybe } g_i(x) \ge 0)\\ &g(x) \ge t \end{aligned}

Or should it be

\begin{aligned} \underset {x, t} {\text{minimize}} \quad &-t \\ \text{subject to} \quad &g_i(x) \le 0 \quad \text{(or maybe } g_i(x) \ge 0)\\ &g(x) \ge t \end{aligned}

Thank you for your enthusiasm !