MSc: Computational Intelligence

Computational intelligence

• Course name: Computational Intelligence
• Course number: R-02
• Area of instruction: Computer Science and Engineering

What subject area does your course (discipline) belong to?

• Machine Learning
• Optimization

Key concepts of the class

• Convex Optimization
• Global Optimization
• Machine Learning and function approximation

What is the purpose of this course?

Computational Intelligence serves as a combined multidisciplinary subject, encompassing a wide range of topics. These include numeric optimization, especially convex optimization, which is the necessary and required topic for most of the modern engineering and scientific work. The course also covers global non-convex optimization methods, which are important instruments in a number of areas: product design and manufacturing, control, and others. Basic information from a number of other areas, such as machine learning, are added to complete the picture of modern intelligent computational tools that serve the same set of goals.

Prerequisites

Prerequisites for CI course:

• Linear Algebra (SVD, least squares, pseudoinverse, semidefinite matrices, solving systems of linear eq., dot product, norms)
• Basic Geometry (ellipsoids, planes, normal, tangent)
• Basic multivariable Calculus (extremum and minimum of a function, derivatives, Jacobians)
• Programming (Python/Matlab)

How can students fill the gap?

• 3blue1brown playlist on Linear Algebra can help to overview selected topics, or https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/
• Or any textbook on Linear algebra

- What should a student remember at the end of the course?

By the end of the course, the students should be able to outline:

• Convexity, Convex Sets, Convex optimization
• Quadratic programming, Second Order Cone Programming, Semidefinite Programming
• Optimization in Controller design, Optimization in path planning, Optimization in Mechanical Engineering
• Nonlinear non-convex optimization, RRT algorithm, Genetic Algorithm, Particle Swarm Optimization, Function approximation.

- What should a student be able to understand at the end of the course?

By the end of the course, the students should be able to understand:

• Structure of optimization problems
• Convexity criteria
• Properties of convex optimization
• Types of problems that cab be transformed into Linear Programs
• Types of problems that cab be transformed into Quadratic Programs
• Types of problems that cab be transformed into Second Order Cone Programs
• Types of problems that cab be transformed into Semidefinite Programs
• Types of non-convex problems that can be approximated by a convex relaxation
• Mixed-integer Optimization
• Path planning as an optimization
• Controller design as an optimization
• Optimal parameter choice
• RRT implementation
• PSO implementation

- What should a student be able to apply at the end of the course?

By the end of the course, the students should be able to

• Design Control using Convex Optimization.
• Implement iterative non-linear controllers with inequality constraints.
• Find optimal parameter choice for processes
• proof convexity of a problem
• program optimization in CVX
• make RRT-based algorithms, understand their limitations
• make PSO-based algorithms, understand their limitations
• make GA-based algorithms, understand their limitations

Course evaluation

Course grade breakdown

		Proposed points
Labs/seminar classes	20	30
Interim performance assessment	30	20
Exams	50	50

Grades range

Course grading range

		Proposed range
A. Excellent	90-100	85-100
B. Good	75-89	70-84
C. Satisfactory	60-74	50-69
D. Poor	0-59	0-49

Resources and reference material

Main textbooks:

• Engelbrecht, A.P., 2007. Computational intelligence: an introduction. John Wiley & Sons.
• Pedrycz, W., 1997. Computational intelligence: an introduction. CRC press.
• Konar, A., 2006. Computational intelligence: principles, techniques and applications. Springer Science & Business Media.

Course Sections

The main sections of the course and approximate hour distribution between them is as follows:

Course Sections

Section	Section Title	Teaching Hours
1	Introduction to optimization methods	6
2	Convex Optimization	6
3	Global Optimization	6

Section 1

Section title:

Introduction to optimization methods

Topics covered in this section:

• Optimization problem types.
• Constraint types.
• Cost function (Reward function) types.
• Practical examples of optimization problems.
• Basic optimization algorithms and their limitations.
• Lagrange multipliers.
• Gradient descent.

