Lecture 2 | Convex Optimization I (Stanford)

Transcript

this presentation is delivered by the Stanford center for professional development okay good morning and welcome to we 364a this is the second lecture and in case you haven't guest I am not Professor boydd he is uh currently on his way back from India and he'll be here in time for the lecture on Tuesday so you don't need to worry it'll be a proper ... Read More

Summary

This video covers various topics related to convex sets. The instructor introduces the concept of affine sets and convex sets, giving examples and explanations. They also discuss convex combinations and convex hulls of sets, providing graphical representations and explanations. The video then explores the concept of convex cones and their properties. Next, the instructor explains hyperplanes and half spaces, showing how they can be used to create convex sets. The video also covers various types of norm balls and their properties. The instructor then discusses polyhedra as the intersection of convex sets, highlighting their convexity. The video concludes by explaining how certain operations, such as intersections and affine mappings, preserve convexity.

Questions & Answers

Q: What is an affine set and how is it different from a convex set?

An affine set is a set where any two distinct points and the line through them are all inside the set. In other words, if you take any two points from an affine set and trace the line through them, that line should be in the same set. An affine set is a special case of a convex set, as it contains the entire line through the two points. Unlike affine sets, convex sets are more restricted in that they only contain the line segments between any two points in the set.

Q: What is a convex combination of points and how does it relate to the convex hull of a set?

A convex combination of points is a set where each point is weighted by a non-negative weight and the weights sum up to 1. The set of all convex combinations of a given set is called the convex hull of the set. The convex hull is the smallest convex set that contains all the points in the original set. For example, if we have three points, the convex hull would be the set of all points that can be obtained by taking convex combinations of the three points.

Q: Can a convex combination of two convex sets also be a convex set?

No, a convex combination of two convex sets is not guaranteed to be a convex set. In general, the convex combination of two sets can result in a more complex set that may not have convex properties. Convex combinations are more commonly used within a single set to generate new points that lie within the set.

Q: What is the difference between a norm ball and a norm cone?

A norm ball is a set defined by a center point and a radius, where any point within the radius of the center point is considered to be in the ball. A norm cone, on the other hand, is defined by taking any point within a certain norm value from the origin. The cone shape is formed by the set of all points within this norm value. While both norm balls and norm cones are convex sets, they differ in terms of their specific shapes and definitions.

Q: How can we determine if a set is convex?

There are several ways to determine if a set is convex. One approach is to use the definition of convexity, which states that for any two points in the set, the line segment connecting them must also be in the set. By checking this condition for all possible pairs of points in the set, we can determine if it is convex. Another method is to use known operations that preserve convexity, such as intersections, affine mappings, and perspective functions. Applying these operations to a set and checking if the resulting set is convex can also determine convexity.

Q: Can a non-convex set become convex after applying an affine function to it?

Yes, a non-convex set can become convex after applying an affine function to it. An affine function, which includes scaling, translation, and projection, preserves convexity. This means that if we take a non-convex set and apply an affine function to it, the resulting set will be convex. Affine functions can "transform" the shape of a set while maintaining its convex properties.

Q: What is the difference between the image and the inverse image of a set under an affine function?

The image of a set under an affine function refers to the set of all points that the function maps to from the original set. This means that each point in the original set is transformed according to the function. In contrast, the inverse image of a set under an affine function refers to the set of all points in the pre-image of the function. This means that the function is applied in reverse, mapping points back to their original positions from the new set.

Q: Can you briefly explain what a perspective function is?

A perspective function is a special type of function that takes in a higher-dimensional vector and reduces it to a lower-dimensional vector by extracting the last component and dividing all other components by it. This can be thought of as shining a light from the origin onto the vector and measuring the shadow it casts. This function is useful in various applications, such as projective geometry and computer graphics. The image and inverse image of a set under a perspective function can also be convex sets.

Q: Are there any known operations that do not preserve convexity?

There are operations that do not preserve convexity. For example, taking the union of two convex sets may result in a non-convex set. Additionally, taking the absolute value of a convex set may also result in a non-convex set. These operations can alter the shape and properties of the original set, leading to non-convexity. It is always important to consider the specific operations and their effects on convexity.