Re: [Help-glpk] Quadratic Programming

[Meketon, Marc]

If the objective function is of the form:

        sum{i in I} x[i]*x[i]

then you might be able to use a piece-wise linear formulation to approximate a 
quadratic objective function.

For example (assuming the "x" above is non-negative)

        # 
------------------------------------------------------------------------------
        # Parabolic deviation parameters
        # 
------------------------------------------------------------------------------
        param NUM_PIECEWISE_LINEAR_BREAKPOINTS default    20;
        param PIECEWISE_LINEAR_GAP_SIZE default     2;
        set   DEV_SECTIONS := 1..NUM_PIECEWISE_LINEAR_BREAKPOINTS;

        var x{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s < 
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;

For constraints, wherever you would have "x[i]" replace it with

        sum{ i in I, s in DEV_SECTIONS } x[ i, s ]

For the objective, use:

        sum{ i in I, s in DEV_SECTIONS } x[ i, s ]*s


If your "x" is a free variable, then it gets a bit more complicated in that you 
would need two sets of variables:

        var xp{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s < 
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;

        var xn{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s < 
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;

and the constraints would need to replace x[i] with

        sum{ i in I, s in DEV_SECTIONS } (xp[ i, s ]-xn[i, s])

and the objective would be

        sum{ i in I, s in DEV_SECTIONS } (xp[ i, s ]+xn[i, s])*s


-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Thursday, September 24, 2015 6:28 AM
To: address@hidden
Cc: address@hidden
Subject: Re: [Help-glpk] Quadratic Programming


> I wonder if it’s possible to solve an optimisation problem with linear
> constraints and quadratic objective function (the problem is convex)
> by glpk.
>

No, glpk does not support solving non-linear problems.



_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

This e-mail and any attachments may be confidential or legally privileged. If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 
Thank you for your cooperation.