Penalty and Barrier Methods for Constrained Optimization

Penalty and Barrier Methods for Constrained Optimization Robert M. Freund February, 2004 2004 Massachusetts Institute of Technology. 1 1 Introduction Consider the constrained optimization problem P : P : minimize f (x) x s.t. gi (x) ≤ 0, i = 1, . . . , m hi (x) = 0, i = 1, . . . , k x ∈ n , whose feasible region we denote by F := {x ∈ n | gi (x) ≤ 0, i = 1, . . . , m, hi (x) = 0, i = 1, . . . , k}. Barrier and penalty methods are designed to solve P by instead solving a sequence of specially constructed unconstrained optimization problems. In a penalty method, the feasible region of P is expanded from F to all of n , but a large cost or “penalty” is added to the objective function for points that lie outside of the original feasible region F. In a barrier method, we presume that we are given a point xo that lies in the interior of the feasible region F, and we impose a very large cost on feasible points that lie ever closer to the boundary of F, thereby creating a “barrier” to exiting the feasible region. 2 Penalty Methods Consider the constrained optimization problem P : P : minimize f (x) x s.t. gi (x) ≤ 0, i = 1, . . . , m hi (x) = 0, i = 1, . . . , k x ∈ n . 2 By converting the constraints “hi (x) = 0” to “hi (x) ≤ 0, −hi (x) ≤ 0”, we can assume that P is of the form P : minimize f (x) x s.t. g(x) ≤ 0, x ∈ n , where we write g(x) := (g1 (x), . . . , gm (x))T for convenience. Definition: A function p(x) : n →  is called a penalty function for P if p(x) satisfies: • p(x) = 0 if g(x) ≤ 0 and • p(x) > 0 if g(x) ≤  0. Example: p(x) = m
(max{0, gi (x)})2 . i=1 We then consider solving the following penalty program: P (c) : minimize f (x) + cp(x) x s.t. x ∈ n for an increasing sequence of constants c as c → +∞. Note that in the program P (c) we are assigning a penalty to the violated constraints. The scalar quantity c is called the penalty parameter. Let ck ≥ 0, k = 1, . . . , ∞, be a sequence of penalty parameters that satisfies ck+1 > ck for all k and limk→∞ ck = +∞. Let q(c, x) = f (x)+cp(x), and let xk be the exact solution to the program P (ck ), and let x∗ denote any optimal solution of P . The following Lemma presents some basic properties of penalty methods: 3 Lemma 2.1 (Penalty Lemma). 1. q(ck , xk ) ≤ q(ck+1 , xk+1 ) 2. p(xk ) ≥ p(xk+1 ) 3. f (xk ) ≤ f (xk+1 ) 4. f (x∗ ) ≥ q(ck , xk ) ≥ f (xk ) Proof: 1. We have q(ck+1 , xk+1 ) = f (xk+1 ) + ck+1 p(xk+1 ) ≥ f (xk+1 ) + ck p(xk+1 ) ≥ f (xk ) + ck p(xk ) = q(ck , xk ) 2. f (xk ) + ck p(xk ) ≤ f (xk+1 ) + ck p(xk+1 ) and f (xk+1 ) + ck+1 p(xk+1 ) ≤ f (xk ) + ck+1 p(xk ) Thus (ck+1 − ck )p(xk ) ≥ (ck+1 − ck )p(xk+1 ), whereby p(xk ) ≥ p(xk+1 ). 3. From the proof of (1.), f (xk+1 ) + ck p(xk+1 ) ≥ f (xk ) + ck p(xk ). But p(xk ) ≥ p(xk+1 ), which implies that f (xk+1 ) ≥ f (xk ). 4. f (xk ) ≤ f (xk ) + ck p(xk ) ≤ f (x∗ ) + ck p(x∗ ) = f (x∗ ). q.e.d. The next result concerns convergence of the penalty method. 4 Theorem 2.1 (Penalty Convergence Theorem). Suppose that f (x), g(x), and p(x), are continuous functions. Let {xk }, k = 1, . . . , ∞, be a sequence of solutions to P (ck ). Then any limit point x̄ of {xk } solves P . Proof: Let x̄ be a limit point of {xk }. From the continuity of the functions involved, limk→∞ f (xk ) = f (x̄). Also, from the Penalty Lemma, q ∗ := lim q(ck , xk ) ≤ f (x∗ ). k→∞ Thus   lim ck p(xk ) = lim q(ck , xk ) − f (xk ) = q ∗ − f (x̄). k→∞ k→∞ But ck → ∞, which implies from the above that lim p(xk ) = 0. k→∞ Therefore, from the continuity of p(x) and g(x), p(¯ x) = 0, and so g(¯ x) ≤ 0, that is, x ¯ is a feasible solution of P . Finally, from the Penalty Lemma, x) ≤ f (x∗ ), which implies that x ¯ is an f (xk ) ≤ f (x∗ ) for all k, and so f (¯ optimal solution of P . q.e.d. An often-used class of penalty functions is: p(x) = m
[max{0, gi (x)}]q , where q ≥ 1. (1) i=1 We note the following: • If q = 1, p(x) in (1) is called the “linear penalty function”. This function may not be differentiable at points where gi (x) = 0 for some i. • Setting q = 2 is the most common form of (1) that is used in practice, and is called the “quadratic penalty function” (for obvious reasons). 5 • If we denote g + (x) = (max{0, gi (x)}, . . . , max{0, gm (x)})T , then the quadratic penalty function can be written as p(x) = (g + (x))T (g + (x)). 2.1 Karush-Kuhn-Tucker Multipliers in Penalty Methods The penalty function p(x) is in actuality a function only of g + (x), where g + (x) = max{0, gi (x)} (the nonnegative part of gi (x)), i = 1, . . . , m. Then we can write p(x) = γ(g + (x)), where γ(y) is a function of y ∈ (m )+ . Two examples of this type of penalty function are m
γ(y) = yi , i=1 which corresponds to the linear penalty function, and γ(y) = m
yi2 , i=1 which corresponds to the quadratic penalty function. Note that even if γ(y) is continuously differentiable, p(x) might not be continuously differentiable, since g + (x) is not differentiable at points x where gi+ (x) = 0 for some i. However, if we assume the following: ∂γ(y) = 0 at yi = 0, i = 1, . . . , m, ∂yi (2) then p(x) is differentiable whenever the functions gi (x) are differentiable, i = 1, . . . , m, and we can write ∇p(x) = m
∂γ(g + (x)) ∂yi i=1 6 ∇gi (x). (3) Now let xk solve P (ck ). Then xk will satisfy ∇f (xk ) + ck ∇p(xk ) = 0, that is, ∇f (xk ) + ck m
∂γ(g + (xk )) ∂yi i=1 Let us define uki = ck Then ∇f (xk ) + ∇gi (xk ) = 0. ∂γ(g + (xk )) . ∂yi m
(4) uki ∇gi (xk ) = 0, i=1 and so we can interpret the multipliers. In fact, we have: uk as a sort of vector of Karush-Kuhn-Tucker Lemma 2.2 Suppose γ(y) is continuously differentiable and satisfies (2), and that f (x) and g(x) are differentiable. Let uk be definied by (4). Then ¯ and x ¯ satisfies the linear independence condition for gradient if xk → x, vectors of active constraints, then uk → u, ¯ where u ¯ is a vector of KarushKuhn-Tucker multipliers for the optimal solution x̄ of P . Proof: From the Penalty Convergence Theorem, x̄ is an optimal solution of x) < 0}. For i ∈ N , gi (xk ) < 0 x) = 0} and N = {i | gi (¯ P . Let I = {i | gi (¯ k for all k sufficiently large, so ui = 0 for all k sufficiently large, whereby ūi = 0 for i ∈ N . From (4) and the definition of a penalty function, it follows that uki ≥ 0 for i ∈ I, for all k sufficiently large, . Suppose uk → u ¯ as k → ∞. Then ūi = 0 for i ∈ N . From the continuity of all functions involved, ∇f (xk ) + m
uki ∇g(xk ) = 0 i=1 7 implies ∇f (¯ x) + m
u ¯i ∇g(¯ x) = 0. i=1 From the above remarks, we also have u ¯ ≥ 0 and u ¯i = 0 for all i ∈ N . Thus ū is a vector of Karush-Kuhn-Tucker multipliers. It therefore remains to ¯ for some unique ū. show that uk → u k → ∞. But Suppose {uk }∞ k=1 has no accumulation point. Then u then define uk vk = k , u and then v k = 1 for all k, and so the sequence {v k }∞ k=1 has some accumuk lation point v. ¯ For all i ∈ N , vi = 0 for k large, whereby v¯i = 0 for i ∈ N , and
vik ∇gi (xk ) = m
vik ∇gi (xk ) i=1 i∈I = m
 i=1 uki uk  ∇gi (xk ) = −∇f (xk ) uk for k large. As k → ∞, we have xk → x̄, v k → v̄, and uk → ∞, and so the above becomes
v̄i ∇gi (x̄) = 0, i∈I and v̄ = 1, which violates the linear independence condition. Therefore {uk } is a bounded sequence, and so has at least one accumulation point. Now suppose that {uk } has two accumulation points, u ˜ and u. ¯ Note u ¯i = 0 and u ˜i = 0 for i ∈ N , and so
u ¯i ∇gi (¯ x) = −∇f (¯ x) = i∈I so that
u ˜i ∇gi (¯ x), i∈I
(¯ ui − u ˜i )∇gi (¯ x) = 0. i∈I ˜i = 0 for all i ∈ I, and so But by the linear independence condition, u ¯i − u u ¯i = u ˜i . This then implies that u ¯ = u. ˜ 8 q.e.d. Remark. The quadratic penalty function satisfies the condition (2), but that the linear penalty function does not satisfy (2). 2.2 Exact Penalty Methods The idea in an exact penalty method is to choose a penalty function p(x) and a constant c so that the optimal solution x̃ of P (c) is also an optimal solution of the original problem P . Theorem 2.2 Suppose P is a convex program for which the Karush-KuhnTucker conditions are necessary. Suppose that p(x) := m
(gi (x))+ . i=1 Then as long as c is chosen sufficiently large, the sets of optimal solutions of P (c) and P coincide. In fact, it sufficies to choose c > maxi {u∗i }, where u∗ is a vector of Karush-Kuhn-Tucker multipliers. Proof: Suppose x̂ solves P . For any x ∈ Rn we have: q(c, x) = f (x) + c m  i=1 (gi (x))+ ≥ f (x) + ≥ f (x) + ≥ f (x) + = f (x) + m  i=1 m  i=1 m  i=1 m  i=1 (u∗i gi (x))+ u∗i gi (x) u∗i (gi (ˆ x) + ∇gi (ˆ x)T (x − x)) ˆ x)T (x − x) ˆ u∗i ∇gi (ˆ = f (x) − ∇f (ˆ x)T (x − x) ˆ ≥ f (ˆ x) = f (ˆ x) + c m  ˆ (gi (ˆ x))+ = q(c, x). i=1 Thus q(c, x) ˆ ≤ q(c, x) for all x, and therefore x ˆ solves P (c). 9 Next suppose that x ¯ solves P (c). Then if x ˆ solves P , we have: f (¯ x) + c m
x) + c (gi (¯ x))+ ≤ f (ˆ i=1 m
(gi (ˆ x))+ = f (ˆ x), i=1 and so f (¯ x) ≤ f (ˆ x) − c m
(gi (¯ x))+ . (5) i=1 However, if x̄ is not feasible for P , then x − x) ˆ f (¯ x) ≥ f (ˆ x) + ∇f (ˆ x)T (¯ = f (ˆ x) − ≥ f (ˆ x) + = f (ˆ x) − m  x − x) ˆ u∗i ∇gi (ˆ x)T (¯ i=1 m  i=1 m  i=1 x)) u∗i (gi (ˆ x) − gi (¯ x) − c u∗i gi (¯ x) > f (ˆ m  (gi (¯ x))+ , i=1 which contradicts (5). Thus x ¯ is feasible for P . That being the case, x) ≤ f (ˆ f (¯ x) − c m  x))+ = f (ˆ (gi (¯ x) from (5), and so x ¯ solves P . i=1 q.e.d. 2.3 Penalty Methods for Inequality and Equality Constraints The presentation of penalty methods has assumed either that the problem P has no equality constraints, or that the equality constraints have been converted to inequality constraints. For the latter, the conversion is easy to do, but the conversion usually violates good judgement in that it unnecessarily complicates the problem. Furthermore, it can cause the linear independence condition to be automatically violated for every feasible solution. Therefore, instead let us consider the constrained optimization problem P with both inquality and equality constraints: 10 P : minimize f (x) x s.t. g(x) ≤ 0, h(x) = 0, x ∈ n , where g(x) and h(x) are vector-valued functions, that is, g(x) := (g1 (x), . . . , gm (x))T and h(x) := (h1 (x), . . . , hk (x))T for notational convenience. Definition: A function p(x) : n →  is called a penalty function for P if p(x) satisfies: • p(x) = 0 if g(x) ≤ 0 and h(x) = 0 • p(x) > 0 if g(x) ≤  0 or h(x) = 0. The main class of penalty functions for this general problem are of the form: p(x) = m
[max{0, gi (x)}]q + i=1 k
|hi (x)|q , where q ≥ 1. i=1 All of the results of this section extend naturally to problems with equality constraints and for penalty functions of the above form. For example, in the analogous result of Theorem 2.2, it suffices to choose c > ∗ , |v ∗ |, . . . , |v ∗ |}. max{u∗1 , . . . , um 1 k 3 Barrier Methods Definition. A barrier function for P is any function b(x) : n →  that satisfies • b(x) ≥ 0 for all x that satisfy g(x) < 0, and 11 • b(x) → ∞ as limx maxi {gi (x)} → 0. The idea in a barrier method is to dissuade points x from ever approaching the boundary of the feasible region. We consider solving: B(c) : minimize f (x) + 1c b(x) s.t. g(x) < 0, x ∈ n . for a sequence of ck → +∞. Note that the constraints “g(x) < 0” are effectively unimportant in B(c), as they are never binding in B(c). Example: b(x) = m
i=1 1 −gi (x) Suppose g(x) = (x − 4, 1 − x)T , x ∈ 1 . Then b(x) = 1 1 + . 4−x x−1 Let r(c, x) = f (x) + 1c b(x) . Let the sequence {ck } satisfy ck+1 > ck and ck → ∞ as k → ∞. Let xk denote the exact solution to B(ck ) . The following Lemma presents some basic properties of barrier methods. Lemma 3.1 (Barrier Lemma). 1. r(ck , xk ) ≥ r(ck+1 , xk+1 ) 2. b(xk ) ≤ b(xk+1 ) 3. f (xk ) ≥ f (xk+1 ) 12 4. f (x∗ ) ≤ f (xk ) ≤ r(ck , xk ). Proof: 1. r(ck , xk ) = f (xk ) + ≥ f (xk+1 ) + 2. f (xk ) + 1 1 b(xk ) ≥ f (xk ) + b(xk ) ck ck+1 1 ck+1 b(xk+1 ) = r(ck+1 , xk+1 ) 1 1 b(xk ) ≤ f (xk+1 ) + b(xk+1 ) ck ck and f (xk+1 ) + 1 1 b(xk+1 ) ≤ f (xk ) + b(xk ). ck+1 ck+1 Summing and rearranging, we have   1 1 − b(xk ) ≤ ck+1 ck   1 1 − b(xk+1 ). ck ck+1 Since ck < ck+1 , it follows that b(xk+1 ) ≥ b(xk ). 3. From the proof of (1.), f (xk ) + 1 1 b(xk ) ≥ f (xk+1 ) + b(xk+1 ). ck+1 ck+1 But from (2.), b(xk ) ≤ b(xk+1 ). Thus f (xk ) ≥ f (xk+1 ). 4. f (x∗ ) ≤ f (xk ) ≤ f (xk ) + 1 k ck b(x ) 13 = r(ck , xk ). q.e.d. Let N (, x) denote the ball of radius  centered at the point x. The next result concerns convergence of the barrier method. Theorem 3.1 (Barrier Convergence Theorem). Suppose f (x), g(x), and b(x) are continuous functions. Let {xk }, k = 1, . . . , ∞, be a sequence of solutions of B(ck ). Suppose there exists an optimal solution x∗ of P for which N (, x∗ ) ∩ {x | g(x) < 0} =  ∅ for every  > 0 . Then any limit point x̄ of {xk } solves P . Proof: Let x̄ be any limit point of the sequence {xk }. From the continuity of f (x) and g(x), limk→∞ f (xk ) = f (¯ x) and limk→∞ g(xk ) = g(¯ x) ≤ 0. Thus x̄ is feasible for P . For any  > 0 , there exists x ˜ such that g(˜ x) < 0 and f (˜ x) ≤ f (x∗ )+. For each k, f (x∗ ) +  + 1 1 b(˜ x) ≥ f (˜ x) + b(˜ x) ≥ r(ck , xk ). ck ck Therefore for k sufficiently large, f (x∗ )+2 ≥ r(ck , xk ), and since r(ck , xk ) ≥ f (x∗ ) from (4.) of the Barrier Lemma, then f (x∗ ) + 2 ≥ lim r(ck , xk ) ≥ f (x∗ ). k→∞ This implies that lim r(ck , xk ) = f (x∗ ). k→∞ We also have f (x∗ ) ≤ f (xk ) ≤ f (xk ) + 1 b(xk ) = r(ck , xk ). ck Taking limits we obtain f (x∗ ) ≤ f (x̄) ≤ f (x∗ ), 14 whereby x̄ is an optimal solution of P . q.e.d. A typical class of barrier functions are: b(x) = m
(−gi (x))−q , where q > 0. i=1 3.1 Karush-Kuhn-Tucker Multipliers in Barrier Methods Let b(x) = γ(g(x)), where γ(y) : m → , and assume that γ(y) is continuously differentiable for all y < 0. Then ∇b(x) = m
∂γ(g(x)) ∂yi i=1 and if xk solves B(ck ), then ∇f (xk ) + ∇f (xk ) + ∇gi (x), 1 k ck ∇b(x ) = 0, that is, m ∂γ(g(xk )) 1
∇gi (xk ) = 0. ck i=1 ∂yi Let us define uki = Then (6) becomes: ∇f (xk ) + 1 ∂γ(g(xk )) . ck ∂yi m
uki ∇gi (xk ) = 0. (6) (7) (8) i=1 Therefore we can interpret the uk as a sort of vector of KarushKuhn-Tucker multipliers. In fact, we have: 15 Lemma 3.2 Let P satisfy the conditions of the Barrier Convergence Theorem. Suppose γ(y) is continuously differentiable and let uk be defined by (7). Then if xk → x ¯ , and x ¯ satisfies the linear independence condition for gradient vectors of active constraints, then uk → u ¯ , where u ¯ is a vector of Karush-Kuhn-Tucker multipliers for the optimal solution x̄ of P . Proof: Let xk → x ¯ and let I = {i | gi (¯ x) = 0} and N = {i | gi (¯ x) < 0}. For all i ∈ N , 1 ∂γ(g(xk )) uki = → 0 as k → ∞, ck ∂yi x) < 0, and since ck → ∞ and gi (xk ) → gi (¯ all i, and k sufficiently large. x)) ∂γ(g(¯ ∂yi is finite. Also uki ≥ 0 for ¯ as k → ∞. Then u ¯ ≥ 0, and u ¯i = 0 for all i ∈ N . Suppose uk → u From the continuity of all functions involved, (8) implies that ∇f (¯ x) + m
u ¯i ∇gi (¯ x) = 0, u ¯ ≥ 0, u ¯T g(¯ x) = 0. i=1 Thus u ¯ is a vector of Kuhn-Tucker multipliers. It remains to show that k ¯ for some unique u. ¯ The proof that uk → u ¯ for some unique u ¯ is u → u exactly as in Lemma 2.2. q.e.d. 4 Exercises 1. Show that the penalty method problem can be formulated as follows: find sup inf {f (x) + cp(x)} . c≥0 x∈X Next show that this problem is equivalent to: find inf sup{f (x) + cp(x)} . x∈X c≥0 16 2. To use a barrier function method, we must find a point x ∈ X that satisfies gi (x) < 0, i = 1, . . . , m. Consider the following procedure for computing such a point: Initialization: Select x1 ∈ X, set k ← 1 Main Iteration: Step 1. Let I := {i | gi (xk ) < 0}. If I = {1, . . . , m}, stop with xk satisfying gi (x) < 0, i = 1, . . . , m. Otherwise, select j ∈ / I and go to Step 2. Step 2. Use a barrier function method to solve the following problem starting from xk : minimizex gj (x) gi (x) ≤ 0 for i ∈ I s.t. x∈X . Let xk+1 be an optimal solution of this problem. If gj (xk+1 ) ≥ 0, stop; there is no solution x satisfying x ∈ X and gi (x) < 0, i = 1, . . . , m. Otherwise, set k ← k + 1 and repeat Step 1. Show that the above procedure stops in at most m main iterations with a point x ∈ X that satisfies gi (x) < 0, i = 1, . . . , m, or with the valid conclusion that no such point exists. 3. Consider the problem to minimize ct x subject to Ax = b and x ≥ 0, where A ∈ m×n and rank(A) = m. Suppose we are given a feasible solution x̄ > 0 and consider the following logarithmic barrier problem parameterized by the barrier parameter : B(θ) : minimizex cT x − θ s.t. n  ln(xj ) j=1 Ax = b x > 0. Let us denote the objective function of B(θ) by fθ (x). 17 (a) Consider the second-order Taylor series approximation of fθ (x) at x = x̄: P T : minimized fθ (¯ x) + ∇fθ (¯ x)T d + 12 dT ∇2 fθ (¯ x)d s.t. Ad = 0 . ¯ denote the n × n diagonal matrix whose diagonal entries Let X are precisely the components of x̄: ⎛ x̄1 ⎜ 0 ¯ := ⎜ X ⎜ .. ⎝ . 0 x̄2 .. . ... ... .. . 0 0 .. . 0 0 . . . x̄n ⎞ ⎟ ⎟ ⎟. ⎠ x)? for ∇2 fθ (¯ x)? Using this notation, what is the formula for ∇fθ (¯ ˆ (b) Derive a closed form solution for the solution d of P T . (c) The standard linear optimization dual problem is given by: D : maximizeπ,s bT π s.t. AT π + s = c s ≥ 0. Now consider the following problem: P R : minimizeπ,s s.t. 1 ¯ θ Xs −e AT π + s = c . Construct a closed form solution (ˆ π, s) ˆ to P R, and show that the direction of part (3b) satisfies: 1 ¯2 sˆ . dˆ = x ¯− X θ 18