Stochastic Linear Optimization, and Extensions

Issues in Non-Convex Optimization 1 1 Outline • General Nonlinear Optimization Problem • Optimality Conditions for NLP • Sequential Quadratic Programming (SQP) Method • LOQO: Combining Interior-Point Methods and SQP • Practical Issues in Solving NLP Problems 2 General Nonlinear Optimization Problem NLP: minimizex f (x) s.t. gi (x) = 0, i∈E gi (x) ≤ 0, i∈I x ∈ n , where f (x) : n →  , gi (x) : n →  , i ∈ E ∪ I, E denotes the indices of the equality constraints, and I denotes the indices of the inequality constraints. 2.1 General Comments Non-convex optimization problems arise in just about every economic and scientific domain: • radiation therapy • engineering product design • economics: Nash equilibria • finance: options pricing 2 • industrial engineering: traffic equilibria, supply chain management • many other domains as well Non-convex optimization is hard. Since x − x2 = 0 if and only if x ∈ {0, 1}, we can formulate binary integer optimization as the following nonlinear optimization instance: cT x BIP: minimizex Ax ≤ b s.t. xj − x2j = 0, j = 1, . . . , n x ∈ n 2.2 Useful Definitions The feasible region F of NLP is the set F = {x | gi (x) = 0 for i ∈ E, gi (x) ≤ 0 for i ∈ I} We have the following definitions of local/global, strict/non-strict minima/maxima. ¯ ∈ F is a local minimum of NLP if there exists
> 0 such Definition 2.1 x that f (¯ x) ≤ f (x) for all x ∈ B(¯ x,
) ∩ F. Definition 2.2 x ¯ ∈ F is a global minimum of NLP if f (¯ x) ≤ f (x) for all x ∈ F. Definition 2.3 x ¯ ∈ F is a strict local minimum of NLP if there exists
> 0 such that f (¯ x) < f (x) for all x ∈ B(¯ x,
) ∩ F, x = x. ¯ Definition 2.4 x ¯ ∈ F is a strict global minimum of NLP if f (¯ x) < f (x) for all x ∈ F, x = x. ¯ 3 Definition 2.5 x ¯ ∈ F is a local maximum of NLP if there exists
> 0 x) ≥ f (x) for all x ∈ B(¯ such that f (¯ x,
) ∩ F. Definition 2.6 x ¯ ∈ F is a global maximum of NLP if f (¯ x) ≥ f (x) for all x ∈ F. Definition 2.7 x ¯ ∈ F is a strict local maximum of NLP if there exists x) > f (x) for all x ∈ B(¯ ¯
> 0 such that f (¯ x,
) ∩ F, x = x. Definition 2.8 x ¯ ∈ F is a strict global maximum of NLP if f (¯ x) > f (x) for all x ∈ F, x = x. ¯ If x is feasible for NLP, we let I(x) denote the indices of the active inequality constraints, namely: I(x) := {i ∈ I | gi (x) = 0} . 3 Optimality Conditions for NLP Theorem: Karush-Kuhn-Tucker Necessary Conditions. Suppose that f (x) and gi (x), i ∈ E ∪ I, are all differentiable functions. Under mild additional conditions, if x̄ is a local minimum of NLP, then there exists ȳ for which
(i) ∇f (¯ x) + (ii) gi (x̄) = 0, i ∈ E i∈E ȳi ∇gi (¯ x) + (iii) gi (x̄) ≤ 0, i ∈ I (iv) y¯i ≥ 0, i ∈ I (v) ȳi · gi (x̄) = 0, i ∈ I . q.e.d. 4
i∈I x) = 0 ȳi ∇gi (¯ In the absence of convexity, a KKT point can be a global minimum, a local minimum, a “saddlepoint”, or even a local or global maximum. In order to develop sufficient conditions for a KKT point to be a local minimum, we need to work with the Lagrangian function associated with NLP, namely: L(x, y) := f (x) +  yi gi (x) + i∈E  yi gi (x) . i∈I We write ∇2 f (x) for the Hessian matrix of f (x) and we write ∇2x,x L(x, y) for the Hessian matrix of L(x, y) with respect to the x variables, namely: ∇2x,x L(x, y) = ∇2 f (x) +  yi ∇2 gi (x) + i∈E  yi ∇2 gi (x) . (1) i∈I We also need to work with the “cone of tangents” K(x) of a feasible point x, defined as: K(x) := {d | ∇gi (x)T d = 0 for i ∈ E, ∇gi (x)T d ≤ 0 for i ∈ I(x)} . Theorem: Karush-Kuhn-Tucker Sufficient Conditions. Suppose that f (x) and gi (x), i ∈ E ∪ I, are all twice-differentiable functions. Suppose that (¯ x, y) ¯ satisfy the following conditions:
(i) ∇f (¯ x) + (ii) gi (x̄) = 0, i ∈ E i∈E ȳi ∇gi (¯ x) +
i∈I ȳi ∇gi (¯ x) = 0 (iii) gi (x̄) ≤ 0, i ∈ I (iv) ȳi ≥ 0, i ∈ I (v) ȳi · gi (x̄) = 0, i ∈ I (vi) x, y) ¯ d > 0 for d ∈ K(¯ x), d = 0 . dT ∇2x,x L(¯   5 Then x̄ is strict local minimum of NLP. q.e.d. 3.1 Algorithm Issues • It is rare that an algorithm for NLP will compute a global minimum. • It is more usual for an algorithm to try to compute a local minimum, or at least to try to compute a KKT point. • Most algorithms will achieve these goals “in the limit”, in the sense that they generate a sequence which would converge to such a point if allowed to compute an infinite number of iterations. Here is a quick overview of various types of algorithms that you have learned about already: • Gradient-type methods – steepest descent – subgradient method – Frank-Wolfe (conditional gradient) method – conjugate gradient and/or conjugate directions methods These methods have low computational requirements at each iteration (few computations and little memory per iteration), but the convergence rates of these methods are at best linear, sometimes not even linear. • Newton-type methods These methods have higher computational requirements at each iteration (much more computations and more memory per iteration), but convergence rates of these methods are usually locally quadratic. • Interior-Point Methods These methods are best suited for convex optimization, but perform remarkably well on non-convex optimization as well. They usually have local quadratic convergence rates. 6 4 Sequential Quadratic Programming (SQP) Method We consider the general nonlinear optimization problem: f (x) NLP: minimizex s.t. gi (x) = 0, i∈E gi (x) ≤ 0, i∈I x ∈ n . The KKT conditions for this problem are that there exists (¯ x, y) ¯ for which the following hold:
ȳi ∇gi (¯ x) + (i) ∇f (¯ x) + (ii) gi (x̄) = 0, i ∈ E i∈E
i∈I x) = 0 ȳi ∇gi (¯ (iii) gi (x̄) ≤ 0, i ∈ I (iv) y¯i ≥ 0, i ∈ I (v) ȳi · gi (x̄) = 0, i ∈ I The Lagrangian function associated with this problem is: L(x, y) := f (x) +  yi gi (x) + i∈E 4.1  yi gi (x) . i∈I First Key Idea of SQP Method: Solution of a Quadratic Problem with Primal and Dual Information Suppose we have current iterate values x ¯ of the primal variables x and current iterate values ȳ of the multipliers y. We can build a quadratic programming programming instance as follows. First, we use the secondorder (quadratic) Taylor approximation of the objective function f (x) at x̄: 7 f (¯ x + ∆x) ≈ f (¯ x) + ∇f (¯ x)T (∆x) + 12 (∆x)T ∇2 f (¯ x)(∆x) . (2) Second, we can replace the nonlinear constraints by their local linear approximation, and we obtain: x)T (∆x) + 12 (∆x)T ∇2 f (¯ x)(∆x) QPx¯ : minimize∆x ∇f (¯ s.t. x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E gi (¯ x) + ∇gi (¯ x)T (∆x) ≤ 0, i ∈ I gi (¯ (3) ∆x ∈ n . However, this problem makes no use of the current values ȳ of the multipliers y. Instead of using the Hessian of the original objective function ∇2 f (x̄) in forming the objective function of the QP, SQP methods use the Hessian of the Lagrangian function: x, ȳ) = ∇2 f (¯ x) + ∇2x,x L(¯  ȳi ∇2 gi (¯ x) + i∈E  ȳi ∇2 gi (¯ x) . i∈I This yields the following slightly modified QP problem:   x)T (∆x) + 12 (∆x)T ∇2x,x L(¯ x, ȳ) (∆x) QPx,ȳ ¯ : minimize∆x ∇f (¯ s.t. x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E gi (¯ x) + ∇gi (¯ x)T (∆x) ≤ 0, i ∈ I gi (¯ (4) ∆x ∈ n . This problem is an “ordinary” quadratic problem (quadratic objective function and linear constraints). We can solve this problem and obtain ∆x 8 as the primal solution and ỹ as the dual multipliers on the constraints. We then set: ∆y := y˜ − y¯ . In this way we use (¯ x, y) ¯ to create directions (∆x, ∆y). 4.2 Second Key Idea of SQP Method: Merit Function to Measure Progress Our current iterate is (¯ x, y) ¯ and we have computed the direction (∆x, ∆y) from the solution of the quadratic program QPx,¯ ¯ y . We compute the new iterate values x, ȳ) ← (¯ ¯ (¯ x, y) ¯ + α(∆x, ∆y) using a step-size ᾱ. The typical method for choosing the step-size is to use a “merit function” that rewards improving the value of the original objective function f (x) and penalizes for the extent of infeasibility. The most common general merit function is of the form: P (x) := f (x) +  ρi |gi (x)| + i∈E  ρi max{gi (x), 0} , i∈I ¯ is where the penalty parameters ρi , i ∈ E ∪ I, are user-specified. Thus α computed using: x + α∆x) . α ¯ := arg min P (¯ α∈[0,1] 4.3 General SQP Framework The general algorithmic framework for the SQP method is as follows: Step 1: Current Iterate. We have current iterate values x̄ of the primal variables x and current iterate values ȳ of the multipliers y. Step 2: Construct Quadratic Problem. Use (¯ x, y) ¯ to construct as in (4). the quadratic program QPx,¯ ¯y Step 3: Solve Quadratic Problem and Construct (∆x, ∆y). Solve the quadratic problem QPx̄,ȳ and obtain primal solution ∆x and (dual) multipliers y. ˜ Set ∆y = y˜ − ȳ. 9 Step 4: Compute Step-size and Update. Compute x + α∆x) . α ¯ := arg min P (¯ α∈[0,1] Update iterate values (¯ x, y) ¯ ← (¯ x, ȳ) + α(∆x, ¯ ∆y). Go to Step 2. In some versions of the SQP method, the matrix ∇2x,x L(¯ x, ȳ) is not computed exactly at each iteration. Instead, we work with an approximation x, ȳ) at each iteration, and B(¯ x, y) ¯ is “updated” from itB(¯ x, y) ¯ of ∇2x,x L(¯ eration to iteration by simple rules and formulas that do not require much extra computation. 4.4 Where Does QPx̄,ȳ Come From? Herein we attempt to give some more insight/understanding regarding the choice of the quadratic program QPx,¯ ¯ y and the resulting direction (∆x, ∆y). We will present an alternative derivation of the direction (∆x, ∆y) that shows how it arises from considerations of Newton’s method applied to a KKT system related to the original problem. It is best for starters to assume that our problem only has equality constraints: f (x) ENLP: minimizex gi (x) = 0, s.t. i∈E (5) x ∈ n . Then QPx,¯ ¯ y for this problem is exactly: x)T (∆x) + 12 (∆x)T ∇2x,x L(¯ x, y)(∆x) ¯ QPx,ȳ ¯ : minimize∆x ∇f (¯ s.t. x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E gi (¯ (6) ∆x ∈ n . Let y˜ denote the multipliers on the equality constraints. Because this quadratic problem has no inequalities, we can use (1) to write the KKT conditions of this system as: 10  ∇f (¯ x) + ∇2 f (¯ x) +   y¯i ∇ gi (¯ x) (∆x) + 2 i∈E x) + ∇gi gi (¯ (¯ x)T (∆x)  ỹi ∇gi (¯ x) = 0 i∈E (7) = 0, i ∈ E , Now let ∆y = ỹ − ȳ and substitute:  x) + ∇f (¯ x) + ∇2 f (¯   y¯i ∇2 gi (¯ x) (∆x) + i∈E  (¯ yi + ∆yi ) ∇gi (¯ x) = 0 i∈E x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E . gi (¯ (8) Then the solution (∆x, ∆y) of (8) is the SQP direction. We now show how the system of equations (8) in (∆x, ∆y) arises from Newton’s method applied to the KKT system of the original problem. The KKT conditions for problem ENLP are: KKT : ∇f (x) +  yi ∇gi (x) = 0 i∈E (9) gi (x) = 0, i ∈ E . Our current point is (x, y) = (¯ x, y), ¯ and let us consider moving in the x+∆x, ȳ+∆y). We would like (¯ direction (∆x, ∆y) to a point (¯ x+∆x, ȳ+∆y) to satisfy the KKT conditions for the problem ENLP, namely: KKT : ∇f (¯ x + ∆x) +  (¯ yi + ∆yi )∇gi (¯ x + ∆x) = 0 i∈E (10) gi (x̄ + ∆x) = 0, i ∈ E . Replacing each of the nonlinear terms with their linear approximations yields: 11 ∇f (¯ x) + ∇2 f (¯ x)(∆x) +    (¯ yi + ∆yi ) ∇gi (¯ x) + ∇2 gi (¯ x)(∆x) = 0 i∈E x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E . gi (¯ (11) Finally, we delete the second-order terms “∆yi ∇2 gi (x̄)(∆x)” and rearrange the layout to yield the following completely linear system in (∆x, ∆y):  ∇f (¯ x) + ∇2 f (¯ x) +   y¯i ∇ gi (¯ x) ∆x + 2 i∈E  (¯ yi + ∆yi )∇gi (¯ x) = 0 i∈E x) + ∇gi (¯ x)T (∆x) = 0, i ∈ E . gi (¯ (12) This is the Newton direction system associated with the original KKT conditions (9) for ENLP at (¯ x, y). ¯ Now notice that the equation system (12) is a rearranged version the system (8), and so the solution (∆x, ∆y) of (12) and (8) are the same. Here we have shown that the SQP direction (∆x, ∆y) is the Newton direction for the KKT system for ENLP at (¯ x, y). ¯ 5 LOQO: Combining Interior-Point Methods and SQP The software LOQO has been developed by Professors Robert Vanderbei and David Shanno primarily over the last ten years. LOQO combines ideas from SQP and interior-point methods. Herein we describe the more salient features of the LOQO algorithm methodology. For this section it will be convenient to restrict our discussion to NLP problems with inequality constraints only, namely: 12 INLP: minimizex f (x) gi (x) ≤ 0, s.t. i∈I (13) x ∈ n . This problem is then converted to equality form by explicitly adding slack variables s and a logarithmic barrier function: BNLPµ : minimizex f (x) − µ s.t.
i∈I ln(si ) g(x) + s = 0 (14) x ∈ n , s > 0. where g(x) := (g1 (x), . . . , gm (x)) . We then form the Lagrangian for this problem by assigning (dual) multipliers y to the constraints: L(x, s, y) = f (x) − µ  ln(si ) + y T (g(x) + s) . i∈I The KKT conditions for the problem BNLPµ are: ∇f (x) + y T ∇g(x) = 0 −µS −1 e + y = 0 (15) g(x) + s = 0 , which we re-write equivalently as: ∇f (x) + y T ∇g(x) = 0 −µe + SY e = 0 g(x) + s = 0 , 13 (16) Given iterate values (¯ x, s, ¯ y), ¯ the Newton equations for the above KKT system are:     ∇2 f (¯ x) +  ȳi ∇2 gi (¯ x) i∈I 0 ∇g(¯ x) 0 (∇g(¯ x))T Y¯ I S¯ 0      −∇f (¯ x) − ȳ T ∇g(¯ x)  ∆x ¯¯e   ∆s  =   , µe − SY  ∆y −g(x̄) − s̄ (17) which using (1) is the same as:  ∇2x,x L(¯ x, y) ¯ 0  0 Y¯ x) I ∇g(¯     (∇g(¯ x))T ∆x −∇f (¯ x) − ȳ T ∇g(¯ x) ¯¯e ¯      . (18) ∆s = µe − SY S −g(¯ x) − s̄ 0 ∆y This system is essentially the same as an SQP system with the addition of logarthmic barrier function. LOQO solves this system at each iteration to obtain the iterate direction (∆x, ∆s, ∆y). LOQO then updates the iterates using a step-size ᾱ by computing: (¯ x, s, ¯ y) ¯ ← (¯ x, s, ¯ y) ¯ + α(∆x, ¯ ∆s, ∆y) . Here ᾱ is chosen to minimize the following merit function: Pµ,ρ (x, s) = f (x) − µ  ln(si ) + ρg(x) + s2 . i∈I A more complete description of LOQO’s algorithm methodology can be found in the following article: “An interior point algorithm for nonconvex nonlinear programming” by R. Vanderbei and D. Shanno, Computational Optimization and Applications 13 (1999), pp. 231-252. 6 6.1 Illustration of Practical Issues in Solving NLP Problems Illustration I: A Simple Covering Problem Consider the problem of determining the smallest disk that contains the m given points c1 , . . . , cm . The decision variables in the problem are the center 14 x and the radius R of the containing disk. The problem has the simple formulation: CDP1 : minimizex,R R s.t. x − ci  ≤ R, i = 1, . . . , m x ∈ n , R ∈  , where in this case n = 2 is the dimension in which the problem arises. As written the problem is convex but non-differentiable. Why might this be a problem for a solver? 6.1.1 Reformulations We explore several different reformulations of the simple covering problem CDP1. We use these reformulations to become familiar with syntax and construction in Ampl (and LOQO). We attempt to solve the non-differentiable formulation of the problem as a means to explore some of the tricks and art that is necessary when we attempt to tackle non-convex problems. The original simple covering problem can be reformulated in several ways. For example, if we square the non-differentiable constraint function and recognize that minimizing R is the same as minimizing R2 , we obtain: CDP2 : minimizex,R R (or R2 ) s.t. xT x − 2xT ci + cTi ci ≤ R2 , i = 1, . . . , m R≥0 x ∈ n , R ∈  , If we let δ = R2 , we obtain a reformulation of the problem with a linear objective function and a quadratic constraint function: CDP3 : minimizex,δ δ s.t. xT x − 2xT ci + cTi ci − δ ≤ 0 i = 1, . . . , m x ∈ n , δ ∈  , If we let α = xT x − δ in CDP3, we obtain a reformulation of the problem with a quadratic objective and a linear constraints: CDP4 : minimizex,α xT x − α s.t. α − 2xT ci + cTi ci ≤ 0 i = 1, . . . , m x ∈ n , α ∈  , 15 6.1.2 Solving CDP We now explore the solution of the various formulations of the Simple Covering Problem using Ampl with LOQO. We used several very contrived data sets in order to explore and understand the behavior of the solution methods, and then we solved the problem using more realistic data sets. The data sets we used are listed in Table 1 and are shown in Figures 1, 2, 3, 4, and 5. Data Set Cover1.dat Cover2.dat Cover3.dat Cover4.dat Cover5.dat Description 10 × 10 grid of points random distribution of set of points 10 × 9 grid with 10 outliers roughly 10 × 9 grid with 10 points near center 10 × 9 grid with 10 points near center Table 1: Data sets for the Simple Covering Problem. • The Ampl file CDPlqnc.mod is the original formulation (CDP1) of the packing problem. Try running this problem in Ampl with the data file cover1.dat. You should find that it does not solve. Why? • The Ampl file CDPql.mod contains the formulation CDP4 (quadratic objective and linear constraints) version of the problem. CDPql2.mod contains the same formulation as CDPql.mod but demonstrates the problem command in Ampl. The Ampl file CDPlq.mod contains the formulation CDP3 (linear objective and quadratic constraints) version of the problem. All of these formulations of the problem solve very rapidly, with zero duality gap. – Experiment1: Solve CDPql2.mod with the LOQO convex option turned on and off. Is there a difference? If so, why? – Experiment2: Solve CDPlq.mod with the LOQO convex option turned on and off. Is there a difference? If so, why? • The Ampl file CDPlqnc2.mod “solves” the original formulation CDP1. However, we first pre-solve the problem with one of the differentiable 16 formulations and then use this solution, modified slightly, as the starting point for the non-differentiable problem CDP1. The non-differentiable problem now solves. What does this suggest? data: cover1.dat Center: (5.5 5.5). Radius : 6.364 10 8 y 6 4 2 0 −2 0 2 4 6 8 10 12 x Figure 1: Data Set Cover1.dat 6.2 Illustration II: The Partial Covering Problem Consider the following variation of the simple covering problem CDP, where we would like to find the smallest disk that contains 90% of the points. This problem is called the Partial Covering Problem. It arises in data mining, for example. The partial covering problem can be formulated as the following mixed integer problem: 17 data: cover2.dat Center: (5.1 4.7). Radius : 5.9548 10 8 y 6 4 2 0 −2 0 2 4 6 8 10 12 x Figure 2: Data Set Cover2.dat data: cover3.dat Center: (10.5 10.5). Radius : 13.435 20 y 15 10 5 0 −5 0 5 10 x 15 20 Figure 3: Data Set Cover3.dat 18 25 data: cover4.dat Center: (5.3 5.3). Radius : 5.4203 10 9 8 7 y 6 5 4 3 2 1 0 0 2 4 6 8 10 12 x Figure 4: Data Set Cover4.dat data: cover5.dat Center: (5.5 5). Radius : 6.0208 10 8 y 6 4 2 0 −2 0 2 4 6 8 10 x Figure 5: Data Set Cover5.dat 19 12 IPCP : minimizex,R,y,s R s.t. x − ci  ≤ R + si si ≤ Cyi m
i=1 i = 1, . . . , m i = 1, . . . , m yi ≤ 0.1m x ∈ n , R ∈ , s ≥ 0, s ∈ m yi ∈ {0, 1}, i = 1, . . . , m . Here C is chosen beforehand as a large constant. In this formulation the nonnegative variable si is used to relax the constraint that forces ci to be covered. The binary variable yi is then turned on (si ≤ Cyi ) and the constraint m
i=1 yi ≤ 0.1m allows at most 10% of the points to be un-covered. This model should not be easy to solve. Why? 6.2.1 Reformulation of Partial Covering Problem using the Sigmoid Function We use the sigmoid function: fα (s) := 1 1 + e−αs to replace the integer variables yi and the constraints “si ≤ Cyi ” in the model. The sigmoid function with parameter α > 0 has the following attractive properties: fα (s) → 0 as s → −∞. fα (s) → 1 as s → +∞. 1 − fα (s) = fα (−s). fα (0) = 12 . A graph of this function is shown in Figure 6. Note that if α is chosen sufficient large, then the shape of fα (s) is almost the step function with step at s = 0. 20 Figure 6: The sigmoid function. Using the sigmoid function, our problem can be approximated as the following smooth nonlinear non-convex problem: NPCP : minimizex,R,s R s.t. x − ci  ≤ R + si m
i=1 i = 1, . . . , m fα (si ) ≤ 0.1m x ∈ n , R ∈ , s ∈ m . 6.2.2 Another Reformulation Here we explore a reformulation of NPCP. (You are asked to develop other reformulations in the homework assignment.) If we square the non-differentiable constraint functions and recognize that minimizing R is the same as minimizing R2 , we obtain: NPCP2 : minimizex,R,s R (or R2 ) s.t. xT x − 2xT ci + cTi ci ≤ R2 + 2Rsi + s2i i = 1, . . . , m m
i=1 fα (si ) ≤ 0.1m R≥0 x ∈ n , R ∈ , s ∈ m . The Ampl file CDPlqsig1.mod contains this formulation of the packing problem. 21 6.2.3 Solutions of the Partial Covering Problem We solved the Partial Covering Problem using data sets Cover1.dat and Cover3.dat. Table 2 shows results of computational experiments with Cover1.dat for the 90% partial covering problem. Table 3 shows results of solving the 90% partial covering problem on the data set Cover3.dat. Table 4 shows results of solving the 89% partial covering problem on the data set Cover3.dat. As Table 2 shows, we were able to select an appropriate value of α that worked rather well for Cover1.dat. Notice the sensitivity to the sigmoid smoothing parameter α. The larger that α becomes the more difficult the problem is to solve to a small duality gap. Why might this be so? For the data set Cover3.dat, Table 3 shows clearly that there does not appear to be a reasonable combination of α and starting point (x01 , x02 ) for which the algorithm works well. Notice that even if we initialize the solver at the known solution the problem (x01 = 5.5, x02 = 5.0), the algorithm still moves to a non-global local optimum in all cases. Table 4 shows computational results on data set Cover3.dat as the covering percentage is lowered from 90% to 89%. With this 1% relaxation we find that the value of the computed solution is mostly immune to initial conditions for small values of α (large values of α continue to make the problem hard to solve), and for α = 10 the problem appears to be very insensitive to initial conditions. Initial Values α x01 x02 R0 Iterations 5 5.5 5.5 6.634 114 6 5.5 5.5 6.634 79 6.5 5.5 5.5 6.634 1,000 7 5.5 5.5 6.634 1,000 10 5.5 5.5 6.634 1,000 20 5.5 5.5 6.634 1,000 50 5.5 5.5 6.634 1,000 100 5.5 5.5 6.634 1,000 200 5.5 5.5 6.634 1,000 Ideal Solution from Cover4.dat at 100%: x∗1 5.50 5.50 5.40 5.41 5.31 5.31 5.60 5.39 5.48 5.30 x∗2 5.50 5.50 5.43 5.35 5.33 5.32 5.59 5.47 5.43 5.30 Solution Values LOQO LOQO LOQO Primal Dual Duality Value Value Gap (%) 5.60 5.60 0.00 5.58 5.58 0.00 5.58 5.59 0.11 5.58 5.60 0.39 5.59 5.68 1.76 5.59 5.67 1.34 5.64 5.91 4.71 5.63 5.10 -9.51 5.66 5.06 -10.59 5.42 Actual Primal Gap (%) 3.27 3.03 2.99 2.98 3.04 3.14 4.13 3.89 4.40 Table 2: Solution of the 90% Partial Covering Problem Model CDP2 using LOQO for the data set Cover1.dat. 22 Initial Values α 7 7 7 7 7 7 7 7 10 10 10 10 10 10 10 10 20 20 20 20 20 30 Ideal x01 x02 5.5 5.5 5 5.5 5.5 5 0 0 10.5 10.5 5.5 5.5 5.5 5 1 1 5.5 5.5 5 5.5 5.5 5 0 0 10.5 10.5 5.5 5.5 5.5 5 1 1 5.5 5.5 0 0 10.5 10.5 5.5 5 1 1 1 1 Solution from R0 Iterations 6.364 1000.00 6.364 1000.00 6.364 1000.00 6.364 78.00 13.435 1000.00 0 1000.00 6.0208 1000.00 0 1000.00 6.364 1000.00 6.364 1000.00 6.364 1000.00 6.364 1000.00 13.435 1000.00 0 1000.00 6.0208 1000.00 0 1000.00 6.364 1000.00 6.364 1000.00 13.435 1000.00 6.0208 1000.00 0 1000.00 0 1000.00 Cover5.dat at 100%: x∗1 5.50 5.50 5.33 11.36 5.50 11.31 5.66 5.50 5.50 5.50 9.87 5.46 5.50 5.50 5.38 5.70 9.89 -3.74 11.87 >> 0 5.40 -23.34 5.50 x∗2 5.00 5.00 4.77 11.36 5.00 11.21 5.18 5.00 5.00 5.00 9.79 5.04 5.00 5.00 4.96 5.29 10.26 -2.78 12.43 << 0 4.88 -21.76 5.00 Solution Values LOQO LOQO LOQO Primal Dual Duality Value Value Gap (%) 8.34 8.48 1.68 8.33 8.47 1.69 10.87 >> 0 12.52 12.52 0.00 8.32 8.47 1.69 12.86 10.54 -22.00 10.28 >> 0 8.36 8.50 1.68 8.63 8.73 1.15 8.40 8.50 1.18 13.61 >> 0 9.04 5.61 -61.25 7.67 7.77 1.29 7.67 7.77 1.29 7.82 >> 0 15.91 >> 0 12.58 >> 0 28.17 >> 0 11.98 >> 0 99.99 >> 0 >> 0 6.51 >> 0 99.94 36.23 >> 0 6.0208 Actual Primal Gap (%) 38.50 38.31 80.61 107.87 38.24 113.58 70.68 38.80 43.33 39.52 126.06 50.22 27.39 27.35 29.87 164.26 108.92 367.85 98.93 8.06 501.74 Table 3: Solution of the 90% Partial Covering Problem Model CDP2 using LOQO for the data set Cover3.dat. What might be a better reformulation of PCP? You will be asked to propose and solve an alternative formulation and in your homework assignment. 6.3 Illustration III: A Packing Problem Consider the problem of packing a variety of wires of various radii into a cable. The m wires have given radii r1 , r2 , . . . , rm . We would like to determine the minimum width of a cable that will be used to enclose the wires. We can conceptualize this problem by considering a cross-section of the cable. The decision variables in the problem are the centers x1 , . . . , xm of m disks of radii r1 , . . . , rm , and the radius R of the disk that is the cross23 Initial Values α 7 10 15 20 30 7 10 15 20 7 10 15 7 10 15 Ideal x01 x02 10.5 10.5 10.5 10.5 10.5 10.5 10.5 10.5 10.5 10.5 5.5 5.5 5.5 5.5 5.5 5.5 5.5 5.5 1 1 1 1 1 1 0 0 0 0 0 0 Solution from R0 Iterations 13.435 52.00 13.435 69.00 13.435 109.00 13.435 84.00 13.435 1000.00 6.634 48.00 6.634 146.00 6.634 1000.00 6.634 1000.00 0 128.00 0 94.00 0 1000.00 0 177.00 0 183.00 0 121.00 Cover5.dat at 100%: x∗1 5.50 5.50 5.50 11.42 11.84 5.50 5.50 9.69 9.78 5.50 5.50 1.67 5.50 5.50 11.43 5.50 x∗2 5.00 5.00 5.00 11.42 11.07 5.00 5.00 10.15 10.10 5.00 5.00 2.46 5.00 5.00 11.43 5.00 Solution Values LOQO LOQO LOQO Primal Dual Duality Value Value Gap (%) 6.18 6.18 0.00 6.13 6.13 0.00 6.09 6.09 0.00 12.29 12.29 0.00 12.29 12.25 -0.34 6.18 6.18 0.00 6.13 6.13 0.00 12.70 << 0 12.81 << 0 6.18 6.18 0.00 6.13 6.13 0.00 -0.01 >> 0 6.18 6.18 0.00 6.13 6.13 0.00 12.32 12.32 0.00 6.0208 Actual Primal Gap (%) 2.69 1.83 1.22 104.08 104.14 2.69 1.83 110.95 112.74 2.69 1.83 -100.24 2.69 1.83 104.65 Table 4: Solution of the 89% Partial Covering Problem Model CDP2 using LOQO for the data set Cover3.dat. section of the enclosing cable. This problem has the following formulation: PACK : minimizex1 ,...,xm ,R R s.t. xi − xj  ≥ ri + rj xi  + ri ≤ R x1 , . . . , xm ∈ n , R ∈  , 1≤i