Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    Ahviuwrebnqiu 32

    Uploaded by

    hsxrwyzpktdxygmtkq
    The document discusses two optimization problems. The first problem involves minimizing a function subject to bounds on x, and strong duality does not hold. The second problem minimizes x^2 subject to bounds on x, strong duality does hold, and the KKT conditions connect the optimal values of the Lagrange multipliers to whether constraints are strict or not at the optimal x.

    Copyright:

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

    Ahviuwrebnqiu 32

    Uploaded by

    hsxrwyzpktdxygmtkq
    5 views4 pages
    The document discusses two optimization problems. The first problem involves minimizing a function subject to bounds on x, and strong duality does not hold. The second problem minimizes x^2 subject to bounds on x, strong duality does hold, and the KKT conditions connect the optimal values of the Lagrange multipliers to whether constraints are strict or not at the optimal x.

    Original Title

    ahviuwrebnqiu32

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses two optimization problems. The first problem involves minimizing a function subject to bounds on x, and strong duality does not hold. The second problem minimizes x^2 subject to bounds on x, strong duality does hold, and the KKT conditions connect the optimal values of the Lagrange multipliers to whether constraints are strict or not at the optimal x.

    Copyright:

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

    Ahviuwrebnqiu 32

    Uploaded by

    hsxrwyzpktdxygmtkq
    The document discusses two optimization problems. The first problem involves minimizing a function subject to bounds on x, and strong duality does not hold. The second problem minimizes x^2 subject to bounds on x, strong duality does hold, and the KKT conditions connect the optimal values of the Lagrange multipliers to whether constraints are strict or not at the optimal x.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    EECS 127/227AT Optimization Models in Engineering UC Berkeley Spring 2024

    Discussion 10

    1. Magic with constraints


    In this question, we will represent a problem in two different ways and show that strong duality holds in one case
    but doesn’t hold in the other.
    Let 
    x3 − 3x2 + 4, x≥0
    .
    f0 (x) = (1)
    −x3 − 3x2 + 4, x < 0.

    (a) Consider the minimization problem

    p∗ = inf f0 (x) (2)


    x∈R

    s.t. − 1 ≤ x, x ≤ 1. (3)

    i. Show that p∗ = 2 and the the set of optimizers x ∈ X ∗ is X ∗ = {−1, 1} by examining the “critical"
    points, i.e., points where the gradient is zero, points on the boundaries, and ±∞.

    ii. Show that the dual problem can be represented as

    d∗ = sup g(⃗λ), (4)


    λ1 ,λ2 ≥0

    where n o
    g(⃗λ) = min g1 (⃗λ), g2 (⃗λ) , (5)
    with

    g1 (⃗λ) = inf x3 − 3x2 + 4 − λ1 (x + 1) + λ2 (x − 1) (6)


    x≥0

    g2 (⃗λ) = inf −x3 − 3x2 + 4 − λ1 (x + 1) + λ2 (x − 1). (7)


    x<0

    iii. Next, show that

    g1 (⃗λ) ≤ −3λ1 + λ2 (8)


    g2 (⃗λ) ≤ λ1 − 3λ2 . (9)

    Use this to show that g(⃗λ) ≤ 0 for all λ1 , λ2 ≥ 0.

    1
    EECS 127/227AT Discussion 10 2024-03-22 12:16:07-07:00

    iv. Show that g(⃗0) = 0 and conclude that d∗ = 0.

    v. Does strong duality hold?

    (b) Now, consider a problem equivalent to the minimization in (2):

    p∗ = inf f0 (x) (10)


    x∈R

    s.t. x2 ≤ 1. (11)

    Observe that p∗ = 2 and the set of optimizers x ∈ X ∗ is X ∗ = {−1, 1}, since this problem is equivalent
    to the one in part (a).
    i. Show that the dual problem can be represented as

    d∗ = sup g(λ), (12)


    λ≥0

    where
    g(λ) = min{g1 (λ), g2 (λ)}, (13)
    with

    g1 (λ) = inf x3 − 3x2 + 4 + λ(x2 − 1) (14)


    x≥0

    g2 (λ) = inf −x3 − 3x2 + 4 + λ(x2 − 1). (15)


    x<0


    4 − λ, λ≥3
    ii. Show that g1 (λ) = g2 (λ) = .
    4
    −
    27 (3 − λ)3 + 4 − λ, 0 ≤ λ < 3.

    © UCB EECS 127/227AT, Spring 2024. All Rights Reserved. This may not be publicly shared without explicit permission. 2
    EECS 127/227AT Discussion 10 2024-03-22 12:16:07-07:00

    iii. Conclude that d∗ = 2 and the optimal λ = 23 .

    iv. Does strong duality hold?

    2. Complementary Slackness
    Consider the problem:

    p⋆ = min x2 (16)
    x∈R

    s.t. x ≥ 1, x ≤ 2. (17)

    (a) Does Slater’s condition hold? Is the problem convex? Does strong duality hold?

    (b) Find the Lagrangian L(x, λ1 , λ2 ).

    (c) Find the dual function g(λ1 , λ2 ) so that the dual problem is given by,

    d⋆ = max g(λ1 , λ2 ). (18)


    λ1 ,λ2 ∈R+

    (d) Solve the dual problem in (18) for d⋆ .

    © UCB EECS 127/227AT, Spring 2024. All Rights Reserved. This may not be publicly shared without explicit permission. 3
    EECS 127/227AT Discussion 10 2024-03-22 12:16:07-07:00

    (e) Solve for x⋆ , λ⋆1 , λ⋆2 that satisfy KKT conditions.

    (f) Can you spot a connection between the values of λ⋆1 , λ⋆2 in relation to whether the corresponding inequality
    constraints are strict or not at the optimal x⋆ ?

    © UCB EECS 127/227AT, Spring 2024. All Rights Reserved. This may not be publicly shared without explicit permission. 4

    You might also like