Abstract—Most independent system operators (ISOs) adopt bid cost minimization (BCM) to select bids and their generation levels while minimizing the total cost of the offer. It has been shown that customer payment costs resulting from selected offers can differ significantly from customer payments resulting from payment cost minimization (PCM), whereby payment costs are minimized directly. To solve PCM in dual space, the Lagrangian relaxation and surrogate optimization approach is often used. When standard optimization methods, such as branch-and-cut, become ineffective due to the large size of a problem, Lagrangian relaxation and the surrogate optimization approach provide a good feasible solution in reasonable CPU time. The convergence of the standard Lagrangian relaxation and the surrogate subgradient approach depends on the optimal dual value, which is usually unknown. Furthermore, when using the surrogate subgradient approach, the upper bound property is lost, so additional conditions are needed to ensure convergence. The main goal of this paper is to develop a convergent variation of the surrogate subgradient method without invoking the optimal dual value and to show the relevance and effectiveness of the new method for solving large constrained optimization problems, such as PCM.I. INTRODUCTIONCURRENTLY, most ISOs in the United States adopt the bid cost minimization (BCM) settlement mechanism to minimize total bid costs. In this setup, customer payment costs, which are determined by a mechanism that assigns uniform market equilibrium prices (MCPs), are different from minimized bidding costs. An alternative method for determining customer payment costs is ...... half the card ...... friendly step size [8]. Perhaps the most recent and comprehensive survey of subgradient methods for convex optimization is [2]. The approach to Lagrangian relaxation and optimization of surrogate subgradients has been specifically addressed in [6] and [5]. The first paper develops the surrogate subgradient method and demonstrates its convergence. Compared to subgradient and gradient methods, the surrogate subgradient approach finds better and smoother directions in less CPU time. This latest paper extends the methodology to coupled problem solving. Since the optimal dual value or multipliers remain unknown, it is necessary to develop the surrogate subgradient method, whose convergence does not depend on the optimal dual value. The convergence of the surrogate subgradient method with dynamic or constant pitch is still remains an open question.