I have the following mixed-integer optimization problem:

\begin{aligned} \max_{x,y} \quad & \sum_i x_i - \|wx\|_2 \\ \text{s.t.} \quad & \sum_i x_i \leq A \\ \quad & x \leq x_{\max} y \\ \quad & x \geq x_{\min} y \\ \quad & y \in \{0,1\} \end{aligned}

where $\delta$ is a positive constant, $A$ is a positive constant, $x$ is a $n \times 1$ vector of positive real values, $y$ is a $n \times 1$ binary vector, $w$ is a $n \times n$ diagonal matrix, and $x_{\min}, x_{\max}$ are each $n \times n$ diagonal matrices with positive constants. This optimization problem is solved online (where the diagonal values of $w$ are changing in each iteration). For fixed values in $w$, the oscillations can still occur.

When I tried to solve this problem numerically, the optimal values of $x$ are oscillating in each iteration. This is expected because of the hard constraints imposed. Is there a way to prevent these oscillations with relaxation or hysteresis on the $w$? Or possibly adding another constraint/variable to prevent the oscillations?

Your help will be much appreciated.

Here is an example of the kind of oscillations I get. For this plot, $x_{\min} = 6$, $x_{\max} = 32$, $A = 50$, and $x$ is a $5 \times 1$ vector. So from this plot, its clear that the values jump from 0 to 6 (since this is imposed by the hard constraints in the problem). But I want to prevent this kind of behavior (i.e., keep constant and only change based on some kind of epsilon relaxation).

enter image description here

  • $\begingroup$ @Johnny You can use the same account to edit your posts. $\endgroup$ – TheSimpliFire Mar 24 at 10:37
  • $\begingroup$ Can you give an example of the oscillation? For a fixed w, do you observe oscillations of w as it proceeds from one iteration to the next when solving that one problem instance? If so, perhaps you can show solver output (log). $\endgroup$ – Mark L. Stone Mar 24 at 12:30
  • $\begingroup$ The $y$ variable does not appear anywhere except to bound the value of $x$. Is there anything preventing $y$ to be set to $1$ all the time? [Edit: oh, this would only be the case if $x_{min} \leq 0$] $\endgroup$ – mtanneau Mar 24 at 13:06
  • 1
    $\begingroup$ Why is $x=0$, $y=0$ not automatically the optimal solution? $\endgroup$ – prubin Mar 24 at 22:05
  • $\begingroup$ @Johnny As mentioned by TheSimpliFire, you can use the same account to ask, edit, and answer. So please use your original account to suggest your edits to the question. $\endgroup$ – EhsanK Mar 25 at 13:38

If I understand the problem correctly, the $y$ variables decide which components of $x$ are non-zero, and the rest is essentially some variant of a least-square problem.

There are several ways you can prevent a solution $x^{*}, y^{*}$ from deviating too much from a previous solution $\bar{x}, \bar{y}$.

Adding extra constraints

  • Restrict the number of components of $y$ that can be changed. For instance, you may add a constraint specifying that only $5$ elements of $y$ may be changed. This can be done with a single linear constraints on $y$ using a Hamming distance $$ \sum_{j | \bar{y}_{j} = 0} y_{j} + \sum_{j | \bar{y}_{j} = 1} (1 - y_{j}) \leq K, $$ where $K \geq 0$ is the number of coordinates you allow to be modified.

  • Explicitly restrict the distance between $x$ and $\bar{x}$ $$ \| x - \bar{x}\| \leq D, $$ where $D \geq 0$ and $\|.\|$ is any norm you want. A sub-case is to set a box around $\bar{x}$ and constraint $x$ to lie in that box: $$ \bar{x} - \epsilon \leq x \leq \bar{x} + \epsilon. $$

Changing the objective

A simple way would be to add a so-called "proximal term" to the objective, which would penalize large deviations from a reference point $\bar{x}, \bar{y}$. The objective would become, e.g., $$ \| w x \|_{2} + \rho \|x - \bar{x}\|, $$ where $\rho \geq 0$ and $\|.\|$ is any norm you want; common choices include $\ell_{1}$ and $\ell_{2}$ norms. You can also square the norm, i.e., add a term $\rho \|x - \bar{x}\|^{2}$.

Note that setting $\bar{x} = 0$ yields the so-called regularization terms in machine-learning literature.

  • $\begingroup$ Thanks for the detailed explanation! I had modified the optimization problem in the original post...Does the logic you provided still apply? For changing the objective, I guess I would now impose $-\rho \|x - \bar{x} \|$ instead (since the problem is now a maximization). $\endgroup$ – Johnny Apr 1 at 19:32
  • $\begingroup$ You can still apply the same logic, yes: either explicitly constrain the change in $x, y$, or penalize it in the objective, or both. Be aware that any change in the value of $y$ will likely result in jumps in $x$ (some coordinate of $x$ gets bumped from $0$ to some positive value). This might explain part of the oscillations you're seeing. $\endgroup$ – mtanneau Apr 2 at 13:27

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.