Constrained optimization: Difference between revisions

Revision as of 00:31, 16 July 2018

Revision as of 20:58, 18 July 2018

Line 27:

===Inequality constraints===

With inequality constraints, the problem can be characterized in terms of the [[Geometricgeometric optimality conditions]], [[Fritz John conditions]] and [[Karush–Kuhn–Tucker conditions]], inunder which simple problems may be solvable.

====Linear programming====

If the objective function and all of the hard constraints are linear and some hard constraints are inequalities, then the problem is a [[linear programming]] problem. This can be solved by the [[simplex method]], which usually works in [[polynomial time]] in the problem size but is not guaranteed to, or by [[interior point method]]s which are guaranteed to work in polynomial time.

====Quadratic programming====

If all the hard constraints are linear and some are inequalities, but the objective function is quadratic, the problem is a [[quadratic programming]] problem. It can still be solved in polynomial time by the [[ellipsoid method]] if the objective function is [[Convex function|convex]]; otherwise the problem is [[NP hard]].

===Constraint optimization problems===