Primal Dual Active Set Algorithm

The Primal-Dual-Active-Set-Algorithm is a method to solve a quadratic optimization problem over a convex subset of a Hilbert space over the set . ${\displaystyle S}$ ${\displaystyle V}$ ${\displaystyle \Omega }$

The problem

A quadratic optimization problem is a problem of the following form: A convex set is given that is bounded by an upper bound : ${\displaystyle {\overline {v}}\in V}$

${\displaystyle S:=\{v\in V:v(x)\leq {\overline {v}}(x)\forall x\in \Omega \}}$

Find such that: ${\displaystyle y\in S}$

${\displaystyle y={\text{argmin}}_{v\in S}{\frac {1}{2}}a(v,v)-l(v)}$.

Here is a symmetric continuous bilinear form and a continuous linear operator . ${\displaystyle a(\cdot ,\cdot ):V\times V\rightarrow V}$ ${\displaystyle l:V\rightarrow V}$

The algorithm

This article or section is not worded in a generally understandable manner. The shortcomings are described under Discussion: Primal-Dual-Active-Set-Algorithm . If you remove this block, it is founded, please visit the article talk page, and fill up the project page section created automatically Wikipedia: Incomprehensible Item # primal-dual active set algorithm to{{ Done | 1 = ~~~~}}.

The following should be improved: Various things are unclear. For example: is a vector (as in the formulation of the KKT conditions) or a number? How is it initialized? What is a solution from "in "? Does this refer to the s? Or the s? Or both? In addition, the formulation in its abstract form over a Hilbert space is not exactly conducive to general understanding. ${\displaystyle \lambda }$ ${\displaystyle \lambda }$ ${\displaystyle a(y^{(k)},v)=l(v)}$ ${\displaystyle A^{(k)}}$ ${\displaystyle y}$ ${\displaystyle v}$

The Primal Dual Active Set algorithm uses the Lagrange multiplier to arrive at a solution that is both allowed and optimal. The algorithm works as follows: ${\displaystyle \lambda }$

1. Calculation of the active amount and the inactive amount ${\displaystyle A^{(k)}:=\{x\in \Omega :y(x)+\lambda (x)\geq {\overline {v}}(x)\}}$ ${\displaystyle I^{k}:=\Omega \setminus A^{(k)}}$
   
2. Solution to the following problem

   ${\displaystyle a(y^{(k)},v)=l(v){\text{ in }}A^{(k)}}$

   and

   ${\displaystyle y^{(k)}(x)={\overline {v}}(x)\,\forall x\in A^{(k)}}$

3. If the solution does not meet the Lagran conditions, a set is made and a restart is made at (1) ${\displaystyle k:=k+1}$

Applications

The primal-dual-active-set algorithm is used in particular for the solution of restricted problems via partial differential equations , since the weak formulation of a linear elliptic partial differential equation is precisely a quadratic optimization problem .

Convergence properties

By considering the Primal-Dual-Active-Set-Algorithm as a semi-smooth Newton method , locally superlinear convergence can be shown. For one-sidedly bounded convex subsets the global convergence of the primal-dual-active-set algorithm can be shown over finite-dimensional Hilbert spaces.

Web links

• Sample exercise (PDF; 17 kB; English)

Individual evidence

1. ↑ M. Hintermuller, K. Ito, K. Kunisch: The primal-dual active set strategy as a semismooth Newton method . In: SIAM J. Optim , 2003.
2. ^ A dual-active-set algorithm for positive semi-definite quadratic programming . NL Boland - Mathematical Programming. Springer, 1996.