1
$\begingroup$

I am writing a model for an optimization problem. I need to write the following constraint:

$$\sum^{N - 1}_i \lvert (a_i - a_{i+1}) \rvert \leq 2\, .$$

  1. How to write this constraint (or linearize)?

  2. Is it permissible to use absolute value constraints in an optimization problem (even for nonlinear programming)?

    After I searched, I found that absolute values can be modeled as the following (without the sum or difference):

    $$\lvert a_i \rvert \leq 2 \: \text{ to }\: a_i \leq 2 \: \text{ and }\: - a_i \leq 2 $$

  3. Is this type of transformation is applicable here?

$\endgroup$
4
$\begingroup$

The way to deal with this kind of constraint is to add "slack variables" to your system. In your case, let us say that you want to solve the problem $$ \min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} |a_i - a_{i+1}| \le 2 $$ then you could introduce slack variables $y_1,\ldots y_{N-1}$ so that $$ y_i \ge |a_i-a_{i+1}| $$ and then solve this problem instead: $$ \min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} y_i \le 2, \\ \qquad \qquad \quad y_i \ge |a_i - a_{i+1}| $$

Next, recognize that $$ y_i \ge |a_i-a_{i+1}| $$ is equivalent to the two conditions $$ y_i \ge +(a_i-a_{i+1}) \\ y_i \ge -(a_i-a_{i+1}) \\ $$ and consequently your initial problem is equivalent to the following, which is now an entirely linearly constrained linear optimization problem: $$ \min_a c^T a \\ \text{subject to}\; \sum_{i=1}^{N-1} y_i \le 2, \\ \qquad \qquad \quad y_i \ge +(a_i - a_{i+1}), \\ \qquad \qquad \quad y_i \ge -(a_i - a_{i+1}). $$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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