# Oscillations with (online) mixed-integer optimization problem

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).

• @Johnny You can use the same account to edit your posts. Mar 24, 2021 at 10:37
• 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). Mar 24, 2021 at 12:30
• 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$] Mar 24, 2021 at 13:06
• Why is $x=0$, $y=0$ not automatically the optimal solution?
– prubin
Mar 24, 2021 at 22:05
• @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.
– EhsanK
Mar 25, 2021 at 13:38

## 1 Answer

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.

• 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). Apr 1, 2021 at 19:32
• 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. Apr 2, 2021 at 13:27
• Quick question...For the objective modification, how would you optimize the value of $\rho$ in $\rho \|x-\hat{x} \|$? Depending on the values of $x$, $w$, etc, the oscillations can heavily depend on the value of $\rho$...so how can one optimize this value so that oscillations are minimized while maximizing the objective function properly? May 18, 2021 at 14:26
• $\rho$ is a hyper-parameter here. What value you should take will depend on your data inputs... Qualitatively, the larger $\rho$ is, the closer to $\hat{x}$ your solution will be. One simple rule would be to start with $\rho=1$, solve, increase to, e.g., $\rho=10$ if the deviation is too large, and repeat May 18, 2021 at 15:54
• I see...So I would have to do something like check the value of $J=\rho \|x^* - \hat{x} \|$ (after the optimization), and then if $J$ is too large, then I would run the optimization again with a larger $\rho$, right? May 19, 2021 at 8:21