Dual Descent and Primal infeasibility (near feasible)?

36 Views Asked by At

Suppose one considers a constrained and convex primal optimization problem:

$$P=\max f(x), \text{s.t.}\quad Ax\leq c$$

Consider now its Lagrangian:

$$L=\max f(x)+ \lambda ^T(c-Ax) $$

Suppose we perform dual-descent on $L$ and we converge to an optimal dual $\lambda^\star$. Then maximizing the lagrangian w.r.t. $x$ should yield the optimal primal $x^\star$.

Now suppose we arrive at a near-optimal dual variables $\tilde \lambda$ (for example by stopping before complete convergence). Then optimizing the lagrangian w.r.t. $x$ is not guaranteed to yield a feasible solution. How do we handle this case? Can we argue that this solution is near-feasible through a formal argument?

1

There are 1 best solutions below

2
On

Can I suppose that this happens in $\mathbb R^n$? If $A$ is a general operator, I think we can't help this case. Otherwise $f$ is convex on the whole space, so it is continuous. Therefor $L$ is continuous and the dual function as well. If you then maximize $L$ wrt $x$ for $\lambda^*$ something like the Taylor-like approximation tells you, that $x^*$ is an approximation of $x$.