1
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 14:45

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.