Module 3: Non-linear Programming

3.1.1 Convex and Non-convex function

 Convex Functions:
A function f(x) is called convex on an interval if for any two points x1, x2 in the interval and
for any 0 ≤ λ ≤ 1, f(λx1 + (1−λ)x2) ≤ λf(x1) + (1−λ)f(x2)
Properties of Convex Functions:
• The line segment joining any two points on the graph lies above or on the curve.
• Every local minimum is also a global minimum.
• Convex functions have a single minimum.
• If f''(x) ≥ 0 for all x, then f(x) is convex.(second derivative test)

 Non-Convex Functions:
A function that does not satisfy the convexity condition is called a non-convex function.
Properties of Non-Convex Functions:
• May have multiple local minima and maxima.
• A local optimum need not be a global optimum.
• Second derivative may change sign.

 Context: Multivariable Convex Functions

Let f : Rⁿ → R be a twice differentiable function. The Hessian matrix of the function f at a
point x is defined as:

• The Hessian matrix contains all second-order partial derivatives and captures the curvature
of the function in all directions.
• Let λ₁, λ₂, … , λₙ be the eigenvalues of the Hessian matrix H(x).
• Eigenvalues describe the curvature of the function along principal directions.

Relationship Between Eigenvalues and Convexity

Eigenvalues of Hessian Nature of the Function

All λᵢ ≥ 0 Convex function

All λᵢ > 0 Strictly convex function

Any λᵢ < 0 Function is not convex (concave in some direction)

Mixed signs Saddle point, not convex

Page 1
 Exercise 3.1

1. Show that the following functions are convex:

(i) f(x) = x² , (ii) f(x) = log(1 + e2x) ,(iii) f(x) = 𝑒 ,(iv) f(x) = (x-3)2

2. Discuss convexity of the following functions:

(i) f(x) = √𝑥 , (ii) f(x) = x³-3x , (iii) f(x) = tan x ,(iv) f(x) = x4 – x2

3. Discuss convexity of the following two variable functions:

(i) f(x, y) = 4x² + y² ,(ii) f(x, y) = x² + y² + xy ,(iii) f(x, y) = x² + y⁴ − y² ,(iv) f(x, y) = xy

Practise Exercise 3.1

1. Show that the following functions are convex:

(i) f(x) = x6 , (ii) f(x) = log(1 + ex) ,(iii) f(x) = ex ,(iv) f(x) = x4

2. Discuss convexity of the following functions:

(i) f(x) = x2 − 2x , (ii) f(x) = x³ , (iii) f(x) = sin x ,(iv) f(x) = log x

3. Discuss convexity of the following two variable functions:

(i) f(x, y) = (x + y)² ,(ii) f(x, y) = x² + 3y² ,(iii) f(x, y) = x³ + y³ , (iv) f(x, y) = x²y² − x² − y²

3.2.1 Unconstrained optimization technique-Newton’s Method

Newton’s method is a second-order method that uses first and second derivatives.

 Iteration Formula:
𝑓′(𝑥 )
𝑥 =𝑥 −
𝑓′′(𝑥 )

Note:
 Sign of 𝑓′′(𝑥 ) decides f has a maximum or minimum at 𝑥
 If 𝑓 (𝑥 ) ≥ 0, then f has minimum at 𝑥 and 𝑓(𝑥 ) is the minimum value of the
function.
 If 𝑓 (𝑥 ) ≤ 0, then f has maximum at 𝑥 𝑓(𝑥 ) is the maximum value of the
function.

Exercise 3.2
1. Maximize the function f(x) = 2 sin x – using Newton’s method. Take the initial guess
x₀ = 2.5
2. Maximize f(x) = 4 sinx(1 + cos x) with x0 = 𝜋/4 = 0.7854 rad
3. Minimize the function f(x) = 𝑥 − 4𝑥 + 𝑥 using Newton’s method with initial
approximation x₀ = 1.5

