Consider the following optimization problem.Minimizex∈IR2 3x1 − (x2)3Subject to (x1)2 + (x2)2 ≤ 2,−x1 + x2 ≤ −1.(a) Show that the MFCQ holds at every feasible point.[5 marks](b) Write down the KKT conditions.
Question
Consider the following optimization problem.Minimizex∈IR2 3x1 − (x2)3Subject to (x1)2 + (x2)2 ≤ 2,−x1 + x2 ≤ −1.(a) Show that the MFCQ holds at every feasible point.5 marks Write down the KKT conditions.
Solution
(a) The Mangasarian-Fromovitz Constraint Qualification (MFCQ) holds at a feasible point if the gradients of the active constraints at that point are linearly independent.
The constraints of the problem are:
- (x1)² + (x2)² ≤ 2
- -x1 + x2 ≤ -1
The gradient of the first constraint is (2x1, 2x2) and the gradient of the second constraint is (-1, 1). These two gradients are linearly independent because there is no scalar multiple that can transform one gradient into the other. Therefore, the MFCQ holds at every feasible point.
(b) The Karush-Kuhn-Tucker (KKT) conditions are necessary conditions for a solution in nonlinear programming to be optimal. For this problem, the KKT conditions are:
-
Stationarity: ∇f(x) + ∑λi∇gi(x) + ∑μj∇hj(x) = 0, where f(x) is the objective function, gi(x) are the inequality constraints, and hj(x) are the equality constraints. In this case, there are no equality constraints, so the stationarity condition simplifies to ∇f(x) + ∑λi∇gi(x) = 0.
-
Primal feasibility: All constraints must be satisfied, i.e., gi(x) ≤ 0 for all i and hj(x) = 0 for all j.
-
Dual feasibility: The Lagrange multipliers associated with the inequality constraints must be nonnegative, i.e., λi ≥ 0 for all i.
-
Complementary slackness: For each inequality constraint, the product of the constraint function and its associated Lagrange multiplier must be zero, i.e., λigi(x) = 0 for all i.
Similar Questions
Consider the following optimization problem:Minimizex∈IR3 2x21 + x22 + 2x23Subject to x1 + 2x2 + x3 ≤ −3.(a) (10 points) For each c > 0, defineqc(x) := 2x21 + x22 + 2x23 + c2 (x1 + 2x2 + x3 + 3)2+Argue that qc is convex and find the global minimizer of qc.(b) (10 points) For each µ > 0, defineℓµ(x) := 2x21 + x22 + 2x23 − µ ln (−3 − x1 − 2x2 − x3) .Argue that ℓµ is convex and find the global minimizer of ℓµ. You may use without proof thefact that the function t 7 → − ln(−3 − t) is convex (as an extended real-valued function).
Optimality. Consider the following optimization problemminimize 12 xT P x + qT x + rsubject to −1 ≤ xi ≤ 1, i = 1, 2, 3whereP = 26 24 −424 34 12−4 12 24 , q =−44−2926 , r = 1.(a) Prove that x? = (1, 0.5, −1) is optimal.(b) Are any of the constraints inactive at x?? If so, which one(s)?
Write the dual of the following linear programming problem:Maximize 8x1 + 3x2 − 2x3subject to x1 − 6x2 + x3 > 25x1 + 7x2 − 2x3 = −4x1 ≤ 0, x2 ≥ 0, x3 unrestricted.
Consider the optimisation problemminx∈R3x1−2x2+ex3subject toAx=0min𝑥∈𝑅3𝑥1−2𝑥2+𝑒𝑥3subject to𝐴𝑥=0where A𝐴 is a 2×32×3 matrix with rank two. Moreover, the sum of the entries in each row of A𝐴 is zero.(a) This problem can be rewritten as an unconstrained convex optimisation problem in how many variables? Answer 1 Question 1(b) The optimal solution to the original problem, in the variables x1,x2𝑥1,𝑥2 and x3𝑥3, is given by:
Consider the following linear program:minx1,x2,x3,x4c1x1+c2x2+c3x3+2x4subject to⎧⎩⎨x1+x2+x3+x4≥103x1+x2+4x3+2x4≥12x1≥0,x2≥0,x3≥0,x4≥0min𝑥1,𝑥2,𝑥3,𝑥4𝑐1𝑥1+𝑐2𝑥2+𝑐3𝑥3+2𝑥4subject to{𝑥1+𝑥2+𝑥3+𝑥4≥103𝑥1+𝑥2+4𝑥3+2𝑥4≥12𝑥1≥0,𝑥2≥0,𝑥3≥0,𝑥4≥0 The parameters c1,c2,c3𝑐1,𝑐2,𝑐3 are real numbers.(a) How many variables does the dual problem have? Answer 1 Question 2Suppose that the optimal solution to the primal is x1=0𝑥1=0, x2=0𝑥2=0, x3=0𝑥3=0, x4=10𝑥4=10.(b) What is the optimal value of the objective function of the dual linear program? Answer 2 Question 2.(c) How many entries of the optimal dual variable are equal to zero?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.