../

CVXOPT Notes

$\newcommand{\dom}{\mathbf{dom}~}$ $\newcommand{\R}{\mathbb{R}}$

Ch. 2 Convex Sets

Affine sets

  • Define an affine set
    • A set $C \subseteq \R^n$ is an affine set if $\forall x, y\in C$ $$\theta y + (1-\theta) x\in C, \theta \in \R$$
  • Express an affine set as offset from a subspace
  • If you had some affine set $C$ and you picked $x_0 \in C$ and subtracted it from all $x\in C$, what would be the result?
  • What is the dimension of an affine set?
  • What does an affine set correspond to geometrically ?
    • Hyperplane
  • What is an affine combination?
    • An affine combination of a set of points $x_1, x_2, \ldots, x_n$ is defined as $$\sum_{i=1}^n\theta_i x_i$$ given that the coefficients sum up to one $\theta_i \in \R, \sum_{i=1}^n \theta_i = 1$
  • Does an affine combination result in an affine set?
    • Yes
  • Given a set of point, how would you form an affine set with them?
    • Take an affine combination of them
  • Given a system of linear equations $Ax = b$, what is the first affine set that you can think of?
    • The solutions to the equations form an affine set
  • Given an affine set which is the solution to a system of linear equations, how would you find the subspace associated with it?
    • The null space of $A$ is the subspace associated with $C$
  • What is the relation between affine sets and linear system of equations?
  • What is an affine hull?
  • If a convex set $C$ is a subset of $S$, what is the relation between $\mathbf{aff}\ C$ and $S$?
  • What is the affine dimension of a set $C$?
  • Give a counter example of when affine dimensions don’t match our intuitive definitions of dimensions?
  • What do we do when the affine dimension of a set in $\R^n$ is not equal to $n$?
  • Why doesn’t $\mathbf{int}$ work for lower dimensional objects in higher dimension?
  • Intuitively what is $\mathbf{relint}$ doing?
  • What norm should we use for defining $\mathbf{relint}$ of a set?
  • What is $\mathbf{cl}$ of a set?
  • What is the relative boundary of a set?
  • What would be the $\mathbf{int}$, $\mathbf{relint}$, boundary, relative boundary for a unit square embedded in $\R^3$?

Convex set

  • Define a convex set
    • A set $C \subseteq \R^n$ is a convex set if $\forall x, y\in C,$ $$\theta y + (1 - \theta) x \in C, \theta \in [0, 1]$$
  • Are all affine sets convex sets? If so why?
    • Yes. All affine sets are convex sets. Convex sets require every point on the line segment between two points to be in the set. Affine sets have all the points on the line in them. As the line segment is part of the line, every point on the line segment will be in the set, therefore making it convex.
  • If a set is convex does it make it affine?
    • No.
  • Can a set be convex if it is missing one convex combination?
  • What is a convex hull?
  • What is the smallest convex set that contains a set $C$?
  • How would you extend the convex combinations definition to infinite sums?
  • How would you extend the convex combinations definition to integrals?
  • How would you extend the convex combinations definition to probabilities?

Cones

  • Define a cone
  • Define a convex cone
  • Give the combined equation to be a convex cone?
  • What is a conic combination?
  • What is the conic hull?
  • What is the smallest convex cone containing a set $C$?
  • Explain the relationship between a conic combination and a convex combination

Examples

  • What is the smallest set that is affine?
  • When is a line a convex cone?
  • When is line segment affine?
  • What is the general form of a ray?
  • Ray is convex or affine?
  • When is a ray a convex cone?
  • What can you say about a subspace?

Hyperplanes and halfspaces

  • What is the general form of a hyperplane?
  • How would you describe a hyperplane using a normal vector?
  • Represent a hyperplane using offset + normal vector
  • Why aren’t halfspaces affine?
  • Using the normal and a vector on the plane form of a hyperplane, which halfspace does $a$ point towards?
  • For the lesser than inequality hyperspace, what kind of angle does one have to make with $x_0$ to be in the haflspace?
  • What is the boundary of a halfspace?
  • What is the open halfspace?
  • Define the euclidean ball
  • Define the norm ball
  • Define the norm cone
  • What is the second order cone?
  • What are some other names of the second order cone?
  • Explain the naming of the second order cone
  • What is a polyhedra
  • What is a polytope
  • What is positive semi-definite
  • What is the dimension of $\mathbf{S}^n$
  • What are the conditions for a $2\times2$ matrix to be in $\mathbf{S}^2$ in terms of the individual matrix entries?

Operations that preserve convexity

  • How do you relate positive semi-definiteness and intersection?
  • Mention all the simple affine functions that preserve convexity
  • What are projective functions
  • does the inverse of a projective function have the same qualities as the function itself?
  • What is a linear fractional?
  • How do they relate to affine and linear functions?

Generalized inequalities

  • What is a proper cone
  • Define the generalized inequality based on the cone
  • What are the properties of generalized inequalities?

Ch. 3 Convex functions

  1. Define a norm
  2. What is an affine function
  3. Define a convex function?
  4. What is strictly convex?
  5. Define concavity and strict concavity
  6. When will you have both convexity and concavity?
  7. Any function that is both concave and convex is ______
  8. Affine functions are both ______
  9. Assume a function $f$ is convex, will it also be convex when we restrict it to some line on its $\dom$?
  10. What is a very easy way to check a function is convex?
  11. How do you extend the $\dom$ of a convex function to all of $\R$
  12. Show how the domain extension of a convex function still retains convexity
  13. How do you recover the original function from a domain extended version of it?
  14. Define the indicator function of a convex set
  15. What is the purpose of an indicator function?
  16. Given a convex function $f$ defined on $\R$ and a convex set $C \subset \R$, how do you optimize $f$ on $C$?
  17. How do you domain extend a concave function?
  18. Condition for convexity using first-order derivatives
  19. What is the first-order Taylor approximation of a function?
  20. What can you say about the first-order Taylor approximation in terms of affinity?
  21. Why is the first-order Taylor series affine?
  22. What is the significance of the first-order condition for a convex function?
  23. What is the most important property of a convex function?
  24. How do you identify the global minimizer of a convex function?
  25. First order condition for strict convexity
  26. First order condition for concavity
  27. What is the second order condition for concavity
  28. What is the geometric interpretation of the second-order condition?
  29. For a concave function $f$, comment on convex/concavity of $\dom f$
  30. Condition for concavity in terms of second-order conditions
  31. second order conditions for strict convexity
  32. Are the second-order conditions for strict convexity complete? If not give an CEX.
  33. Express quadratic functions in terms of matrices
  34. Explain when a quadratic function is strictly convex
  35. Mention why the second requirement on $\dom f$ is important and give an example
  36. Give an example of a function satisfying first and second order conditions while still not being convex