Convex Analysis

296. Convex Analysis

Difficulties of NLP

A local minimum is not always a global minimum

An optimal solution may not be an extreme point optimal solution

296.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

𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2} \in 𝐹

for all $𝜆 \in [0, 1]$ and $𝑥_{1}, 𝑥_{2} \in 𝐹$

Convex Function

For a convex domain $𝐹 \subseteq ℝ^{𝑛}$ , a function $𝑓 : ℝ^{𝑛} \to ℝ$ is convex over $𝐹$ if

𝑓 (𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}) \leq 𝜆 𝑓 (𝑥_{1}) + (1 - 𝜆) 𝑓 (𝑥_{2})

for all $𝜆 \in [0, 1]$ and $𝑥_{1}, 𝑥_{2} \in 𝐹$

Concave Function

For a convex domain $𝐹 \in ℝ^{𝑛}$ , a function $𝑓 : ℝ^{𝑛} \to ℝ$ 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:

Function needs to be convex
Domain (feasible region) need to be convex

Proof

Suppose a local minimum $𝑥^{'}$ is not a global minimum and there exists $𝑥^{″}$ such that $𝑓 (𝑥^{″}) < 𝑓 (𝑥^{'})$ . Consider a small enough $𝜆 > 0$ such that $\bar{𝑥} = 𝜆 𝑥^{″} + (1 - 𝜆) 𝑥^{'}$ satisfies $𝑓 (\bar{𝑥}) > 𝑓 (𝑥^{'})$ . Such $\bar{𝑥}$ exists because $𝑥^{'}$ is a local minimum. Now, note that

\begin{aligned} 𝑓 (\bar{𝑥}) & = 𝑓 (𝜆 𝑥^{″} + (1 - 𝜆) 𝑥^{'}) \\ > 𝑓 (𝑥^{'}) \\ = 𝜆 𝑓 (𝑥^{'}) + (1 - 𝜆) 𝑓 (𝑥^{'}) \\ > 𝜆 𝑓 (𝑥^{″}) + (1 - 𝜆) 𝑓 (𝑥^{'}) \end{aligned}

Which violates the fact that $𝑓 (\cdot)$ 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 $𝑓 (\cdot)$ over a convez feasible region $𝐹$ :

If $𝑓 (\cdot)$ is convex, search for a local minimum
If $𝑓 (\cdot)$ is concave, search among extreme points of $𝐹$

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 $𝑓 : ℝ^{𝑛} \to ℝ$ is both convex and concave

Proof:

𝑓 (𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}) = 𝜆 𝑓 (𝑥_{1}) + (1 - 𝜆) 𝑓 (𝑥_{2})

Let $𝑓 (𝑥) = 𝑐^{𝑇} 𝑥 + 𝑏$ be a linear function, $𝑐 \in ℝ^{𝑛}, 𝑏 \in ℝ$ , then:

\begin{aligned} 𝑓 (𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}) & = 𝑐^{𝑇} (𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}) + 𝑏 \\ = 𝜆 (𝑐^{𝑇} 𝑥_{1} + 𝑏) + (1 - 𝜆) (𝑐^{𝑇} 𝑥_{2} + 𝑏) \\ = 𝜆 𝑓 (𝑥_{1}) + (1 - 𝜆) 𝑓 (𝑥_{2}) \end{aligned}

Convex Programming

Consider a general NLP

\begin{aligned} min_{𝑥 \in ℝ^{𝑛}} & 𝑓 (𝑥) \\ 𝑠 . 𝑡 . & 𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚 \end{aligned}

If:

The feasible region $𝐹 = {𝑥 \in ℝ^{𝑛} | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚}$ (intersection of all the regions satisfying the constraints)
$𝑓$ is convex over $𝐹$

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:

Minimizing convex function
Maximizing concave function

Subject to a convex feasible region

Local min = Global min

For an NLP

