1
$\begingroup$

I would like to use simplex on a non-linear programming problem and was wondering if there was a way to transform it to a linear constraint.

The problem is the following:

$$ \mathbb{min:} \space \space {q^*}_{q<0}*{C^T_{q<0}} + {q^*}_{q>0}*{C^T_{q>0}} $$ $$ subject \space to: \space {\tau}_{\mathbb{lower\_limit}} \lt (p+q)*w^T < {\tau}_{\mathbb{upper\_limit}} $$

where: $$ \text{q is the variable vector of length n and } $$ $$ q^*_{q<0} = q \text{ where q < 0 and 0 else (same definition for } q^*_{q>0} ) $$ $$ \text{C}_{q<0} \text{ is a cost vector of length n for when q <0} $$ $$ \text{C}_{q>0} \text{ is a cost vector of length n for when q >0} $$ $$ \text{w} \text{ is a weight vector of length n} $$ $$ \tau \text{ are scalars} $$

Thanks in advance.

$\endgroup$
  • $\begingroup$ In linear/non linear programming you want to optimize a linear/non linear scalar function over a closed set. The closure hypothesis of the feasible set directly comes from the Weierstrass theorem. In the problem you propose: 1)the feasible set is not a closed set, since you use strict inequalities; 2) the objective function is not a scalar function, because you are taking the product between the column vector q and the row vector C and the result of this operation is a matrix; 3) in the constraints there is the same issue and p is undefined. $\endgroup$ – Marcello Sammarra Nov 18 '16 at 20:20
1
$\begingroup$

Assuming the costs are all positive you can use variable splitting:

$$\begin{align} \min & \sum_i c^+_i q^+_i + c^-_i q^-_i\\ & q_i = q^+_i - q^-_i\\ & q^+_i, q^-_i \ge 0 \end{align}$$

$\endgroup$
  • $\begingroup$ I ended up doing the following: $$.5 ( C^- + C^+)^T q + .5(C^- - C^+)^T |q|$$ Now we use the absolute value linearization trick and we get: $$ .5(C^- + C^+)^T(T_1 + T_2) + .5(C^- - C^+)^T (T_1 - T_2) $$ $\endgroup$ – Andrew Nov 21 '16 at 15:59
  • $\begingroup$ I'm an idiot, ends up being the same solution. $\endgroup$ – Andrew Nov 22 '16 at 0:24

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.