Complementary slackness

These results may be restated to include all constraints by defining the multiplier uj to be zero if gj(x ) previous example uj, the multiplier of the inactive constraint g3, is zero. Then we can say that uj > 0 if g/x ) = c-, and uj = 0 if gj(x ) < Cp thus the product uj gj(x) - cj is zero for all j. This property, that inactive inequality constraints have zero multipliers, is called complementary slackness. Conditions (8.21) and (8.22) then become... 

Any optimal basis for a mathematical programming problem not only must be feasible for the original constraints and satisfy the complementary slackness conditions, but also must be feasible for the equations... 

Ordinarily we would introduce artificial variables and begin using the simplex method to reduce the sum of these variables to zero. However, in order to save space, as well as to demonstrate the effect of the quadratic term in the cost function, we shall start with the basis which was optimal in the linear case just solved. This basis, namely x2, x3, and u2, will of course be feasible for the three original constraints. If we filled out the basis by using vly v2, and v2, the basis would be feasible and there would be no artificial variables. Although at first glance it would appear that the basis x2) x3l u2, vlt v2 and v3 is optimal, this is not true because of the complementary slackness condition, which prohibits having both x2 and v2, or both x3 and v3, in the same basis. 

Since the complementary slackness principle does not allow the use of v2 and v3 in the basis, two artificial variables v 2 and v 3 must be introduced. With this basis, x2, x3, u2, vu v 2, and v 3, the tableau of equations is as given below. Notice that the first three lines come directly from the optimal table of the preceding example. The only changes needed in the second trio of equations are in the x columns. The equation below the double line, which is the sum of the fifth and sixth equations, is simply the expression of the sum of artificial variables v 2 + i/3). We shall use the simplex method to minimize this sum, hopefully until it becomes zero. 

Bringing any of the variables xu uly y2, —y3, vu or v2 into the basis will decrease (v 2 + v 3). However, xlt y2, v2, and v3 are ruled out by the complementary slackness principle, leaving only ux and y3. We know that —y3 will be in the optimal basis, since it is associated with the material balance constraint which is always binding. Hence we choose to bring in — y3, displacing v 3, since... 

Of the three variables 1, Ui, and v2 which would reduce (v 2 + v ) if brought into the basis, only ux can enter without violating the complementary slackness principle Ui displaces v 2, giving the following feasible solution ... 

Conditions in Eq. (3-86), called complementary slackness conditions, state that either the constraint gj(z) = 0 and/or its corresponding multipher p is zero. If constraint gj(z) is zero, it is behaving hke an equality constraint, and its multipher p is exactly the same as a Lagrange multipher for an equahty constraint. If the constraint is... 

Static maximisation conditions (complementary slackness) either ... 

Conditions (49) and (50) are called primal feasibility, conditions (51) and (52) are called dual feasibility, and condition (53) is called complementary slackness. To interpret these results geometrically, it is helpful to rewrite (51) in a more compact notation using gradients. 

Furthermore, an optimal solution to a relaxation (GAJ may not be optimal in (GA) even if it satisfies the relaxed constraints. Since the objective function values in (GA) and (GAJ may differ, complementary slackness conditions... 

In (GA ), the situation is much easier because dualized constraints are equalities. Terms weighted by Vj will be zero at feasible solutions. Thus, no sign restrictions on Lagrange multipliers are needed for a proper relaxation, and complementary slackness is not an issue for (GA) optimahty. 

Observe that the complementary slackness condition, p K u) — fco] = 0, requires p to be zero when the constraint is inactive. Otherwise, p could be zero or greater. 

Note that V L = 0 gives Eqs. (18.21), which are the definitions of the slack variables and need not be expressed in the KKT conditions. Note also that L = 2A.jZ, = 0, and, using Eqs. (18.21), Eqs. (18.26) result. These are the so-called complementary slackness equations. For constraint i, either the residual of the constraint is zero, g, = 0, or the Kuhn-Tucker multiplier is zero, X., = 0, or both are zero that is, when the constraint is inactive (gj > 0), the Kuhn-Tucker multiplier is zero, and when the Kuhn-Tucker multiplier is greater than zero, the constraint must be active (g, = 0). Stated differently, there is slackness in either the constraint or the Kuhn-Tucker multiplier. Finally, it is noted that V c x is the Jacobian matrix of the equality constraints, J x, and V g i is the Jacobian matrix of the inequality constraints, K[x). 

Step b) can be answered by paying careful attention to an economic interpretation of the complementary-slackness (CS) conditions. The goal is to demonstrate that the auction terminates with an allocation and prices that satisfy the CS conditions. We provide an outline of the proof of the properties of /Bundle, focusing on the special case (/Bundle(2)) that prices are still anonymous. See Parkes Ungar [79] for additional details. Let Xi S) = 1 denote that bundle S is allocated to agent /, and let tti denote the maximal payoff to agent i at prices p S). The first important CS condition is ... 

Choosing the dual variables in this way satisfies the complementary-slackness conditions. 

Optimal objective function values of SPP and its dual coincide (when both are well defined). There is also a complementary slackness condition ... 

Design of Combinatorial Auctions complementary slackness means... 

Other ascending auctions that do not fit neatly into our division between primal-dual and lagrangean have also been proposed. Wurman and Wellman [68] propose an iterative auction that allows bids on subsets but uses anonymous, non-linear prices to direct the auction. Bidders submit bids on bundles and using these bids, an instance of CAPl is formulated and solved. Then, another program is solved to impute prices to the bundles allocated that will satisfy a complementary slackness condition. In the next round, bidders must submit a bid that is at least as large as the imputed price of the bundles. 

---