Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$.

Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-negative vectors (meaning $f(v^i) \ge 0$ for $i\in [n]$). I want to find non-negative $c_1,\dots,c_n \ge 0$ satisfying $c_1+\dots+c_n=1$ which maximize $$f(c_1v^1+\dots +c_nv^n).$$Is this a studied problem? Are there efficient algorithms to exactly solve this problem? If not, what about numerical heuristics?

  • 1
    $\begingroup$ The set of vectors defined by $\{c_1 v^1 + \dotsc + c_n v^n$ such that $c_1 + \dotsc + c_n = 1 \}$, is nothing but the convex hull of the given set of vectors. $\endgroup$ Sep 21 at 19:03
  • $\begingroup$ Thanks, well then I guess I'm looking for a way to optimize $f(v)$ over $v$ in the convex hull of $v^1,\dots,v^n$. I have no idea how to search this besides brute force. Presumably there's some sort of gradient ascent that can be done, but I do not know the details. $\endgroup$ Sep 21 at 19:09

The problem can be solved using linear programming in polynomial time.

Objective Function: $\max \,\, \gamma$

Constraint $1$ : $x_i \geq \gamma$ for every $i \in \{1,\dotsc,d\}$. This constraint is due to $f(X) = \min_{i} \{x_i \}$ for any vector $X = (x_1,\dotsc,x_d)$

Constraint $2$ : $x_{i} = c_{1} v^{1}_{i} + \dotsc + c_{n}v_{i}^{n}$ for every $i \in \{1,\dotsc,d\}$

Constraint $3$ : $c_{1} + \dotsc + c_{n} = 1$, and $c_{i} \geq 0$ for every $i \in [n]$

The variables $x_1,\dotsc,x_d$, and $\gamma$ are also greater than $0$.

Please check carefully if it makes sense. And, let me know of any issue in it.

  • $\begingroup$ sorry, I am not the most familiar with LP, and am not sure how this is an instance of linear programming. for instance, the objective function does not seem to be linear, and the constraints do not seem to be given by a matrix either. $\endgroup$ Sep 21 at 20:03
  • $\begingroup$ @ZachHunter Why do you think the objective function is not linear? $\gamma$ is a linear function. If it would have been $\sqrt{\gamma}$ or $\gamma^3$ that would non-linear. $\endgroup$ Sep 21 at 20:14
  • $\begingroup$ @ZachHunter The constraints are also linear and can be expressed in matrix form. $\endgroup$ Sep 21 at 20:16
  • $\begingroup$ $\gamma(X) = f(X)$ correct? well $f(X)$ is not a linear function, $f((1,2))+f((2,1))=2 \neq 3 = f((3,3))$. $\endgroup$ Sep 21 at 20:44
  • $\begingroup$ @ZachHunter It is not $\gamma(X)$. It is simply $\gamma$. I introduced a new variable $\gamma$ and a new set of constraints $x_i \geq \gamma$ to mean $f(X)$. This might help. Let me know, if you understand. $\endgroup$ Sep 21 at 20:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.