# Tag Info

You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is undefined when $x_1=0$, so you need to deal with the case $x_1=0$ (and the case $x_2=0$) separately. Given the monotonicity of $L$, you can easily show that if $... 6 For an application to very large set covering problems you can see e.g. here This approach can be extended (somehow) to general MILPs and allows one to quickly find a “core” set of variables defining heuristically a restricted MILP to be solved by Cplex or alike. 6 I am not aware of specific algorithmic methods for MIPs that use Lagrangian multipliers directly. However, as for the interpretation of the solution of a MIP: probably one of the nicer applications I have seen comes from Martin Greiner from Aarhus university who solves a large-scale MIP of the European electricity prices with a focus on renewable energies. ... 5 It is explained in this link as: Simplex multipliers are essentially the shadow prices associated with a particular basic solution. Those are the multiples of their initial system of equations such that, when all of these equations are multiplied by their respective simplex multipliers and subtracted from the initial objective function, the coefficients of ... 5 Lagrangian relaxation is extremely common as an algorithmic method to solve facility location problems. Because many "minisum"-type problems ($p$-median, uncapacitated facility location problem, etc.) tend to have very tight LP relaxation bounds, the Lagrangian bound is also very tight. The use of LR for facility location dates back to the 1970s—the main ... 3 If you look at the "allowable decrease" in the RHS of the highlighted constraint, it's zero. A number of the binding constraints have either allowable increase or allowable decrease zero. That means that your primal solution is degenerate, and your dual problem has multiple optima. The highlighted difference probably means that the simplex solver ... 3 By dual feasibility, all that the authors mean is that$(x^{k+1}, \lambda^{k+1})$in Equation (1) satisfies the stationarity equation in the KKT optimality conditions for the problem shown at the top of your question. Recall that the stationarity equation for the problem is to find$x, \lambda$such that $$\nabla f(x) + A^{\top} \lambda = 0$$ 2 A proof that$x^*$is optimal can be achieved by a Taylor expansion around$x^*$at optimality. Observe that $$f(x^*+p) = f(x^*) + p^\top f'(x^*) + \frac12p^\top f''(x^*)p$$ Note that at a local optimum$\nabla f=0$and given that$f$is strictly convex it is a PD matrix with positive eigenvalues. Thus the third argument involving the Hessian$>0$thereby ... 2 Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP). Generally, there is no easy algorithm that is guaranteed to find the optimal solution of MIP problems quickly. My reason to believe that is: I can implement a boolean satisfiability (b-sat) ... 1 This sounds like parametric programming to me. In short, you can calculate a set of regions, typically called "critical regions", within which the same set of constraints is active. This in return enables you to calculate$x$,$\lambda$and$\mu$as an explicit function of your parameter$a$. There are MATLAB tools to do this, most prominently the ... 1 Minimize$x^2$where$1 \le x \le 2\$. \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^2 \\ h_{1}(x) &= 1 - x \\ h_{2}(x) &= x - 2 \end{align} KKT conditions: \begin{align} 0 &= \nabla f(x) + \mu_{1}\nabla h_{1}(x) + \mu_{2} \nabla h_{...