Deck 1 Flashcards
(118 cards)
1
Q
a set of points is convex if:
A
0 ≤ α ≤ 1, we have αx + (1 − α)y ∈ C
all points in C can see each other
can include boundary or not
can be bounded or unbounded
2
Q
difference between cone and subspace
A
alpha > 0 instead of alpha ∈ R
3
Q
infinity norm
A
minimize the largest component
4
Q
minimizing the max of a function is NOT the same as maximizing the min of a function
A
absolute values and sums of absolute values are piecewise linear so can use the epigraph trick
min |x| = > min t
st Ax = x
t >= -x
5
Q
When a system is over-determined, what kind of solution should you look for?
A
sparse solution
6
Q
x^t *y
A
inner product (dot product), produces a scalar
7
Q
subspace
A
set of points that satisfy many linear equations (Ax=0)
8
Q
L1 regularization
A
LASSO, sparsifying
9
Q
what is a cone?
A
αx ∈ C when x ∈ C and α > 0
x + y ∈ C when x ∈ C and y ∈ C
10
Q
Note: the incidence matrix of A is a property of the graph
A
it does not depend on which nodes are sources/sinks/relays
11
Q
True or False, every LP, convex QP, and QCQP are SOCPs
A
True.
LP - make each A = 0
QP/QCQP -
convert quadratic cost to epigraph form (add a variable)
convert quadratic constraints to SOCP (complete square)
12
Q
for linear constraints, the set of all x satisfying c^Tx = b is
A
a hyperplane and the set c^Tx
13
Q
what is a convex cone?
A
all slices are convex
14
Q
polyhedron
A
set of points that satisfy many linear inequalities
intersection of many half spaces
15
Q
if m >n, usually no solution. A is tall.
A
overdetermined
16
Q
x*y^T
A
outer product, nxn matrix
17
Q
a slice of a cone is
A
its intersection with a subspace
18
Q
Dual
A
primal is a maximization, dual is a minimization
there is a dual for each primal constraint
there is a dual constraint for each primal variable
(any feasible primal point)
19
Q
2-norm
A
minimize Euclidean norm
20
Q
A vector-valued function F(x) is linear in x if
A
if there exists a
constant matrix A such that F(x) = Ax
21
Q
L2 regularization
A
smoothing
22
Q
Primal problem. What is dual?
max c^Tx
sub Ax =0
A
Dual. what is primal?
minimize b^T*lambda
subj A^Tλ >=c
λ >=0
23
Q
convert min to max
A
take the negative min f (x) = − max (−f (x))
24
Q
simplex algorithm
A
tranverse the surface of the feasible polyhedron looking for best vertex
25
if QCQP is positive semidefinite
then it is convex. Feasible set is convex, solution can be on boundary or in the interior, relatively easy to solve
26
```
The set of x satisfying x
TQx ≤ 1 corresponds to the set of z
satisfying λ1z
2
1 + · · · + λnz
2
n ≤ 1.
```
in the z coordinates, this is an ellipsoid (stretched by 1/sqrt(lamda)
in xi coordinates, this is a rotated ellipsoid
27
Standard form of linear equations
Maximize c^T*x
| sub to: Ax =0
28
equalities to inequalities
double up
| f (x) = 0 ⇐⇒ f (x) ≥ 0 and f (x) ≤ 0
29
if primal constraint is tight, then dual variable is
not zero
30
A function f (x1, . . . , xm) is linear if:
if there exist constants a1, . . . , am such that
| f (x1, . . . , xm) = a1x1 + · · · + amxm = a^T*x
31
feasible set of QCQP
intersection of multiple ellipsoids
32
epigraph trick only works for:
convex functions
33
ball constraint
SOCP
| new region is smaller, no longer a polyhedron, more robust to uncertain constraints
34
Chebyshev center
What is the largest sphere you can fit inside a polyhedron
| want to maximize the smallest line from the center to the side
35
how to get ellipsoidal cone:
Ellipsoid x^TPx + q^T*x + r ≤ 0 where P is positive semi definite and x ∈ R^n
Complete the squar ||Ax + b||
36
halfspace
set of points that satisfy linear inequality
37
max flow primal
each edge of the network has a max capacity, pick how much commodity flows along each edge to maximize the total amount transported from the start node
partition of nodes into 2 subsets, with start node in one subset, end node in other
choose the partition that minimizes the sum of capcities of the dges that connect both subsets
38
if ellipsoid center is feasible, then
it is also the optimal point
39
QP
convex quadratic cost and linear constraints
40
hyperplane
The set of points x ∈ R^n that satisfies a linear equation
| a1x1 + · · · + anxn = 0 (or a^T*x = 0)
41
optimization hierarchy
modeling languages > solvers > algorithms > models
42
bounded to nonnegative
shift the variable
p ≤ x ≤ q ⇐⇒ 0 ≤ (x −p) and (x −p) ≤ (q −p)
43
for quadratic constraints what is the set
| x^TQx
if Q >0 the set x^TQx
44
what are the options for solutions in a LP?
infeasible, unbounded, on the boundary
45
if m
underdetermined
46
if P is positive semidefinite, then what kind of QP
convex QP. Feasible set is a polyhedron. solution can be on boundary or in the interior. relatively easy to solve.
47
adding linear terms to a degenerate ellipsoid produces
a paraboloid if the added term is in the degenerate direction
48
if primal constraint is slack,dual
dual is zero
49
unbounded to bounded
x ∈ R ⇐⇒ u ≥ 0, v ≥ 0, and x = u − v
50
blended
mix of simplex and interior point
51
if x is a locally optimal point, then it is
globally optimal
52
regularization
additional penalty term added to the cost function to encourage a solution with desirable properties
53
if ellipsoid center of QCQP is feasible then
it is also the optimal point
54
reverse inequalities
flip the sign
| Ax ≤ b ⇐⇒ (−A)x ≥ (−b)
55
decision variables in network flow
flow on each edge
56
the set of matrices x is positive semidefinite is
a convex cone
57
When is a matrix over determined?
More columns than rows (wide)
58
c^T* x ≤ p* ≤ d* ≤ b^Tλ
dual
59
if Q = Q^T
| x^T *Qx >=0 for all x
all eigenvalues of Q satisfy lambda >=0
60
semi definite constraint
symmetric matrix that is semidefinite, we can represent as a vector
61
What type of quadratic constraints make a QCQP difficult to solve?
```
Indefinite quadratic constraints
quadratic equalities (can encode boolean)
```
62
epigraph - R^n -> R is a convex function iff
{x,t} exists R^n+1 |f(x)
63
bounded to unbounded
p ≤ x ≤ q ⇐⇒
1
−1
x ≤
q
−p
64
intersections preserve convexity
the union does not have to be convex
65
CX
convex cost and constraints
66
If maximum profit is p*, every feasible point of the LP yields
a lower bound for p*
67
inequalities to equalities
add slack
| f (x) ≤ 0 ⇐⇒ f (x) + s = 0 and s ≥ 0
68
if lamda = 0, Q >=0, the ellipsoid x^TQx
degenerate. Stretches to infinity in direction vi
69
SOCP
linear cost, second order cone constraints
70
what are nodes in network flow problems
sources, relays, sinks
71
LP has what kind of variables, constraints, cost function
- continuous variables
- linear constraints
- linear cost funtion
72
How to transform a convex piecewise linear function to linear function?
convert to epigraph form -
| add extra decision variable t and turn cost into a constraint
73
if Q is positive definite, then the quadratic form with extra affine terms
is a shifted ellipsoid
74
Four combinations of general LP duality:
1. (P) and (D) are both feasible and bounded, and p* = d*
2. p* = +∞ (unbounded primal) and d* = +∞ (infeasible dual).
3. p* = −∞ (infeasible primal) and d* = −∞ (unbounded dual).
4. p* = −∞ (infeasible primal) and d* = +∞ (infeasible dual).
Can't have both unbounded
75
A function f (x1, . . . , xm) is affine in the variables
| x1, . . . , xm if
if there exist constants b, a1, . . . , am such that
| f (x1, . . . , xm) = a0 + a1x1 + · · · + amxm = a^T*x + b
76
QCQP
convex quadratic cost and constraints
77
level set
if f is a convex function, the set of all points satisfying f(x)
78
Can you square both sides of second order cone?
Generally, no
79
Optimization models categorized on:
types of variables, types of constraints, types of cost functions
80
A matrix is totally unimodular if
every square matrix of A has a determinant of 0, 1, -1
81
Transformation tricks
```
convert min to max
reverse inequalities
equalities to inequalities
inequalities to equalities
unbounded to bounded
bounded to unbounded
bounded to non-negative
```
82
SDP
linear cost, semidefinite constraints
83
QCQP
Quadratically constrained quadratic program. has both quadratic cost and quadratic constraints
84
convex functions
```
affine
absolute value
quadratic
exponential
powers
negative entropy
norms
```
85
the maximum of several linear functions is always convex. So we can blank it using the blank trick.
we can minimize it using the epigraph trick
86
Where do quadratics commonly occur?
```
as a regularization or penalty term
hard norm bounds on a decision variable
allow some tolerance in constraint satisfaction
energy quantities
covariance constraints
```
87
minimizing the largest component is an LP
| minimizint the sum of absolute values is an LP
minimizing the 2 norm is not an LP
88
is x^TQx ever negative
Look at eigenvalues of Q
define new coordinates z= V^Tx
x^T*Qx - lambda*z1....lambda*zn
if all lambda >= 0, then x^TQx >=0 for any x
89
lambda is
the price item i is worth to us
90
pareto curve
visualize tradoffs
91
L infinity regularization
equalizing effect
92
upper bound for p*
combining constraints in different ways. Create a multiplier for each constraint. Some of constraints must be
93
LP
linear cost and linear constraints
94
a^T*x = b
affine hyperplane
95
changes in primal constraints are changes in dual _______
cost
96
infeasible p* (maximization)
-∞
97
hyperplanes are
subspaces
| A hyperplane in R^n is a subspace of dimension n − 1.
98
1-norm
minimize sum of the absolute values
99
if ^x satisfies the normal equations, then ^x is a solution to the least-squares optimization problem
then ^x is a solution to the least-squares optimization problem
100
if ellipsoid center of QCQP is infeasible then
the optimal point is on the boundary
101
special cases of second order cones
if A=0, we have a linear constraint (hyperplane)
| if c = 0 we can square both sides
102
unbounded p* (maximization problem)
+∞
103
Quadratic form
x^T*Qx when Q is a symmetric matrix
104
Second order cone
set of points x exists in R^n satisfying
| ||Ax +b ||
105
LP
real valued variables
affine cost function (c^T*x)
affine equations or inequalities
individual variables may have bounds or not
106
if A is symmetric then
all eigenvalues of A are real
| A is diagnalizable and its eigenvectors can be chosen to be orthogonal
107
if ellipsoid center is infeasible, then
optimal point is on the boundary (but not always at a vertex)
108
interior point
traverse the inside of the polyhedron and move towards best vertex
109
If A is a TU and b is an integer vector, then the vertices of {x| Ax
If a minimum-cost flow problem has integer supplies, integer demands, and integer edge capacities, then there is a minimum cost INTEGER flow.
Every shortest path problem is an LP.
110
Quadratic program is like an LP but with a quadratic cost
min x^TPx + q^Tx +r
| subj Ax
111
transportation primal
edges have transportation cost, pick x to minimize total cost
if supply/demand is integral, flow will be integral
maximization of total prices of what to buy/sell commodities at each node
if edge cost is integral, prices will be integral
112
• A vector-valued function F(x) is affine in x if there exists
a constant matrix A and vector b such that F(x) = Ax + b.
113
LP solvers
simplex
interior point
blended
114
How to get a polyhedral cone:
Begin with polyhedron Ax =0} is a polyhedral cone in (x,t) ∈ R ^n+1
slice t =1 is original polyhedron
115
if p* and d* exist and are finite then
p*=d*
| strong duality
116
robust LP to account for uncertainty in some vectors
box constraint, ball constraint
117
a change to the feasible set of the primal problem can change the optimal f and s but lambdas will not change
optimal f and s might change but lambdas will not
118
every LP and SOCP a SDP
polyhedra and second-order cones are special cases of spectrahedra
