Prove NP Hardness for non-convex multi-objective optimization

Question

The multi-objective optimization problem in my case is non-linear as it consists of three objective function of which two are nonlinear function and the third is a linear function. Lets say objective 1 is as given below:

• Objective 1: Minimize $f_1(X_1,X_2)=230.54X_1^2+305X_2^2+554.56X_1X_2+121.59X_1+112.9X_2$

• Constraint 1: $ 0 \le X_1 \le 1.5$

• Constraint 2: $ 0 \le X_2 \le 1$

• Constraint 3: $ X_1 + X_2 \le 30$

Here, $X_1$ and $X_2$ are decision variable and are real numbers.

To determine convexity of the above function, the eigenvalues of its Hessian matrix is examined.

For this case, I get both positive and negative eigenvalue. The eigenvalues are 1306.5 and -235.4. Hence, it is a non-convex optimization problem. For this case, how can classify this problem as NP-Hard and use NSGA-II to solve the problem?

Answer 1

Considering the first given objective function, the problem is trivial to solve. The decision variables X1 and X2 are positive. Because polynomial with positive coefficients only, the objective function is thus monotonically increasing over the space of feasible solutions. The last constraint over X1 and X2 is inactive because dominated by the previous ones. Consequently, the minimum (0) is reached for X1 = 0 and X2 = 0. In the same way, if you want to maximize, you can easily show that the maximum (1950.84) is reached for X1 = 1.5 and X2 = 1.

As previously suggested, you can quickly check it using any nonlinear solver. For example, below is the maximization problem solved using LocalSolver.

function model() {
    X1 <- float(0,1.5);
    X2 <- float(0,1);
    constraint X1 + X2 <= 30;
    obj <- 230.54 * X1 * X1 + 305 * X2 * X2 + 554.56 * X1 * X2 + 121.59 * X1 + 112.9 * X2; 
    maximize obj;
}

function output() {
    println("X1 = " + X1.value + ", X2 = " + X2.value);
}

> localsolver .\orstackexchange_20210716.lsp
LocalSolver 10.5.20210624-Win64. All rights reserved.
Load .\orstackexchange_20210716.lsp...
Run input...
Run model...
Run param...
Run solver...
    
Model:  expressions = 19, decisions = 2, constraints = 1, objectives = 1
Param:  no time limit, no iteration limit

[objective direction ]:     maximize

[  0 sec,       0 itr]:            0
[ optimality gap     ]:      100.00%
[  0 sec,       2 itr]:      1950.84
[ optimality gap     ]:           0%

2 iterations performed in 0 seconds

Optimal solution:
  obj    =      1950.84
  gap    =           0%
  bounds =      1950.84

Run output...
X1 = 1.5, X2 = 1 

Answer 2

The notion of NP-hardness relates to whether one class of problems can be solved by a solver for another class of problems where the translation overhead is negligible.

The problem you presented is member of many classes of problems. However NP-hardness is the property of a class of problems. So it is impossible to answer whether this particular instance is NP hard as the question doesn't make sense.

As for is that problem solvable via NSGA-II, yes you can get a solution. But due it's simple structure and low dimensionality a global optimizer of this single objective (such as the Octeract Engine, Baron or a non convex QP solver) can be used to have guarantees that it is indeed the optimal solution.

Answer 3

NP-hardness is an asymptotic result of increasing problem dimensions. It is not a property of one fixed problem instance. So to ask whether your problem class is NP-hard, you would have to explain how the problem would grow with increasing numbers of $X$ variables.

As far as solving your specific instance, a number of nonlinear solvers could probably do it, and for that matter you could probably "brute force" it by solving the Karush-Kuhn-Tucker necessary conditions. There are three possibilities for the first constraint (binding at 0, binding at 1.5, nonbinding) and similarly for the second, and two possibilities (binding or not) for the third. That gives you 3x3x2=18 sets of KKT conditions to solve, which is very manageable. The best of the 18 solutions (fewer if some combinations yield no feasible solution) is your winner.