Convex Optimization In Python

Retired

This book is no longer available for sale.

Convex Optimization In Python

Python Implementations For Examples in Textbook, Convex Optimization

About the Book

Preface

The objective of the book is to assist the reader to acquire Python programming experience of the convex optimization theory, by first reproducing the examples and the figures in the textbook ([book-convex-2004][1]) by Python, and then by tuning the model parameters for further understanding the characteristics of the convex problems and their solutions.

These characteristics include,

• The possible variations and restrictions of the convex problems

• The convergence rate

• The uniqueness of the optimal solution,

• The bounds of the optimal value

• The feasibility and infeasibility of the problems

• The challenges in numerical implementations

The reader will also learn how to implement and verify the algorithm through the convex optimization theory by himself. The jupyter noteboks for all the demos have been in the appendix.

The textbook ([book-convex-2004]) has been popularly used in many open courses about convex optimization, including

* Engineering Everywhere open course, https://see.stanford.edu/Course/EE364A

However, many learners from the convex optimization course have been complaining time is pressing to deep dive into the details of the algorithms. This book will help learners catch the essential cruxes of the convex optimization theory without writing the algorithms from the scratch. Readers are encouraged to use this book as the supplementary material to the course.

The content of the book is organized in a series of demos. Each demo is corresponding to an example in the textbook ([book-convex-2004]). The jupyter notebook implementation for each demo is also provided.

Only the examples in the textbook have been implemented; the implementations for the exercises at the end of each chapter in the textbook haven’t been provided. However, readers are encouraged to reuse the demo codes in the book as the baseline, to implement not only the exercises, but also any new idea.

All the source codes in python jupyter notebook can be accessed through the website:

https://wuzhuchun.club:9091/lab/tree/welcome.ipynb

All the demos have been written in jupyter notebooks. Readers are encouraged to run the jupyter notebooks in the JupyterLab server (provided in the above website). The JupyterLab server has already installed the necessary Python libraries. It also has provided the online debugging environment to facilitate interested readers to deep dive into the implementation details.

Have fun!

Author: Edwin Jiang

Hangzhou, China

1 [book-convex-2004] Boyd, S. & Vandenberghe, L., 2004. Convex optimization, Cambridge university press. Download: https://web.stanford.edu/ boyd/cvxbook/bv_cvxbook.pd

About the Author

Edwin JIANG
Edwin JIANG

Edwin Jiang

Career Ambition

To become a certificated algorithm researcher and engineer, to explore the computer algorithm engineering and communication technology to unleash the potential in connecting human with nature. To achieve this ambition, I am reinventing myself in,

  • 1. Optimization theory including but not limited to, linear and convex optimization[1] , meta-heuristic optimization[2][3]
  • 2. Machine Learning[4][5][6][7] and Reinforcement Learning[8][9][10]
  • 3. To apply the optimization theory and ML/AI to wireless communication technology including signal design, transmitter and receiver techniques, resource scheduling algorithm and network architecture evolution

Programming Skills 

  1. Expert in C/C++, MATLAB, Java, Python
  2. Intermediate in LATEX

