2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Why is sdp tag involved? $\endgroup$
    – Turbo
    Commented May 15, 2021 at 14:39

1 Answer 1

Reset to default
1
$\begingroup$

$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))
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! I was thinking if there is a way to relax the objective to make it convex optimizable? $\endgroup$
    – koo
    Commented May 15, 2021 at 14:35
  • $\begingroup$ It's not "close" to being convex. I suppose the goodness of any relaxation depends on the constraints from $g$. Anyhow, if $g$ is linear, the optimization problem can be solved as a Mixed-Integer Linear Programming problem (MILP), by introducing binary variables to handle $\text{min(}x_i,x_j)$ $\endgroup$
    – Mark L. Stone
    Commented May 15, 2021 at 15:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .