maximizing sum over feasible set of vectors

asked 2019-11-05 22:28:50 +0200

anonymous user


updated 2019-11-05 22:51:16 +0200

Let $[5]$ be the set of the first 5 positive integers. We let $\underline{\alpha} =(\alpha_A)_{A\neq \emptyset, A\subseteq [5]}$ consist of a vector with $31$ real entries, where each $\alpha_A$ is associated with a subset $A \subseteq [5]$.

Define $\displaystyle OBJ(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A \log(|A|)$, $\quad \displaystyle v(\underline{\alpha})=\sum_{A\subseteq [5], A\neq \emptyset} \alpha_A$, $\quad$ and $\quad \displaystyle E(\underline{\alpha})=\sum_{ {A,B}: A\cap B\neq \emptyset} \alpha_A \alpha_B$, where the sum for $E(\underline{\alpha})$ is taken over all unordered pairs of disjoint nonempty sets $A$ and $B$, where $A, B \subseteq [5]$.

Also define $FEAS(1/4)$ to be the set of all such vectors $\underline{\alpha}$ with nonnegative real entries such that $v(\underline{\alpha})=1$ and $E(\underline{\alpha})\geq 1/4$.

I want to learn how to program the following optimization problem: $$\displaystyle OPT(1/4):=\max_{\underline{\alpha} \in FEAS(1/4)} OBJ(\underline{\alpha})$$

I was told that I can do this in SageMath. I have some basic knowledge of how to use Sage. How could I create the set $FEAS(1/4)$? I think that from there I may be able to figure out how to maximize $OBJ(\underline{\alpha})$ over this set.

edit retag flag offensive close merge delete


Homework ?

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-11-06 04:49:25 +0200 )edit

Also, go easy on (pseudo-)formalism: I can't make head or tails of your definition of $\underline{\alpha}$... For another example, you define $A$ as a subset of $[5]$ ; but now, what is $\log(|A|)$ ???

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-11-06 05:22:56 +0200 )edit

$|A|$ means the number of elements in $A$. To have $\underline{\alpha}$ be a vector one should choose an ordering of the (nonempty) subsets of $[5]$, e.g. by identifying them with binary strings of length 5 (not equal to $00000$).

rburing gravatar imagerburing ( 2019-11-06 12:38:39 +0200 )edit

Okay. you want to (pedantly) number the components of $\underline{\alpha}$ in binary. And to ignore $\alpha_0$. Right ?

$A$ is therefore an index of the 31 components of $\underline{\alpha}$,$v(\underline{\alpha})$ is $\sum_{i=1}^{32}\alpha_{i-1}$. Still right ?

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-11-06 19:46:07 +0200 )edit

I didn't ask the question, but yes that's right. The binary ordering was just a (natural) suggestion. Of course the ordering is irrelevant, but probably some ordering is necessary for the implementation.

rburing gravatar imagerburing ( 2019-11-06 20:16:48 +0200 )edit