Oscillations with (online) mixed-integer optimization problem

Question

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

Answer 1

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.