the magnitude of computation time
yuyu...@gmail.com
What is the unit of these times? Thanks!!!
_ampl_elapsed_time = 1.4e-05
_ampl_system_time = 0.020001
_ampl_user_time = 0.16401
_ampl_time = 0.184011
Robert Fourer
Ronald Menich
using AMPL and attempted to solve it locally using CPLEX and then using
some other solvers on NEOS. Both CPLEX and MOSEK say it cannot be
solved because the Hessian is not positive semi-definite. The OOQP
solver solves it "successfully", though I don't trust the result because
when I remove a constraint and resolve, the result is a lower objective
function value (the problem is a maximization --- removing a constraint
should only cause the objective to increase, but it decreased instead!).
So I probably do have a problem.
* My question is, "What should I do now?".
* How can I diagnose what I have done wrong?
* Can AMPL help me to understand what the problem is in my formulation?
* Are there some parameters I should try tweaking, in case it's not a
real Hessian problem but something readily solved with some "epsilon"
parameter of which I'm not aware?
* What sequence of steps should I take to ascertain whether or not the
Hessian is PSD?
OOQP completes "successfully":
"
OOQP completed sucessfully. Objective value: 19283.774.
"
CPLEX complains:
"
CPLEX 8.0.0: QP Hessian is not positive semi-definite.; no basis.
"
MOSEK complains:
"
The quadratic constraint matrix in the objective is not NSD.
MOSEK Error 1291 - The optimization problem is nonconvex.
MOSEK Error 1265 - The solution with code 0 is not defined.
Return code - 1291 [MSK_RES_ERR_NONCONVEX] MOSEK finished.
MOSEK return code - 1291 (The optimization problem is nonconvex.)
"
Ron Menich
Dominique
Ron,
It does seem that your Hessian is indefinite. I am not sure why OOQP
processes it successfully. I don't think it is supposed to. There are
tools out there that will be able to tell you whether or not your
Hessian is positive definite, but if it isn't, those tools won't tell
you where the problem is coming from. The best is probably to obtain
the Hessian explicitly and give it to, e.g., a Cholesky factorization
or a method that computes the smallest eigenvalue. NLPy (nlpy.sf.net)
will help you obtain your Hessian explicitly as a sparse matrix in the
Python programming language. Then you can use tools from SciPy
(www.scipy.org) to process it.
Dominique
Ronald Menich
It turns out that I seem to have resolved my problem. My objective
function was of the form
sum { s in sSet } vX[ s ] * vY[ s ]
where vX[] and vY[] are variables and the the vY[] is a linear function
of the vX[], as represented by the constraint
s.t. cConstraint { s in sSet }:
vY[ s ] = pIntercept[ s ] + pSlope[ s ] * vX[ s ]
where pIntercept[] and pSlope[] are constant parameters. There are
many other constraints in my problem, but they are all linear in the
variables; only the objective function in nonlinear.
My original thought was that the QP would solve just fine --- hey, the
vY[] is linear in vX[], so vX[]*vY[] is quadratic in vX[], right? ---
but it didn't and failed with Hessian errors mentioned in my note. I
had a hunch and replaced my objective function
sum { s in sSet } vX[ s ] * vY[ s ]
by substituting for vY[] in terms of vX[]
sum { s in sSet } vX[ s ] * ( pIntercept[ s ] + pSlope[ s ] *
vX[ s ] )
so that the objective function became explictly quadratic in vX[] rather
than quadratic by implication of the linear equality constraint. My
initial thought was that I had changed nothing regarding the problem, I
had just done a direct substitution of variables.
However, after performing this trick the problem solved successfully in
both CPLEX and MOSEK, giving the same answer in both to several decimal
places of agreement, and there was no complaint by the software
regarding the Hessian.
Lesson learned on my part. Thank you for the pointers.
Ron
P.S. (After the variable substitution trick, OOQP also "successfully"
solved the problem, but gave a quite different answer than the common
one upon which both CPLEX and MOSEK agreed. My faith in OOQP is
accordingly very low.)
-----Original Message-----
From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of
Dominique
Sent: Friday, August 17, 2007 9:46 AM
To: AMPL Modeling Language