The Slacked Unconstrained Minimization Technique for Convex Programming

An algorithm for solving the problem: minimize $f( x )$ (a convex function) subject to gᵢ ( x ) 0, i = 1, ⋯ ,m, each gᵢ a concave function, is presented. Specifically, the function \[ P[ {x,t,r_k } ] ≡ f( x ) + r_k- 1 ∑ {[ {g_i ( x ) - t_i } ]} ^2 \] is minimized over all x, nonnegative t, for a strictly decreasing null sequence \ rₖ \. This extends the work of T. Pietrzykowski [5]. It is proved that for every rₖ > 0, there exists a finite point [ x( rₖ ),t( rₖ ) ] which minimizes P, and which solves the convex programming problem as rₖ → 0. This algorithm is similar to the Sequential Unconstrained Minimization Technique (SUMT) [1] in that it solves the (Wolfe) dual programming problem [6]. It differs from SUMT in that (1) it approaches the optimum from the region of infeasibility (i.e., it is a relaxation technique), (2) it does not require a nonempty interior to the nonlinearly constrained region, (3) no separate feasibility phase is required before optimization takes place, (4) the computational effort per iteration is reduced.