How these kind of optimization problems are called (reference request)?

Question

I am looking for the name of the following kind of optimization problem (the later one):

Let say I have $N$ real-valued variables $x_i$, and some selection indexes $a_i = \begin{cases} 1, \ x_i\text{ is considered}, \\ 0, \text{else} \end{cases}$ and I am looking for maximize the average value $\mu(\vec{x}) = \frac{1}{M}\sum\limits_{i=1}^M a_i x_i$ considering all possible combinations of $a_i$ and $x_i$.

Surely I am not explain myself properly so lets make and example: consider that I have the following values for $x_i = \{0.5, -0.1,\ 0.3\}$ so $N=3$. Now the possible scenarios are: $$\begin{array}{c c c | c c} i=1 & i=2 & i=3 & & \\ x_1 = 0.5 & x_2 = -0.1 & x_3=0.3 & M &\mu(\vec{x})\\ \hline 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0.3 \\ 0 & 1 & 0 & 1 & -0.1 \\ 0 & 1 & 1 & 2 & 0.1 \\ \color{red}{1} & \color{red}{0} & \color{red}{0} & \color{red}{1} & \color{red}{0.5} \\ 1 & 0 & 1 & 2 & 0.4 \\ 1 & 1 & 0 & 2 & 0.2 \\ 1 & 1 & 1 & 3 & 0.2\bar{3} \\ \end{array}$$

so I have $2^N$ different possible combinations with different normalization constant for the average. I know beforehand that in this case the answer is trivial since $\frac{1}{M}\sum\limits_{i}^M x_i \leq \text{max}\{x_i\}$ so it will always choose only one element.

But now let think in the real problem: let say now that the variables $x_i$ are random with mean $\mu_i$, variance $\sigma_i^2$, and among variables the correlation coefficient is $\rho_{ij}$ when $i\neq j$.

Now in the same sense that before, I am wanting to find for every possible combination, to keep only the variables that maximizes the following: $$\nu(\vec{x}) = \frac{1}{M}\sum_{i=1}^M\left(\mu_i-\frac{\sigma_i^2}{2}\right)-\frac{1}{M^2}\left(\sum_{i=1}^M \sigma_i^2 + 2\sum_{1\leq i < j \leq M}\sigma_i\sigma_j\rho_{ij}\right)$$

As increase $M^2$ the second part becomes more irrelevant, but for small $M$ instances, different from before, due the terms $\rho_{ij}$ my intuition tells me that is not going to happen "necessarily" that the maximum $\nu(\vec{x})$ will happen at the variable "$i$" when $\left(\mu_i - \frac{3}{2}\sigma_i^2\right)$ is higher.

This is why I am trying to understand how this kind of problems are named to see how to solve them, if it is possible to do it without checking all the $2^N$ alternatives, if there are some libraries (Excel, R, Octave, among others) were is implemented in order to don't reprogram it unnecessarily, if there are fast ways to do it, if it could be solved in some clever matrix form (like in Ordinary Least Squares), or if my intuition is wrong and the trivial one-scenario solution is the only maximum alternative.

---

Added later:

Thanks to @TonyMathew and @Abhinav Patel I have now a better idea of what I am asking: it is a combinatorial optimization problem with integer programming within, named "Subset Selection Problem", and unfortunately it is class NP. But in line with the original question, I would like to focus it now on the matrix implementation of the problem.

As @TonyMathew pinpoint I have used a notation abuse, and the proper formulation of the problem is: $$\text{maximize}_{\vec{a}} \left\{ \nu(\vec{a},\vec{x}) := \frac{1}{\sum_{i=1}^N a_i}\sum_{i=1}^{\sum_{i=1}^N a_i} a_i\left(\mu_i-\frac{\sigma_i^2}{2}\right)-\frac{1}{\left(\sum_{i=1}^N a_i\right)^2}\left(\sum_{i=1}^{\sum_{i=1}^N a_i} a_i\sigma_i^2 + 2\sum_{1\leq i < j \leq \sum_{i=1}^N a_i}a_ia_j\sigma_i\sigma_j\rho_{ij}\right)\right\} \\ \text{s.t.} \quad a_i \in \{0;\ 1\}$$

Since I have to check every $2^N$ alternative, I could make an index $k$ such starts at zero and increase by one up to $2^N$, and test as the vector $\vec{a}$ a vector of size $N$ with each component given by the binary description of the number $k$. The problem of this idea is, if I try to implement it on Excel, I will need at least $2^N$ files for each vector, and just for a small number of random variables like $N=20$ I will require $2^{20} = 1,048,576$ files: the size of a whole Excel spreadsheet tab!!!

