293. Convex Analysis

Difficulties of NLP

293.0.0.1. Convexity

Convex Set

If for whatever two points you select in the set, the line segment connecting them also lies in the set, then the set is convex

A set is convex if

for all and

Convex Function

For a convex domain , a function is convex over if

for all and

Concave Function

For a convex domain , a function is concave over if is convex

Global Optimality of Convext Functions

Proposition 1. For a convex (concave) function over a convex doain , a local minimum (maximum) is a global minimum (maximum)

Two conditions:

Proof

Suppose a local minimum is not a global minimum and there exists such that . Consider a small enough such that satisfies . Such exists because is a local minimum. Now, note that

Which violates the fact that is convex. Therefore, by contradiction, the local minimum must be a global minimum.

Minimize a concave function

Proposition 2: For a concave function that has a global minimum over a convex feasible region, there exists a global minimum that is an extreme point

Extreme point: In convex analysis, an extreme point of a convex set is a point in that cannot be expressed as a strict convex combination of two other distinct points in

Special Case: LP

When we minimize over a convez feasible region :

For any LP we have both

Proposition 3. The feasible region of an LP is convex

The intersections of convex sets are convex

Proposition 4. A linear function is both convex and concave

Proof:

Let be a linear function, , then:

Convex Programming

Consider a general NLP

If:

A local minimum is a global minimum

Definition 0: Convex Program (CP)

An NLP is convex if its feasible region is convex and its objective function is convex over the feasible region

Convex Programming:

Subject to a convex feasible region

Local min = Global min

For an NLP

if and s are all convex functions, the NLP is a Convex Program

Proof:

We only need to prove that the feasible region is convex, which is implied if is convex for all . For two points and an arbitrary , we have

Which implies that is convex. repeating this argument for all completes the proof

If each constraint independently given a convex feasible region, then their intersection is convex

Definition 0: Affine Combination

An affine combination of points , is any point of the form:

where the coefficients sum to 1:

This is like a linear combination, but with the extra condition that the weights add up to 1.

For a twice differentiable function over an interval :

First order condition (FOC)

Example

Economic Order Quantity (EOQ)

Determine the order quantity in each order

  • Demand is deterministic and occurs at a constant rate
  • Each order incurs a fixed cost (independent of the order size)
  • No shortage allowed
  • Lead time is zero
  • Holding cost is proportional to the average inventory
  • Constant holding cost

Parameters:

  • : annual demand (units/year)
  • : unit ordering cost ($/order)
  • : annual holding cost ($/unit/year)
  • : unit purchase cost ($/unit)

Decision Variable:

  • : order quantity (units/order)

Objective:

  • Minimize the total annual cost

Average inventory level:

Annual holding cost:

Annual purchase cost:

Annual ordering cost:

NLP, since does not depend on it does not affect the minimizer:

For:

we have

and

Since a twice differentiable function is convex If

and

we have

Therefore, is convex

Let be the quantity satisfying the FOC:

Implications:

  • If order cost increases, order quantity increases
  • If demand increases, order quantity increases
  • If holding cost increases, order quantity decreases

293.0.1. Multivariate Convex Analysis

An optimal solution either:

If a NLP is a CP, a feasible point satisfying the FOC is optimal (any local minimum is a global minimum)

For a function , its th partial derivative is

For a twice differentiable function , if all second order partial derivatives are continuous:

for all and .

Single variate case:

Multivariate case:

Example

You may ask:

  • What is the gradient at a point:
  • What is the Hessian at a point:

Single Variate Function
  • is convex in if for all
  • is an interior local minimum if
  • If is convex in , is a global minimum iff

Multi Variate Function
  • is convex in a convex set if is positive semi-definite for all
  • is an interior local minimum if
  • If is convex in a convex set , is a global minimum iff

Definition 0: Positive Semi-Definite (PSD) Matrix

A symmetric matrix is positive semi-definite if for all

Example

Semi-Definite Matrix

Given a function , when is its Hessian PSD?

For a symmetric matrix , the following statements are equivalent:

‘s level- principal minors is the determinant of a submatrix whose diagonal is a subset of ‘s diagonal.

A sufficient condition is for ‘s leading principl minors to all positive

For a function :

  1. Find Hessian
  2. Find eigenvalues or principal minors of
  3. Determine over what region is PSD

The function is convex over that region

Example

Find eigenvalues

Or find leading principal minors

So is PSD and thus is a CP.

The FOC requires and

I.e.,

Example
  • 1st leading principle minor ()
  • 2nd leading principal minor ()

Therefore, the function is convex iff

Example

Two-Product Pricing

A retailer sells product 1 and 2 at prices and . For product the demand is:

where and . The retailer sets and to maximize its total profit.

If and are substitutes of one another then the price of one will affect the demand of the other.

  1. Why ?

If : the other product’s price will have the equal or greater impact on your own product’s price

If : Complimentary products (rather than substitutes), the higher the other product’s price, the lower our demand

  1. Formulate problem

Let

  1. Is it a CP?

Which is PSD if since

  • 1st leading principle minor
  • 2nd leading principle minor ()

Therefore is convex and , the objective function is concave

The problem is a CP

  1. Solve problem

requires:

So,

  1. How does optimal prices change with and ?

When

  • increases, the two prices increase: price of product increases when demand increases
  • increases, the two prices increase: effective demand becomes larger
Example

Question 1

For each of the following sets, select all that are convex:

✅ , a disk of radius 2, is convex and the lines are also convex

The intersection of convex sets is convex

❌ Integer programs are never convex in the usual sense, because the feasible set of integers is discrete

✅ , a -dimensional sphere (hypersphere) of radius 2, is convex and the lines are also convex

The intersection of convex sets is convex

✅ is a linear function () so is also affine and is therefore convex

❌ and

Question 2

For each of the following functions, select all that are convex over the given region:

  1. for

❌

✅

  1. for

❌

  1. where ,

✅

  1. , where

✅

Question 3

For the NLP

which of the following statements is correct?

  1. This is a convex program.

❌

  1. There are two local minimizers.

✅

  1. The unique global minimizer is a boundary point.

❌

  1. This program is unbounded.

❌

  1. None of the above.

❌

Question 4

For each of the following matrices, select all that are positive semi-definite:

✅

❌

✅

✅

❌

Question 5

For the following statements, select all that are incorrect:

  1. An optimal solution to a linear program must be a boundary point.

❌ not guaranteed if the objective is constant over the feasible region

  1. An optimal solution to a linear program must be an extreme point.

✅

  1. An optimal solution to a nonlinear program can be an interior point.

❌

  1. An optimal solution to a nonlinear program must be an interior point.

✅

  1. A global optimal solution to a nonlinear program must be a local optimal solution.

❌