Optimization Engineering For Machine Learning and AI

A master class to learn convex optimization for ML and its applications to different fields and areas of engineering

What you'll learn
Convex optimization theory and concepts for machine learning and AI
Engineering mathematics of convex optimization for ML, DL, and AI
Convex optimization methods and techniques in ML, DL, and AI
Convex optimization applications and use cases in engineering fields

Requirements
Basic knowledge of Mathematics
Desire to learn the subject of convex optimization
Description
Optimization is a core fundamental area for machine learning and AI in general. Moreover, Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing or maximizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

In the first lesson/lecture of this course, we will talk about the following points

What is Optimization?

Examples on Optimization

Factors of Optimization

Reliable/Efficient Problems

Goals & Topics of this Course

Brief History on Optimization

=======

In the second lesson/lecture, we will be covering important points on convex sets, which are the following

00:00:00 Affine Combination

00:01:33 Affine Set

00:08:21 Convex Combination

00:09:25 Convex Set

00:13:45 Convex Hull

00:16:28 Example 1-Convex Cones

00:16:55 Conic Combination

00:20:47 Example 2-Hyperplanes

00:24:22 Example 3-Euclidean Ball

00:26:37 Example 4-Ellipsoid

00:30:40 Norms

00:35:51 Example 5-Polyhedra

00:41:18 Example 6-Positive Semidefinite cone

00:54:31 Operations preserving convexity

01:15:10 Closed & Open set

01:21:10 Solid sets

01:26:25 Pointed set

01:26:57 Proper cones

01:27:28 Generalized Inequalities

01:34:12 Minimum & Minimal Elements

01:46:28 Partial Order

01:48:53 Properties of Generalized Inequalities

01:53:09 Dual Cones

02:04:31 Dual Inequalities

=======

In the third lesson/lecture of this course on convex optimization, we will be covering important points on convex functions, which are the following

00:01:14 Definition of Convex Function

00:03:31 Examples of Convex Function

00:13:50 Convexity in Higher Dimensions

00:24:30 First-order Condition

00:27:08 Second-order Conditions

00:35:17 Epigraphs

00:37:25 Jensen's Inequality

00:39:49 Operations preserving Convexity

00:52:21 Conjugate Convex function

01:02:09 Quasi Convex functions

01:11:14 Log-Convex functions

01:16:16 Convexity with respect to generalized inequalities

=======

In Lecture 4 of this course on convex optimization, we will be covering the fundamental principles of convex optimization, which include the following

00:00 Standard form

04:19 Feasible point

05:07 Globally Optimum point

05:50 Locally Optimum point

15:04 Explicit & Implicit constraints

30:10 Optimality criterion for differentiable cost functions

34:48 Supporting Hyperplane

=======

In Lecture 5 of this course on convex optimization, we will be covering Linear Programming and the Simplex algorithm, which was introduced by George Dantzig. The outline of the lecture is as follows

00:00:00 What is a Linear Program (LP) ?

00:07:24 LP feasible set

00:10:22 LP forms

00:10:50 Standard form LP

00:10:50 Standard form LP

00:11:24 Slack variables

00:13:08 Inequality form LP

00:13:34 Omitting inequality constraints

00:20:38 LP Example: The Diet Problem

00:25:49 The SIMPLEX Algorithm: Method and the usage of Non-basic, Slack, and Artificial variables

00:33:59 The SIMPLEX Algorithm - Example: Iteration 0

00:40:37 The SIMPLEX Algorithm - Example: Iteration 1

00:48:18 The SIMPLEX Algorithm - Example: Iteration 2

00:55:27 The SIMPLEX Algorithm - Example: Iteration 3

01:00:13 MATLAB: Implementing SIMPLEX

01:53:15 MATLAB: Verifying with linprog

01:58:48 George Bernard Dantzig

01:59:12 SIMPLEX: Geometric Interpretation

02:01:09 SIMPLEX: Time Complexity

=======

In Lecture 6 of this course on convex optimization, we will cover the essentials of Quadratic Programming.The outline of the lecture is as follows

00:00 Intro

00:32 What is a Quadratic Program (QP) ?

03:24 QP reformulation

06:05 Illustrating the optimal solution

16:54 Solving a QP on MATLAB

25:43 Outro

=======

In Lecture 7 of this course on convex optimization, we will cover the essentials of Quadratically Constrained Quadratic Programs, i.e. QCQPs.The outline of the lecture is as follows

00:00 Intro

00:33 What is a Quadratically Constrained Quadratic Program (QCQP) ?

05:16 QCQP Feasible Set

06:01 MATLAB Illustration of QCQP Feasible Set

13:39 QCQP Application 1: Minimizing a linear function over a centered ellipsoid

30:42 QCQP Application 2: Minimizing a linear function over an uncentered ellipsoid

37:16 QCQP Application 3: Minimizing a quadratic function over a centered ellipsoid

42:36 Outro

=======

In Lecture 8 of this course on convex optimization, we will cover Second Order Cone Programming, i.e. SOCPs. The outline of the lecture is as follows

00:00:00 What is Second Order Cone Programming (SOCP) ?

