Deck 1 Flashcards
a set of points is convex if:
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
difference between cone and subspace
alpha > 0 instead of alpha ∈ R
infinity norm
minimize the largest component
minimizing the max of a function is NOT the same as maximizing the min of a function
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
When a system is over-determined, what kind of solution should you look for?
sparse solution
x^t *y
inner product (dot product), produces a scalar
subspace
set of points that satisfy many linear equations (Ax=0)
L1 regularization
LASSO, sparsifying
what is a cone?
αx ∈ C when x ∈ C and α > 0
x + y ∈ C when x ∈ C and y ∈ C
Note: the incidence matrix of A is a property of the graph
it does not depend on which nodes are sources/sinks/relays
True or False, every LP, convex QP, and QCQP are SOCPs
True.
LP - make each A = 0
QP/QCQP -
convert quadratic cost to epigraph form (add a variable)
convert quadratic constraints to SOCP (complete square)
for linear constraints, the set of all x satisfying c^Tx = b is
a hyperplane and the set c^Tx
what is a convex cone?
all slices are convex
polyhedron
set of points that satisfy many linear inequalities
intersection of many half spaces
if m >n, usually no solution. A is tall.
overdetermined
x*y^T
outer product, nxn matrix
a slice of a cone is
its intersection with a subspace
Dual
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)
2-norm
minimize Euclidean norm
A vector-valued function F(x) is linear in x if
if there exists a
constant matrix A such that F(x) = Ax
L2 regularization
smoothing
Primal problem. What is dual?
max c^Tx
sub Ax =0
Dual. what is primal?
minimize b^T*lambda
subj A^Tλ >=c
λ >=0
convert min to max
take the negative min f (x) = − max (−f (x))
simplex algorithm
tranverse the surface of the feasible polyhedron looking for best vertex
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
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
Standard form of linear equations
Maximize c^T*x
sub to: Ax =0
equalities to inequalities
double up
f (x) = 0 ⇐⇒ f (x) ≥ 0 and f (x) ≤ 0
if primal constraint is tight, then dual variable is
not zero
A function f (x1, . . . , xm) is linear if:
if there exist constants a1, . . . , am such that
f (x1, . . . , xm) = a1x1 + · · · + amxm = a^T*x
feasible set of QCQP
intersection of multiple ellipsoids
epigraph trick only works for:
convex functions
ball constraint
SOCP
new region is smaller, no longer a polyhedron, more robust to uncertain constraints
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
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||
halfspace
set of points that satisfy linear inequality
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
if ellipsoid center is feasible, then
it is also the optimal point
QP
convex quadratic cost and linear constraints
hyperplane
The set of points x ∈ R^n that satisfies a linear equation
a1x1 + · · · + anxn = 0 (or a^T*x = 0)
optimization hierarchy
modeling languages > solvers > algorithms > models
bounded to nonnegative
shift the variable
p ≤ x ≤ q ⇐⇒ 0 ≤ (x −p) and (x −p) ≤ (q −p)
for quadratic constraints what is the set
x^TQx
if Q >0 the set x^TQx
what are the options for solutions in a LP?
infeasible, unbounded, on the boundary
if m
underdetermined
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.
adding linear terms to a degenerate ellipsoid produces
a paraboloid if the added term is in the degenerate direction
if primal constraint is slack,dual
dual is zero
unbounded to bounded
x ∈ R ⇐⇒ u ≥ 0, v ≥ 0, and x = u − v
blended
mix of simplex and interior point
if x is a locally optimal point, then it is
globally optimal
regularization
additional penalty term added to the cost function to encourage a solution with desirable properties
if ellipsoid center of QCQP is feasible then
it is also the optimal point
reverse inequalities
flip the sign
Ax ≤ b ⇐⇒ (−A)x ≥ (−b)
decision variables in network flow
flow on each edge
the set of matrices x is positive semidefinite is
a convex cone
When is a matrix over determined?
More columns than rows (wide)
c^T* x ≤ p* ≤ d* ≤ b^Tλ
dual
if Q = Q^T
x^T *Qx >=0 for all x
all eigenvalues of Q satisfy lambda >=0
semi definite constraint
symmetric matrix that is semidefinite, we can represent as a vector
What type of quadratic constraints make a QCQP difficult to solve?
Indefinite quadratic constraints quadratic equalities (can encode boolean)
epigraph - R^n -> R is a convex function iff
{x,t} exists R^n+1 |f(x)
bounded to unbounded
p ≤ x ≤ q ⇐⇒
1
−1
x ≤
q
−p
intersections preserve convexity
the union does not have to be convex
CX
convex cost and constraints
If maximum profit is p*, every feasible point of the LP yields
a lower bound for p*
inequalities to equalities
add slack
f (x) ≤ 0 ⇐⇒ f (x) + s = 0 and s ≥ 0
if lamda = 0, Q >=0, the ellipsoid x^TQx
degenerate. Stretches to infinity in direction vi
SOCP
linear cost, second order cone constraints
what are nodes in network flow problems
sources, relays, sinks
LP has what kind of variables, constraints, cost function
- continuous variables
- linear constraints
- linear cost funtion
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
if Q is positive definite, then the quadratic form with extra affine terms
is a shifted ellipsoid
Four combinations of general LP duality:
- (P) and (D) are both feasible and bounded, and p* = d*
- p* = +∞ (unbounded primal) and d* = +∞ (infeasible dual).
- p* = −∞ (infeasible primal) and d* = −∞ (unbounded dual).
- p* = −∞ (infeasible primal) and d* = +∞ (infeasible dual).
Can’t have both unbounded
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
QCQP
convex quadratic cost and constraints
level set
if f is a convex function, the set of all points satisfying f(x)
Can you square both sides of second order cone?
Generally, no
Optimization models categorized on:
types of variables, types of constraints, types of cost functions
A matrix is totally unimodular if
every square matrix of A has a determinant of 0, 1, -1
Transformation tricks
convert min to max reverse inequalities equalities to inequalities inequalities to equalities unbounded to bounded bounded to unbounded bounded to non-negative
SDP
linear cost, semidefinite constraints
QCQP
Quadratically constrained quadratic program. has both quadratic cost and quadratic constraints
convex functions
affine absolute value quadratic exponential powers negative entropy norms
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
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
minimizing the largest component is an LP
minimizint the sum of absolute values is an LP
minimizing the 2 norm is not an LP
is x^TQx ever negative
Look at eigenvalues of Q
define new coordinates z= V^Tx
x^TQx - lambdaz1….lambda*zn
if all lambda >= 0, then x^TQx >=0 for any x
lambda is
the price item i is worth to us
pareto curve
visualize tradoffs
L infinity regularization
equalizing effect
upper bound for p*
combining constraints in different ways. Create a multiplier for each constraint. Some of constraints must be
LP
linear cost and linear constraints
a^T*x = b
affine hyperplane
changes in primal constraints are changes in dual _______
cost
infeasible p* (maximization)
-∞
hyperplanes are
subspaces
A hyperplane in R^n is a subspace of dimension n − 1.
1-norm
minimize sum of the absolute values
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
if ellipsoid center of QCQP is infeasible then
the optimal point is on the boundary
special cases of second order cones
if A=0, we have a linear constraint (hyperplane)
if c = 0 we can square both sides
unbounded p* (maximization problem)
+∞
Quadratic form
x^T*Qx when Q is a symmetric matrix
Second order cone
set of points x exists in R^n satisfying
||Ax +b ||
LP
real valued variables
affine cost function (c^T*x)
affine equations or inequalities
individual variables may have bounds or not
if A is symmetric then
all eigenvalues of A are real
A is diagnalizable and its eigenvectors can be chosen to be orthogonal
if ellipsoid center is infeasible, then
optimal point is on the boundary (but not always at a vertex)
interior point
traverse the inside of the polyhedron and move towards best vertex
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.
Quadratic program is like an LP but with a quadratic cost
min x^TPx + q^Tx +r
subj Ax
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
• 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.
LP solvers
simplex
interior point
blended
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
if p* and d* exist and are finite then
p=d
strong duality
robust LP to account for uncertainty in some vectors
box constraint, ball constraint
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
every LP and SOCP a SDP
polyhedra and second-order cones are special cases of spectrahedra
