Convex Optimization In Python
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
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...
Earn $8 on a $10 Purchase, and $16 on a $20 Purchase
We pay 80% royalties on purchases of $7.99 or more, and 80% royalties minus a 50 cent flat fee on purchases between $0.99 and $7.98. You earn $8 on a $10 sale, and $16 on a $20 sale. So, if we sell 5000 non-refunded copies of your book 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
