# 优化总结

# 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