Quadratic programming builds on linear programming by introducing quadratic terms in the objective function. This allows for modeling more complex relationships between variables, like diminishing returns or trade-offs between competing goals.

The standard form includes a quadratic objective function with linear constraints. Key components are the Q matrix for quadratic coefficients, c vector for linear terms, and Ax ≤ b for constraints. This versatile framework applies to many real-world optimization problems.

Quadratic Programming Standard Form

Mathematical Representation

• Minimize or maximize quadratic objective function $f(x) = \frac{1}{2}x^T Q x + c^T x$ subject to linear constraints
• $Q$ represents symmetric matrix of quadratic coefficients
• $c$ denotes vector of linear coefficients
• $x$ signifies vector of decision variables
• Linear constraints expressed as $Ax \leq b$
  • $A$ represents matrix of constraint coefficients
  • $b$ denotes vector of constraint constants
• Non-negativity constraints $x \geq 0$ ensure feasibility of solution

Characteristics and Special Cases

• Feasible region formed by intersection of all constraints creates convex set
• Positive semi-definite $Q$ matrices ensure convexity of objective function
• Convexity guarantees global optimality of local minimum (portfolio optimization)
• Indefinite $Q$ matrices may lead to multiple local optima (facility location problems)

Objective Function and Constraints

Objective Function Components

• Quadratic expression minimized or maximized contains linear and quadratic terms
• $Q$ matrix represents quadratic interactions between variables (production costs)
• $c$ vector represents linear coefficients of decision variables (profit margins)
• Objective function models complex relationships (diminishing returns in marketing)
• Captures trade-offs between competing objectives (risk vs. return in finance)

Constraint Types and Formulation

• Linear inequalities or equalities restrict feasible region of solution
• Equality constraints expressed as $Ax = b$ (resource allocation)
• Inequality constraints expressed as $Ax \leq b$ or $Ax \geq b$ (production limits)
• Bound constraints limit individual variables (inventory levels)
• Separating bound constraints from general linear constraints improves computational efficiency

Real-World Problems in Quadratic Form

Problem Formulation Process

• Identify decision variables representing quantities to be optimized (production quantities)
• Formulate objective function expressing goal in terms of decision variables
• Include both linear and quadratic terms (profit maximization with diminishing returns)
• Determine constraints by identifying limitations or requirements (resource availability)
• Express constraints as linear equalities or inequalities (machine capacity limits)
• Convert all expressions to matrix and vector notation aligning with standard form
• Verify formulation accurately represents original problem (portfolio optimization)

Common Applications

• Portfolio optimization balancing risk and return
• Production planning with economies of scale
• Facility location problems considering distance and demand
• Traffic flow optimization in transportation networks
• Resource allocation in project management
• Machine learning algorithms (support vector machines)

Linear vs Quadratic Programming

Objective Function Differences

• Linear programming involves linear objective function (maximize profit)
• Quadratic programming includes both linear and quadratic terms (minimize risk)
• Quadratic terms model more complex relationships between variables (economies of scale)
• Quadratic programming captures diminishing returns or increasing costs (marketing effectiveness)

Solution Characteristics

• Linear programming optimal solutions always occur at vertices of feasible region
• Quadratic programming optimal solutions may lie in interior of feasible region
• Interior solutions in quadratic programming reflect trade-offs between competing objectives
• Quadratic programming solutions often more realistic for real-world scenarios (portfolio allocation)

Computational Complexity

• Linear programming solved efficiently using simplex method or interior point methods
• Quadratic programming requires more complex algorithms (active set methods)
• Convexity of quadratic programming problems crucial for global optimality
• Non-convex quadratic programs may have multiple local optima, requiring global optimization techniques