Page 2
4. Maximize f(x) = 𝑥𝑒 𝑤𝑖𝑡ℎ using Newton’s method. Take x₀ = 0.5 and perform four
iterations to find the optimal value of x.
5. Minimize f(x) = x – log x with Newton’s method with initial approximation 𝑥 = 2

Practise Exercise 3.2

1. Maximize the function f(x) = sin x – using Newton’s method. Take the initial guess x₀ =
1.2 . Perform at least four iterations and find the point of maximum.
2. Minimize the function f(x) = x⁴ − 6x² + x using Newton’s method with initial
approximation x₀ = 2
3. Maximize the function f(x) = x.𝑒 using Newton’s method. Take x₀ = 0.8 and perform
four iterations to find the optimal value of x.
4. Maximize the function f(x) = 4x − x³ using Newton’s method with initial guess x₀ = 1.0.
Carry out four iterations to find the maximum point.
5. Maximize f(x) = 3𝑥 − using Newton’s method with initial guess 𝑥 = 0.8

3.2.2 Unconstrained optimization technique-Gradient Descent

Method
Gradient Descent is an iterative first-order optimization method used to find the minimum of
a function.

Algorithm
1. Choose an initial guess x0
2. Choose learning rate α > 0
3. Update: 𝑥 = 𝑥 − 𝛼. 𝑓′(𝑥 )

4. Stop when |f'(x)| is sufficiently small

Note:
 Sign of 𝑓′′(𝑥 ) decides f has a maximum or minimum at 𝑥
 If 𝑓 (𝑥 ) ≥ 0, then f has minimum at 𝑥 and 𝑓(𝑥 ) is the minimum value of the
function.
 If 𝑓 (𝑥 ) ≤ 0, then f has maximum at 𝑥 𝑓(𝑥 ) is the maximum value of the
function.

Exercise 3.3

1. Minimize the function f(x) = 𝑥 + 4𝑥 + 4 , using Gradient Descent method by taking

learning rate, 𝛼 = 0.1. Perform 5 iterations with initial guess x₀ = -1.5

2. Minimize f(x) = x⁴ − 4x² + 1 using Gradient Descent method by taking learning rate, α =
0.05 . Perform 5 iterations with initial guess x₀ = 1

Page 3
 3. Maximize f(x) = 3x - eˣ using Gradient Descent method by taking learning rate, α = 0.1 .
Perform 4 iterations with initial guess x₀ = 1.5

4. Minimize f(x) = sin x + 0.1x² using Gradient Descent method by taking learning rate, α =
0.2 . Perform 4 iterations with initial guess x₀ = -1

Practise Exercise 3.3

1. Maximize f(x) = 4x − x² using Gradient Descent method by taking learning rate, α = 0.25 .
Perform 3 iterations with initial guess x₀ = 2.5
2. Minimize the function f(x) = x³ − 3x, using Gradient Descent method by taking learning
rate, 𝛼 = 0.1. Perform 5 iterations with initial guess x₀ = 1.5
3. Minimize f(x) = (x − 3)² + 2 , using Gradient Descent method by taking learning rate, 𝛼 =
0.5. Perform 2 iterations with initial guess x₀ = 2.5
4. Minimize f(x) = x² − 6x + 5 using Gradient Descent method by taking learning rate, 𝛼 =
0.1 . Perform 6 iterations with initial guess x₀ = 3.5

3.2.3 Application of Gradient Descent in ML (Backpropagation)

In ML, for backpropagation, Gradient descent is used to minimize the loss function by
updating weights in the opposite direction of the gradient .

 Steps:
 Objective :
Minimize the loss function L(w), where w represents network weights.

 Forward Pass (neuron with 2 Inputs):

a = w1 x1 + w2 x2 + b

 Loss Function (Mean Squared Error):

1
𝐿 = (𝑦 − 𝑎)
2
 Backpropagation:
Gradients are computed using the chain rule:
= . , for i = 1,2

 For linear activation:

= −(𝑦 − 𝑎)𝑥 , for i = 1,2

 Weight Update Rule:

𝑤 = 𝑤 − η , for i = 1,2

