📊Mathematical Methods for Optimization Unit 13 – Quadratic Programming in Optimization

Key Concepts and Definitions

• Quadratic programming involves optimizing a quadratic objective function subject to linear constraints
• Objective function takes the form $\frac{1}{2}x^TQx + c^Tx$ where $Q$ is a symmetric matrix, $c$ is a vector, and $x$ is the decision variable vector
  • $Q$ determines the curvature of the objective function (convex if $Q$ is positive semidefinite)
• Linear constraints include equality constraints $Ax = b$ and inequality constraints $Cx \leq d$
  • $A$ and $C$ are matrices, while $b$ and $d$ are vectors
• Feasible region defined by the intersection of all linear constraints
• Optimal solution is a point in the feasible region that minimizes or maximizes the objective function
• Convex quadratic programming occurs when $Q$ is positive semidefinite, ensuring a global optimum
• Non-convex quadratic programming arises when $Q$ is indefinite, leading to potential local optima

Quadratic Programming Formulation

• Standard form: $\min_{x} \frac{1}{2}x^TQx + c^Tx$ subject to $Ax = b$ and $Cx \leq d$
• Decision variables $x$ represent the quantities to be optimized
• Objective function coefficients $Q$ and $c$ define the quadratic and linear terms, respectively
• Equality constraints $Ax = b$ enforce strict requirements on decision variables
  • Used for balance equations, fixed allocations, or definitional constraints
• Inequality constraints $Cx \leq d$ impose upper or lower bounds on decision variables or their combinations
  • Model resource limitations, capacity restrictions, or performance requirements
• Quadratic programming is a generalization of linear programming, allowing for quadratic terms in the objective function

Optimality Conditions

• Karush-Kuhn-Tucker (KKT) conditions provide necessary and sufficient conditions for optimality in convex quadratic programming
  • Stationarity: $Qx + c + A^T\lambda + C^T\mu = 0$
  • Primal feasibility: $Ax = b$ and $Cx \leq d$
  • Dual feasibility: $\mu \geq 0$
  • Complementary slackness: $\mu^T(Cx - d) = 0$
• Lagrange multipliers $\lambda$ and $\mu$ associated with equality and inequality constraints, respectively
• For non-convex problems, KKT conditions are necessary but not sufficient for global optimality
• Second-order sufficient conditions involve the positive definiteness of the reduced Hessian matrix
• Complementary slackness ensures that either the constraint is active ($Cx = d$) or its corresponding multiplier is zero ($\mu = 0$)

Solution Methods and Algorithms

• Active set methods iteratively solve a sequence of equality-constrained quadratic programming subproblems
  • Identify the active constraints at the solution and solve the resulting system of linear equations
  • Update the active set by adding or removing constraints based on optimality conditions
• Interior point methods follow a path through the strict interior of the feasible region to reach the optimal solution
  • Barrier functions or penalty terms are added to the objective function to enforce constraint satisfaction
  • Newton's method or its variants are used to solve the modified optimization problem
• Gradient projection methods take steps in the direction of the negative gradient projected onto the feasible region
  • Efficient for problems with simple constraint sets (box constraints or linear equality constraints)
• Dual methods solve the dual problem, which involves maximizing the Lagrangian function over dual variables
  • Particularly useful when the dual problem has a simpler structure than the primal problem
• Specialized algorithms exist for specific problem classes (convex, separable, or sparse quadratic programs)

Geometric Interpretation

• Objective function defines a quadratic surface in the decision variable space
  • Ellipsoid, paraboloid, or hyperboloid depending on the definiteness of $Q$
• Linear constraints form hyperplanes or half-spaces that intersect to create the feasible region
  • Polytope defined by the intersection of linear inequality constraints
• Optimal solution lies at the point where the objective function contour is tangent to the feasible region boundary
  • Unique global optimum for convex quadratic programs
  • Multiple local optima possible for non-convex problems
• Graphical representation aids in visualizing the problem structure and solution characteristics
  • Two-dimensional problems can be plotted and analyzed geometrically
• Active constraints at the solution correspond to the faces of the feasible region polytope

Applications and Examples

• Portfolio optimization: Maximize expected return while minimizing risk (variance) subject to budget and investment constraints
  • Decision variables: asset weights; Objective function: mean-variance trade-off; Constraints: budget, diversification, and short-selling restrictions
• Least squares regression with regularization: Minimize the sum of squared residuals plus a quadratic penalty term
  • Decision variables: regression coefficients; Objective function: fitting error and regularization term; Constraints: sparsity or smoothness requirements
• Control and trajectory optimization: Minimize quadratic cost functions subject to system dynamics and state/input constraints
  • Decision variables: control inputs and state variables; Objective function: tracking error and control effort; Constraints: physical limitations and safety requirements
• Resource allocation problems: Optimize the allocation of limited resources to maximize a quadratic utility function
  • Decision variables: resource amounts; Objective function: total utility or performance measure; Constraints: resource availability and demand satisfaction
• Support vector machines (SVM): Maximize the margin between classes subject to misclassification penalties
  • Decision variables: SVM parameters; Objective function: hinge loss and regularization term; Constraints: classification constraints

Challenges and Limitations

• Computational complexity increases with the problem size, especially for non-convex problems
  • Solving large-scale quadratic programs can be time-consuming and memory-intensive
• Sensitivity to problem formulation and data uncertainty
  • Small changes in the objective function or constraint coefficients can lead to significant changes in the optimal solution
• Difficulty in handling non-convex objective functions or non-linear constraints
  • Local optimization techniques may converge to suboptimal solutions
  • Global optimization approaches are computationally expensive and not guaranteed to find the global optimum
• Numerical issues such as ill-conditioning, scaling, and round-off errors can affect the solution accuracy and convergence
• Limited modeling flexibility compared to more general nonlinear programming techniques
  • Quadratic terms may not adequately capture complex relationships or objectives

Related Optimization Techniques

• Linear programming: Special case of quadratic programming with a linear objective function
  • Simpler problem structure and more efficient solution algorithms (simplex method)
• Semidefinite programming: Generalization of quadratic programming with matrix decision variables and positive semidefinite constraints
  • Useful for problems with ellipsoidal or spectral constraints
• Second-order cone programming: Quadratic constraints with a specific structure (norm constraints)
  • Arises in robust optimization, signal processing, and finance applications
• Nonlinear programming: General optimization problems with nonlinear objective functions and constraints
  • Quadratic programming is a subclass of nonlinear programming with a quadratic objective and linear constraints
• Integer quadratic programming: Quadratic programming with integrality constraints on some or all decision variables
  • Combinatorial optimization problems with quadratic objectives (facility location, scheduling)
• Stochastic quadratic programming: Quadratic programming with uncertain parameters modeled as random variables
  • Optimization under uncertainty, risk management, and robust decision-making