3
$\begingroup$

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

$\endgroup$
5
  • $\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$ 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
3
$\begingroup$

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.

$\endgroup$
5
  • $\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
  • 1
    $\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
  • $\begingroup$ 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? $\endgroup$
    – Johnny
    May 18 at 14:26
  • $\begingroup$ $\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 $\endgroup$
    – mtanneau
    May 18 at 15:54
  • $\begingroup$ 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? $\endgroup$
    – Johnny
    May 19 at 8:21

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.