Michael H. Veatch - Linear and Convex Optimization

Gordon College

This edition first published 2021

© 2021 by John Wiley and Sons, Inc.

All rights reserved. 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, or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Michael H. Veatch to be identified as the author of this work has been asserted in accordance with law.

Registered Office

John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

Editorial Office

111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty

While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging‐in‐Publication Data

Names: Veatch, Michael H., author. | John Wiley and Sons, Inc., publisher.

Title: Linear and convex optimization : a mathematical approach / Michael

Veatch, Gordon College.

Description: Hoboken, NJ : Wiley, 2021. | Includes index.

Identifiers: LCCN 2020025965 (print) | LCCN 2020025966 (ebook) | ISBN

9781119664048 (cloth) | ISBN 9781119664024 (adobe pdf) | ISBN

9781119664055 (epub)

Subjects: LCSH: Mathematical optimization. | Nonlinear programming. |

Convex functions.

Classification: LCC QA402.5 .V395 2021 (print) | LCC QA402.5 (ebook) |

DDC 519.6–dc23

LC record available at https://lccn.loc.gov/2020025965

LC ebook record available at https://lccn.loc.gov/2020025966

Cover Design: Wiley

Cover Image: © Hybrid_Graphics/Shutterstock

To Dad, who introduced me to operations research, and Christian and Jackie, who were always curious how things worked

This book is about optimization problems that arise in the field of operations research, including linear optimization (continuous and discrete) and convex programming. Linear programming plays a central role because these problems can be solved very efficiently; it also has useful connections with discrete and convex optimization. Convex optimization is not included in many books at this level. However, in the past three decades new algorithms and many new applications have increased interest in convex optimization. Like linear programming, large applied problems can now be solved efficiently and reliably. Conceptually, convex programming fits better with linear programming than with general nonlinear programming.

These types of optimization are also appropriate for this book because they have a clear theory and unifying mathematical principles, much of which is included. The approach taken has three emphases.

1 Modeling is covered through a broad range of applications to fields such as on‐line marketing and inventory management, retail pricing, humanitarian response and rural development, public sector planning, health delivery, finance, manufacturing, service systems, and transportation. Many of these tell the story of successful applications of operations research.

2 A mathematical approach is used to communicate in a concise, unified manner. Matrix notation is introduced early and used extensively. Questions of correctness are not glossed over; the mathematical issues are described and, where the level is appropriate, proofs presented. Connections are made with some other topics in undergraduate mathematics. This approach grew out of my 30 years of teaching these topics to undergraduate mathematics students.

3 The reasoning behind algorithms is presented. Rather than introducing algorithms as arbitrary procedures, whenever possible reasons are given for why one might design such an algorithm. Enough analysis of algorithms is presented to give a basic understanding of complexity of algorithms and what makes an algorithm efficient. Algorithmic thinking is taught, not assumed.

Many introductory operations research textbooks emphasize models and algorithms without justifications and without making use of mathematical language; such books are ill‐suited for mathematics students. On the other hand, texts that treat the subject more mathematically tend to be too advanced and detailed, at the expense of applications. This book seeks a middle ground.

The intended audience is junior and senior mathematics students in a course on optimization or (deterministic) operations research. The background required is a good knowledge of linear algebra and, in a few places, some calculus. These are reviewed in the appendix. The coverage and approach is intentionally kept at an undergraduate level. Material is often organized by depth, so that more advanced topics or approaches appear at the end of sections and chapters and are not needed for continuity. For example, the many ways to speed up the simplex method are saved for the last section of Chapter 9.

In keeping with this audience, the number of different problem types and algorithms is kept to a minimum, emphasizing instead unified approaches and more general problems. In particular, heuristic algorithms are only mentioned briefly. They are used for hard problems and use many different approaches, while this book focuses on problems that have efficient algorithms or at least unified approaches. The goal is to introduce students to optimization, not to be a thorough reference, and to appeal to students who are curious about other uses of mathematics. The many applications in the early chapters make the case that optimization is useful. The latter chapters connect the solution of these problems to the linear algebra and other mathematics that this audience is familiar with.

The book is also specifically written for the instructor who is mathematically trained, not for a specialist in operations research and optimization. The careful treatment of algorithmic thinking and the introduction to complexity of algorithms are intended to assist these instructors. The mathematical style throughout the book should be more accommodating to mathematics professors. It is also intended to support learning objectives more likely to be found in a mathematics department, including why the algorithms are correct and how they use theoretical results such as convexity and duality. Being able to perform an algorithm by hand is not a primary objective; it plays a supporting role to understanding the notation and reasoning of the algorithm. Calculations that are well‐understood by mathematics students, such as solving a linear system or performing row operations, are not elaborated on. The somewhat more advanced material at the end of sections or chapters is also intended to support instructors who are not specialists, allowing them to extend their knowledge and explore the literature.