Quadratic equality constraints

The vector x can contain slack variables, so the equality constraints (8.33) may contain some constraints that were originally inequalities but have been converted to equalities by inserting slacks. Codes for quadratic programming allow arbitrary upper and lower bounds on x we assume x>0 only for simplicity. 

For problems with only equality constraints, we could simply solve the linear equations (8.66)-(8.67) for (Ax, AX) and iterate. To accommodate both equalities and inequalities, an alternative viewpoint is useful. Consider the quadratic programming problem... 

Illustration 3.2.4 Consider the following convex quadratic problem subject to a linear equality constraint ... 

The objective function /( ) and the inequality constraint g(x) are convex since f(x) is separable quadratic (sum of quadratic terms, each of which is a linear function of xi, x2,X3, respectively) and g(x) is linear. The equality constraint h(x) is linear. The primal problem is also stable since v(0) is finite and the additional stability condition (Lipschitz continuity-like) is satisfied since f(x) is well behaved and the constraints are linear. Hence, the conditions of the strong duality theorem are satisfied. This is why... 

Note that the objective function is convex since it has linear and positive quadratic terms. The only nonlinearities come from the equality constraint. By introducing three new variables w1,w2)w3, and three equalities ... 

Equality constraints are added to the objective function as a quadratic penalty function. Thus, the NBI subproblem is redefined as follows (note that max tn is the same as min -tjv) ... 

A quadratic programming problem minimizes a quadratic function of n variables subject to m linear inequality or equality constraints. A convex QP is the simplest form of a nonlinear programming problem with inequality constraints. A number of practical optimization problems are naturally posed as a QP problem, such as constrained least squares and some model predictive control problems. 

Clearly, the objective function and the second (equality) constraint are nonlinear since they involve quadratic terms. For such problems, a good initial guess is often necessary if Solver is to find a solution. It is sometimes necessary to try several initial guesses before a proper solution can be found. In this case, the initial guess of [0 1 1] was tried. The following spreadsheet shows a setup for this problem ... 

Another method for solving nonlinear programming problems is based on quadratic programming (QP)1. Quadratic programming is an optimization procedure that minimizes a quadratic objective function subject to linear inequality or equality (or both types) of constraints. For example, a quadratic function of two variables x and X2 would be of the general form ... 

The general form of the quadratic penalty function for a problem of the form (8.25)-(8.26) with both equality and inequality constraints is... 

Successive Quadratic Programming (SQP) The above approach to finding the optimum is called a feasible path method, as it attempts at all times to remain feasible with respect to the equality and inequality constraints as it moves to the optimum. A quite different method exists called the Successive Quadratic Programming (SQP) method, which only requires one be feasible at the final solution. Tests that compare the GRG and SQP methods generally favor the SQP method so it has the reputation of being one of the best methods known for nonlinear optimization for the type of problems considered here. 

This theorem implies that the additive Gaussian SIC capacity is independent of Q and is equal to the capacity of the additive Gaussian channel with signal to noise ratio P. The next corollary to this theorem implies that the same capacity equality holds for the additive Gaussian IHS with quadratic mean distortion constraint. 

Corollary 2.5 Define an IHS in the following way The covertext sequence is a realization ofn i.i.d. r.v. distributedQ). The mean distortion constraint is based on the quadratic distortion measure d x,y) = x — s). The attack channel is memoryless and stationary, with output Y = X Y Z, where Z A/ (0, N) is independent of S and of X. Then, the capacity of this IHS is equal to the capacity of the additive Gaussian channel with signal to noise ratio of P (without distortion constraint), i.e. log2(l + ). 

Algorithms for the solution of quadratic programs, such as the Wolfe (1959) algorithm, are very reliable and readily available. Hence, these have been used in preference to the implementation of the Newton-Raphson method. For each iteration, the quadratic objective function is minimized subject to linearized equality and inequality constraints. Clearly, the most computationally expensive step in carrying out an iteration is in the evaluation of the Lapla-cian of the Lagrangian, V xL x , X which is also the Hessian matrix of the La-grangian that is, the matrix of second derivatives with respect to X . 

The augmented Lagrangian method is not the only approach to solving constrained optimization problems, yet a complete discussion of this subject is beyond the scope of this text. We briefly consider a popular, and efficient, class of methods, as it is used by fmincon, sequential quadratic programming (SQP). We wUl find it useful to introduce a common notation for the equality and inequality constraints using slack variables. 

---