00:02:37 QCQP as an SOCP

00:20:25 Robust Linear Programming as an SOCP

00:31:06 Linear Programming with Random Constraints as an SOCP

00:41:09 Sum of Norms minimization as an SOCP

00:47:27 Max of Norms minimization as an SOCP

00:49:40 Hyperbolic Constrained Programs as SOCPs

00:58:59 Quadratic Fractional Problems as SOCPs

01:02:16 Outro

==========

In Lecture 9 of this course on convex optimization, we will cover Geometric Programs, i.e. GPs. The outline of the lecture is as follows

00:00 Intro

01:51 Monomials and Posynomials

10:45 GP problem formulation (polynomial form)

19:50 Relevant papers

23:12 GP in convex form

29:27 Example 1: Frobenius Norm Diagonal Scaling

33:25 Example 2: Volume Maximization given aspect ratios and area limitations

38:12 Summary

=====

In Lecture 10 of this course on convex optimization, we will cover Generalized Geometric Programs, i.e. GPs. The outline of the lecture is as follows

00:00 Intro

01:16 Generalized Posynomials

08:46 Generalized Geometric Program (GGP)

09:45 GGP as a GP

17:40 Example 1: Floor Planning (GGP)

23:48 Example 2: Power Control (GP)

33:00 Example 3: Digital Circuit Design (GGP)

37:26 Mixed-Integer Geometric Program

39:27 Outro

======

In Lecture 11 of this course on convex optimization, we will cover Semidefinite programming, i.e. SDPs. The outline of the lecture is as follows

00:00 Intro

01:05 Generalized Inequality Constraints

05:18 Conic Programs

07:59 Linear Matrix Inequality (LMI)

09:56 LMI brief history (Lyapunov, Kalman, Ricatti etc..)

18:10 Semidefinite Programming (SDP)

21:56 SOCP as SDP

29:30 Eigenvalue Minimization

32:43 Matrix Norm Minimization

34:39 Outro

=====

In Lecture 12 of this course on convex optimization, we will cover various topics related to Vector optimization, such as Pareto optimal points and the Pareto frontier, which is a well known boundary studied in Game theory, risk and trade-off analysis, portfolio analysis, etc. The topics covered are outlined as follows

00:00:00 Intro

00:01:55 What is Vector Optimization ?

00:06:38 Optimal points & the set of achievable objective values

00:13:27 Pareto optimal points

00:18:56 BLUE estimator (example)

00:28:09 Scalarization

00:32:03 Pareto Frontier (Boundary)

00:38:28 Minimal Upper Bound on a set of matrices (example)

00:43:36 Plotting a Pareto front of regularized least squares on MATLAB (1st way: the genetic algorithm)

00:47:43 Plotting a Pareto front of regularized least squares on MATLAB (2nd way: using fminsearch)

00:53:43 Multicriterion optimization

01:01:39 Scalarization for Multicriterion optimization

01:06:51 Analytical Pareto Front of Regularized Least Squares

01:09:44 Plotting a Pareto front of regularized least squares on MATLAB (3rd way: Analytically)

01:12:08 Outro

======

In Lecture 13 of this course on convex optimization, we will cover various topics related to Vector optimization, such as Pareto optimal points and the Pareto frontier, which is a well known boundary studied in Game theory, risk and trade-off analysis, portfolio analysis, etc. The topics covered are outlined as follows

00:00 Intro

00:29 Reminder: Multicriterion Optimization

03:17 Multicriterion Optimization: A closer look

09:02 Optimal Trade-off Analysis

12:38 Outro

========

In Lecture 14 of this course on Convex Optimization, we introduce the Lagrangian duality theory. In essence, for each optimization problem (convex or not), we can associate a certain function referred to as the Lagrangian function. This function, in turn, has a dual function (which serves as an infimum over the variable of interest x). It turns out that, for any optimisation problem, the dual function is a lower bound on the optimal value of the optimisation problem in hand. This lecture focuses on many examples that derive the Lagrangian and the associated dual functions. MATLAB implementations are also presented to give useful insights. This lecture is outlined as follows

00:00 Intro

01:00 Lagrangian function and duality

04:02 Lagrangian dual function

06:46 Lower bound on the optimal value

09:16 MATLAB: Lower bound verification

15:28 Example 1 - Least Squares

17:48 Example 2 - Linear Programming

20:48 Example 3 - Two-way Partitioning

26:04 Relationship between conjugate function and the dual function

31:22 Example 4 - Equality Constrained Norm minimization

33:37 Example 5 - Entropy Maximization

35:44 Outro

========

In Lecture 15 of this course on Convex Optimization, we talk about a very very important topic in convex optimisation that is the Lagrange Dual Problem. This lecture is outlined as follows

00:00:00 Intro

00:00:44 Revision: Lagrange Dual Function

00:01:30 The Dual Problem

00:06:54 Example 1: Dual Problem of Standard LP

00:08:59 Example 2: Dual Problem of Inequality LP

00:13:59 Weak Duality

00:16:24 Example 3: The 2-way Partitioning Problem (Revisited)

00:21:42 Strong Duality

