Complementary slackness conditions

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. 

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... 

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... 

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. 

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 ... 

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. 

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. 

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 ... 

---