C20 convex optimisation Flashcards
(40 cards)
Q: What is an optimization problem in its most general form?
A: Minimize f0(x) subject to fi(x) <= 0 for i from 1 to m and hj(x) = 0 for j from 1 to p with decision variable x in R^n
Q: List the four possible outcomes when trying to solve an optimization problem.
A: Finite optimum infeasible unbounded or finite infimum without a minimizer
Q: Define active inactive and redundant constraints.
A: Active means fi(x)=0 at the point inactive means fi(x)<0 at the point redundant means removing the constraint leaves the feasible set unchanged
Q: Give the standard form of a feasibility problem.
A: Find x such that fi(x)<=0 and hj(x)=0 which is equivalent to minimizing 0 under those constraints
Q: Write the canonical form of a linear program LP.
A: Minimize c^T x subject to Gx <= h and Ax = b with x in R^n
Q: Write the canonical form of a convex quadratic program QP.
A: Minimize 0.5 x^T P x + q^T x subject to Gx <= h and Ax = b with P positive semidefinite
Q: What is a mixed integer linear program MILP.
A: An LP in which some or all components of x must be integer or binary in addition to the linear constraints
Q: Why is modeling crucial in optimization.
A: It selects variables expresses objectives and constraints accurately and balances realism with solver tractability
Q: State the conditions for a problem to be a convex optimization problem.
A: Convex domain convex objective convex inequality functions and affine equality constraints
Q: Provide four standard examples of convex sets.
A: Affine subspace polyhedron norm ball and positive semidefinite cone
Q: Define the convex hull of a set S.
A: The set of all convex combinations of finitely many points in S that is sum lambda_i x_i with lambda_i >= 0 and sum lambda_i = 1
Q: Is the union of two convex sets always convex.
A: No because the line segment between one point in each set may lie outside the union
Q: Define a cone and a convex cone.
A: A cone K satisfies theta x in K for all theta>0 and x in K and it is convex if it also contains every conic combination of its points
Q: Give an example of a non convex cone.
A: The two dimensional wedge formed by two rays that excludes the region between those rays
Q: What is a polytope.
A: A bounded polyhedron equivalently the convex hull of a finite set of vertices
Q: Explain the relation between halfspaces and hyperplanes.
A: A hyperplane is the set where a^T x = b and each corresponding halfspace is the set where a^T x <= b or a^T x >= b
Q: State the definition of a convex function using the chord condition.
A: f is convex if f(lambda x + (1-lambda) y) <= lambda f(x) + (1-lambda) f(y) for all x y and lambda in [0 1]
Q: Give the first order condition for convexity of a differentiable function.
A: f(y) >= f(x) + grad f(x)^T (y - x) for all x and y
Q: Give the second order condition for convexity of a twice differentiable function.
A: The Hessian matrix grad^2 f(x) is positive semidefinite for every x in the domain
Q: Define the epigraph of a function.
A: The set of points (x t) such that t >= f(x)
Q: Give three common convex functions and one concave function.
A: Convex examples are affine functions norms and exp(x) and a concave example is log(x) on positive reals
Q: Why is any norm convex.
A: Because it satisfies the triangle inequality which implies the chord condition
Q: List five operations that preserve convexity of functions.
A: Nonnegative weighted sums affine composition pointwise maximum supremum over parameters and partial minimization
Q: Show how minimizing the L1 norm can be written as an LP.
A: Introduce t and minimize sum t_i subject to -t <= Ax - b <= t and t_i >= 0
