Linear programming (LP) vs quadratic programming (QP)

Linear Programming (LP): LP problems have an objective and all constraints that are linear functions of the decision variables. LP problems are intrinsically easier to solve than general nonlinear problems, as they have at most one feasible region with “flat faces” on its outer surface, and the optimal solution will always be found at a “corner point” on the surface where the constraints intersect.

Quadratic Programming (QP): QP problems have an objective that is a quadratic function of the decision variables, and constraints that are all linear functions of the variables. QP problems can be convex or non-convex, and the optimal solution may be found anywhere within the feasible region or on its surface.

Key differences:

• Objective function: LP problems have a linear objective function, while QP problems have a quadratic objective function.
• Constraints: Both LP and QP problems have linear constraints.
• Solution complexity: LP problems are generally easier to solve than QP problems, especially when the QP problem is non-convex.
• Solver efficiency: LP solvers are often more efficient than QP solvers, especially for large problems.

Relationship between LP and QP:

• LP is a special case of QP: Every LP problem can be formulated as a QP problem by setting the quadratic term to zero.
• QP solvers can be applied to LP problems: However, using a QP solver on an LP problem may be less efficient than using an LP solver.

Choosing between LP and QP:

• Use LP when: The objective function is linear, and the constraints are linear.
• Use QP when: The objective function is quadratic, and the constraints are linear.