🎛️Optimization of Systems Unit 12 – Quadratic Programming

What's Quadratic Programming?

• Optimization technique deals with minimizing or maximizing a quadratic objective function subject to linear constraints
• Objective function contains linear and quadratic terms, making it a specific type of nonlinear programming
• Quadratic term allows modeling of interactions and nonlinear relationships between decision variables
• Linear constraints define the feasible region, which is a convex polytope (simplex, hypercube)
• Quadratic programming is a generalization of linear programming, but more complex due to the quadratic term
• Applications span various fields including finance (portfolio optimization), engineering (control systems), and operations research (resource allocation)
• Special case of nonlinear programming where the objective function is quadratic and the constraints are linear

Key Components and Terminology

• Objective function: Mathematical expression to be minimized or maximized, consists of linear and quadratic terms
  • Linear term: Coefficients multiplied by decision variables, represents linear contribution to the objective
  • Quadratic term: Matrix of coefficients multiplied by pairs of decision variables, captures interactions and nonlinearities
• Decision variables: Unknown quantities to be determined, represented by symbols (x, y, z)
• Constraints: Linear equalities or inequalities that define the feasible region for the decision variables
  • Equality constraints: Equations that must be satisfied exactly ($Ax = b$)
  • Inequality constraints: Inequalities that impose bounds on the decision variables ($Cx \leq d$)
• Feasible region: Set of all points (solutions) that satisfy the constraints, forms a convex polytope
• Optimal solution: Point in the feasible region that minimizes or maximizes the objective function
• Positive semidefinite matrix: Symmetric matrix with non-negative eigenvalues, ensures convexity of the quadratic term

Formulating Quadratic Problems

• Identify the decision variables and their domains (continuous, integer, binary)
• Define the objective function as a quadratic expression, specifying the linear and quadratic coefficients
  • Quadratic term is represented by a symmetric matrix, often denoted as Q
  • Linear term is represented by a vector, often denoted as c
• Express the constraints as linear equalities or inequalities using the decision variables
  • Equality constraints have the form $Ax = b$, where A is a matrix and b is a vector
  • Inequality constraints have the form $Cx \leq d$, where C is a matrix and d is a vector
• Ensure the quadratic matrix Q is positive semidefinite to guarantee a convex optimization problem
• Consider any additional requirements or restrictions specific to the problem domain
• Verify the feasibility of the formulated problem by checking if there exists at least one solution satisfying all constraints

Solving Methods and Algorithms

• Interior point methods: Iterative algorithms that traverse the feasible region's interior to reach the optimal solution
  • Primal-dual interior point methods maintain primal and dual feasibility while reducing duality gap
  • Barrier methods introduce a logarithmic barrier term to the objective function to enforce strict inequalities
• Active set methods: Iteratively solve a sequence of equality-constrained quadratic subproblems
  • Identify the active constraints (those satisfied as equalities) at each iteration
  • Solve the subproblem considering only the active constraints, update the active set based on optimality conditions
• Gradient projection methods: Project the negative gradient onto the feasible region to determine the descent direction
  • Compute the gradient of the objective function at the current point
  • Project the negative gradient onto the feasible region defined by the constraints
  • Perform a line search along the projected direction to find the next iterate
• Augmented Lagrangian methods: Reformulate the constrained problem as an unconstrained one by adding penalty terms
  • Introduce Lagrange multipliers for the equality and inequality constraints
  • Augment the objective function with a quadratic penalty term for constraint violations
  • Alternately minimize the augmented Lagrangian function and update the multipliers

Constraints and Feasibility

• Linear equality constraints restrict the feasible region to a lower-dimensional affine subspace
  • Represent relationships that must be satisfied exactly, such as balance equations or fixed resource allocations
  • Can be handled by substitution or elimination techniques to reduce the problem dimensionality
• Linear inequality constraints define the boundaries of the feasible region, forming a convex polytope
  • Impose upper or lower bounds on the decision variables or their linear combinations
  • Determine the active constraints at the optimal solution, which are satisfied as equalities
• Feasibility refers to the existence of a solution that satisfies all the constraints simultaneously
  • Infeasible problems have no solution within the constrained region, indicating contradictory or overly restrictive constraints
  • Feasibility can be checked by solving a linear programming problem with the same constraints and a dummy objective function
