Journal of Convex Analysis Volume 7 (2000), No. 1, 197–202

Absolute Minimizer in Convex Programming by Exponential Penalty

F. Alvarez^{∗}

Departamento de Ingeniería Matemática, Universidad de Chile, Casilla 170/3 Correo 3, Santiago, Chile. e-mail: falvarez@dim.uchile.cl

Received May 28, 1998 Revised manuscript received July 23, 1999

We consider a nonlinear convex program. Under some general hypotheses, we prove that approximate solutions obtained by exponential penalty converge toward a particular solution of the original convex program as the penalty parameter goes to zero. This particular solution is called the absolute minimizer and is characterized as the unique solution of a hierarchical scheme of minimax problems.

Keywords: Convexity, minimax problems, penalty methods, nonuniqueness, optimal trajectory, convergence

1991 Mathematics Subject Classification: 90C25, 90C31

1. Introduction

Let us consider a mathematical program of the type:

(P)  min_{x∈ℝ^{n}} {f_{0}(x) | f_{i}(x) ≤ 0, i = 1, ..., m} ,

where for each i = 0, ..., m, f_{i} is a convex function. The exponential penalty method consists in solving for r > 0 small enough the unconstrained problem

(P_{r})  min_{x∈ℝ^{n}} {f_{0}(x) + r ∑_{i=1}^{m} exp[f_{i}(x)/r]} .

We denote by x(r) an optimal solution of (P_{r}) and we regard it as an approximate solution of the original problem (P). Generally speaking, the convergence as r → 0^{+} of x(r) is well determined when (P) has a unique optimal solution. We are interested in the convergence of the whole optimal path {x(r) : r → 0^{+}} when (P) admits a multiplicity of optimal solutions. It is proved in [6] that for linear programs, x(r) converges toward the centroid, a sort of analytic center of the optimal polytope. A similar situation occurs for linear-quadratic minimax problems (see [1]).

The aim of this paper is to extend the convergence results of [1, 6] to a more general nonlinear setting. Under some conditions on the functions f_{i}, we prove that the approximate solution x(r) converges to a “distinguished” solution of (P), which is called the absolute minimizer and is characterized as the unique solution of a recursive hierarchy of

∗Supported by FONDECYT 1990884 and FONDAP Matematicas Aplicadas.

ISSN 0944-6532 / $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag

198 F. Alvarez / Absolute minimizer and exponential penalty

reduced minimax problems. A similar selection of a particular solution appears in the L^{p} approximation of L^{∞} problems (see [2] and references therein). See [3, 7, 11] for other path-following methods in linear and convex programming.

Exponential penalty methods have been widely applied since the pioneering work of Motzkin [12]. For constrained problems, it was introduced in [10] an exponential multiplier method (see also [4]); under uniqueness and second order sufficiency conditions, the convergence of this kind of algorithms can be established for several penalty functions (see [5, 14, 15]). Although it is possible to obtain dual convergence without these restrictive hypotheses (see [16]), primal convergence is not well understood in the case of multiple optimal solutions. For an implementable algorithm for solving convex programs by applying an exponential penalty technique, we refer the reader to [9]. A different approach is given in [13], where convergence is forced by combining the exponential penalty with a proximal regularization.

2. Absolute minimizer for convex minimax.

From now on, I = {1, ..., m} and f_{i} : ℝ^{n} → ℝ is convex for each i ∈ I. Set f̄(x) := max_{i∈I}{f_{i}(x)} and consider the minimax problem

(P̂)  μ^{∗} := min_{x∈F} f̄(x).

where F ⊂ ℝ^{n} is a closed convex set. We denote by S(P̂) the set of optimal solutions of (P̂), and we assume that S(P̂) is nonempty and compact. The question is how to distinguish a best optimal solution among all the elements in S(P̂). To this end, we define the set of optimal active indices by

I_{0} := {i ∈ I | ∀x ∈ S(P̂), f_{i}(x) = μ^{∗}}.

