Quadratic optimization under linear constraints

• Quadratic optimization under linear constraints
• • Optimization under equality constraints
  • Under inequality constraints

Each iteration of the general algorithm requires to optimize a quadratic form under a linear inequality constraint. For this purpose, we must solve a quadratic optimization problem under a linear equality constraint.

Optimization under equality constraints

The general formulation of a quadratic optimization problem under linear equality constraint is as follow :

Optimize under the constraints .

This problem can be solved by using Lagrange multipliers. The constrained optimizer is the solution of the linear system:

Under inequality constraints

The general formulation of a quadratic optimization problem under linear equality constraint is as follow :

Optimize under the constraints where ≥ means that all the components of the left-hand side vector are greater than the ones of the right-hand side.

The principle of the algorithm is to produce a finite sequence x_1,...,x_v of point which satisfy the inequality constraints and such that . Such points are called feasible points.