0
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2016 at 18:10

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2016 at 9:04
  • $\begingroup$ @Pierre: Subtract $98f\cdot x$ on both sides to get $(e-98f)\cdot x>0$. $\endgroup$ Dec 24, 2016 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .