Welcome!

0 %
Yun Peng
A second-year Ph.D. student in CUHK
  • Chinese Name
    彭昀
  • Major
    Computer Science
  • City
    Hong Kong
  • Age
    21
  • Mail
    normal@yunpeng.work
Research Interest
Software Engineering
Artificial Intelligence
Computer Security

优化总结

April 16, 2021
Optimization Cheatsheet

Optimization Cheatsheet

Handout 1 Introduction

Basic Notions

Optimal Value: Is defined to be the greatest lower bound or infimum of the set

Global Minimizer: The such that

Note that optimal value can be finite even if global minimizer does not exist

Different Problems

LP Problems: is a linear function and is a set defined by linear inequalities

minimize subject to

Note that eualities can be transformed to inequalities by:

=>

Quadratic Programming (QP) Problems: is also a set defined by linear inequalities while ( is symmertric without loss)

Note that this is different from Quadratically Constrained Quadratic Programming Problems.

Semidefinite Programming (SDP) Problems:

inf subject to ,

Positive Semidefinte: or if for any

How to combine multiple constraints?

=>

 

Properties of Semidefinte Matrix

1)

Let , then and

Handout 2 Elements of Convex Analysis

Affine and Convex Sets

Affine Set:

Convex Set: and

Note that is convex.

Proposition 1: is not empty

1) is affine

2) Any affine combination of finite points in belongs to

3) is the translation of some linear subspace ; is of the form for some

Proposition 2: is arbitary

1) is convex

2) Any convex combination of points in belongs to

Examples of Convex Sets: Non-negative orthant, hyperplane, halfspaces, euclidean ball, ellipsoid, simplex, convex cone, positive semidefinte cone

Cone: if for every

Note that not every cone is convex and is a convex cone.

Affine Hull: The intersection of all affine subspaces containing , denoted by

Convex Hull: The intersection of all convex sets containing , denoted by . if is convex

Proposition 3:

1) is the set of all affine combinations of points in

2) is the set of all convex combinations of points in

Convexity-Preserving Operations

Affine Functions:

Note that translation (), projection (, ) and rotation () are all affine operations

Proposition 4: Affine functions operated on a convex set remains its convexity

Projection onto Closed Convex Sets

Note that Projection points do not always exist and are not always unique.

Note that every finite point set is closed since it has no limit points thus fulfill the conditon that every limit points belong to itself.

Theorem 4: If is non-empty, closed and convex, then for every , there exists a unique point that s closest to

Projection:

Weierstrass's Theorem: If is continuous on a compact set , then it attains its maximum and minimum on

Theorem 5: If is non-empty, closed and convex, we have iff and for all

Separation Theorems

Theorem 6 (Point-Set Separation): If is non-empty, closed and convex, is arbitary. Then there exists a such that

Theorem 7: A closed convex set is the intersection of all the halfspaces containing

Note that set-set separation does not always holds, example can be and

Theorem 8 (Set-Set Separation): If , is non-empty. closed and convex with . is bounded. Then there exists a such that

Basic Definitions and Propeerties of Convex Functions

Convex Functions:

Concave Functions: is convex

Epigraph:

Effective Domain:

Proposition 9: Let , it is convex iff is convex

Note that is also convex if is convex

Corollary 2: (Jensen's Inequality) Let , it is convex iff for any and such that

Convexity-Preserving Transformations

Theorem 11:

Non-Negative Combinations: is onvex if is convex and

Pointwise Supremum:

Affine Composition:

Composition with an Increasing Convex Function: is increasing on ,

Restriction on Lines: is convex iff is convex for any and

Differentiable Convex Functions

Theorem 12: is differentiable on the open set, then it is convex iff for all

Theorem 13: When is twice continuously differentiable on convex set . Then is convex on iff for

Non-Differentiable Convex Functions

Subgradient: is subgradient of at if , the set of is called subdifferetial of at and is denoted by

Theorem 14:

1) The convex function is differentiable at iff

2) Let be convex and be the directional derivative of at in the direction . Then is a non-empty compact convex set and for any

Calculus and Linear Algebra Preparations

Cachy-Schwarz Inequality:

Vector Norm:

1-Norm:

