Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 1 views

    QuadraticProgramming Wolfe

    Uploaded by

    8132301010

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    QuadraticProgramming Wolfe

    Uploaded by

    8132301010
    1 views23 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    1 views23 pages

    QuadraticProgramming Wolfe

    Uploaded by

    8132301010

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 23

    Wolfe’s Method

    (Quadratic Programming)
    Dedy Suryadi
    2020

    Source: Winston, W.L. & Goldberg, J.B. (2004). Operations research: applications and algorithms (4th ed).
    Wolfe’s Method
    • Wolfe’s method may be used to solve QPP in which all variables must
    be nonnegative.

    • Example:
    Using Theorem 11’
    (1) Checking Convexity

    • Objective function
    dz/dx1 = -1 + x1 – x2 d2z/dx12 = 1 1 −1
    𝐻=
    d2z/dx1x2 = -1 −1 2
    dz/dx2 = -1 + 2x2 – x1 d2z/dx2x1 = -1 Principal minors = z is convex
    d2z/dx22 = 2 1, 2, (1*2)-(-1*-1) = 1
    (1) Checking Convexity

    • Constraints (all linear, so must be convex)


    dg1/dx1 = 1 d2z/dx12 = 0 0 0
    𝐻=
    d2z/dx1x2 = 0 0 0
    dg1/dx2 = 1 d2z/dx2x1 = 0 Principal minors = g1 is convex
    d2z/dx22 = 0 0, 0, (0*0)-(0*0) = 0
    (2) Deriving K-T Conditions
    (2) Deriving K-T Conditions
    First K-T Condition (1)

    with respect to x1:


    𝑑𝑧 𝑑𝑔1 𝑑𝑔2
    + 𝜆1 + 𝜆2 ≥0
    𝑑𝑥1 𝑑𝑥1 𝑑𝑥1
    −1 + 𝑥1 − 𝑥2 + 𝜆1 1 + 𝜆2 (−2) ≥ 0
    First K-T Condition (2)

    with respect to x2:


    𝑑𝑧 𝑑𝑔1 𝑑𝑔2
    + 𝜆1 + 𝜆2 ≥0
    𝑑𝑥2 𝑑𝑥2 𝑑𝑥2
    −1 + 2𝑥2 − 𝑥1 + 𝜆1 1 + 𝜆2 (−3) ≥ 0
    First & Third K-T Conditions
    Standard Form:
    −1 + 𝑥1 − 𝑥2 + 𝜆1 1 + 𝜆2 (−2) ≥ 0

    −1 + 2𝑥2 − 𝑥1 + 𝜆1 1 + 𝜆2 (−3) ≥ 0

    ej =
    Original Constraints

    2x1 + 3x2 > 6

    Simplex Algorithm:
    Multiply by (-1) if the original rhs is negative

    Standard Form:
    Complete Formulation
    First KT condition;
    in standard form

    Original constraints;
    in standard form

    Fourth
    KT condition Third KT condition
    Complete Formulation

    bi – gi(x)
    -6 – (-2x1-3x2)
    -6 + 2x1 + 3x2
    2x1 + 3x2 - 6

    Second KT condition
    (3) Solving the LP
    • Use the Phase I of the two-phase method.
    • To ensure that the solution satisfies the complementary slackness
    constraints:
    (3) Solving the LP

    Old Row 0:

    +
    New Row 0
    (3) Solving the LP
    Old Row 0:

    +
    New Row 0
    None
    1/2
    3/1
    6/3
    Can’t choose this
    because s1’ is a BV
    Optimal Solution
    Wolfe’s Method: Optimal Solution
    • Wolfe’s method is guaranteed to obtain the optimal solution if all
    leading principal minors of the objective function’s Hessian are
    positive.

    • Otherwise, Wolfe’s method may not converge in a finite number of


    pivots.
    Wolfe’s Method
    (Quadratic Programming)
    Dedy Suryadi
    2020

    Source: Winston, W.L. & Goldberg, J.B. (2004). Operations research: applications and algorithms (4th ed).

    You might also like