min_{𝑥 \in ℝ^{𝑛}} {𝑓 (𝑥) | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} \forall 𝑖 - 1, \dots, 𝑚}

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 $𝐹_{𝑖} = {𝑥 \in ℝ^{𝑛} | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖}}$ is convex for all $𝑖$ . For two points $𝑥_{1}, 𝑥_{2} \in 𝐹_{𝑖}$ and an arbitrary $𝜆 \in [0, 1]$ , we have

\begin{aligned} 𝑔_{𝑖} (𝜆 𝑥_{1} + (1 - 𝜆) 𝑥_{2}) & \leq 𝜆 𝑔_{𝑖} (𝑥_{1}) + (1 - 𝜆) 𝑔_{𝑖} (𝑥_{2}) \\ \leq 𝜆 𝑏_{𝑖} + (1 - 𝜆) 𝑏_{𝑖} = 𝑏_{𝑖} \end{aligned}

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 $𝑥_{1}, 𝑥_{2}, \dots, 𝑥_{𝑘} \in ℝ^{𝑛}$ , is any point of the form:

𝛼 1 𝑥_{1} + 𝛼_{2} 𝑥_{2} + \dots + 𝛼_{𝑘} 𝑥_{1} + 𝑥_{𝑘} where the coefficients sum to 1: 𝛼_{1} + 𝛼_{2} + \dots + 𝛼_{𝑘} = 1 This is like a linear combination, but with the extra condition that the weights add up to 1.For a twice differentiable function 𝑓 : ℝ \to ℝ over an interval (𝑎, 𝑏) :𝑓 is convex over (𝑎, 𝑏) iff 𝑓^{″} (𝑥) > 0 for all 𝑥 \in (𝑎, 𝑏) \bar{𝑥} is a local minimum over (𝑎, 𝑏), iff 𝑓^{'} (𝑥) = 0 If 𝑓 is concave over (𝑎, 𝑏), 𝑥^{*} is a global minimum over (𝑎, 𝑏) iff 𝑓^{'} (\bar{𝑥}) = 0First order condition (FOC) 𝑓^{'} (𝑥) = 0FOC is necessary for local optimality FOC is sufficient for global optimality if 𝑓 is convexExample 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: \frac{𝑞}{2} Annual holding cost: 𝐻 = ℎ (\frac{𝑞}{2}) = \frac{ℎ 𝑞}{2} Annual purchase cost: 𝑝 𝐷 Annual ordering cost: 𝑂 = (\frac{𝐷}{𝑞}) 𝐾 = \frac{𝐷 𝐾}{𝑞} NLP, since 𝑝 𝐷 does not depend on 𝑞 it does not affect the minimizer: \begin{aligned} min_{𝑞 > 0} 𝑓 (𝑞) & = (\frac{𝐷}{𝑞}) 𝐾 + (\frac{𝑞}{2}) ℎ \\ = \frac{𝐷 𝐾}{𝑞} + \frac{𝑞 ℎ}{2} \end{aligned} For: 𝑇 𝐶 (𝑞) = \frac{𝐾 𝐷}{𝑞} + \frac{ℎ 𝑞}{2} we have 𝑇 𝐶^{'} (𝑞) = - \frac{𝐾 𝐷}{𝑞^{2}} + \frac{ℎ}{2} and 𝑇 𝐶^{″} (𝑞) = \frac{2 𝐾 𝐷}{𝑞^{3}} Since a twice differentiable function is convex If 𝑓^{″} (𝑥) > 0 \forall 𝑥 \in (𝑎, 𝑏) and 𝐾 > 0, 𝐷 > 0, 𝑞 > 0 we have 𝑇 𝐶^{″} (𝑞) = \frac{2 𝐾 𝐷}{𝑞^{3}} > 0 Therefore, 𝑇 𝐶 (𝑞) is convex Let 𝑞^{*} be the quantity satisfying the FOC: 𝑇 𝐶^{'} (𝑞^{*}) = - \frac{𝐾 𝐷}{{(𝑞^{*})}^{2}} + \frac{ℎ}{2} = 0 \Rightarrow 𝑞^{*} = \sqrt{\frac{2 𝐾 𝐷}{ℎ}} Implications: If order cost 𝐾 increases, order quantity 𝑞^{*} increases If demand 𝐷 increases, order quantity 𝑞^{*} increases If holding cost ℎ increases, order quantity 𝑞^{*} decreases296.0.1. Multivariate Convex AnalysisAn optimal solution either:Satisfies the FOC Lies on the boundary of the feasible regionIf a NLP is a CP, a feasible point satisfying the FOC is optimal (any local minimum is a global minimum)For a function 𝑓 : ℝ^{𝑛} \to ℝ, its 𝑖 th partial derivative is \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{𝑖}}For a twice differentiable function 𝑓 : ℝ^{𝑛} \to ℝ, if all second order partial derivatives are continuous:\frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{𝑖} 𝜕 𝑥_{𝑗}} = \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{𝑗} 𝜕 𝑥_{𝑖}}for all 𝑖 = 1, \dots, 𝑛 and 𝑗 = 1, \dots, 𝑛 .Single variate case:For 𝑓 : ℝ \to ℝ, 𝑓 is convex iff 𝑓^{″} (𝑥) \geq 0 for all 𝑥Multivariate case:\nabla 𝑓 (𝑥) = [\begin{matrix} \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{1}} \\ ⋮ \\ \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{𝑛}} \end{matrix}] \nabla^{2} 𝑓 (𝑥) = 𝐻_{𝑓} = [\begin{matrix} \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{1}^{2}} & \dots & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{1} 𝜕 𝑥_{𝑛}} \\ ⋮ & ⋱ & ⋮ \\ \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{𝑛} 𝜕 𝑥_{1}} & \dots & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{𝑛}^{2}} \end{matrix}]Example 𝑓 (𝑥_{1}, 𝑥_{2}, 𝑥_{3}) = 𝑥_{1}^{2} + 𝑥_{2} 𝑥_{3} + 𝑥_{3}^{3} \nabla 𝑓 (𝑥) = [\begin{matrix} \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{1}} \\ \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{2}} \\ \frac{𝜕 𝑓 (𝑥)}{𝜕 𝑥_{3}} \end{matrix}] = [\begin{matrix} 2 𝑥_{1} \\ 𝑥_{3} \\ 𝑥_{2} + 3 𝑥_{3}^{2} \end{matrix}] \nabla^{2} 𝑓 (𝑥) = [\begin{matrix} \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{1}^{2}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{1} 𝜕 𝑥_{2}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{1} 𝜕 𝑥_{3}} \\ \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{2} 𝜕 𝑥_{1}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{2}^{2}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{2} 𝜕 𝑥_{3}} \\ \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{3} 𝜕 𝑥_{1}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{3} 𝜕 𝑥_{2}} & \frac{𝜕^{2} 𝑓 (𝑥)}{𝜕 𝑥_{3}^{2}} \end{matrix}] = [\begin{matrix} 2 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 6 𝑥_{3} \end{matrix}] You may ask: What is the gradient at a point: \nabla 𝑓 (3, 2, 1) What is the Hessian at a point: \nabla^{2} 𝑓 (3, 2, 1)Single Variate Function 𝑓 : ℝ \to ℝ 𝑓 is convex in [𝑎, 𝑏] if 𝑓^{″} (𝑥) \geq 0 for all 𝑥 \in [𝑎, 𝑏] \bar{𝑥} is an interior local minimum if 𝑓^{'} (\bar{𝑥}) = 0 If 𝑓 is convex in [𝑎, 𝑏], 𝑥^{*} is a global minimum iff 𝑓^{'} (𝑥^{*}) = 0 Multi Variate Function 𝑓 : ℝ^{𝑛} \to ℝ 𝑓 is convex in a convex set 𝐹 \subseteq ℝ^{𝑛} if \nabla^{2} 𝑓 (𝑥) is positive semi-definite for all 𝑥 \in 𝐹 \bar{𝑥} is an interior local minimum if \nabla 𝑓 (\bar{𝑥}) = 𝟎 If 𝑓 is convex in a convex set 𝐹, 𝑥^{*} is a global minimum iff \nabla 𝑓 (𝑥^{*}) = 0Definition 0: Positive Semi-Definite (PSD) MatrixA symmetric matrix 𝐴 is positive semi-definite if 𝐱^{𝑇} 𝐴 𝐱 \geq 0 for all 𝐱 \in ℝ^{𝑛}Example Semi-Definite Matrix 𝐴 = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] \begin{aligned} 𝑥^{𝑇} 𝐴 𝑥 & = [\begin{matrix} 𝑥_{1} & 𝑥_{2} \end{matrix}] [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] [\begin{matrix} 𝑥_{1} \\ 𝑥_{2} \end{matrix}] \\ = 2 𝑥_{1}^{2} + 2 𝑥_{1} 𝑥_{2} + 2 𝑥_{2}^{2} \\ = 2 {(𝑥_{1} + 𝑥_{1})}^{2} + 𝑥_{1}^{2} + 𝑥_{2}^{2} \geq 0 \end{aligned}Given a function 𝑓, when is its Hessian \nabla^{2} 𝑓 PSD?For a symmetric matrix 𝐴, the following statements are equivalent:𝐴 is positive semi-definite All eigenvalues of 𝐴 are non-negative All principal minors of 𝐴 are non-negative𝐴 ’s level- 𝑘 principal minors is the determinant of a 𝑘 \times 𝑘 submatrix whose diagonal is a subset of 𝐴 ’s diagonal.A sufficient condition is for 𝐴 ’s leading principl minors to all positiveFor a function 𝑓 :Find Hessian \nabla^{2} 𝑓 (𝑥) Find eigenvalues or principal minors of \nabla^{2} 𝑓 (𝑥) Determine over what region \nabla^{2} 𝑓 (𝑥) is PSDThe function is convex over that regionExample min_{𝑥 \in ℝ^{2}} 𝑓 (𝑥_{1}, 𝑥_{2}) 𝑓 (𝑥_{1}, 𝑥_{2}) = 𝑥_{1}^{2} + 𝑥_{2}^{2} + 𝑥_{1} 𝑥_{2} - 2 𝑥_{1} - 4 𝑥_{2} \nabla 𝑓 (𝑥) = [\begin{matrix} 2 𝑥_{1} + 𝑥_{2} - 2 \\ 𝑥_{1} + 2 𝑥_{2} - 4 \end{matrix}] \nabla^{2} 𝑓 (𝑥) = [\begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix}] Find eigenvalues 𝐴 𝑥 = 𝜆 𝑥 ⟺ (𝐴 - 𝜆 𝐼) 𝑥 = 0 ⟺ det (𝐴 - 𝜆 𝐼) = 0 | \begin{matrix} 2 - 𝜆 & 1 \\ 1 & 2 - 𝜆 \end{matrix} | = 0 ⟺ 3 - 4 𝜆 + 𝜆^{2} = 0 ⟺ 𝜆 = 1 or 3 Or find leading principal minors | \begin{matrix} 2 \end{matrix} | = 2 and | \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} | = 3 So \nabla^{2} 𝑓 (𝑥_{1}, 𝑥_{2}) is PSD and thus {min}_{𝑥 \in ℝ^{2}} 𝑓 (𝑥_{1}, 𝑥_{2}) is a CP. The FOC requires 2 𝑥_{1}^{*} + 𝑥_{2}^{*} - 2 = 0 and 𝑥_{1}^{*} + 2 𝑥_{2}^{*} - 4 = 0 I.e., (𝑥_{1}^{*}, 𝑥_{2}^{*}) = (0, 2)Example min_{𝑥 \in ℝ^{2}} 𝑓 (𝑥_{1}, 𝑥_{2}) 𝑓 (𝑥_{1}, 𝑥_{2}) = 𝑥_{1}^{3} + 4 𝑥_{1} 𝑥_{2} + \frac{1}{2} 𝑥_{2}^{2} + 𝑥_{1} + 𝑥_{2} \nabla^{2} 𝑓 (𝑥) = [\begin{matrix} 6 𝑥_{1} & 4 \\ 4 & 1 \end{matrix}] 1st leading principle minor 6 𝑥_{1} \geq 0 (𝑥_{1} \geq 0) 2nd leading principal minor 6 𝑥_{1} - 16 \geq 0 (𝑥_{1} \geq \frac{8}{3}) 1 \geq 0 Therefore, the function is convex iff 𝑥_{1} \geq \frac{8}{3}Example Two-Product Pricing A retailer sells product 1 and 2 at prices 𝑝_{1} and 𝑝_{2} . For product 𝑖 the demand 𝑞_{𝑖} is: \begin{matrix} 𝑞_{1} = 𝑎 - 𝑝_{1} + 𝑏 𝑝_{2} \\ 𝑞_{2} = 𝑎 - 𝑝_{2} + 𝑏 𝑝_{1} \end{matrix} where 𝑎 > 0 and 𝑏 \in [0, 1) . The retailer sets 𝑝_{1} and 𝑝_{2} to maximize its total profit. If 𝑝_{1} and 𝑝_{2} are substitutes of one another then the price of one will affect the demand of the other. Why 𝑏 \in [0, 1) ? If 𝑏 \geq 1 : the other product’s price will have the equal or greater impact on your own product’s price If 𝑏 < 0 : Complimentary products (rather than substitutes), the higher the other product’s price, the lower our demand Formulate problem max_{𝑝_{1}, 𝑝_{2}} 𝑝_{1} \underset{𝑞_{1}}{\underset{⏟}{(𝑎 - 𝑝_{1} + 𝑏 𝑝_{2})}} + 𝑝_{2} \underset{𝑞_{2}}{\underset{⏟}{(𝑎 + 𝑏 𝑝_{1} - 𝑝_{2})}} Let 𝑓 (𝑝) = - [𝑝_{1} (𝑎 - 𝑝_{1} + 𝑏 𝑝_{2}) + 𝑝_{2} (𝑎 + 𝑏 𝑝_{1} - 𝑝_{2}) Is it a CP? \nabla^{2} 𝑓 (𝑝) = [\begin{matrix} 2 & - 2 𝑏 \\ - 2 𝑏 & 2 \end{matrix}] Which is PSD if 𝑏 \in [0, 1) since 1st leading principle minor 2 \geq 0 2nd leading principle minor 4 - 4 𝑏^{2} (4 (1 - 𝑏) (1 + 𝑏) \geq 0) Therefore 𝑓 (𝑝) is convex and - 𝑓 (𝑝), the objective function is concave The problem is a CP Solve problem \nabla 𝑓 (𝑝) = 0 requires: - 𝑎 + 2 𝑝_{1} - 2 𝑏 𝑝_{2} = 0 - 𝑎 + 2 𝑝_{2} - 2 𝑏 𝑝_{1} = 0 So, 𝑝_{1} = 𝑝_{2} = \frac{𝑎}{2 (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 largerExample Question 1 For each of the following sets, select all that are convex: 𝑆 = {(𝑥_{1}, 𝑥_{2}) \in ℝ^{2} | 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4, 𝑥_{1} \geq 0, 𝑥_{2} \leq 0} ✅ 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4, a disk of radius 2, is convex and the 𝑥_{1} \geq 0, 𝑥_{2} \leq 0 lines are also convex The intersection of convex sets is convex 𝑆 = {(𝑥_{1}, 𝑥_{2}) \in ℤ^{2} | 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4, 𝑥_{1} \geq 0, 𝑥_{2} \leq 0} ❌ Integer programs are never convex in the usual sense, because the feasible set of integers is discrete 𝑆 = {𝑥 \in ℝ^{𝑛} | \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2} \leq 4, 𝑥_{1} \geq 0, 𝑥_{2} \leq 0} ✅ \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖}^{2} \leq 4, a 𝑛 -dimensional sphere (hypersphere) of radius 2, is convex and the 𝑥_{1} \geq 0, 𝑥_{2} \leq 0 lines are also convex The intersection of convex sets is convex 𝑆 = {𝑥 \in ℝ^{𝑛} | 𝑥_{1} + 𝑥_{2} = 10 (𝑥_{3} + 𝑥_{4})} where 𝑛 \geq 4 ✅ ℎ (𝑥) is a linear function (ℎ (𝑥) = 𝑥_{1} + 𝑥_{2} - 10 𝑥_{3} - 10 𝑥_{4}) so ℎ (𝑥) is also affine and is therefore convex 𝑆 = {𝑥 \in ℝ^{𝑛} | {max}_{𝑖 = 1, \dots, 𝑛} {𝑥_{𝑖}} = 10 {min}_{𝑖 = 1, \dots, 𝑚} {𝑥_{𝑖}}} ❌ min (𝑥) and max (𝑥) Question 2 For each of the following functions, select all that are convex over the given region: 𝑓 (𝑥) = 2 𝑥^{3} - 𝑥^{2} - 2 𝑥 + 1 for 𝑥 \in ℝ 𝑓^{'} (𝑥) = 6 𝑥^{2} - 2 𝑥 - 2 𝑓^{″} (𝑥) = 12 𝑥 - 2 ❌ 𝑓 (𝑥) = {\begin{cases} - 𝑥 if 𝑥 < 1 \\ - 1 if 𝑥 \geq 1 \end{cases} for 𝑥 \in ℝ ✅ 𝑓 (𝑥) = 𝑥_{1}^{2} - 4 𝑥_{1} 𝑥_{2} + 3 𝑥_{2}^{2} + 3 𝑥_{1} + 4 𝑥_{2} for 𝑥 \in ℝ^{2} ❌ 𝑓 (𝑥) = \sum_{𝑖 = 1}^{𝑛} {(𝑥_{𝑖} - 𝑎)}^{2} where 𝑎 > 0, 𝑥 \in ℝ^{𝑛} ✅ 𝑓 (𝛼, 𝛽) = \sum_{𝑖 = 1}^{𝑛} {(𝛼 + 𝛽 𝑥_{𝑖} - 𝑦_{𝑖})}^{2}, where 𝑥_{𝑖}, 𝑦_{𝑖}, 𝛼, 𝛽 \in ℝ ✅ Question 3 For the NLP \begin{aligned} min & 2 𝑥^{3} - 𝑥^{2} - 2 𝑥 + 1 \\ 𝑠 . 𝑡 . & 𝑥 \geq - 1 \end{aligned} which of the following statements is correct? This is a convex program. ❌ There are two local minimizers. ✅ The unique global minimizer is a boundary point. ❌ This program is unbounded. ❌ None of the above. ❌ Question 4 For each of the following matrices, select all that are positive semi-definite: 𝐴 = [\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}] ✅ 𝐴 = [\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{matrix}] ❌ 𝐴 = [\begin{matrix} 1 & 2 & 3 \\ 0 & 3 & 1 \\ 0 & 0 & 2 \end{matrix}] ✅ 𝐴 = [\begin{matrix} 1 & 2 & 3 & \dots & 𝑛 \\ 0 & 2 & 3 & \dots & 𝑛 \\ 0 & 0 & 3 & \dots & 𝑛 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \dots & 𝑛 \end{matrix}] ✅ 𝐴 = [\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}] ❌ Question 5 For the following statements, select all that are incorrect : An optimal solution to a linear program must be a boundary point. ❌ not guaranteed if the objective is constant over the feasible region An optimal solution to a linear program must be an extreme point. ✅ An optimal solution to a nonlinear program can be an interior point. ❌ An optimal solution to a nonlinear program must be an interior point. ✅ A global optimal solution to a nonlinear program must be a local optimal solution. ❌← Convexity Gradient Descent →window.addEventListener('DOMContentLoaded', () => { if (typeof PagefindUI === 'undefined') return; const addTextFrag = (url, q) => {   if (!q) return url;   const enc = encodeURIComponent(q);   if (url.includes(':~:text=')) return url;   return url.includes('#') ? url + ':~:text=' + enc                            : url + '#:~:text=' + enc; }; new PagefindUI({   element: '#search',   showSubResults: true,   processResult: (result) => {     const inp = document.querySelector('.pagefind-ui__search-input');     const q = inp ? inp.value.trim() : '';     result.url = addTextFrag(result.url, q);     if (result.sub_results) {       result.sub_results.forEach(sr => { sr.url = addTextFrag(sr.url, q); });     }     return result;   }, });});(() => { const root = document.documentElement, body = document.body; const W_KEY = 'ieor-sidebar-w', C_KEY = 'ieor-sidebar-collapsed'; const MOBILE = 900; const savedW = localStorage.getItem(W_KEY); if (savedW) root.style.setProperty('--sidebar-w', savedW + 'px'); if (localStorage.getItem(C_KEY) === '1' && window.innerWidth > MOBILE)   body.classList.add('sidebar-collapsed'); const btn = document.querySelector('.nav-toggle'); if (btn) btn.addEventListener('click', () => {   if (window.innerWidth <= MOBILE) {     body.classList.toggle('nav-open');   } else {     body.classList.toggle('sidebar-collapsed');     localStorage.setItem(C_KEY, body.classList.contains('sidebar-collapsed') ? '1' : '0');   } }); const rz = document.querySelector('.sidebar-resizer'); if (rz) rz.addEventListener('pointerdown', (e) => {   e.preventDefault();   rz.setPointerCapture(e.pointerId);   body.classList.add('resizing');   const COLLAPSE_AT = 120;   let cleanup;   const onMove = (ev) => {     if (ev.clientX < COLLAPSE_AT) {       body.classList.add('sidebar-collapsed');       localStorage.setItem(C_KEY, '1');       cleanup();       return;     }     const w = Math.min(600, Math.max(180, ev.clientX));     root.style.setProperty('--sidebar-w', w + 'px');   };   cleanup = () => {     try { rz.releasePointerCapture(e.pointerId); } catch (_) {}     body.classList.remove('resizing');     rz.removeEventListener('pointermove', onMove);     rz.removeEventListener('pointerup', cleanup);     const w = parseInt(getComputedStyle(root).getPropertyValue('--sidebar-w'));     if (!isNaN(w)) localStorage.setItem(W_KEY, String(w));   };   rz.addEventListener('pointermove', onMove);   rz.addEventListener('pointerup', cleanup); });})();

Single Variate Function $𝑓 : ℝ \to ℝ$	$𝑓$ is convex in $[𝑎, 𝑏]$ if $𝑓^{″} (𝑥) \geq 0$ for all $𝑥 \in [𝑎, 𝑏]$ $\bar{𝑥}$ is an interior local minimum if $𝑓^{'} (\bar{𝑥}) = 0$ If $𝑓$ is convex in $[𝑎, 𝑏]$ , $𝑥^{}$ is a global minimum iff $𝑓^{'} (𝑥^{}) = 0$
Multi Variate Function $𝑓 : ℝ^{𝑛} \to ℝ$	$𝑓$ is convex in a convex set $𝐹 \subseteq ℝ^{𝑛}$ if $\nabla^{2} 𝑓 (𝑥)$ is positive semi-definite for all $𝑥 \in 𝐹$ $\bar{𝑥}$ is an interior local minimum if $\nabla 𝑓 (\bar{𝑥}) = 𝟎$ If $𝑓$ is convex in a convex set $𝐹$ , $𝑥^{}$ is a global minimum iff $\nabla 𝑓 (𝑥^{}) = 0$