Meetup 5: Convex Sets

George I. Hagstrom

Zoology of Optimization Problems

\[ \min_{\mathbf{x}} f(\mathbf{x}) \\ g_i(\mathbf{x}) \leq 0, i=1, \cdots, p \]

  • Different “names” for optimization problems based on what \(f\) and \(g\) are

Zoology: Linear Programs (LP)

\[ \min_{\mathbf{x}} \mathbf{c}^T\mathbf{x} \\ A\mathbf{x} \leq \mathbf{d} \]

Zoology: Quadratic Programming (QP)

\[ \min_{\mathbf{x}} \frac{1}{2} \mathbf{x}^T P \mathbf{x} + \mathbf{c}^T\mathbf{x} \\ A\mathbf{x} \leq \mathbf{d} \]

  • \(P\) positive (semi)-definite

Zoology: Quadratic Programming Quadratic Constraints (QCQP)

\[ \min_{\mathbf{x}} \frac{1}{2} \mathbf{x}^T P \mathbf{x} + \mathbf{c}^T\mathbf{x} \\ \frac{1}{2} \mathbf{x}^T P_i \mathbf{x} + \mathbf{c}_i^T\mathbf{x} \leq \mathbf{d}_i \\ A\mathbf{x} = \mathbf{b} \]

Zoology: Others…

  • Semidefinite Programming
  • Conic Optimization
  • Second Order Cone Programming

Development

  • These problems were studied sequentially starting in the 1800s
  • Development of Computer in the 1940s led to wide application
  • Change in perspective:
    • Pre 1970s, Linear problems are easy, linear hard
    • Post 1970s, Convex problems are easy, non-convex hard

Development

Robert Vanderbei/NY Times 1984

Development

wikipedia

Week(s) Ahead

  • We begin convex optimization today
  • We will learn how to recognize and formulate convex problems
  • At first it will seem weird, but stick with it
  • Next two weeks: Understanding whether constraint sets are convex

How will we solve Convex Problems?

  • For us \(f\) will be convex and so will be the constraint set

  • The hard part is recognizing the convexity, algorithms are very well developed

import cvxpy as cp
x = cp.Variable()
y = cp.Variable()

# DCP problems.
prob1 = cp.Problem(cp.Minimize(cp.square(x - y)),
                    [x + y >= 0,
                    x >= 4,
                    y <= 1])
prob1.solve()

What is a Convex Set

  • If you draw a line between any two points in the set, the entire line will be in the set

What is a Convex Set

  • If even one pair of points exists where this fails, the set is not convex

Why is Convexity Important?

  • Convex optimization: local minimum always coincides with global minimum
  • Local minimum is findable

Why is Convexity Important?

  • Convex region
  • Single Local Min

Why is Convexity Important?

  • Nonconvex
  • Many local min

Convex Combinations

  • If we have two points \(\mathbf{x}_1\) and \(\mathbf{x}_2\), a convex combination is: \[ \theta_1\mathbf{x}_1 + (1-\theta_1)\mathbf{x}_2, \]

where \(0\leq\theta_1\leq 1\)

  • Genearlize to more points (weighted averages): \[ \sum_i \theta_i\mathbf{x}_i, \quad 0\leq \theta_i, \quad \sum_i \theta_i = 1 \]

Math Definition of Convex Sets

  • A set is convex is for every pair of points \(\mathbf{x}_1\) and \(\mathbf{x}_2\) in the set, every convex combination of those two points is in the set.

Definition Not Useful In Practice

  • Using the definition is a last resort
  • Instead, we will use a constructive approach
    1. Have example convex sets
    2. Have operations that preserve convexity
    3. Write target set use operations on examples

Affine Sets (Lines, Planes, Hyperplanes)

  • \(y = ax + b\)
  • Solutions of: \[ A\mathbf{x} = \mathbf{d} \]
  • Underdetermined Case

Convex Hull

  • Suppose you have a non-convex set
  • Define a new set to be the convex combination of all the points in the set

Examples: Polyhedra

What is a polyhedron?

  • Solution set of linear inequalities and equations

What is a polyhedron?

  • Solution set of linear inequalities and equations

What is a polyhedron?

  • Solution set of linear inequalities and equations

What is a polyhedron?

  • Solution set of linear inequalities and equations

What is a Polyhedron?

  • Solution set of linear inequalities and equations

What is a Polyhedron?

  • Solution set of linear inequalities and equations

What is a Polyhedron?

  • Solution set of linear inequalities and equations

\[\{x\, |\, C\mathbf{x}\preceq \mathbf{d},\, A\mathbf{x} = \mathbf{h} \}\]

  • \(\preceq\) stands for componentwise inequality
  • True if every single entry satisfies inequality
  • Sometimes polyhedron stands for closed, polytope stands for open