It is easy to see that I_{0} is nonempty. For each i ∈ I_{0} the corresponding f_{i} is constant on S(P̂) and for such an f_{i} all the solutions are in some sense equivalent. If I_{0} = I there is nothing else to do. Otherwise, there exist i_{0} ∈ I\I_{0} and an optimal solution x̂ such that f_{i_{0}}(x̂) < μ^{∗}; we consider

(P̂^{1})  μ_{1}^{∗} := min_{x∈S(P̂)} max_{i∈I\I_{0}}{f_{i}(x)},

in order to select the minimizers of max_{i∈I\I_{0}}{f_{i}} among all the minimizers of max_{i∈I}{f_{i}}. Of course, μ_{1}^{∗} < μ^{∗} and S(P̂^{1}) is nonempty and compact. Let A := {i ∈ I\I_{0} | ∀x ∈ S(P̂^{1}), f_{i}(x) = μ_{1}^{∗}}; it is a simple matter to verify that A is nonempty. If the set I_{1} := I_{0} ∪ A is not equal to I, we can proceed recursively and consider the following minimax problem

(P̂^{2})  μ_{2}^{∗} = min_{x∈S(P̂^{1})} max_{i∈I\I_{1}}{f_{i}(x)}.

We continue in this manner obtaining a sequence of problems of the type:

(P̂^{t})  μ_{t}^{∗} = min_{x∈S(P̂^{t−1})} max_{i∈I\I_{t−1}}{f_{i}(x)}.

By construction, we have a strictly increasing sequence of sets I_{0} ⊂ I_{1} ⊂ .... Therefore, I_{p+1} = {1, ..., m} = I for some p ≤ m. For each x̂ ∈ S(P̂^{p})

max_{i∈I\I_{t}}{f_{i}(x̂)} = μ_{t+1}^{∗} = min_{x∈S(P̂^{t})} max_{i∈I\I_{t}}{f_{i}(x)},

for all t ∈ {0, ..., p}, where I_{t}\I_{t−1} = {i ∈ I | ∀x ∈ S(P̂^{t}), f_{i}(x) = μ_{t}^{∗}} is the set of active indices for the problem (P̂^{t−1}). We consider S(P̂^{p}) as the set of best optimal solutions of the original minimax problem (P̂). Similar constructions can be found in [2, 3, 6].

The final optimal set S(P̂^{p}) depends on the analytical representation of f̄ = max_{i∈I}{f_{i}}. For instance, define f̄(x) = |x| if |x| > 1 and f̄(x) = 1 otherwise. Then S(P̂) = [−1, 1]. Setting f_{1} := 1/2 and f_{2} := f̄, we can write f̄ = max{f_{1}, f_{2}} to obtain S(P̂^{1}) = [−1, 1]. But if we set f_{1}(x) := 1 and f_{2}(x) := |x|, then S(P̂^{1}) = {0}. As this trivial example illustrates, in general we cannot ensure uniqueness of the solution generated by the hierarchical process defined above. Nevertheless, we may overcome this disadvantage by restricting our analysis to a suitable class of max-type representations.

Definition 2.1 ([2]). A function f : ℝ^{n} → ℝ is said to be quasi-analytic if whenever f is constant on the segment [x, y] with x ≠ y, then f is constant on the whole line passing through x and y.

Affine, quadratic and analytic functions are quasi-analytic. If we assume that for each i ∈ I, f_{i} is quasi-analytic then there exists a unique solution x^{∗} of the recursive hierarchy of minimax problems; to see this, fix x_{1}, x_{2} ∈ S(P̂^{p}) and note that each f_{i} is constant on [x_{1}, x_{2}] so that x_{2} − x_{1} is a constancy direction for every f_{i} and then x_{2} = x_{1} (recall that S(P̂) is bounded). We call such x^{∗} the absolute minimizer of (P̂).

3. Convergence toward the absolute minimizer

Let us return to the convex program

α := min_{x∈ℝ^{n}}{f_{0}(x) | f_{i}(x) ≤ 0, i ∈ I}.  (P)

We assume that f_{0} : ℝ^{n} → ℝ ∪ {+∞} is a closed proper convex function, and f_{i} : ℝ^{n} → ℝ are all convex. We tacitly assume that α is finite and we consider the penalty approximation

