B A Z A R A A GERSTEN • SH Solutions Manual to Accompany E R A L SMITH I • SH E T T Y S olu NONLINEAR tio n s M a n u a PROGR AMMING l to A c c o m p a n y Th eory and Algorithms N O N L I N E A R P R O Th ird Edition G R A M M M O K H TA R S . B A Z A R A A I N G H A N I F D . S H E R A L I C . M . S H E T T Y ISBN 9781118762370 ,!7IB1B8-hgcdha!:t;K;k;K;k E Prepared by HANIF D. SHERALI ditionTh ird JOANNA LELENO 6.000x9.000 6.000x9.000 .322 Pantone 2748C Black ,!7IB1B8-hgcdha! AutoTemplate bazaraa-fm_grid.qxd 6/25/2013 7:08 AM Page i Solutions Manual to Accompany Nonlinear Programming: Theory and Algorithms bazaraa-fm_grid.qxd 6/25/2013 7:08 AM Page ii bazaraa-fm_grid.qxd 6/25/2013 7:08 AM Page iii Solutions Manual to Accompany Nonlinear Programming: Theory and Algorithms Third Edition Mokhtar S. Bazaraa Department of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA Hanif D. Sherali Department of Industrial and Systems Engineering Virginia Polytechnic Institute and State University Blacksburg, VA C. M. Shetty Department of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA Solutions Manual Prepared by: Hanif D. Sherali Joanna M. Leleno Acknowledgment: This work has been partially supported by the National Science Foundation under Grant No. CMMI-0969169. bazaraa-fm_grid.qxd 6/25/2013 7:08 AM Page iv Copyright © 2013 by John Wiley & Sons, Inc. Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved. Published simultaneously in Canada. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission. Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages. For general information on our other products and services please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com. Library of Congress Cataloging-in-Publication Data is available. ISBN 978-1-118-76237-0 10 9 8 7 6 5 4 3 2 1 TABLE OF CONTENTS Chapter 1: Introduction ...................................................................................... 1 1.1, 1.2, 1.4, 1.6, 1.10, 1.13 Chapter 2 Convex Sets ...................................................................................... 4 2.1, 2.2, 2.3, 2.7, 2.8, 2.12, 2.15, 2.21, 2.24, 2.31, 2.42, 2.45, 2.47, 2.49, 2.50, 2.51, 2.52, 2.53, 2.57 Chapter 3: Convex Functions and Generalizations .......................................... 15 3.1, 3.2, 3.3, 3.4, 3.9, 3,10, 3.11, 3.16, 3.18, 3.21, 3.22, 3.26, 3.27, 3.28, 3.31, 3.37, 3.39, 3.40, 3.41, 3.45, 3.48, 3.51, 3.54, 3.56, 3.61, 3.62, 3.63, 3.64, 3.65 Chapter 4: The Fritz John and Karush-Kuhn-Tucker Optimality Conditions .. 29 4.1, 4.4, 4.5, 4.6, 4.7, 4.8, 4.9, 4.10, 4.12, 4.15, 4.27, 4.28, 4.30, 4.31, 4.33, 4.37, 4.41, 4.43 Chapter 5: Constraint Qualifications ................................................................ 46 5.1, 5.12, 5.13, 5.15, 5.20 Chapter 6: Lagrangian Duality and Saddle Point Optimality Conditions ........ 51 6.2, 6.3, 6.4, 6.5, 6.7, 6.8, 6.9, 6.14, 6.15, 6.21, 6.23, 6.27, 6.29, Chapter 7: The Concept of an Algorithm ......................................................... 64 7.1, 7.2, 7.3, 7.6, 7.7, 7.19 Chapter 8: Unconstrained Optimization ........................................................... 69 8.10, 8.11, 8.12, 8.18, 8.19, 8.21, 8.23, 8.27, 8.28, 8.32, 8.35, 8.41, 8.47, 8.51, 8.52 Chapter 9: Penalty and Barrier Functions ........................................................ 88 9.2, 9.7, 9.8, 9.12, 9.13, 9.14, 9.16, 9.19, 9.32 Chapter 10: Methods of Feasible Directions .................................................... 107 10.3, 10.4, 10.9, 1.012, 10.19, 10.20, 10.25, 10.33, 10.36, 10.41, 10.44, 10.47, 10.52 v Chapter 11: Linear Complementary Problem, and Quadratic, Separable, Fractional, and Geometric Programing ........................................ 134 11.1, 11.5, 11.12, 11.18, 11.19, 11.22, 11.23, 11.24, 11.36, 11.41, 11.42, 11.47, 11.48, 11.50, 11.51, 11.52 vi CHAPTER 1: INTRODUCTION 1.1 In the figure below, x and x denote optimal solutions for Part (a) min max and Part (b), respectively. x 2 2 (4, 2) 1 3 2 3 0 2 3 4 x 1 2 xmax 2 xmin Feasible region 1.2 a. The total cost per time unit (day) is to be minimized given the storage limitations, which yields the following model: d Q d Q Minimize f(Q ,Q )  k 1  h 1  k 2  h 2 cd c d 1 2 1Q 1 2 2Q 2 2 1 1 2 2 1 2 subject to sQ  s Q  S 1 1 2 2 Q  0, Q  0. 1 2 Note that the last two terms in the objective function are constant and thus can be ignored while solving this problem. b. Let S denote the lost sales (in each cycle) of product j, j = 1, 2. In j this case, we replace the objective function in Part (a) with F(Q ,Q ,S ,S ), where F(Q ,Q ,S ,S ) = F(Q ,S ) + F (Q ,S ), 1 2 1 2 1 2 1 2 1 1 1 2 2 2 and where d Q2 j j F (Q ,S )  (k c Q  S  PQ ) h , j 1,2. j j j Q  S j j j j j j j 2(Q  S ) j j j j Q  S j j This follows since the cycle time is , and so over some T d j Td j days, the number of cycles is . Moreover, for each cycle, the Q  S j j fixed setup cost is k , the variable production cost is c Q , the lost j j j sales cost is  S , the profit (negative cost) is PQ , and the j j j h Q j j inventory carrying cost is Q ( ). This yields the above total cost 2 j d j function on a daily basis. 1.4 Notation: x : production in period j, j = 1,…,n j d : demand in period j, j = 1,…,n j I : inventory at the end of period j, j = 0, 1,…,n. j The production scheduling problem is to: n Minimize  [f(x )cI ] j j1 j1 subject to x d  I  I for j = 1,…,n j j j1 j I  K for j = 1,…,n–1 j I  0 n x  0, I  0 for j = 1,…,n–1. j j 1.6 Let X denote the set of feasible portfolios. The task is to find an xX such that there does not exist an xX for which ctx  ctx and xt V x  xt V x, with at least one inequality strict. One way to find efficient portfolios is to solve: Maximize {ctx xt V x:x X} 1 2 for different values of (,)  0 such that   1. 1 2 1 2 1.10 Let x and p denote the demand and production levels, respectively, and let Z denote a standard normal random variable. Then we need p to be such that P(p  x 5)  0.01, which by the continuity of the normal random variable is equivalent to P(x  p 5)  0.01. Therefore, p must satisfy 2