# Can a solution of SDP be proven optimal by estimating the perturbation of each variable individually?

More precisely, I'm considering the special case for vector programming, which is an equivalent form to semidefinite programming:

$$\min \sum_{i,j} c_{i,j} (x_i \cdot x_j) \\ \textbf{subject to: }\sum_{i,j}a_{i,j,k} (x_i \cdot x_j) \le b_k \\ \textbf{where: } x_i\in\mathbb{R}_n$$

Is it sufficient to prove a certain solution $\{x'_i\}_{i=1}^n$ is optimal if for any vector $x'_i$, any pertubation of it (but still in the feasible region, of course) leads to the increasing of our objective?

For "pertubation" I mean adding an arbitrary vector in $\mathbb{R}_n$ to $x'_i$ with length smaller than some $\varepsilon$. And note that each time only one vector may be changed from the initial solution.

If so, then can we weaken the condition, such as if the pertubation is non-decreasing? (Actually I would love to know the exact condition, but if someone can answer this it's OK)

-
add comment