What forms of evaluation were used to test students’ performance in this section?

	Yes/No
Development of individual parts of software product code	0
Homework and group projects	1
Midterm evaluation	0
Testing (written or computer based)	1
Reports	1
Essays	0
Oral polls	0
Discussions	0

Typical questions for ongoing performance evaluation within this section

1. Describe an engineering problem as an optimization problem.
2. What is the domain of an optimization problem?
3. What is the difference between Convex and Non-convex optimization?

Typical questions for seminar classes (labs) within this section

1. Formulate a linear system with multi-dimensional solution space and inequality constraints.
2. Solve a linear system with inequality constraints via gradient descent.

Section 2

Section title:

Convex Optimization.

Topics covered in this section:

• Convex sets.
• Convex functions.
• Convex optimization problems.
• Properties of the convex optimizations.
• Linear Programming
• Quadratic Programming.
• Second Order Cone Programming.
• Semidefinite Programming.
• Vertical Stability of a bipedal robot as an optimization.
• Quadrotor path planning as an optimization.
• Controller design as an optimization.
• CVX.

What forms of evaluation were used to test students’ performance in this section?

	Yes/No
Development of individual parts of software product code	0
Homework and group projects	1
Midterm evaluation	1
Testing (written or computer based)	0
Reports	1
Essays	0
Oral polls	0
Discussions	1

Typical questions for ongoing performance evaluation within this section

1. Provide examples of convex problems.
2. What is a convex domain?
3. Examples of problems with a convex cost but non-convex domain?
4. What is the difference between quadratic and conic programming?
5. What is the hierarchy of convex optimization problems?
6. What solvers can solve quadratic programs?
7. What solvers can solve SOCP?
8. What solvers can solve LP?
9. What solvers can solve SDP?

Typical questions for seminar classes (labs) within this section

1. What kinds of inequality constraints make the problem non-convex?
2. What kinds of inequality constraints make the problem non-feasible?
3. Show an example of a problem where the cost is a 2-norm. Show that it is a SOCP.
4. Show an example of a problem where the cost is a 2-norm. Prove that it can be equivalently solved as a QP.
5. Solve trajectory planning for a quadrotor as a SOCP.
6. Solve vertical stability check for a biped as a QP.
7. implement ZMP trajectory planning as a QP.
8. implement LTI controller design as a SDP.

Section 3

Section title:

Global Optimization

Topics covered in this section:

• Properties of non-convex problems.
• Problems with multiple solutions.
• Problems with weak local minima.
• Problems with computationally expensive gradients.
• Path planning on non-convex maps.
• Controller design as a non-convex problem.
• Relaxations.
• Mixed integer programming.
• PSO.
• RRT.
• Genetic Algorithm.
• Machine Learning.

What forms of evaluation were used to test students’ performance in this section?

	Yes/No
Development of individual parts of software product code	0
Homework and group projects	1
Midterm evaluation	0
Testing (written or computer based)	0
Reports	1
Essays	0
Oral polls	0
Discussions	0

Typical questions for ongoing performance evaluation within this section

1. Provide examples of non-convex problems?
2. Why non-convex problems can have multiple solutions?
3. What are local minima?
4. What is global optimization?
5. Provide an example of a non-convex path planning problems?
6. What are the limitations of PSO?

Typical questions for seminar classes (labs) within this section

1. Implement PSO for a parameter optimization problem.
2. Make a comparative study of PSO, GA and Random Search.
3. What is the difference between random search, Sobol sequences-based methods and PSO? Show it in the numerical examples.
4. Implement RRT
5. Implement GA

Test questions for final assessment in this section

1. Solve minimum distance to a plane problem, when the domain is non-convex.
2. Find optimal controller parameters for a given trajectory of a non-linear system.
3. Which non-linear algorithms can solve problems with non-convex domains?