Page 4
  Bias update:
𝑏 = 𝑏 −η

 Learning Rate (η):

Controls step size. Too small → slow learning, too large → divergence.

Algorithm Steps:
1. Initialize weights
2. Forward pass
3. Compute loss
4. Backpropagate error
5. Update weights
6. Repeat until convergence

Exercise 3.4
1. Consider a single-neuron neural network with the following details: Input x = 2, desired
output y = 5, Initial weight w0 =1, Bias b = 0.05, Learning rate η = 0.1, activation function:
Linear, Loss function: 𝐿 = (𝑦 − 𝑎) . Compute the neuron output and loss function, update
the weight and bias using gradient descent with backpropagation for two iterations.

2. Consider a single-neuron neural network with the following details:Input x=3, desired
output y=10, initial weight w0=0.5, bias b=0.3, learning rate η=0.1, activation function:
Linear, loss function 𝐿 = (𝑦 − 𝑎) . Compute the neuron output and loss function, and
update the weight and bias using gradient descent with backpropagation for two iterations.

3. Consider a single-layer neural network with two input neurons and one output neuron with
following details: Inputs x1=1, x2=2, Target output y = 6, Initial weights w1=1, w2=1, Bias
b=0.5, Learning rate η=0.1, activation function: linear, Loss function 𝐿 = (𝑦 − 𝑎) .
Compute the neuron output and loss function, update the weights and bias using gradient
descent with backpropagation for two iterations.

4. Consider a single-layer neural network with two input neurons and one output neuron with
following details: Inputs x1=2, x2=2, Target output y = 5, Initial weights w1=1, w2=0.5, Bias
b=0.1, Learning rate η=0.1, activation function: linear, Loss function 𝐿 = (𝑦 − 𝑎) .
Compute the neuron output and loss function, update the weights and bias using gradient
descent with backpropagation for two iterations.

Practise Exercise 3.4

1. Consider a single-neuron neural network with the following details: Input x = 4, desired
output y = 12, Initial weight w0 =1.5, Bias b = 0.5, Learning rate η = 0.05, activation
function: Linear, Loss function: 𝐿 = (𝑦 − 𝑎) . Compute the neuron output and loss
function and using backpropagation, update the weight and bias using the gradient descent
rule for two iterations.

Page 5
 2. Consider a single-neuron neural network with the following details: Input x = 1.5, desired
output y = 4, Initial weight w0 =0.8, Bias b = 0.2, Learning rate η = 0.2, activation function:
Linear, Loss function: 𝐿 = (𝑦 − 𝑎) . Compute the neuron output and loss function, update
the weight and bias using gradient descent with backpropagation for two iterations.

3. Consider a single-layer neural network with two input neurons and one output neuron with
following details: Inputs x1=1, x2=3, Target output y = 8, Initial weights w1=1, w2=1, Bias
b=0.05, Learning rate η=0.05, activation function: linear, Loss function 𝐿 = (𝑦 − 𝑎) .
Compute the neuron output and loss function, update the weights and bias using gradient
descent with backpropagation for two iterations.

4. Consider a single-layer neural network with two input neurons and one output neuron with
following details: Inputs x1=2, x2=2, Target output y = 10, Initial weights w1=0.5, w2=1, Bias
b=0.1, Learning rate η=0.1, activation function: linear, Loss function 𝐿 = (𝑦 − 𝑎) .
Compute the neuron output and loss function, update the weights and bias using gradient
descent with backpropagation for two iterations.

3.3.1 Constrained optimization technique-Lagrange’s Multiplier

Method
 ONE EQUALITY CONSTRAINT (TWO VARIABLES)
Problem
Optimize (maximize or minimize): z = f(x₁, x₂)
subject to the equality constraint: g(x₁, x₂) = b, x₁ , x₂ ≥ 0

Step for solving

1. The constraint is rewritten with RHS equal to zero: h(x₁, x₂) = g(x₁, x₂) − b = 0
2. The Lagrangian function is defined as: L(x₁, x₂, λ) = f(x₁, x₂) − λ h(x₁, x₂)
where λ is the Lagrange multiplier.