Table of Contents

  • 8 Unconstrained minimization 3
  • 8.1 Demo: A minimization on a quadratic problem in R2 . . . 4
  • 8.2 Demo: A minimization on a non-quadratic problem in R2 . . . 6
  • 8.3 Demo: A minimization of a log-barrier function . . . 9
  • 8.4 Demo: A minimization of a log-barrier function . . . 9
  • 8.5 Demo: A minimization of a log-barrier function . . . 10
  • 8.6 Demo: The influence to the convergence rate for different α, β for the gradient method applied to log barrier function . . . 10
  • 8.7 Demo: the impact of condition number to the gradient method . . . 11
  • 8.8 Demo: solving the geometric program: Frobenius norm scaling . . . 12
  • 8.9 Demo: the relations between the steepest descent for quadratic norm and the change of coordinate . . . 14
  • 8.10 Demo: Newton’s method on the non-quadratic problem in R2 . . . 16
  • 8.11 Demo: Newton’s method on the log-barrier function in R100 . . . 18
  • 8.12 Demo: An experiment on Newton’s method implementation on an example in R5000 . . . 20
  • 8.13 Demo: An Experiment on Affine Invariance in Newton’s Method . . . 21
  • 8.14 Demo: An Experiment on Convergence Rate on A Family of Self-Concordant Function . . . 22
  • 8.15 Demo: An Experiment on Exploiting the Diagonal plus Low Rank Structure . . . 24
  • 8.16 Demo: An Experiment on Exploiting the Band Structure in Newton Method . . . 26
  • 9 Equality constrained minimization 27
  • 9.1 Demo: Solving Equality Constrained Analytic Center By Infeasible Start Newton Method - I : Feasible and Lower Bounded Problem . . . 28
  • 9.2 Demo: Solving Equality Constrained Analytic Center By Infeasible Start Newton Method - 2 : Infeasible or Unbounded Problem . . . 30
  • 9.3 Demo: Solving Convex-Concave Game via Infeasible Start Newton Method . . . 32
  • 9.4 Demo: Solve KKT System via Block Elimination . . . 34
  • 9.5 Demo: Solve Minimum Length Piecewise-Linear Curve Subject to Equality Constraints . . . 35
  • 9.6 Demo: Further experiments on Solving Minimum Length Piecewise-Linear Curve Subject to Equality Constraints . . . 37
  • 9.7 Demo: Experiments on using Block Elimination on Solving Minimum Length Piecewise-Linear Curve Subject to Equality Constraints . . . 39
  • 9.8 Demo: Experiments on Three Methods in Solving the Equality Constrained Analytic Centering Problem . . . 41
  • 9.9 Demo: Further Readings on Optimal Network Flow . . . 43
  • 9.10 Demo: Solving Analytic Center of a Linear Matrix Equality . . . 46
  • 9.11 Demo: From Newton Method to Riccati Recursion in solving Linear Quadratic Regulator (LQR) 49
  • 10 Interior-point methods 53
  • 10.1 Demo: The Central Path in Inequality form Linear Programming . . . 54
  • 10.2 Demo: An Experiment on Solving Linear Programming in Inequality Form by the Barrier Method . . . 55
  • 10.3 Demo: Solving Geometric Programming by Barrier Method . . . 57
  • 10.4 Demo: Further Experiments on Barrier Method Convergence in Solving the Geometric Programming . . . 59
  • 10.5 Demo: Using Barrier Method to Solve a Family of Standard Form LPs . . . 61
  • 10.6 Demo: Further Experiments on Comparison of Phase I methods . . . 65
  • 10.7 Demo: Further Experiments on Solving A Family of Linear Feasibility Problem by Basic Phase I Method . . . 67
  • 10.8 Demo: Further Experiments on Feasibility Detection Using Infeasible Start Newton Method . 69
  • 10.9 Demo: Further Experiments on Solving SOCP by Barrier Method . . . 70
  • 10.10 Demo: Further Experiments on Solving a Small SDP by Barrier Method . . . 73
  • 10.11 Demo: Further Experiments on Solving a Small SDP by Barrier Method – II (continue.) . . . 75
  • 10.12 Demo: Further Experiments on Solving a Small SDP by Barrier Method – III (continue.) . . . 77
  • 10.13 Demo: Further Experiments on Solving A Family of SDP by Barrier Method . . . 79
  • 10.14 Demo: Further Experiments on Solving A Small Linear Programming by Primal-Dual Interior Point Method . . . 81
  • 10.15 Demo: Further Experiments on Solving Geometric Programming by Primal-Dual Interior-Point Method . . . 83
  • 10.16 Demo: Further Experiments on Solving A Family of LP by Primal-Dual Interior-Point Method 85
  • 10.17 Demo: Further Experiments on Solving A Family of LP by Barrier Method . . . 87
  • 10.18 Demo: Further Experiments on Solving l1-norm approximation by Barrier Method . . . 89

The Leanpub 60 Day 100% Happiness Guarantee

Within 60 days of purchase you can get a 100% refund on any Leanpub purchase, in two clicks.

Now, this is technically risky for us, since you'll have the book or course files either way. But we're so confident in our products and services, and in our authors and readers, that we're happy to offer a full money back guarantee for everything we sell.

You can only find out how good something is by trying it, and because of our 100% money back guarantee there's literally no risk to do so!

So, there's no reason not to click the Add to Cart button, is there?

See full terms...

80% Royalties. Earn $16 on a $20 book.

We pay 80% royalties. That's not a typo: you earn $16 on a $20 sale. If we sell 5000 non-refunded copies of your book or course for $20, you'll earn $80,000.

(Yes, some authors have already earned much more than that on Leanpub.)

In fact, authors have earnedover $13 millionwriting, publishing and selling on Leanpub.

Learn more about writing on Leanpub

Free Updates. DRM Free.

If you buy a Leanpub book, you get free updates for as long as the author updates the book! Many authors use Leanpub to publish their books in-progress, while they are writing them. All readers get free updates, regardless of when they bought the book or how much they paid (including free).

Most Leanpub books are available in PDF (for computers) and EPUB (for phones, tablets and Kindle). The formats that a book includes are shown at the top right corner of this page.

Finally, Leanpub books don't have any DRM copy-protection nonsense, so you can easily read them on any supported device.

Learn more about Leanpub's ebook formats and where to read them

Write and Publish on Leanpub

You can use Leanpub to easily write, publish and sell in-progress and completed ebooks and online courses!

Leanpub is a powerful platform for serious authors, combining a simple, elegant writing and publishing workflow with a store focused on selling in-progress ebooks.

Leanpub is a magical typewriter for authors: just write in plain text, and to publish your ebook, just click a button. (Or, if you are producing your ebook your own way, you can even upload your own PDF and/or EPUB files and then publish with one click!) It really is that easy.

Learn more about writing on Leanpub