1

I have difficulty understanding how permutation-invariance and convexity are related in an optimization problem.

Let $f(.)$ be a convex function defined on $d$-dimensional vectors. Suppose, also that $f$ is permutation-invariant, i.e., if we permute elements of $x$, $f(x)$ remains fixed where $x$ is a $d$-dimensional vector. Also, we know that $f$ is not a constant function.

Convexity, ensures that any convex combination of a set of solutions is also a solution. Permutation-invariance ensures that any permutation of a solution is also a solution.

Do these two properties contradict each other?

When do these two properties contradict each other?

user25004
  • 3,586
  • 2
  • 33
  • 61

1 Answers1

2

There's no contradiction here. $f$ can have the form

$$f(x_1, ... x_n) = \sum_{i=1}^n g(x_i)$$

where $g$ is a convex function of one variable, e.g. $g(x) = x$ or $g(x) = x^2$.

Qiaochu Yuan
  • 419,620