3. Necessary Conditions: For maxima or minima, the following conditions must be satisfied:
=0 , =0 , =0
Solving these three equations gives the stationary point X0 =(x₁, x₂)

4. Second-Order Sufficient Condition

To determine the nature of the stationary point, evaluate:

𝜕ℎ 𝜕ℎ
0
𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿
∆ =
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥

Page 6
 5. Decision rule:
• If Δ₃ > 0 → X0 is a Maximum
• If Δ₃ < 0 → X0 is a Minimum

 ONE EQUALITY CONSTRAINT (THREE VARIABLES)

Problem
Optimize (maximize or minimize): z = f(x₁, x₂, x₃)
subject to the equality constraint: g(x₁, x₂, x₃) = b ,x₁ , x₂ , x₃ ≥ 0

Step for solving

1. The constraint is rewritten as: h(x₁, x₂, x₃) = g(x₁, x₂, x₃) − b = 0
2. The Lagrangian function is defined as: L(x₁, x₂, x₃, λ) = f(x₁, x₂, x₃) − λ h(x₁, x₂, x₃)
where λ is the Lagrange multiplier.

3. Necessary Conditions: For maxima or minima, the following conditions must be satisfied:
𝝏𝑳 𝝏𝑳 𝝏𝑳 𝝏𝑳
=0 , =0 , =0 , =0
𝝏𝒙𝟏 𝝏𝒙𝟐 𝝏𝒙𝟑 𝝏𝛌
Solving these four equations gives the stationary point X0 = (x₁, x₂, x₃).

4. Second-Order Sufficient Conditions

To determine the nature of the stationary point X₀, evaluate the bordered Hessian
determinants:

𝜕ℎ 𝜕ℎ 𝜕ℎ
0
𝜕𝑥 𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿 𝜕 𝐿
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥
∆ =
𝜕ℎ 𝜕 𝐿 𝜕 𝐿 𝜕 𝐿
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿 𝜕 𝐿
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥

𝜕ℎ 𝜕ℎ
0
𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿
∆ =
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥
𝜕ℎ 𝜕 𝐿 𝜕 𝐿
𝜕𝑥 𝜕𝑥 𝜕𝑥 𝜕𝑥

5. Decision Rules
• If Δ₃ < 0 and Δ₄ < 0 , then X₀ is a Minimum
• If Δ₃ > 0 and Δ₄ < 0 , then X₀ is a Maximum

Exercise 3.5
Page 7
 1. Optimize: z = 6x₁² + 5x₂² 2. Optimize: z = 4x₁ + 8x₂ − x₁² − x₂²
subject to: subject to:
x₁ + 5x₂ = 7, x₁ , x₂ ≥ 0 x₁ + x₂ = 4
x₁ , x₂ ≥ 0

3. Optimize: 4. Optimize:
z = x₁² + x₂² + x₃² − 10x₁ − 6x₂ − 4x₃ z = 12x₁ + 8x₂ + 6x₃ − x₁² − x₂² − x₃² − 23
subject to: subject to:
x₁ + x₂ + x₃ = 7 x₁ + x₂ + x₃ = 10
xᵢ ≥ 0 , i = 1, 2, 3 x₁ , x₂ , x₃ ≥ 0

Practise Exercise 3.5

1. Optimize: z = 5x₁² + 4x₂² − 6x₁ − 8x₂ 2. Optimize: z = 3x₁² + 7x₂² − 10x₁ − 14x₂
subject to: subject to:
2x₁ + x₂ = 6 x₁ + 2x₂ = 8
x₁ , x₂ ≥ 0 x₁ , x₂ ≥ 0

3. Optimize: z = 2x₁² + 6x₂² − 8x₁ − 12x₂ 4. Optimize:

