I'm trying to minimize the following function:
$f(x) = \frac{a \cdot x}{min(b \cdot x, c \cdot x)}$
where $x, a, b$ and $c$ are vectors of $n$ values. For instance, $x = (1, x_1, x_2, ..., x_n)$. The first problem is the min() function but it's not the only one because I have a bunch of constraints:
$d \cdot x$ < 16
$\frac{e \cdot x}{f \cdot x} > -4$
$\frac{g \cdot x}{f \cdot x} > 98$
$\frac{h \cdot x}{i \cdot x} > 30$
where $d, e, f, g, h$ and $i$ are vectors of $n$ values.

How can I minimize my $f$ function? I thought to SGD but with the min() function and the constraints, I'm not sure it can work.

  • $\begingroup$ I finally used SLSQP algorithm to solve my problem with approximate method to compute the gradients. In Python, the scipy module does it perfectly. $\endgroup$ – Pierre Dec 25 '16 at 18:10

A minimum will either be a minimum of $\frac{a\cdot x}{b\cdot x}$ or a minimum of $\frac{a\cdot x}{c\cdot x}$, or lie on the hyperplane defined by $b\cdot x=c\cdot x$ where the two functions are equal.

This gives you three simpler minimization tasks; after you have solved them check which of the three outcomes is best.

Each constraint like $\frac{e\cdot f}{f\cdot x} > 98$ can be split into two cases based on the sign of $f\cdot x$ to give $e\cdot x \gtrless 98 f\cdot x$. Also splitting on $i\cdot x$, this gives you $4$ regions to consider for each of the three tasks, where each of the regions is defined by linear constraints only.

  • $\begingroup$ I'm not sure to understand the last part of your answer. How to handle constraints like $e \cdot x > 98 f \cdot x$? Which method used to resolve it? $\endgroup$ – Pierre Dec 24 '16 at 9:04
  • $\begingroup$ @Pierre: Subtract $98f\cdot x$ on both sides to get $(e-98f)\cdot x>0$. $\endgroup$ – Henning Makholm Dec 24 '16 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.