Example: Designing a Healthy Diet

  • You are in charge of buying food
  • Large org
    • Army
    • School System
    • NGO/UN
  • Food \(i\) has \(V_{ij}\) of nutrient \(j\)
Nutrient Content
Calories (kCal) 100
Fat (g) 2
Carbs (g) 20
Protein (g) 2
Vitamin C (mg) 90
Fiber (g) 4

Oranges

Example: Designing a Healthy Diet

  • Each nutrient has a minimum and/or maximum
Nutrient Minimum Maximum
Calories 2500
Fat 50
Carbs 200
Protein 40 200
Vitamin C 100 1000
Fiber 20 80

RDV Constraints

  • Split the inequalities up:

\[ -\mathbf{v}_j^T\mathbf{w} \leq -l_{min,j} \\ \mathbf{v}_j^T\mathbf{w} \leq l_{max,j} \]

Constraints are a polyhedron

  • Form matrix \(U\) from rows \(\mathbf{v}\)
  • If both positive and negative, include both \(-\mathbf{v}_j\) and \(\mathbf{v}_J\).
  • If only have a negative or positive, include just one
  • \(\mathbf{l}\) contains upper and lower bounds
  • Add constraint that \(-\mathbf{w}\preceq 0\) \[ U\mathbf{w} \preceq \mathbf{l}\]

Each Food Has a Cost

  • Each food has a cost \(c_i\)
  • Describe with vector \(\mathbf{c}\)
  • Objective function \(\mathbf{c}^T\mathbf{w}\)
  • Optimization Problem:

\[ \min_{\mathbf{w}} \mathbf{c}^T\mathbf{w} \\ U\mathbf{w} \preceq \mathbf{l} \]

Simplex

  • Simplex is set of points satisfying: \[ \{\mathbf{p}\, |\, \sum_{i}p_i=1,\, p_i\geq 0\} \]

  • Discrete probability distribution

Half-Planes

  • Special case of polyhedron (and also cone)
  • \(\mathbf{c}^T\mathbf{x} \leq d\)

Balls and Ellipsoids

  • Ball has center and radius \[ B(\mathbf{x}_c,r) = \{\mathbf{x}\,|\, \|\mathbf{x}-\mathbf{x}_c\|\leq r\} \]

Balls and Ellipsoids

  • Ellipsoid described by positive definite matrix \(P\) \[ E(\mathbf{x}_c,P) = \{\mathbf{x}\,|\, (\mathbf{x}-\mathbf{x}_c)^TP^{-1}(\mathbf{x}-\mathbf{x}_x)\leq 1\} \]

Balls and Ellipsoids

  • Ellipsoid described by positive definite matrix \(P\)
  • Alternately: \[ E(\mathbf{x}_c,P) = \{\mathbf{x}\,|\, \|A\mathbf{x}-\mathbf{x_c} \|\leq 1 \}, \]
  • Where \(P = A^TA\), \(A\) square, non-singular

Examples:

  • Limit on expected return variance in a portfolio:
    • \(\mathbf{w}^T\Gamma\mathbf{w} \leq v_{max}\)
  • Limit on distance of an antenna from a transmitter:
    • \(\|\mathbf{x}-\mathbf{x}_c\|< r\)

Cones

  • Cone is a set which has the following property:
  • If \(\mathbf{x}\) is in the cone, then \(\theta \mathbf{x}\) is also in the cone, for \(\theta\geq 0\)

Conic Combination

  • Like convex combination, but \(\theta\) can be large: \[ \sum_{i}\mathbf{x}_i\theta_i,\, \theta_i \geq 0 \]

Conic Combination

  • Like convex combination, but \(\theta\) can be large: \[ \sum_{i}\mathbf{x}_i\theta_i,\, \theta_i \geq 0 \]

Norm Balls and Norm Cone

  • For any norm \(N\): \[ B_N(r,\mathbf{x}_c) = \{\mathbf{x}\,|\, \|\mathbf{x}-\mathbf{x}_c\|_N < r\} \]

  • \(B_N(r,\mathbf{x}_c)\) is Convex and called a “Norm Ball”

  • Norm Cone: \[ \{[\mathbf{x}\,, t]\,|\, \|\mathbf{x}\|_N \leq t\} \]

Norm Cone

  • Here the \(t\) is restricting how wide \(\mathbf{x}\) is allowed to be

Optimization Under Uncertainty

  • Consider “uncertain” nutrition optimization problem \[ \min_{\mathbf{w}} \mathbf{c}^T\mathbf{w} \\ U\mathbf{w} \preceq \mathbf{l} \]
  • The nutrient contents in \(U\) are random
  • Variance \(\sigma_i\), for each nutrient, mean \(\bar{U_i}\).
  • Insist that: \[ \bar{U_i}\mathbf{w} + k\|\sigma_i^T\mathbf{w} \| \leq l_i \]

Thanks!