subject to: z = x₁² + x₂² + x₃² − 8x₁ − 12x₂ − 6x₃
x₁ + 3x₂ = 9 subject to:
x₁ , x₂ ≥ 0 x₁ + x₂ + x₃ = 9
xᵢ ≥ 0 , i = 1, 2, 3

5. Optimize: 6. Optimize:
z = 10x₁ + 6x₂ + 4x₃ − x₁² − x₂² − x₃² z = x₁² + x₂² + x₃² − 14x₁ − 10x₂ − 6x₃
subject to: subject to:
x₁ + x₂ + x₃ = 8 x₁ + x₂ + x₃ = 12
x₁ , x₂ , x₃ ≥ 0 xᵢ ≥ 0 , i = 1, 2, 3

3.3.2 Constrained optimization technique-Karush-Kuhn-Tucker

method.
 ONE INEQUALITY CONSTRAINT (KKT conditions)

Problem
Optimize (maximize / minimize): z = f(x₁, x₂, … , xₙ)
subject to: g₁(x₁, x₂, … , xₙ) ≤ b₁ , x₁ , x₂ , … , xₙ ≥ 0

Step for solving

1. The constraint is rewritten as: h(x₁, x₂,….., xn) = g(x₁, x₂,….., xn) − b = 0

2. The Lagrangian function is defined as: L(x₁, x₂,…. xn, λ) = f(x₁, x₂,…. xn) − λ h(x₁, x₂,…xn)
where λ is the Kuhn–Tucker multiplier.

Page 8
3. Kuhn–Tucker Conditions:
(i) Stationarity Conditions
= 0, = 0 , ……, =0 .
(ii) Complementary Slackness Conditions
λh=0
(iii) Primal Feasibility
h ≤ 0 , x₁ , x₂ , … , xₙ ≥ 0
Solving these equations gives the stationary point X0 = (x₁, x₂,…. xn) and λ.
(iv) Dual Feasibility
λ≥0

4. Decision Rules
• If λ ≥ 0 → Z is Maximum
• If λ ≤ 0 → Z is Minimum

Exercise 3.6
1. Maximise 2. Minimise 3. Maximise
z = 8x₁ + 10x₂ − x₁² − x₂² z = x₁³ − 4x₁ − 2x₂ z = 10x₁ + 12x₂ − x₁² − 2x₂²
subject to: subject to: subject to:
3x₁ + 2x₂ ≤ 6 x₁ + x₂ ≤ 1 2x₁ + x₂ ≤ 5
x₁ , x₂ ≥ 0 x₁ , x₂ ≥ 0 x₁ , x₂ ≥ 0

4. Minimise
z = x₁³ + x₂² − 6x₁ − 4x₂
subject to:
x₁ + 2x₂ ≤ 4
x₁ , x₂ ≥ 0

Practise Exercise 3.6

1. Maximise 2. Minimise 3. Maximise
z = 14x₁ + 6x₂ − 2x₁² − x₂² z = x₁² + 3x₂² − 8x₁ − 12x₂ z = 9x₁ + 15x₂ − x₁² − 3x₂²
subject to: subject to: subject to:
x₁ + x₂ ≤ 6 3x₁ + x₂ ≤ 7 x₁ + 3x₂ ≤ 9
x₁ , x₂ ≥ 0 x₁ , x₂ ≥ 0 x₁ , x₂ ≥ 0

4. Minimise
z = x₁³ + 2x₂² − 10x₁ − 6x₂
subject to:
2x₁ + x₂ ≤ 5
x₁ , x₂ ≥ 0

Page 9
3.3.2 Application of KKT conditions in Optimal MIMO power
allocation (Waterfilling).
Introduction
MIMO stands for Multiple-Input Multiple-Output. It is a wireless communication technology
that utilizes multiple antennas at both the transmitter (input) and receiver (output) to improve
network performance, capacity, and data speed by using spatial multiplexing.

Water-filling is an optimal power allocation technique used in MIMO / multichannel

communication systems to maximize channel capacity under a total power constraint.

Core idea (intuition): Think of each channel as a container with a different bottom height
(noise level).
 Good channels (low noise / high gain) → get more power
 Bad channels (high noise / low gain) → get less or no power
 Power is poured like water, filling lower levels first
