Polynomial optimization problem can't deal with redundant constraints

Specific Domains Optimization (Mathematical)
,
1

I’m exploring the following polynomial optimization problem:

using SumOfSquares
using DynamicPolynomials
using MosekTools

# Create symbolic variables (not JuMP decision variables)
@polyvar x1 x2

# Create a Sum of Squares JuMP model with the Mosek solver
model = SOSModel(with_optimizer(Mosek.Optimizer))

# Create a JuMP decision variable for the lower bound
@variable(model, γ)
@variable(model, x)

# f(x) is the Goldstein-Price function
f1 = x1+x2+1
f2 = 19-14*x1+3*x1^2-14*x2+6*x1*x2+3*x2^2
f3 = 2*x1-3*x2
f4 = 18-32*x1+12*x1^2+48*x2-36*x1*x2+27*x2^2

f = (1+f1^2*f2)*(30+f3^2*f4)

when the constraint takes the form of

@constraint(model, f >= γ)

this problem can be solved to optimal:

@objective(model, Max, γ)
optimize!(model)
# The lower bound found is 3
println(objective_value(model))

However, when I added a redundant constraint

@constraint(model, f1>= x)

the output indicates that this problem has not been solved:

Problem
  Name                   :                 
  Objective sense        : max             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 49              
  Cones                  : 0               
  Scalar variables       : 3               
  Matrix variables       : 1               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Eliminator - tries                  : 0                 time                   : 0.00            
Lin. dep.  - tries                  : 0                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Optimizer terminated. Time: 0.00    

0.0

I’m pretty confused about this result since the additional constraint is obviously redundant. Why adding a redundant ruins everything? Thanks for your help in advance!

2

In the first problem, you are trying to find a value of γ such that f >= γ for all x1 and x2. Therefore γ gives you a lower bound for the function f but you still don’t know what are the values of x1 and x2 that minimize f (although you may be able to get it from the dual, see here).
In the second example, you want to find a value of x such that x1 + x2 + 1 >= x for all x1 and x2. As the linear expression x1 + x2 + 1 is not bounded below, e.g. take x1 -> -Inf or x2 -> -Inf, there is no value of x satisfying this so the problem is infeasible.

2 Likes