[Scip] Optimal Multiplier Vector in Quadratic Programs

[Stefan Vigerske]

Hi,

SCIP computes one global optimal primal solution.
But while for a convex problem, a proof optimality is given by a dual 
solution that just consists of single values for each constraint, for a 
nonconvex problem a dual solution that gives you a proof of optimality 
is much more complex. Just look at dual value functions for MIP to get 
some idea.
Thus, the dual solution you can compute for a nonconvex problem will 
just provide you a proof of local optimality, but no global information. 
In other words, I doubt it is useful for anything, so solvers like SCIP 
put no effort in providing this.

Stefan

On 06/05/2015 05:50 PM, Apurv Shukla wrote:
> Hi
> Thanks for the help. I will make that addition to my code. I have one
> question from your response. You say "let that solver compute a locally
> optimal dual solution for it". However when SCIP finds a globally optimal
> solution wouldn't the corresponding dual solution correspond to globally
> optimal multiplier vector (i.e global optimal solution of the resultant
> lagrangian dual)? What does "locally optimal dual solution" (quoted above)
> refer to?
> Thanks for your time.
> Regards
> ᐧ
>
> Apurv Shukla
> Third Year Undergraduate Student
> Department of Mechanical Engineering
> IIT Kharagpur
>
> On Fri, Jun 5, 2015 at 4:36 PM, Stefan Vigerske <stefan at math.hu-berlin.de>
> wrote:
>
>> Hi,
>>
>> no, SCIP might not even have computed dual multipliers internally for the
>> quadratic constraints when finding an optimal solution.
>> If you have a (local) QCQP/NLP solver at hand, you could pass the solution
>> from SCIP to it and let that solver compute a locally optimal dual solution
>> for it.
>>
>> If you want to dig into SCIP code, you could try to trigger an explicit
>> call to Ipopt within SCIP after SCIP has finished the solve. The function
>> solveSubNLP() in heur_subnlp.c may give an idea how to do this.
>> Essentially, you have to call SCIPtransformProb(), SCIPpresolve(), and
>> SCIPsolve() (with a nodelimit of 1) to get into a state in which one can
>> start a solve of the NLP relaxation (which isn't relaxing anything of your
>> problem in your case) in SCIP. Then set the previously found solution via
>> SCIPsetNLPInitialGuess() and solve the NLP with SCIPsolveNLP(). If that
>> worked, you can query the rows of the NLP for their dual solution via
>> SCIPnlrowGetDualsol(). Looking at the code in heur_subnlp.c, this sounded
>> easier than it is :-).
>>
>> Stefan
>>
>>
>> On 06/05/2015 11:45 AM, Apurv Shukla wrote:
>>
>>> Dear All
>>> I am using SCIP as a black box solver for solving a nonconvex
>>> quadratically
>>> constrained quadratic program consisting of an indefinite quadratic
>>> objective, one quadratic equality constraint, one linear equality
>>> constraint  and box constraints on the variables. SCIP has been able to
>>> solve all the instances to optimality till now however since this is a
>>> part
>>> of a bigger primal-dual algorithm, I need the optimal multiplier vector
>>> (Lagrange Dual Vector) associated with each of the constraint at the
>>> optimal solution. Is there any method or procedure to retrieve these
>>> values? Any help regarding this will be much appreciated.
>>> Thanks
>>>
>>>
>>>
>>> Apurv Shukla
>>> Third Year Undergraduate Student
>>> Department of Mechanical Engineering
>>> IIT Kharagpur
>>> ᐧ
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>
>