13.1 Formulation of quadratic programs

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

Top images from around the web for Mathematical Representation

• 

  Frontiers | Creating Better Collision-Free Trajectory for Robot Motion Planning by Linearly ... View original

  Is this image relevant?

• 

  Sequential quadratic programming - Wikipedia View original

  Is this image relevant?

• 

  quadprog | Scilab.in View original

  Is this image relevant?

• 

  Frontiers | Creating Better Collision-Free Trajectory for Robot Motion Planning by Linearly ... View original

  Is this image relevant?

• 

  Sequential quadratic programming - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Mathematical Representation

• 

  Frontiers | Creating Better Collision-Free Trajectory for Robot Motion Planning by Linearly ... View original

  Is this image relevant?

• 

  Sequential quadratic programming - Wikipedia View original

  Is this image relevant?

• 

  quadprog | Scilab.in View original

  Is this image relevant?

• 

  Frontiers | Creating Better Collision-Free Trajectory for Robot Motion Planning by Linearly ... View original

  Is this image relevant?

• 

  Sequential quadratic programming - Wikipedia View original

  Is this image relevant?

1 of 3

• 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