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.

  • 1
    $\begingroup$ The vector $p$ is fixed, right? If so how is it given? As an explicit (exponentially long) vector? $\endgroup$
    – Neal Young
    Nov 8 at 1:43
  • $\begingroup$ 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$. $\endgroup$
    – ashtavakra
    Nov 8 at 1:49
  • $\begingroup$ 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. $\endgroup$
    – ashtavakra
    Nov 8 at 23:03
  • $\begingroup$ 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. $\endgroup$
    – ashtavakra
    Nov 9 at 19:26
  • $\begingroup$ 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? $\endgroup$
    – ashtavakra
    Nov 11 at 14:45


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.