Maximize number of subsets
I'm not sure how well it'll work, but the idea is simple:

Consider a continuous relaxation of the function
Run projected gradient descent


1.) First, consider a discrete case: let $x_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum_i x_i \le k$. For each set $S_j$, we want to write a function which is $1$ when all $i \in S_j$ are picked, and $0$ otherwise. A natural choice is $g(S_j, x) = \prod_{i \in S_j} x_i$. Our objective is $f(x) = \sum_j g(S_j, x)$
Now, to make it continuous, let $x_i$ vary in the range $[0,1]$ - in other words, it represents a probability that we pick the $i$-th element.
Now, $g(S_j, x)$ represents the probability that the set $S_j$ is chosen.
The constraint $\sum_i x_i \le k$ and the objective $f$ are as before.
Therefore, the continuous relaxation is the following:
\begin{align*}
    f(x) &amp;= \sum_j \prod_{i \in S_j} x_i \to \max &amp; s.t.\\
    x_i &amp;\in [0,1] \ \ \forall i \\
    \sum_i x_i &amp;\le k \\
\end{align*}
2.) The gradient has a relatively simple form:
$$(\nabla f(x))'_{x_i} = \sum_{j\colon i \in S_j} \prod_{i' \in S_j \setminus \{i\}} x_{i'}$$
In other words, it's a sum of over terms containing $x_i$: product of all factors except $x_i$.
Since the problem is constrained, you need to run  $projected$ gradient descent. I.e.
$$x^{(t+1)} \gets Proj(x^{(t)} - \gamma \nabla f(x^{(t)})),$$
where $Proj$ is a projection on the set $\{x | \sum_i x_i \le k \land x_i \in [0,1] \ \ \forall i\}$. It may be hard to find the exact projection, but you can use Alternating projection or, better, Dykstra's projection.
For that purpose, we rewrite our constraint set as
$$\{x| \sum_i x_i \le k\} \cap (\cap_i\{x| x_i \le 1\}) \cap (\cap_i\{x| x_i \ge 0\}).$$
Now, we can project at each set in turns. Note that projection on $\{x| x_i \le 1\}$ is trivial: when $x_i \le 1$, don't do anything, otherwise $x_i \gets 1$.
I'm not sure that the function is &quot;good&quot;, and therefore I would try a smaller step size first. There are multiple optimizations that one can do, but I omit them here.