So thinking in a less memory extensive way, noting the variables $x_i$'s parameters is given data, I think that a matrix description would be more useful, for then checking each instance $k$ in a "for"-loop (like in Matlab/Octave language since I could use it for free), which work fast with matrix operations.

But I am a bit rusty on linear algebra: the second term is $\text{Var}\left[\sum_{i=1}^N a_i x_i\right]$, now if $\mathbb{\Sigma}$ is the Covariance Matrix of $\vec{x}$, if I am not mistaken I will have that $\text{Var}\left[\sum_{i=1}^N a_i x_i\right] \equiv a^T\mathbb{\Sigma}a$ (using here that since $a_i \in \{0;\ 1\}$ then $a_i^2 \equiv a_i$), and also that the right-side sum is a dot product of $\vec{a}\cdot\vec{b}$ where I think is simpler to just make directly each component $b_i = \mu_i-\frac{\sigma_i^2}{2}$ (I don't know how to implement it as a matrix operator), and $M := \sum_{i=1}^N a_i = \vec{a}\cdot\vec{a}$. I hope you could check if these matrix implementation is right and/or give a better/right expression.

I moved the matrix implementation into this question so I could close the original question as it first attempt.

After answer in the other question: Looks like the problem could be defined as: $$\underset{\vec{a}}{\text{max}}\left\{ \frac{1}{\vec{a}^T\vec{a}}\left(\vec{a}^T\left(\vec{\mu}-\frac12\vec{\sigma^2}\right)\right)- \frac{1}{(\vec{a}^T\vec{a})^2}\vec{a}^T\Sigma\vec{a} \right\}$$

Answer 1

The problem you are asking for is a type of combinatorial optimization problem which is a very interesting field of research as well as study , specifically a subset selection problem with a continuous objective function. In general, this kind of problem is known as a "Subset Selection Problem" or "Subset Optimization Problem."

More specifically, your objective function $\nu(\vec{x})$ involves maximizing a weighted sum of means and minimizing a weighted sum of variances and covariances. The decision variables are the binary indicators $a_i$ that determine whether each variable $x_i$ is included in the subset.

Given the binary nature of your decision variables, this problem falls into the category of combinatorial optimization, where the goal is to find the optimal subset from a finite set of possible elements. Unfortunately, combinatorial optimization problems are often NP-hard, meaning there may not be a polynomial-time algorithm to solve them optimally in all cases.

In your case, the complexity is compounded by the presence of correlation coefficients $\rho_{ij}$ among the variables. This introduces additional interdependencies between variables, making the optimization problem more challenging.

Solving this type of problem typically involves exploring various optimization techniques, heuristics, or metaheuristics, depending on the size of the problem and the available computational resources. Some commonly used techniques for combinatorial optimization problems include:

1. Integer Linear Programming (ILP): You can formulate the problem as an ILP and use solvers like CPLEX, Gurobi, or open-source alternatives like PuLP in Python.

2. Genetic Algorithms (GA): These are evolutionary algorithms inspired by natural selection. They can be effective for finding good solutions to combinatorial optimization problems.

3. Simulated Annealing: A probabilistic optimization algorithm that can escape local optima. It is particularly useful for exploration in large solution spaces.

4. Tabu Search: An iterative local search algorithm that avoids revisiting solutions found in previous iterations, helping to escape local optima.

5. Dynamic Programming: Depending on the specific structure of your problem, dynamic programming techniques might be applicable to reduce the computational complexity.

6. Metaheuristic Algorithms: Other metaheuristic algorithms like Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), or Differential Evolution may be worth exploring.

As for implementation, various optimization libraries in different programming languages provide tools for solving combinatorial optimization problems. For example, in Python, you can use libraries like Scipy, Pyomo, or specialized solvers like Gurobi or CPLEX or many machine learning libraries often use

Answer 2

These optimization problems fall under Integer Programming (IP), which is a sub-class of Mathematical Programming. A more concise way to frame the first problem is below. $M \geq 1$ condition added only to avoid $M=0$ issues. \begin{align} \max_{a_i, M} \; &\mu = \frac{\sum\limits_{i=1}^N a_i x_i}{M} \\ \text{s.t. } &M = \sum\limits_{i=1}^N a_i \\ &M \geq 1 \\ & a_i \in \{0,1\}, \; M \in [1, N] \end{align}

The above has both binary ($a_i$) and integer ($M$) variables in the formulation. If the solver/method you're using works with binary variables only, you could eliminate $M$ as below \begin{align} \max_{a_i} \; &\mu(\vec{a}, \vec{x}) = \frac{\sum\limits_{i=1}^N a_i x_i}{\sum\limits_{i=1}^N a_i} \\ \text{s.t. } &\sum\limits_{i=1}^N a_i \geq 1 \\ & a_i \in \{0,1\} \end{align}