I have derived an optimization objective of the form
$$
f(x) = \sum\_{i,j} C\_{ij}\min(x\_i, x\_j), s.t. g(x) \geq 0
$$
where $C \in \mathcal{R}^{N \times N}$ is a positive definite matrix, and $x \in \mathcal{R}^{N}$ is a vector where each element $ x\_i \geq 1 $. Additionally, $ g(x) \geq 0 $ constrains the solution $ x $ to be inside a convex feasible set.


Is there a way to prove (or disprove) that $ f $ is convex? A simple gradient descent on a test example appear to always converge to the same optimality.


I was able to prove this objective is bounded with $ f(x) \geq \sum\_{i,j} C\_{ij} $, and the unconstrained case gives $ \forall i: x\_i = 1 $ as the optimal solution.



Convexity of a positive definite objective with min(x,y)-nonlinearity
$f(x)$ is not convex. Here is a counterexample to its convexity in MATLAB notation.



```
C = [2 1;1 2]
x1 = [1 2]'
x2 = [2 1]'
x3 = 0.5*(x1 + x2)

```

Then



```
f(x1) = f(x2) = 8
f(x3) = 9 > 0.5*(f(x1) + f(x2))

```