α(r) := min_{x∈ℝ^{n}} {f_{0}(x) + r ∑_{i∈I} exp[f_{i}(x)/r]} .  (P_{r})

When the optimal set S(P) is nonempty and compact, it is well-known (see for instance [3]) that: (i) for every r > 0, the optimal set S(P_{r}) is nonempty and compact; (ii) given r_{0} > 0 there exists a bounded set U such that S(P_{r}) ⊂ U for every r ∈ ]0, r_{0}]; (iii) each cluster point of {x(r) : r → 0^{+}} with x(r) ∈ S(P_{r}) belongs to S(P), and α(r) → α as r → 0^{+}. Certainly, this gives us the convergence of x(r) when (P) has a unique solution. In the case of multiple optimal solutions, we have:

Theorem 3.1. If S(P) is nonempty and compact, and for all i = 0, ..., m, f_{i} is quasianalytic, then for each r > 0 there exists a unique solution x(r) of (P_{r}), and furthermore

lim_{r→0^{+}} x(r) = x^{∗},

where x^{∗} is the absolute minimizer of

min_{x∈S(P)} max_{i∈I}{f_{i}(x)}.  (3.1)

Proof. To establish the uniqueness of x(r), fix r > 0 and x_{1}, x_{2} ∈ S(P_{r}). For every t ∈]0, 1[ set x_{t} := (1 − t)x_{1} + tx_{2}. If there exists i_{0} ∈ I such that f_{i_{0}}(x_{1}) ≠ f_{i_{0}}(x_{2}) then

exp[f_{i_{0}}(x_{t})/r] < (1 − t) exp[f_{i_{0}}(x_{1})/r] + t exp[f_{i_{0}}(x_{2})/r],

and for f(x, r) := f_{0}(x) + r ∑_{i∈I} exp[f_{i}(x)/r] we have

f(x_{t}, r) < (1 − t)f(x_{1}, r) + tf(x_{2}, r) = α(r),

which is impossible. Therefore, for each i ∈ I the function f_{i} is constant on S(P_{r}); hence f_{0} is also constant on S(P_{r}). The boundedness of S(P_{r}) implies x_{2} = x_{1} as claimed.

The task is now to prove the convergence of x(r). It suffices to show that {x(r) : r → 0^{+}} has as unique cluster point the absolute minimizer of (3.1). Let r_{k} → 0^{+} and x̂ ∈ S(P) be such that x(r_{k}) → x̂ as k → +∞. Let \overline{x} ∈ S(P) be arbitrary and set x_{k} := x(r_{k}) + \overline{x} − x̂. Thus x_{k} → \overline{x} as k → +∞. The optimality of x(r_{k}) for (P_{r_{k}}) gives

f_{0}(x(r_{k})) + r_{k} ∑_{i∈I} exp[f_{i}(x(r_{k}))/r_{k}] ≤ f_{0}(x_{k}) + r_{k} ∑_{i∈I} exp[f_{i}(x_{k})/r_{k}].  (3.2)

As S(P) is convex, for all t ∈ [0, 1] we have f_{0}(x̂+ t(\overline{x} − x̂)) = α. It is simple to see that if a quasi-analytic convex function f is constant on a segment [x, y] then f(z +x−y) = f(z) for every z ∈ ℝ^{n} (see [2]). Then the convexity and quasi-analyticity of f_{0} yields

f_{0}(x(r_{k})) = f_{0}(x(r_{k}) + \overline{x} − x̂).

Therefore, (3.2) gives

∑_{i∈I} exp[f_{i}(x(r_{k}))/r_{k}] ≤ ∑_{i∈I} exp[f_{i}(x_{k})/r_{k}].

Since for all y ∈ ℝ^{m} we have that

lim_{r→0^{+},z→y} r ln (∑_{i∈I} exp[z_{i}/r]) = max_{i∈I}{y_{i}},

we can let k → +∞ in the last inequality to obtain

max_{i∈I}\{f_{i}(x̂)\} ≤ max_{i∈I}\{f_{i}(\overline{x})\}.

Since \overline{x} ∈ S(P) is arbitrary, we have that x̂ solves

(P̂)  μ^{∗} = min_{x∈S(P)} max_{i∈I}{f_{i}(x)}.

Denote I_{0} := \{i ∈ I | ∀x ∈ S(P̂), f_{i}(x) = μ^{∗}\} and assume that I_{0} ≠ I. Let now \overline{x} ∈ S(P̂). We have that for all i ∈ I_{0} and t ∈ [0, 1] f_{i}(x̂ + t(\overline{x} − x̂)) = μ^{∗}; hence

f_{i}(x(r_{k})) = f_{i}(x(r_{k}) + \overline{x} − x̂).

Thus

∑_{i∈I\I_{0}} exp[f_{i}(x(r_{k}))/r_{k}] ≤ ∑_{i∈I\I_{0}} exp[f_{i}(x_{k})/r_{k}].

Letting k → +∞ in the last inequality, we obtain

max_{i∈I\I_{0}}\{f_{i}(x̂)\} ≤ max_{i∈I\I_{0}}\{f_{i}(\overline{x})\}.

We deduce that x̂ solves

μ_{1}^{∗} = min_{x∈S(P)} max_{i∈I\I_{0}}{f_{i}(x)}.

Repeated application of these arguments enables us to prove that x̂ solves the recursive hierarchy of minimax problems that define the absolute minimizer x^{∗} of (P̂), which completes the proof.

Remark 3.2. In practice, (P_{r}) is solved only approximately. An interesting open question is the extension of this result to the case of inexact solutions.

Acknowledgements. I wish to thank an anonymous referee for helpful comments concerning the presentation of this paper.

References

[1] F. Alvarez: Métodos continuos en optimización paramétrica, Engineering memoir, Universidad de Chile (1996).

[2] H. Attouch, R. Cominetti: L^{p} approximation of variational problems in L^{1} and L^{∞}, Nonlinear Anal. 36, 3, Ser. A (1999) 373–399.

[3] A. Auslender, R. Cominetti, M. Haddou: Asymptotic analysis for penalty methods in convex and linear programming, Math. Oper. Res. 22, 1 (1997) 43–62.

[4] D. P. Bertsekas: Approximation procedures based on the method of multipliers, J. Optim. Theory Appl. 23 (1977) 487–510.

[5] D. P. Bertsekas: Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, 1981.

[6] R. Cominetti, J. San Martín: Asymptotic analysis of the exponential penalty trajectory in linear programming, Math. Programming 67 (1994) 169–187.

[7] C. G. Gonzaga: Path-following methods for linear programming, SIAM Review 34 (1992) 167–224.

[8] N. I. M. Gould: On the convergence of a sequential penalty function method for constrained minimization, SIAM J. Numer. Anal. 26 (1989) 107–128.

[9] M. Grigoriadis, L. Khachiyan: An exponential-function reduction method for block-angular convex programs, Networks 26, 2 (1995) 59–68.

[10] B. W. Kort, D. P. Bertsekas: A new penalty function method for constrained minimization, in: Proceedings of the IEEE conference on decision and control, New Orleans (1972) 162– 166.

[11] N. Megiddo: Pathways to the optimal set in linear programming, in: Progress in Mathematical Programming: Interior-Point and Related Methods, Springer-Verlag (1989) 131–158.

[12] T. S. Motzkin: New technique for linear inequalities and optimization, in: Project SCOOP Symposium on Linear Inequalities and Programming, Planning Research Division, U.S. Air Force, Washington D.C., 1952.

[13] K. Mouallif, P. Tossings: Une méthode de pénalisation exponentielle associée à une régularisation proximale, Bull. Soc. Roy. Sci. Liege 56, 2 (1987) 181–192.

[14] R. A. Polyak: Smooth optimization methods for minimax problems, SIAM J. Control and Optimization 26, 6 (1988) 1274–1286.

[15] J. J. Strodiot, V. H. Nguyen: An exponential penalty method for non-differentiable minimax problems with general constraints, JOTA 27 (1979) 205–219.

[16] P. Tseng, D. P. Bertsekas: On the convergence of the exponential multiplier method for convex programming, Math. Programming 60 (1993) 1–19.