Welcome!

0 %
Yun Peng
Principal Engineer at Huawei HK Research Center
  • Chinese Name
    彭昀
  • Major
    Computer Science
  • City
    Hong Kong
  • Age
    24
  • Email
    normal@yunpeng.work
Research Interest
Software Engineering
Artificial Intelligence

优化总结

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 be feasible for (D). Then

Theorem 2: (CLP Farkas Lemma) Suppose that there exists such that , then exactly one of the following holds:

1) for ,

2)

Theorem 3: (CLP Strong Duality)

1) Suppose (P) is bounded below and strictly feasible. Then we have and there exists a feasible solution to (D) such that

2) Suppose (D) is bonded above and stictly feasible. Then we have and there exists a feasible solution to (D) such that

3) Suppose (P) and (D) are bounded and strictly feasible. Then given a feasible solution to (p) and to (D), the following are equivalent:

  • They are optimal solutions
  • The duality gap is zero
  • We have complementary slackness:

Handout 6 Some Applications of Conic Linear Programming

Quadratically Constrained Quadratic Optimization

Original Problem:

minimize ` minimize

subject to for subject to , ,

Semidefinite Relaxation:

minimize

subject to ,

handout 7 Optimality Conditions and Lagrangian Duality

Unconstrained Optimizationm Problems

Proposition 1: Suppose that is continuously differentiable at . If there exists a such that , then there exists an such that for all . In other words, is a descent direction of at .

Corollary 1: (First Order Necessary Condition for Unconstrained Optimization) Suppose that is continuously differentiable at . If is a local minimum, then we have . In particular, we have .

Proposition 2: Let be an open convex set. Suppose that is convex on and continuously differentiable at . Then, is a global minimum in iff .

Proposition 4: (Second Order Sufficient Condition for Unconstrained Optimization) Suppose that is twice continuously differentiable at . If and is positive definite, then is a local minimum.

Constrained Optimization Problems

Problem:

inf

subject to , for

, for

Theorem 2: (The Fritz John Necessary Conditions) Let be a local minimum of the above problem. Then there exists , , and such that

, for

, for

Theorem 3: (The Karush-Kuhn-Tucker Necessary Conditions) Let ​ be a local minimum of the above problem. Let be the index set for active constraints. Suppose that is regular which means and of vectors is linearly independent. Then there exist and such that

, for

, for

Theorem 4: Suppose that and are affine. Let be a local minimum and . Suppose that the Slater condition is satisfied which means there exists an such that for . Then satisfies the KKT conditions.

Theorem 5: Suppose that are concave and are affine. Let be a local minimum. Then satisfies the KKT conditions.

Theorem 6: Suppose that is open and convex, are convex on , and are affine. Suppose that is a solution to the KKT conditions (includes primal conditions), then is an optimal solution.

, for

, for

, for

, for

Lagrangian Duality

Primal Problem:

= inf

subject to , for

, for

Dual Problem:

= sup

where

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

Theorem 8: (Strong Duality Theorem) is a saddle point of the Lagrangian function associated with (P) iff the duality gap between (P) and (D) is zero, is optimal for (P), is optimal for (D)

Saddle Point:

1)

2)

3) For all and , we have

Posted in TechnologyTags:
Write a comment
© 2024 All Rights Reserved.