• Redundant constraints do not affect the feasible region but may impact the efficiency of solving algorithms
• Preprocessing techniques can help identify and remove redundant or inconsistent constraints before solving the quadratic program

Applications in Real-World Systems

• Portfolio optimization in finance
  • Maximize expected return while minimizing risk (variance) of a portfolio
  • Decision variables represent investment weights in different assets
  • Constraints ensure budget limits, diversification requirements, and trading restrictions
• Control systems in engineering
  • Minimize tracking error or energy consumption in dynamic systems
  • Decision variables are control inputs or system states
  • Constraints capture physical limitations, safety requirements, and performance specifications
• Resource allocation in operations research
  • Optimize the allocation of limited resources (budget, workforce, materials) across competing activities
  • Decision variables denote the amount of resources assigned to each activity
  • Constraints reflect resource capacities, demand requirements, and operational restrictions
• Quadratic assignment problem in facility location
  • Minimize the total cost of assigning facilities to locations considering pairwise distances and flow volumes
  • Decision variables are binary, indicating the assignment of facilities to locations
  • Constraints ensure each facility is assigned to exactly one location and each location receives at most one facility
• Energy optimization in power systems
  • Minimize generation costs or transmission losses while satisfying demand and network constraints
  • Decision variables represent power generation levels and transmission flows
  • Constraints include power balance equations, generator capacity limits, and transmission line capacities

Common Challenges and Pitfalls

• Ill-conditioning: Quadratic matrix Q may be close to singular, leading to numerical instability and slow convergence
  • Regularization techniques (adding a small multiple of the identity matrix to Q) can improve conditioning
  • Scaling and preconditioning of the problem data can enhance numerical stability
• Non-convexity: If the quadratic matrix Q is not positive semidefinite, the problem becomes non-convex
  • Non-convex quadratic programs are NP-hard and may have multiple local optima
  • Convex relaxation techniques (semidefinite programming) can provide approximate solutions or bounds
• Scalability: Large-scale quadratic programs with many decision variables and constraints can be computationally challenging
  • Exploiting problem structure (sparsity, separability) can lead to more efficient solution methods
  • Decomposition techniques (Benders decomposition, Dantzig-Wolfe decomposition) can break the problem into smaller subproblems
• Infeasibility detection: Identifying infeasible problems early can save computational resources
  • Infeasibility certificates (Farkas lemma) can provide proof of infeasibility
  • Phase I methods can be used to find a feasible starting point or detect infeasibility
• Sensitivity analysis: Understanding how the optimal solution changes with perturbations in problem data is important for decision-making
  • Shadow prices (Lagrange multipliers) indicate the marginal impact of constraint changes on the objective value
  • Parametric programming techniques can compute the range of parameter values for which the current solution remains optimal

Tools and Software for Quadratic Programming

• Optimization modeling languages
  • AMPL, GAMS, JuMP (Julia), Pyomo (Python), YALMIP (MATLAB)
  • Provide high-level interfaces for formulating and solving quadratic programs
  • Support various solvers and enable easy model development and maintenance
• Quadratic programming solvers
  • CPLEX, Gurobi, MOSEK, OSQP, Xpress
  • Implement efficient algorithms for solving quadratic programs
  • Offer APIs and interfaces for integration with different programming languages and environments
• Numerical libraries
  • LAPACK, BLAS, Eigen (C++), NumPy (Python), MATLAB
  • Provide low-level routines for linear algebra operations and matrix computations
  • Can be used to implement custom quadratic programming algorithms or preconditioning techniques
• Modeling and optimization frameworks
  • CVX (MATLAB), CVXPY (Python), Convex.jl (Julia)
  • Provide disciplined convex programming environments for formulating and solving convex optimization problems
  • Enable users to express quadratic programs using intuitive syntax and automatic transformation into standard forms
• Visualization and analysis tools
  • MATLAB, Python (Matplotlib), R, Tableau
  • Facilitate data exploration, model visualization, and solution interpretation
  • Help in communicating insights and making data-driven decisions based on quadratic programming results