0
$\begingroup$

So, I'm trying to solve this,
given $\Omega \in \mathbb{R}^{p \times n}$ and $c>0$:

$$ \min_{x\in \mathbb{R}^n} \{|| \Omega \cdot x ||\} $$ Sustained to: $$ \sum_{k=1}^{n} x_{k} = c $$ $$ x\in \{0,1\}^n $$

Basically, the problem consists of finding the appropiate configuration of vector $x$ (that has a fixed number of non-zero elements) such that the module of the matrix product with $\Omega$ minimizes. I've never solved an optimization problem with binary variables so I been trying to think different ways of approaching it but I'm not sure which path should I take (or if there's a better way of thinking this problem). Here are some of the things I came up with

  • Approach this problem as a Quadratic Optimization Problem. The thing is that I'm not sure how to include the fact that the variables are binary. For example, Matlab includes the function quadprog that solves this kind of problems but it only works with continuous variables.
  • Find a way to linearize the functional to minimize (though I don't think this is possible) in order to take advantage of linear programming methods. For example, Maltab includes a function intlinprog which can deal with linear integer optimization problems.
  • Use a genetic algorithm: I've already tried this using (again) Matlab's function ga but didn't give good results. Maybe I'm not translating well the problem to the function or maybe (for some reason) it's not the best way to approach this particular problem.
  • I also came up with the idea that there may exist some kind of Ising-inspired algorithm in which you flip randomly two elements $x(i)=1\rightarrow x(i)=0$, $x(j)=0\rightarrow x(j)=1$ and if the functional becomes smaller, you stay with that change, and if not, you got a probability for that flip to actually happen, related to the difference between the original and the new value of the functional.

So far, I've been trying to solve this problem computationally. However, if there exists an analitical approach, that will also be useful.
Does anyone have any suggiestion?

$\endgroup$
4
  • 1
    $\begingroup$ This looks like it might be helpful. It restricts the variables to $\pm1$ but I don't imagine that's hard to deal with. $\endgroup$ Commented Jun 16, 2020 at 16:09
  • $\begingroup$ do you really need the minimum at high precision? Or is a small value for $\|\Omega x\|$ just fine? How large is $n$? Do you want to just solve a particular problem with some existing software? Solving integer problem in general is not easy and there are many good methods tailor to particular well-known problems. $\endgroup$ Commented Jun 16, 2020 at 16:27
  • $\begingroup$ Thanks saulspatz! I'll take a look at it $\endgroup$ Commented Jun 16, 2020 at 17:20
  • $\begingroup$ user251257, actually, for the problem I'm working on, I guess that a sufficiently small value for $||\Omega x||$ will just be fine (I'm Also trying yo find this Upper bound) . However, I'm interested in finding the absolute minimum if it's possible. The reason why I don't even consider calculating each configuration possible for $x$ is that $n≥1000$. Solving this particular problem with an existing computer software would be fine $\endgroup$ Commented Jun 16, 2020 at 17:42

2 Answers 2

Reset to default
1
$\begingroup$

There are three approaches:

  1. Linearize the quadratic terms and use intlinprog.

  2. Use a mixed integer quadratic optimization solver such as cplex or gurobi.

  3. If $c$ is small you can list all feasible points.

$\endgroup$
1
$\begingroup$

To obtain a linearization, you can introduce a nonnegative variable $y_{i,j}$ for $i<j$ to represent the product $x_i x_j$, along with the following linear constraints: \begin{align} y_{i,j} &\le x_i \\ y_{i,j} &\le x_j \\ y_{i,j} &\ge x_i + x_j - 1 \end{align} Note that $y_{i,j}$ will automatically take values $\{0,1\}$ when $x$ does. So far, this is the usual linearization. But note that you can further strengthen the formulation by including the following valid constraints, obtained by multiplying both sides of your cardinality constraint by $x_j$: $$\sum_{i=1}^{j-1} y_{i,j} + \sum_{i=j+1}^n y_{j,i} = (c-1) x_j$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.