MINLP returns infeasible solution

[Xuezhou Zhang]

Hi all,

I'm using the MINLP solver to solve a nonlinear mixed integer optimization problem of selecting training subset for SVM. The problem I have is that the MINLP solver often returns solutions with the continuous variable theta not satisfy the nonlinear constraint. This happens often when I restrict the binary variable to a single feasible point. Below I pasted a sample output. I also attached the AMPL codes. Any feedback is helpful.

Thanks,

Xuezhou

Presolve eliminates 10 constraints and 10 variables.
Adjusted problem:
2 variables, all nonlinear
2 constraints, all nonlinear; 4 nonzeros
	2 equality constraints
1 nonlinear objective; 2 nonzeros.

MINLP-B&B (20100607): eps=1.0e-6
rho=100
miopttol=1.0e-6
m(before SOS) = 2
m(a f t e r SOS) = 2
MINLP-B&B (20100607): Optimal solution found
1 subproblem, objective = 1e+20
Evals: obj = 562, constr = 741, grad = 454, Hes = 730
risk = 0.5

y [*] :=
 1  -1
 2  -1
 3  -1
 4  -1
 5  -1
 6  -1
 7  -1
 8  -1
 9  -1
10  -1
;

theta [*] :=
1  0
2  0
;

b [*] :=
 1  1
 2  1
 3  1
 4  1
 5  1
 6  1
 7  1
 8  1
 9  1
10  1
;

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
   then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -0.657632

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
   then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -0.409823


Presolve eliminates 10 constraints.
Adjusted problem:
12 variables, all nonlinear
2 constraints, all nonlinear; 24 nonzeros
	2 equality constraints
1 nonlinear objective; 2 nonzeros.

MINLP-B&B (20100607): eps=1.0e-6
rho=100
miopttol=1.0e-6
m(before SOS) = 2
m(a f t e r SOS) = 2
MINLP-B&B (20100607): Optimal solution found
58 subproblems, objective = 0.01092791509
Evals: obj = 7378, constr = 9507, grad = 3445, Hes = 5775
risk = 0.0109279

y [*] :=
 1  -1
 2  -1
 3  -1
 4  -1
 5  -1
 6  -1
 7  -1
 8  -1
 9  -1
10  -1
;

theta [*] :=
1  0.553799
2  0.593192
;

b [*] :=
 1  1
 2  1
 3  0
 4  1
 5  1
 6  1
 7  0
 8  0
 9  0
10  0
;

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
   then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -2.08167e-17

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
   then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -6.93889e-18

[Xuezhou Zhang]

Guys any ideas? When will a solver returns infeasible solution when the initialization is feasible?

[Robert Fourer]

Both the if-then-else function and the abs function are nonsmooth, in the sense that there are points where these functions change slope abruptly and do not have a well-defined derivative. Thus when you use if-then-else with a variable in the "if" part, and abs applied to a variable, you create nonsmooth objective and constraint functions.

Nonlinear solvers such as MINLP will try to deal with nonsmooth functions but in general they do not have much success, and can even give incorrect results. As another example, when I try your problem with Knitro, I get these messages from the first solve:

EXIT: Terminate at infeasible point because the relative change in solution
estimate < xtol for 3 consecutive iterations.

Knitro 10.2.0: Relative change in infeasible solution estimate < xtol for xtol_iters.
objective 0.06518413354; feasibility error 0.0491
56 iterations; 272 function evaluations

To fix this you'll need to re-think how your write your objective and constraint expressions, so that they are smooth functions of the variables. Usually this is done by including binary variables in your smooth function so that a value of 0 gives your "then" expression and a value of 1 gives your "else" expression.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Xuezhou Zhang
Sent: Monday, October 9, 2017 11:16 PM
To: AMPL Modeling Language
Subject: [AMPL 14886] MINLP returns infeasible solution

Hi all,
I'm using the MINLP solver to solve a nonlinear mixed integer optimization problem of selecting training subset for SVM. The problem I have is that the MINLP solver often returns solutions with the continuous variable theta not satisfy the nonlinear constraint. This happens often when I restrict the binary variable to a single feasible point. Below I pasted a sample output. I also attached the AMPL codes. Any feedback is helpful.

Thanks,
Xuezhou

Presolve eliminates 10 constraints and 10 variables.
Adjusted problem:
2 variables, all nonlinear
2 constraints, all nonlinear; 4 nonzeros
2 equality constraints
1 nonlinear objective; 2 nonzeros.

MINLP-B&B (20100607): eps=1.0e-6
rho=100
miopttol=1.0e-6
m(before SOS) = 2
m(a f t e r SOS) = 2
MINLP-B&B (20100607): Optimal solution found
1 subproblem, objective = 1e+20
Evals: obj = 562, constr = 741, grad = 454, Hes = 730
risk = 0.5

...

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -0.657632

1/N*(sum{i in 1 .. N} ( if 1 - sum{j in 1 .. d} y[i]*x[i,j]*theta[j] > 0
then -(x[i,s]*y[i]*b[i]))) + lambda*theta[s] = -0.409823


Presolve eliminates 10 constraints.
Adjusted problem:
12 variables, all nonlinear
2 constraints, all nonlinear; 24 nonzeros
2 equality constraints
1 nonlinear objective; 2 nonzeros.

MINLP-B&B (20100607): eps=1.0e-6
rho=100
miopttol=1.0e-6
m(before SOS) = 2
m(a f t e r SOS) = 2
MINLP-B&B (20100607): Optimal solution found
58 subproblems, objective = 0.01092791509
Evals: obj = 7378, constr = 9507, grad = 3445, Hes = 5775
risk = 0.0109279

...