00:23:15 Slater’s Condition

00:24:32 What is a Relative Interior (Convex Analysis by Tyrell Rockefellar) ?

00:28:16 Generalization of Slater’s Condition

00:29:26 Example 4: Duality of LS problems

00:38:33 Example 5: Duality of LP problems

00:54:52 Example 6: Duality of QCQP problems

00:59:22 Example 7 : Duality of the Entropy Maximization Problem

01:03:48 Example 8 : Duality of the Trust Region Problem (non-convex problem)

01:11:51 Outro

======

In Lecture 16 of this course on Convex Optimization, we talk about a very practical topic, when it comes to numerical optimization algorithms, and that is the ε-suboptimal inequality, which could report how good of an estimate we have. Said differently, the Lagrangian dual feasible points (λ,ν) provides a proof or certificate of the dual gap.

00:00 Intro

01:59 Lagrangian & Dual Functions

03:40 How good of an estimate ? (Certificate)

07:09 ε-suboptimal

10:09 Stopping Criterion

17:23 Outro

==============

In Lecture 17 of this course on Convex Optimization, we talk about Complementary Slackness, which could be used a test for optimality, or it could even tell us which constraints are active and which are not !!

This lecture is outlined as follows

00:00 Intro

00:46 What is Complementary Slackness ?

08:15 A Genie Example

14:45 Another Genie Example

16:00 Outro

=====

In Lecture 18 of this course on Convex Optimization, we talk about KKT conditions for nonconvex and convex optimization problems.

This lecture is outlined as follows

00:00 Intro

00:57 KKT Conditions for NonConvex Problems

04:32 KKT Conditions for Convex Problems

07:48 Example

10:47 Outro

=======

In Lecture 19 of this course on Convex Optimization, we talk about Perturbation and Sensitivity Analysis of general and convex optimization problems.

This lecture is outlined as follows

00:00 Intro

02:34 Perturbed Optimization Problem

16:33 Global Perturbation Behavior

37:35 Local Perturbation Behavior

49:36 Shadow Price Interpretation

53:40 Outro

=======

In Lecture 20 of this course on Convex Optimization, we talk about Equivalent Reformulations of general and convex optimization problems.

This lecture is outlined as follows

00:00:00 Intro

00:01:46 Reformulation 1: Introducing new variables

00:25:06 Log-Sum-Exponential Cost

00:33:23 Norm Minimization

00:49:39 Reformulation 1 (cont'd): Introducing constraint variables

01:05:11 Reformulation 2: Cost Transformation

01:14:23 Reformulation 3: Constraint Absorption

01:32:05 Summary

========

In Lecture 21 of this course on Convex Optimization, we talk about the theorem of weak alternatives of general optimization problems.

This lecture is outlined as follows

00:00 Introduction

04:02 Feasibility Problem

05:41 Optimization Feasibility Problem

07:55 Dual Function

08:41 Note on Strong Alternatives

10:43 Dual Problem

13:12 Weak Duality

13:41 Relating (S) with (T)

15:16 Weak Alternatives

17:31 Why Weak Alternatives ?

19:33 Summary

23:18 Outro

======

In Lecture 22 of this course on Convex Optimization, we talk about the theorem of strong alternatives of convex optimization problems.

This lecture is outlined as follows

01:43 Introduction

02:13 Strengthening Weak Alternatives

03:21 Strong Alternatives Conditions

08:27 Strict Inequality Case

09:49 Strong Alternatives of Linear Inequalities

13:31 Strong Alternatives of Strict Linear Inequalities

22:46 Strong Alternatives of Intersection of Ellipsoids

34:53 Summary

38:46 Outro

=======

In Lecture 23 of this course on Convex Optimization, we focus on algorithms that solve unconstrained minimization type problems. The lecture evolves around unconstrained minimization problems that might or might not enjoy closed form solutions. Descent methods are discussed along with exact line search and backtracking. MATLAB implementations are given along the way.

This lecture is outlined as follows

00:00:00 Introduction

00:01:06 Unconstrained Minimization

00:01:36 Iterative Algorithm Assumptions

00:04:28 Gradient Equivalence

00:09:04 Unconstrained Least Squares

00:20:13 Unconstrained Geometric Program

00:28:10 Initial Subset Assumption

00:35:16 Intuitive Solution of Logarithmic Barrier Minimization

00:40:42 Generalization of Logarithmic Barriers

00:42:57 Descent Methods

00:50:42 Gradient Descent

00:52:59 Exact Line Search

00:56:23 Backtracking

01:00:25 MATLAB: Gradient Descent with Exact Line Search

01:17:35 MATLAB: Gradient Descent with Backtracking

01:20:12 MATLAB: Gradient Descent with Explicit Step Size Update

01:28:07 Summary

01:30:59 Outro

===============

References

[1] Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[2] Nesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2013. Reference no. 3

[3] Ben-Tal, Ahron, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Vol. 2. Siam, 2001.

Who this course is for
Computer Engineers
Electical Engineers
Communication Engineers
Civil Engineers
Industrial Engineers
Mechanical Engineers
Programers
Developers
Coders
App Builders
AI and ML Professionals