Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Optimization > Deck 1 > Flashcards

Deck 1 Flashcards

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

difference between cone and subspace

A

alpha > 0 instead of alpha ∈ R

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

infinity norm

A

minimize the largest component

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

When a system is over-determined, what kind of solution should you look for?

A

sparse solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

x^t *y

A

inner product (dot product), produces a scalar

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

subspace

A

set of points that satisfy many linear equations (Ax=0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

L1 regularization

A

LASSO, sparsifying

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what is a cone?

A

αx ∈ C when x ∈ C and α > 0

x + y ∈ C when x ∈ C and y ∈ C

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

for linear constraints, the set of all x satisfying c^Tx = b is

A

a hyperplane and the set c^Tx

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what is a convex cone?

A

all slices are convex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

polyhedron

A

set of points that satisfy many linear inequalities

intersection of many half spaces

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

if m >n, usually no solution. A is tall.

A

overdetermined

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

x*y^T

A

outer product, nxn matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

a slice of a cone is

A

its intersection with a subspace

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

2-norm

A

minimize Euclidean norm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

L2 regularization

A

smoothing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

convert min to max

A 
take the negative 
min f (x) = − max (−f (x))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

simplex algorithm

A

tranverse the surface of the feasible polyhedron looking for best vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

if QCQP is positive semidefinite

A

then it is convex. Feasible set is convex, solution can be on boundary or in the interior, relatively easy to solve

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q 
The set of x satisfying x
TQx ≤ 1 corresponds to the set of z
satisfying λ1z
2
1 + · · · + λnz
2
n ≤ 1.
A

in the z coordinates, this is an ellipsoid (stretched by 1/sqrt(lamda)
in xi coordinates, this is a rotated ellipsoid

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Standard form of linear equations

A

Maximize c^T*x

sub to: Ax =0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

equalities to inequalities

A

double up

f (x) = 0 ⇐⇒ f (x) ≥ 0 and f (x) ≤ 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

if primal constraint is tight, then dual variable is

A

not zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

A function f (x1, . . . , xm) is linear if:

A

if there exist constants a1, . . . , am such that

f (x1, . . . , xm) = a1x1 + · · · + amxm = a^T*x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

feasible set of QCQP

A

intersection of multiple ellipsoids

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

epigraph trick only works for:

A

convex functions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

ball constraint

A

SOCP

new region is smaller, no longer a polyhedron, more robust to uncertain constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Chebyshev center

A

What is the largest sphere you can fit inside a polyhedron

want to maximize the smallest line from the center to the side

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

how to get ellipsoidal cone:

A

Ellipsoid x^TPx + q^T*x + r ≤ 0 where P is positive semi definite and x ∈ R^n

Complete the squar ||Ax + b||

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

halfspace

A

set of points that satisfy linear inequality

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

if ellipsoid center is feasible, then

A

it is also the optimal point

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

QP

A

convex quadratic cost and linear constraints

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

hyperplane

A

The set of points x ∈ R^n that satisfies a linear equation

a1x1 + · · · + anxn = 0 (or a^T*x = 0)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

optimization hierarchy

A

modeling languages > solvers > algorithms > models

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

bounded to nonnegative

A

shift the variable

p ≤ x ≤ q ⇐⇒ 0 ≤ (x −p) and (x −p) ≤ (q −p)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

for quadratic constraints what is the set

x^TQx

A

if Q >0 the set x^TQx

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

what are the options for solutions in a LP?

A

infeasible, unbounded, on the boundary

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

if m

A

underdetermined

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

if P is positive semidefinite, then what kind of QP

A

convex QP. Feasible set is a polyhedron. solution can be on boundary or in the interior. relatively easy to solve.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

adding linear terms to a degenerate ellipsoid produces

A

a paraboloid if the added term is in the degenerate direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

if primal constraint is slack,dual

A

dual is zero

49
Q

unbounded to bounded

A

x ∈ R ⇐⇒ u ≥ 0, v ≥ 0, and x = u − v

50
Q

blended

A

mix of simplex and interior point

51
Q

if x is a locally optimal point, then it is

A

globally optimal

52
Q

regularization

A

additional penalty term added to the cost function to encourage a solution with desirable properties

53
Q

if ellipsoid center of QCQP is feasible then

A

it is also the optimal point

54
Q

reverse inequalities

A

flip the sign

Ax ≤ b ⇐⇒ (−A)x ≥ (−b)

55
Q

decision variables in network flow

A

flow on each edge

56
Q

the set of matrices x is positive semidefinite is

A

a convex cone

57
Q

When is a matrix over determined?

A

More columns than rows (wide)

58
Q

c^T* x ≤ p* ≤ d* ≤ b^Tλ

A

dual

59
Q

if Q = Q^T

x^T *Qx >=0 for all x

A

all eigenvalues of Q satisfy lambda >=0

60
Q

semi definite constraint

A

symmetric matrix that is semidefinite, we can represent as a vector

61
Q

What type of quadratic constraints make a QCQP difficult to solve?

A 
Indefinite quadratic constraints
quadratic equalities (can encode boolean)
62
Q

epigraph - R^n -> R is a convex function iff

A

{x,t} exists R^n+1 |f(x)

63
Q

bounded to unbounded

A

p ≤ x ≤ q ⇐⇒
1
−1

x ≤

q
−p

64
Q

intersections preserve convexity

A

the union does not have to be convex

65
Q

CX

A

convex cost and constraints

66
Q

If maximum profit is p*, every feasible point of the LP yields

A

a lower bound for p*

67
Q

inequalities to equalities

A

add slack

f (x) ≤ 0 ⇐⇒ f (x) + s = 0 and s ≥ 0

68
Q

if lamda = 0, Q >=0, the ellipsoid x^TQx

A

degenerate. Stretches to infinity in direction vi

69
Q

SOCP

A

linear cost, second order cone constraints

70
Q

what are nodes in network flow problems

A

sources, relays, sinks

71
Q

LP has what kind of variables, constraints, cost function

A
  • continuous variables
  • linear constraints
  • linear cost funtion
72
Q

How to transform a convex piecewise linear function to linear function?

A

convert to epigraph form -

add extra decision variable t and turn cost into a constraint

73
Q

if Q is positive definite, then the quadratic form with extra affine terms

A

is a shifted ellipsoid

74
Q

Four combinations of general LP duality:

A
  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
Q

A function f (x1, . . . , xm) is affine in the variables

x1, . . . , xm if

A

if there exist constants b, a1, . . . , am such that

f (x1, . . . , xm) = a0 + a1x1 + · · · + amxm = a^T*x + b

76
Q

QCQP

A

convex quadratic cost and constraints

77
Q

level set

A

if f is a convex function, the set of all points satisfying f(x)

78
Q

Can you square both sides of second order cone?

A

Generally, no

79
Q

Optimization models categorized on:

A

types of variables, types of constraints, types of cost functions

80
Q

A matrix is totally unimodular if

A

every square matrix of A has a determinant of 0, 1, -1

81
Q

Transformation tricks

A 
convert min to max
reverse inequalities
equalities to inequalities
inequalities to equalities
unbounded to bounded
bounded to unbounded
bounded to non-negative
82
Q

SDP

A

linear cost, semidefinite constraints

83
Q

QCQP

A

Quadratically constrained quadratic program. has both quadratic cost and quadratic constraints

84
Q

convex functions

A 
affine
absolute value
quadratic
exponential
powers
negative entropy
norms
85
Q

the maximum of several linear functions is always convex. So we can blank it using the blank trick.

A

we can minimize it using the epigraph trick

86
Q

Where do quadratics commonly occur?

A 
as a regularization or penalty term
hard norm bounds on a decision variable
allow some tolerance in constraint satisfaction
energy quantities
covariance constraints
87
Q

minimizing the largest component is an LP

minimizint the sum of absolute values is an LP

A

minimizing the 2 norm is not an LP

88
Q

is x^TQx ever negative

A

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

89
Q

lambda is

A

the price item i is worth to us

90
Q

pareto curve

A

visualize tradoffs

91
Q

L infinity regularization

A

equalizing effect

92
Q

upper bound for p*

A

combining constraints in different ways. Create a multiplier for each constraint. Some of constraints must be

93
Q

LP

A

linear cost and linear constraints

94
Q

a^T*x = b

A

affine hyperplane

95
Q

changes in primal constraints are changes in dual _______

A

cost

96
Q

infeasible p* (maximization)

A

-∞

97
Q

hyperplanes are

A

subspaces

A hyperplane in R^n is a subspace of dimension n − 1.

98
Q

1-norm

A

minimize sum of the absolute values

99
Q

if ^x satisfies the normal equations, then ^x is a solution to the least-squares optimization problem

A

then ^x is a solution to the least-squares optimization problem

100
Q

if ellipsoid center of QCQP is infeasible then

A

the optimal point is on the boundary

101
Q

special cases of second order cones

A

if A=0, we have a linear constraint (hyperplane)

if c = 0 we can square both sides

102
Q

unbounded p* (maximization problem)

A

+∞

103
Q

Quadratic form

A

x^T*Qx when Q is a symmetric matrix

104
Q

Second order cone

A

set of points x exists in R^n satisfying

||Ax +b ||

105
Q

LP

A

real valued variables
affine cost function (c^T*x)
affine equations or inequalities
individual variables may have bounds or not

106
Q

if A is symmetric then

A

all eigenvalues of A are real

A is diagnalizable and its eigenvectors can be chosen to be orthogonal

107
Q

if ellipsoid center is infeasible, then

A

optimal point is on the boundary (but not always at a vertex)

108
Q

interior point

A

traverse the inside of the polyhedron and move towards best vertex

109
Q

If A is a TU and b is an integer vector, then the vertices of {x| Ax

A

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
Q

Quadratic program is like an LP but with a quadratic cost

A

min x^TPx + q^Tx +r

subj Ax

111
Q

transportation primal
edges have transportation cost, pick x to minimize total cost

if supply/demand is integral, flow will be integral

A

maximization of total prices of what to buy/sell commodities at each node

if edge cost is integral, prices will be integral

112
Q

• A vector-valued function F(x) is affine in x if there exists

A

a constant matrix A and vector b such that F(x) = Ax + b.

113
Q

LP solvers

A

simplex
interior point
blended

114
Q

How to get a polyhedral cone:

A

Begin with polyhedron Ax =0} is a polyhedral cone in (x,t) ∈ R ^n+1
slice t =1 is original polyhedron

115
Q

if p* and d* exist and are finite then

A

p=d

strong duality

116
Q

robust LP to account for uncertainty in some vectors

A

box constraint, ball constraint

117
Q

a change to the feasible set of the primal problem can change the optimal f and s but lambdas will not change

A

optimal f and s might change but lambdas will not

118
Q

every LP and SOCP a SDP

A

polyhedra and second-order cones are special cases of spectrahedra

Optimization (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions