# How to solve the following continuous optimization problem?

Consider a function $$f: X\times Y\times N$$, where $$X, Y \subseteq \mathbb{R}^m$$ are convex sets, and $$N = \{1,2,\dots,n\}$$. We additionally know that

1. $$f(\cdot,y,S)$$ is convex for fixed $$y,S$$
2. $$f(x,\cdot,S)$$ is concave for fixed $$x,S$$
3. $$f(x,y,\cdot)$$ is linear for fixed $$x,y$$, i.e. $$f(x,y,S) = \sum_{i\in S} f(x,y,\{i\})$$.

We can also assume the following: $$f$$ is continuous, differentiable, smooth, and that $$X = Y$$. I am interested in solving the following optimization problem: $$\min_{x\in X} \sum_{S:S\subseteq N} p_S \cdot \max_{y\in Y} f(x,y,S),$$

where $$p_S \ge 0$$ are non-negative reals. How should I go about solving this? Would it be possible to reduce this to a min max convex concave problem? Another issue is that there could be potentially exponential (in $$n$$) many sets $$S$$ in the inner summation. Would appreciate any ideas or references.

• The vector $p$ is fixed, right? If so how is it given? As an explicit (exponentially long) vector? Nov 8 at 1:43
• Yes, $p$ is fixed. We can either assume it is available via oracle access or as an explicitly given vector. In my specific example, sets are sampled from some distribution over $N$ and $p_S$ is some function of the probability of realizing $S$. Nov 8 at 1:49
• Yes, I would like to have a polynomial-time algorithm in $n,m$. Let me clarify that $p_S$ is not given explicitly but is some function of $n$ and $S$, for e.g., $p_S = 1/|S|$ for non-empty $S$ and 0 for the empty set. For constant $n$ the problem becomes easy, but for general $n$ I am not sure. Nov 8 at 23:03
• Thanks for pointing that out. However, we can make the following simplifying assumptions as needed. $f$ is continuous, differentiable, smooth, and even that $X = Y$. I will update the question to reflect these additional assumptions. Nov 9 at 19:26
• We can assume the partial gradients (wrt $x$ and wrt $y$) of $f$ are Lipschitz continuous. Also, with $X=Y$ and $n=1$ I do not see how your example can be duplicated, as in that case it's simply a min-max convex-concave problem, right? Nov 11 at 14:45