Hence the name water-filling.

In MIMO communication systems, the channel can be decomposed into parallel independent
sub-channels using Singular Value Decomposition (SVD). The objective is to optimally
allocate the total transmit power among these sub-channels so as to maximize the total
channel capacity. This optimization problem is solved using Karush–Kuhn–Tucker (KKT)
conditions, leading to the well-known water-filling solution.

 Mathematical Formulation
Let: λi = gain of the ith eigen-channel
pi = power allocated to that channel , i = 1 to n
N0= noise power(kept as 1)
P = total available power
 Formulation of the Problem
Maximize the total capacity: C = Σ log₂(1 + λᵢ pᵢ)

Subject to the constraints: Σ pᵢ ≤ P ,

pᵢ ≥ 0 for all , i = 1 to n
 Steps for solving:
(a) Lagrangian Function
The Lagrangian is given by: L = Σ log₂(1 + λᵢ pᵢ) − μ(Σ pᵢ − P) − Σ νᵢ pᵢ

(b) KKT Conditions

The KKT conditions are:

Stationary condition : =0
Complementary slackness : νᵢ pᵢ = 0 and μ(Σ pᵢ − P) = 0
Primal feasibility : pᵢ ≥ 0, Σ pᵢ ≤ P
Dual feasibility : νᵢ ≥ 0, μ ≥ 0

Page 10
 Water-Filling Solution
νᵢ pᵢ = 0 gives pᵢ = − or pᵢ = 0 .
ᵢ

Hence, pᵢ = max 0, − , i = 1 to n . Eq 1.
ᵢ
&
μ(Σ pᵢ − P) = 0 gives Σ pᵢ − P = 0 , μ ≠ 0 Eq 2.

Solve these to get values of pᵢ , i = 1 to n

Exercise 3.7
1. A MIMO system consists of three parallel channels with gains λ₁ = 4, λ₂ = 2, and λ₃ = 1.
The noise power is unity for all channels. The total available transmit power is P = 5 units.
a) Formulate the capacity maximization problem. b) Derive the KKT conditions. c) Find the
optimal power allocation using the water-filling principle.

2. A MIMO channel is decomposed into four parallel sub-channels with gains λ₁ = 6, λ₂ = 3,

λ₃ = 2, and λ₄ = 1. The total available transmit power is 6 units.
a) Write the optimization problem for maximizing capacity. b) Apply KKT conditions to
derive the water-filling solution. c) Identify the channels that receive non-zero power.

Practise Exercise 3.7

1. A MIMO channel is decomposed into four parallel sub-channels with gains: λ₁ = 6, λ₂ = 3,

λ₃ = 2, λ₄ = 1. The total available transmit power is 6 units.
a) Write the optimization problem for maximizing capacity. b) Apply KKT conditions to
derive the water-filling solution. c) Identify the channels that receive non-zero power.

2. A MIMO channel is decomposed into three parallel sub-channels with gains: λ₁ = 5, λ₂ = 2,

λ₃ = 0.5. The total available transmit power is 4 units.
a) Formulate the capacity maximization problem. b) Derive the water-filling power allocation
using KKT conditions. c) Identify which channels receive zero power and justify.

3. A 4×4 MIMO system results in four eigen-channels with gains: λ₁ = 8, λ₂ = 4, λ₃ = 1, λ₄ =

0.25. The total available transmit power is 5 units.
a) Write the optimization problem for capacity maximization. b) Apply KKT conditions to
obtain the water-filling solution. c) Determine the optimal power allocation and comment on
inactive channels.

4. A MIMO communication system produces three independent sub-channels with gains:

λ₁ = 4, λ₂ = 1, λ₃ = 0.25. The total available transmit power is 3 units.
a) Write the capacity maximization problem. b) Apply KKT conditions to derive the water-
filling solution. c) Show mathematically why the weakest channel may receive zero power.

***************************************************************************

Page 11