= Conic dual problem
{title2=$\sup\{b^Ty:A^Ty=c,\ y\in K^*\}$}
A <conic dual problem> searches for a lower bound on a <conic optimization> problem. A <feasible point> exhibits an attainable cost; a feasible <dual variable> explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a <global minimum> without relying on how the points were found.
Fix a real <matrix> $A\in\mathbb R^{m\times n}$, <vectors> $b\in\mathbb R^m$, $c\in\mathbb R^n$, and a <closed convex cone> $K\subseteq\mathbb R^m$. With unrestricted $x\in\mathbb R^n$, use the convention
$$
p_* = \inf\{c^Tx:Ax-b\in K\},\qquad
d_* = \sup\{b^Ty:A^Ty=c,\ y\in K^*\},
$$
where the <dual cone> is $K^*=\{y:y^Ts\geq0\text{ for every }s\in K\}$. The <conic dual problem> uses $K^*$ because it must turn every allowed <slack variable> $s=Ax-b$ into a nonnegative <dot product>. Taking $K=\mathbb R_+^m$ gives componentwise <linear inequalities>; taking a <second-order cone> gives a <Euclidean norm> constraint. A <self-dual cone> has $K^*=K$, but this equality does not guarantee a <feasible point> or <strong duality>.
The <Lagrangian> supplies a short derivation. For $y\in K^*$,
$$
L(x,y)=c^Tx-y^T(Ax-b)=(c-A^Ty)^Tx+b^Ty.
$$
Its <infimum> over unrestricted $x$ is $b^Ty$ when $A^Ty=c$, and $-\infty$ otherwise. Maximizing the resulting <Lagrange dual function> gives the stated <conic dual problem>. The minus sign matches the convention $Ax-b\in K$.
Back to article page
