Must hessiian matrix in QP be semi-possitive?

[facat facat]

We know objective function of a QP problem is

min f(x)=1/2*x'*H*x+x'*C

If the hessian matrix H is semi-positive, this is a convex problem. Do all QP solvers in Yamip require H to be semi-positive?

my problem is as below:
================================

x=sdpvar(7,1);
Constraints=[[zeros(2) A' -eye(2)]*x==-c;[A zeros(length(b)) zeros(3,2)]*x<=b;x>=0];
H1=zeros(7,7);
H1(3:5,1:2)=-A;
F=zeros(1,7);
F(3:5)=b;
H2=zeros(7,7);
H2(6:7,1:2)=eye(2);
Objective=x'*(H1+H2)*x+F*x;
options = sdpsettings('verbose',2,'solver','clp');
solvesdp(Constraints,Objective,options)
double(Objective)
double(x)

================================
I was successfully solve this QP problem with a NLP solver(e.g Ipopt). When I try to solve it with any QP solvers, I fail and get the warning "Solver not applicable". What does this warning mean?  I think mine is a QP problem, only that H is not semi-positive.

[Johan Löfberg]

The solver targeting convex problems assume psd (such as cplex, gurobi, mosek, clp, xpress)

quadprog allows indefinite/negative definite, but is only s local QP solver so no guarantees

global QP solver quadprogBB allows indefinite/negative definite

global QP solver kktqp allows indefinite/negative definite

local NLP solvers such as fmincon, snopt etc allow indefinite/negative definite

global NLP solvers bmibnb allows indefinite/negative definite

[facat facat]

My QP problem is infeasible with kktqp in Yalmip, but it was successfully solved with clp in Opti Toolbox.

[Johan Löfberg]

kktqp assumes you have an efficient MILP solver. It also requires that the feasible space is bounded, which it looks like it isn't in your case.

Hence, you must add bounds on all variables (upper, as you already have lower bounds).

You are welcome to post the numerical data so I can try it (A, c, b)

BTW, when I look at you model, it looks like you are solving some type of a complementarity problem. Hence, it is a bit unnecessary to use kktqp on that model, since kktqp applies a complementarity approach on the kkt conditions of your QP. Better approach then would be to apply a global solver directly on the problem which led to your indefinite QP (if I am correct in my guess)

[facat facat]

I want to solve the KKT condition of LP(my home work). I convert the complementarity equation in the KKT condition to an objective function of a QP problem. I tried adding the upper bounds, but still failed.
Numerical data and code are as below

=============

A=[-2 1; -1 1; 1 0];
b=[2 3 3]';
c=[-1 -2]';
%% 二次规划标准型
x=sdpvar(7,1);
Constraints=[[zeros(2) A' -eye(2)]*x==-c;[A zeros(length(b)) zeros(3,2)]*x<=b;100>=x>=0];

H1=zeros(7,7);
H1(3:5,1:2)=-A;
F=zeros(1,7);
F(3:5)=b;
H2=zeros(7,7);
H2(6:7,1:2)=eye(2);
Objective=x'*(H1+H2)*x+F*x;

options = sdpsettings('verbose',2,'solver','kktqp');
solvesdp(Constraints,Objective,options)
double(Objective)
double(x)

=============

you may have a try.

[Johan Löfberg]

Works here. My guess is that you don't have an efficient MILP solver. What is displayed when you run

intvar x y
solvesdp([x>=1,y>=2],x+y)

BTW, why are you working with such a cumbersome notation. Define primals and duals separately and simply add the constraints you have on these. No reason to create some kind of concatenated vector of variables, and then trying to figure out which parts to use.

% Primals

x = sdpvar(2,1);

% Duals for general

z = sdpvar(3,1);

% duals for simple bounds

v = sdpvar(2,1);

Constraints=[A'*z-v == -c, A*x <= b, x >=0, z >=0, v>=0];

Objective = z'*(b-A*x) + v'*x;

solvesdp(Constraints,Objective,sdpsettings('solver','kktqp'))

However, it is really a bit odd to go over the quadratic model, since the kktqp solver will look at the kkt of this lifted problem, so you are solving an unnecessarily large MILP in the end.

This might be interesting to read

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Complements

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Kkt

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Blog.Solving-nonconvex-QPs

[facat facat]

This is what displayed

Cbc0009I Objective coefficients multiple of 1
Cbc0004I Integer solution of 3 found after 0 iterations and 0 nodes (0.01 seconds)
Cbc0001I Search completed - best objective 3, took 0 iterations and 0 nodes (0.02 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost

ans =

    yalmiptime: 0.800999999999995
    solvertime: 0.0249999999999986
          info: 'Successfully solved (CBC)'
       problem: 0

It's odd to go over quadratic model, but it's an interesting trial, at least my supervisor thinks so.
BTW, why am I solving MIPL? My model doesn't contain integer variables.

[Johan Löfberg]

OK, I can reproduce there here when I use Cbc as the MILP solver. I guess Cbc isn't robust enough. Since you seem to be in academia, you should install a better mixed-integer solver such as cplex or gurobi etc (they are free for academia)

You are solving a MILP since kktqp is based on taking the nonconvex QP and writing down its KKT conditions, and use the fact that the quadratic objective can be written as a linear function of the primal and duals. The complementary constraints are dealt with using a standard big-M reformulation, thus introducing binaries 

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Commands.Kkt

I wouldn't say it is odd to go over to a quadratic model, but attacking this indefinite quadratic model globally using a kkt/milp approach is odd (beyond the fact that all is for fun and testing, since solving a simple LP through KKT conditions is completely useless, but I presume you know that)

You do

(simple LP in x) -> KKT  -> (LP with complementary and duals z and v) -> (indefinite QP in x and z and v) -> KKTQP -> (LP in x and z and v and new duals w) -> big-M-> (MILP in x,z,v,w and binaries d)

When you just as well could do

(simple LP in x) -> KKT  -> (LP with complementary and duals z and v) ->big-M-> (MILP in x,z,v and binaries d)

[facat facat]

Yes, I am a post-degree candidate. After installing gurobi, my model was successfully solved.
I know there are many efficient algorithms solving LP, but I was asked to solve it in my way.
Thank you for you suggestion, I realize I can learn much mathematics here.