There is a wide consensus that the shadow prices of certain resources in an economic system are equal to Lagrange multipliers. However, this is misleading with respect to multiple Lagrange multipliers. In this paper, we propose a new type of Lagrange multiplier, the weighted minimum norm Lagrange multiplier, which is a type of shadow price. An attractive aspect of this type of Lagrange multiplier is that it conveys the sensitivity information when resources are required to be proportionally input. To compute the weighted minimum norm Lagrange multiplier, we propose two algorithms. One is the penalty function method with numeric stability, and the other is the accelerated gradient method with fewer arithmetic operations and a convergence rate of $ O(\frac{1}{k^2}) $. Furthermore, we propose a two-phase procedure to compute a particular subset of shadow prices that belongs to the set of bounded Lagrange multipliers. This subset is particularly attractive since all its elements are computable shadow prices. We report the numerical results for randomly generated problems.
The minimum norm Lagrange multiplier, as a type of informative Lagrange multiplier, is proposed to replace the classical shadow price when the later fails to exist. This kind of multiplier expresses the rate of cost improvement when the right-hand side of the constraints are permitted to slightly violated. However, the minimum norm Lagrange multiplier may fail to be informative in fully parametric optimization problems. In this paper, we extend the classical constraint violation condition to a general formulation, which captures the characteristics of the problem structure of nonlinear parametric programming models. Based on the generalized constraint violation condition, we provide sufficient conditions for the minimum norm Lagrange multiplier to be informative. Furthermore, we propose a kind of penalty function method to derive the informative Lagrange multiplier in fully parametric programming models, which means that the perturbations are not only on the right-hand side of the constraints. Finally, we use examples to support our theoretic results.
Column generation is a fundamental technique for solving large-scale combinatorial optimization problems such as unit commitment and vehicle routing, yet its performance is often limited by dual oscillation. This study explores the intrinsic cause of this phenomenon from the perspective of shadow price theory and demonstrates that dual oscillation arises from the lack of marginal interpretability of Lagrange multipliers when multiple dual solutions coexist. To address this issue, an improved column generation framework is proposed in which traditional multipliers are replaced with minimum-norm multipliers that possess clear economic meaning and act as directional shadow prices. A generalized pricing subproblem is formulated, and partial minimum-norm multipliers are obtained through convex quadratic optimization to guide column generation. Numerical experiments on a simplified single-period unit commitment case and large-scale cutting stock problems showed that the proposed approach eliminated invalid column generation and achieved speedy convergence to the optimal solution within only two iterations for the unit commitment case, and the classical column generation exhibited slow convergence with dual oscillation in large-scale scenarios while the improved algorithm achieved fast and stable convergence. The results indicate that the stabilization method enhances the consistency of dual variables and provides a more robust foundation for the theoretical and practical development of column generation algorithms.