# Determine whether the nonconvex problem has a unique global minimum or not

The original optimization problem is in the constrained least square form as follows:

$$\min\limits_{x_1,x_2,x_3,x_4,x_5,x_6\in \mathbb{R}} \left(\left(x_2^2+x_3^2+2 x_1-x_4+x_5-3 x_6\right)^2+\left(-3 x_3^2+x_1+2 x_2+x_4+x_5-3 x_6\right)^2+\left(x_2^2-x_2+2 x_6^2+3 x_3+2 x_4+x_5\right)^2\right)$$

Subject to:

$$\left\{\qquad \begin{array}{lc} x_1+x_2+x_3+x_4+x_5+x_6&=1 \\ x_1-2 x_2+3 x_3+5 x_4+2 x_5+x_6&=1 \\ x_1+x_3+x_4+6 x_5+4 x_6&=1 \\ \end{array} \right.$$

which can be converted equivalently into the unconstrained minimization by representing $x_4,x_5,x_6$ by the other three variables:

$$\min\limits_{x_1,x_2,x_3\in \mathbb{R}} f(x_1,x_2,x_3)$$

where:

$$f(x_1,x_2,x_3)=\left(640000 x_1^4+3200 \left(1520 x_2+400 x_3-767\right) x_1^3+5 \left(2811200 x_2^2+768 \left(1900 x_3-3613\right) x_2+192000 x_3^2-658880 x_3+1088089\right) x_1^2+2 \left(9147360 x_2^3+7 \left(1004000 x_3-1875197\right) x_2^2+\left(1824000 x_3^2-6201280 x_3+9776797\right) x_2+160000 x_3^3-917133 x_3^2+2177961 x_3-2674151\right) x_1+9068722 x_2^4+186410 x_3^4-327128 x_3^3+1246099 x_3^2-2035392 x_3+2 x_2^3 \left(4573680 x_3-8369231\right)+6 x_2^2 \left(590547 x_3^2-1947444 x_3+2963404\right)+4 x_2 \left(152000 x_3^3-917456 x_3^2+1946254 x_3-2345095\right)+1795462\right)$$

The problem can be further converted into finding real solutions to the following $3\times 3$ polynomial equations system:

$$\left\{\qquad \begin{array}{c} \dfrac{\partial f(x_1,x_2,x_3)}{\partial x_1}=0\\ \dfrac{\partial f(x_1,x_2,x_3)}{\partial x_2}=0 \\ \dfrac{\partial f(x_1,x_2,x_3)}{\partial x_3}=0 \\ \end{array} \right.$$

There are three real solutions to this nonlinear equations. The numerical approximations are:

$$\left\{ \begin{array}{lll} x_1= -0.70232526862089675286,&x_2= 1.1741183197060872210,&x_3= -1.0435032734116017453 \\ x_1= 0.61317184960467391827,&x_2= 0.14196135498347057984,&x_3= -0.098972302734396542811 \\ x_1= 0.12381470074854435315,&x_2= 0.58231508583018740098,&x_3= -0.65302668522354754340\\ \end{array} \right.$$

It is quite easy to eliminate the third solution, since the objective function value for this solution is significantly larger than 0.

However, both the objective function values of the former two solutions are at the numerical computation error level.

For example, for double precision computation, the objective function values are

$$6.36106\times 10^{-13},\quad 1.59026\times 10^{-14},\quad 0.252074$$ respectively.

How to determine whether the minimization problem has a unique or two global minimum(s) for such a problem?

• If the objective function values are actually zero, maybe you can $x$ such that the three terms in your original objective are all $0$. ALso, since the polynomial appears to be nonnegative, it may be written as a sum of squares, and that may help too. – LinAlg Jan 9 '17 at 14:54