2-Norm:

p-Norm:

-Norm:

-Norm:

0-Norm: Nums of non-zero element of

Matrix Norm:

1-Norm:

2-Norm:

-Norm:

F-Norm:

Taylor's Formula:

Semidefinite:

<=>

Handout 3 Elements of Linear Programming

Basic Definitions and Properties

Polyhedron: The intersection of a finite set of halfspaces

Polytope: A bounded polyhedron

Note that a closed convex set is the intersection of all the halfspaces containing it but this does not mean that any closed convex set is a polyhedron

External Elements of a Polyheedron

Active Set: The index set of all constraints such that

Theorem 1: The following are equivalent:

1) There exists n vectors in the set that are linearly independent

2) The point is the unique solution to the following system of linear equations:

Basic Solution: The vector is called basic solution if there are n linearly independent active constraints to , if is in the polyhedron, then it is a basic feasible solution

Note that not every polyhedron has basic feasible solution

Line: A polyhedron contains a line if there exists and a vector such that for all

Theorem 3: Let is a non-empty polyhedron, then the following are equivalent:

1) has at least one vertex

2) does not contain a line

3) There exists n linearly independent vectors in

Existence of Optimal Solutions to Linear Programs

Theorem 4: Consider the LP . Suppose that has at least one vertex, then either the optimal value is or there exists a vertex that is optimal.

Note that there could be non-vertex optimal solutions but at least one vertex optimal solution exists

Corollary 1: Consider the LP . Suppose that is non-empty. Then either the optimal value is or there exists an optimal solution.

Standard LP:

minimize

subject to ,

Theorems of Alternatives

Theorem 5: (Farkas' Lemma) Let and be given. Then exactly one of the following systems has a solution:

1) ,

2) ,

Note that 2) is not a polyhedron since polyhedrons can not have strict inequalites

Corollary 2: (Gordan's Theorem) Let be given. Then exactly one of the following systems has a solution:

1)

2) , ,

LP Duality Theory

Primal Problem and Dual Problem:

(P) minimize

subject to ,

(D) maximize

subject to

Theorem 6: (LP Weak Duality) Let be feasible for (P) and be feasible for (D). Then we have .

Corollary 3:

1) If the optimal value of (P) is , then (D) must be infeasible

2) If the optimal value of (D) is , then (P) must be infeasible

3) Let and be feasible for (P) and (D). Suppose that the duality gap . Then and are optimal solutions to (P) and (D)

Note that if (P) is infeasible, it is possible that (D) is also infeasible

Theorem 7: (LP Strong Duality) Suppose that (P) has an optimal solution . Then (D) also has an optimal solution , and

Corollary 4: Suppose both (P) and (D) are feasible. Then both (P) and (D) have optimal solutions and their respective optimal values are equal

Theorem 8: (Complementory Slackness) and are optimal for their respective problems iff for

Handout 5 Elements of Conic Linear Programming

Introduction

Pointed Cone:

1) is non-empty and closed under addition

2) is a cone

3) is pointed, if and , then

A pointed cone is automatically convex

Examples of Pointed Cone:

1) Non-Negative Orthant:

2) Lorentz Cone/Second-Order Cone/Ice Cream Cone:

3) Positive Semidefinte Cone:

Note that these three cone are all self-dual

Frobenius inner product:

Proposition 1: Let be finite-dimensional Euclidean spaces and be closed pointed cone with non-empty interiors, where . Then the set is a closed pointed cone with non-empty interior.

Conic Linear Programming

Standard Form:

= inf

subject to for

Dual:

= sup

subject to

Proposition 2: Let be a non-empty set. Then the following hold:

1) The set is a closed convex cone

2) If is a closed convex cone, then so is

3) If has a non-empty interior, then is pointed

4) If is a closed pointed cone, then has a mon-empty interior

Examples:

Linear Programming:

(P) inf

subject to for

(D) sup

subject to

,

Second-Order Cone Programming (SOCP):

(P) inf

subject to for

(D) sup

subject to

Semidefinite Programming (SDP):

(P) inf

subject to for

(D) sup

subject to

,

Theorem 1: (CLP Weak Duality) Let be feasible for (P) and