SECTION A – Very Short Answer Type (2 × 10 = 20)
a) Role of Convexity in Optimization
Convexity ensures that any local minimum is also a global minimum. This property simplifies optimization because algorithms are guaranteed to converge to the optimal solution without getting trapped in local minima.
b) Real-World Applications of Convex Optimization
Convex optimization is widely used in:
Machine learning (regularized regression, SVMs)
Signal processing (noise removal)
Finance (portfolio optimization)
Network optimization (routing and bandwidth allocation)
c) Nesterov’s Acceleration in Convex Optimization
Nesterov’s accelerated gradient method improves convergence speed by using a momentum term, achieving a faster rate of O(1/k2)O(1/k^2)O(1/k2) compared to standard gradient descent.
d) Moreau–Yosida Regularization
Moreau–Yosida regularization smooths non-smooth functions by approximating them with a
differentiable surrogate, making gradient-based optimization feasible.
e) Regularization Process
Regularization adds a penalty term to the objective function to prevent overfitting, control model complexity, and improve generalization.
f) Dual Decomposition
Dual decomposition breaks a large optimization problem into smaller subproblems using Lagrange multipliers, enabling parallel and distributed optimization.
g) Douglas–Rachford Splitting
This method handles complex constraints by splitting them into simpler subproblems and solving them iteratively, ensuring convergence in convex settings.
h) Navigating Saddle Points
Optimization algorithms escape saddle points using:
Momentum methods
Random noise (e.g., Langevin dynamics)
Second-order information
i) Implications for Convergence
Efficient optimization algorithms improve:
Faster convergence
Stability
Reduced computational cost
j) Impact of Optimization Landscape
The geometry of the landscape (convex, non-convex, smoothness) determines the choice of algorithm, step size, and convergence guarantees.
SECTION B – Long Answer Type (Attempt Any Three)
2(a) Linear Programming vs SOCP vs SDP
Linear Programming (LP) involves linear objectives and constraints and is computationally efficient.
Example: Resource allocation problems.
Second-Order Cone Programming (SOCP) extends LP by allowing quadratic constraints.
Example: Robust portfolio optimization.
Semidefinite Programming (SDP) involves matrix variables and positive semidefinite constraints.
Example: Control systems and graph partitioning.
Comparison Summary:
LP < SOCP < SDP in expressive power and computational complexity.
2(b) Duality in Convex Optimization
Duality provides a way to analyze optimization problems by converting the primal problem into a dual
problem.
Strong duality holds under Slater’s condition, meaning optimal primal and dual values coincide.
Duality offers:
Lower bounds on solutions
Sensitivity analysis
Efficient distributed optimization
2(c) Mirror Descent vs Gradient Descent
Gradient descent updates parameters in Euclidean space, while mirror descent adapts updates using a geometry-aware distance function.
Advantages of Mirror Descent:
Works well in high-dimensional and constrained spaces
Effective for sparse optimization
Example: Online learning and large-scale NLP models.
2(d) Augmented Lagrangian vs ADMM
Augmented Lagrangian methods penalize constraint violations strongly, while ADMM splits variables and solves them alternately.
ADMM is preferred when:
Problems are large-scale
Distributed computation is required
2(e) Polyak–Juditsky Averaging
This technique averages SGD iterates to reduce variance and improve convergence stability.
In deep learning, it:
Smoothens noisy gradients
Enhances generalization
Accelerates convergence
SECTION C – Descriptive Answer Type
3(a) Karush–Kuhn–Tucker (KKT) Conditions
KKT conditions define optimality in constrained convex optimization.
They include:
Primal feasibility
Dual feasibility
Complementary slackness
Stationarity
Example:
In constrained regression, KKT conditions determine optimal coefficients while respecting constraints.
4(a) Frank–Wolfe Method
The Frank–Wolfe algorithm is used for constrained optimization without projection steps.
Advantages:
Low memory usage
Suitable for large-scale problems
Applications:
Matrix completion and sparse learning problems.
5(b) Proximal Gradient Methods
Proximal gradient methods extend gradient descent to handle non-smooth objectives.
They are widely used in:
LASSO regression
Sparse neural networks
6(b) Douglas–Rachford Splitting
This algorithm alternates between proximal operators and converges under convexity assumptions.
Effective in:
Signal reconstruction
Image processing
7(a) Langevin Dynamics in Bayesian Inference
Langevin dynamics adds noise to gradient updates, enabling:
Escaping saddle points
Efficient sampling
It is widely used in Bayesian deep learning and probabilistic modeling.
