Description

Exercise 4: Inequality Constrained Optimization Algorithms
Prof. Dr. Moritz Diehl, Andrea Zanelli, Dimitris Kouzoupis, Florian Messerer

1. Interior Point method. In the following, we will implement an interior-point method that can be used to solve nonlinear nonconvex problems with both equality constraints g : Rn →Rp and inequality constraints h : Rn →Rq. Consider the optimization problem
min f(x)
x∈Rn
s.t. g(x) = 0, h(x) ≤ 0,
and the system of nonlinear equations: (1)
∇f(x) + ∇g(x)λ + ∇h(x)ν = 0, (2a)
g(x) = 0, (2b)
h(x) + s = 0, (2c)
νisi = τ, i = 1,…,q, (2d)
To circumvent this problem, it is possible to relax the complementarity condition by setting τ to some positive value. Primal-dual interior-point methods iteratively solve this relaxed set of equations while shrinking τ. For τ → 0, a point satisfying the FONC of (1) is obtained.
In the following, we will implement a simple interior-point method using CasADi to generate the quantities needed to compute the Newton steps to solve equations (2a)-(2d) for the following optimization problem:
min f(x) := (x1 − 4)2 + (x2 − 4)2 x∈R2
s.t. g(x) := sin(x1) − x22 = 0 (3) h(x) := x21 + x22 − 4 ≤ 0.
(a) Using the MATLAB template provided with this exercise, implement three CasADi functions F, G and H that return evaluations of f, g and h respectively. For the test point (x1, x2) = (2, 3), check that you obtain the same values as the ones given in the template.
(b) Implement CasADi functions for the Jacobians and Hessians of f, g and h. Check again the correctness of your code with the numerical values provided for the test point.
(c) Derive on paper the form of the linear system associated with every Newton iteration.
Hint: in order to do so, you have to compute a linearization of equations (2a)-(2d) with respect to (x,λ,ν,s). The Newton step ∆z := (∆x,∆λ,∆ν,∆s) at iteration k is the solution to the system:
M(xk,λk,νk,sk)∆z = r(xk,λk,νk,sk). (4)
1
(d) Implement the Newton algorithm in your code by completing M and r in the template.
(e) In order for the dual solution to be meaningful, we have to enforce positivity of the multipliers associated with inequality constraints ν and slack variables s. To this end, it is possible to rely on a line-search scheme that, at every iteration computes a trial step for ν and s. If the resulting dual solution is infeasible, a backtracking line-search is used to scale the Newton step until feasibility is recovered. Fill in the template in order to implement the line-search.
(f) Run your implementation of the primal-dual interior-point starting from the initial guess x0 = (−2,4), λ0 = 10, ν0 = 10 and s0 = 10 and observe the plots. What is the value of the inequality multiplier ν? Is the inequality constraint active? Does the solution change if you set the initial guess for the primal solution to x0 = (−2,−4)? Is the inequality constraint active in this case? Do second order necessary or sufficient optimality conditions (SOSC or SONC) hold at the solution found?
2. [Bonus] SQP method. A second approach that can be used to solve nonlinear programs is the so-called sequential quadratic programming (SQP) approach. When using such a method, a series of quadratic problems (QP) that locally approximate the original problem, is solved:

s.t. (5)
where Bk ≈∇2xL(xk,λk,νk) is an approximation of the exact Hessian of the Lagrangian L.
(a) Using the template provided, implement an SQP solver using CasADi and the QP solver qpOASES. Use a Gauss-Newton approximation of the Hessian. Test your implementation on problem (1) and plot the iterations in the primal space as in Exercise 4.1.
2