0
$\begingroup$

Assume that $x$ and $y$ are $n \times 1$ and $m \times 1$ vectors and we have a set of affine functions $f_i(x)$, $i=1,\ldots,N$, and $g_j(y)$, $j=1,\ldots,M$. We want to solve the following optimization problem:

\begin{align} \min_{x,y} &\Big(\max_{i=1,\ldots,N} f_i(x) + \max_{j=1,\ldots,M} \big(a_j^T \max\{0,1-x\}+ g_j(y)\big) \Big) \\ & Cx \leq d \\ & x \in [0,1]^n \\ & y \in [0,1]^m \\ \end{align} where $C$ and $d$ are a matrix and a vector with appropriate dimensions and $a_j$'s are positive. How can we solve this? Is there any way to write this problem as an LP?

Note that it can be shown that the objective is convex function of $x,y$. If we cannot convert it to an LP, we can try to solve it as a convex optimization problem, but taking derivate of the objective function is not easy. Any idea?

If I follow the idea mentioned in this post, the above problem can be written as: \begin{align} \min_{x,y,z,v}\quad &z +v \\ & Cx \leq d \\ & x \in [0,1]^n \\ & y \in [0,1]^m \\ &z\geq f_i(x),\quad i=1,\dots,N\\ &v\geq a_j^T \max\{0,1-x\}+ g_j(y), \quad j=1,\dots,M. \end{align} It is almost in LP form except for the last set of constraints. Can we use define $w= \max\{0,1-x\}$ and write the last set of constraints as $v\geq a_j^T w+ g_j(y)$, $w \geq 0$, $w \geq 1-x$?

$\endgroup$
7
  • 2
    $\begingroup$ It depends on the sign of $a$. If $a$ is positive you can apply the standard epi-graph reformulation with $w$, but for negative $a$ it is not convex and the epi-graph reformulation is not possible (as you now can let $w$ tend to $-\infty$, i.e., the introduced constraint will not have be tight at optimality for any of the constraints) $\endgroup$ Commented Jun 22, 2017 at 7:40
  • $\begingroup$ @JohanLöfberg Yes, a's are positive. What is the standard epi-graph reformulation with $w$? $\endgroup$ Commented Jun 22, 2017 at 7:53
  • 2
    $\begingroup$ The modelling of the max operator you do is called an epi-graph representation, and very common, thus standard epi-graph reformulation $\endgroup$ Commented Jun 22, 2017 at 9:50
  • $\begingroup$ @JohanLöfberg Thanks. So $v\geq a_j^T \max\{0,1-x\}+ g_j(y)$ can be replaced by three inequalities $v\geq a_j^T w+ g_j(y)$, $w \geq 0$, $w \geq 1-x$ or according to the proposed solution below only by two constraints $v\geq g_j(y)$, $v\geq a_j^T (1-x) + g_j(y)$? $\endgroup$ Commented Jun 22, 2017 at 11:08
  • 2
    $\begingroup$ Yes, jut as you have done before when you modelled a max operator, absolutely nothing new. $\endgroup$ Commented Jun 22, 2017 at 14:46

1 Answer 1

Reset to default
1
$\begingroup$

If $v\geq \max\{u,w\}$, then $v\geq u$ and $v\geq w$. So you could substitute one constraint by two contraints.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.