© M. Hassan and A. Baharum, published by EDP Sciences, 2019

1 Introduction

Duality principle provided an avenue to view an optimization problem from one of the two perspectives, the primal problem (original formulation) or the dual problem (an alternative formulation). The purpose of duality in mathematical programming is to devise an alternative to the optimization problem which might be more convenient computationally or analytically. One interesting property of the dual problem is that its solution need not be equal to that of the primal problem. However, it provides a lower bound to the solution of the primal minimization problem. In general, the difference between the optimal values of the two problems is term as duality gap, if the optimal coincide then no duality gap occurs.

Based on the recent development, one of the suitable approaches in solving nonlinear optimization problem is an unconstrained optimization technique, this technique by extension can also be used to solve constrained optimization problem via a penalty function method. The idea is to carry out by transforming the original nonlinear constrained optimization problem to a single or a sequence of unconstrained optimization problems [1].

Several types of researches have been conducted to demonstrate the idea of a penalty function method and Lagrangian duality in contrast to the conventional approach for solving the constrained optimization problem [2–9].

The concept of duality and penalty function method are essential topics in optimization theory, methods and its applications [10]. There are many advancements regarding those topics in mathematical programming. The work of Changyu et al. [11] proposes a general dual program via generalized nonlinear Lagrangian functions for the constrained optimization problem. However, a dual program consists of a class of general dual programs that possess some explicit structures as special cases. Gao et al. [12] justified that a dual canonical transformation can be used to solve the general non-convex quadratic minimization problem with non-convex constraints, this can only be achieved by converting a non-convex problem into a canonical dual problem with zero duality gap. Antczak [13] combined the idea of exact penalty function and duality theory to investigate and prove the zero duality gap between optimization problems constituted by invex functions introduced by Hanson [14] named by Craven [15] and their Lagrangian dual under some mild assumptions. Ernst and Volle [16] pay more attention to conic convex and established a general zero duality gap for conic convex via generalized Courant-Beltrami penalty function. Kanzi and Soleimani-damaneh [17] proposed and reviewed the Slater constraint qualification (CQ) specifically for a semi-infinite optimization problem, which involved upper semi-continuous quasi-convex objective and constraint functions, Karush-Kuhn-Tucker (KKT) necessary and sufficient optimality conditions were provided.

The distance function was used by Soleimani-Damaneh [18] to illustrates a penalization mechanism, it was specifically designed for providing necessary and sufficient conditions to the solutions of the variational inequality problem. Moreover, Soleimani-Damaneh [19] used mordukhovich's subdifferential to solve nonsmooth optimization and variational problems.

In this paper, we modified a Courant-Beltrami penalty function method, prove and obtain a few optimality and duality results. Precisely, for smooth optimization problems involving invex functions with respect to the same function η via a modified Courant-Beltrami (MCB) penalty function method. Lagrange multiplier vectors based on MCB penalty has been derived. Moreover, a zero-duality gap under some mild assumptions was also established and validated with some examples.

The entire presentation is organized as follows: In Section 2, some preliminary definitions and results that will be useful in the subsequent sections were presented. In Section 3, we present the concept of a penalty function approach and the modification made to Courant-Beltrami penalty function. In Section 4, the derivation of KKT multiplier in view of MCB penalty was presented. In Section 5, the Lagrangian duality and some examples were discussed and finally, we conclude the paper.

2 Preliminary result

We consider the following optimization problem:(1)where f : X → R and g _i  : X → R, i ∈ I, are continuously differentiable functions on a nonempty set X ⊂ R ⁿ .

Some notations that are used throughout this presentation will be introduced. Let F = {x ∈ R ⁿ  : g _i (x) ≤ 0,⩝  i = 1, 2, … , m}, be the set of all feasible solutions of the problem (1).

If the set of indices I partition into I ₁ and I ₂ with I ₁ ∩ I ₂ = ∅ , I ₁ ∩ I ₂ = I, the set of active constraints at a point x ∈ R ⁿ can be denoted as .

Definition 1. [13] If the set of all feasible solutions in the problem (1) is not empty, we say that problem (1) is consistent.

Definition 2. [13] If there exists a strictly feasible solution , that is, , i ∈ I, then problem (1) is super-consistent, and the feasible point is called a Slater point for the problem (1).

Under slightly reasonable convexity assumptions of f (x), and g _i  (x) , the KKT conditions are also necessary and sufficient for optimality of such optimization problem (1).

Theorem 1. Let be an optimal solution to the problem (1) and the suitable constraint qualification [10] be satisfied at . Then there exist the Lagrange multipliers , i = 1, … , m such that(2) (3) (4)

Let assume that is an optimal solution to mathematical programming problem (1) and a suitable constraint qualification be satisfied. Furthermore, the necessary optimality of KKT conditions holds at with the optimal vector of KKT multiplier ξ ∈ R ^m . Then the Lagrangian can be defined as(5)

Invex function is the wider class of convex introduced by Hanson [14] and named by Craven [15]. This new class of function is termed generalized convex functions.

Definition 3. [14] Let f : X → R be a differentiable function on X ⊂ R ⁿ and u ∈ R ⁿ . If, there exists a vector-valued function η : R ⁿ  × R ⁿ  → R ⁿ such that, ∀x ∈ X, the following inequality(6)

Holds, then the function f is said to be an invex (strictly invex) function with respect to η at u on X.

If (6) holds at each point u ∈ R ⁿ , then f is said to be an invex (strictly invex) function with respect to η on R ⁿ .

For a problem (1) to be an invex optimization problem, all functions constituting the problem (1) must be an invex function on R ⁿ with respect to the same function η. If the optimization problem (1) is super-consistent with an invex constraint g _i on R ⁿ (w.r.t. the same function η) then the problem (1) satisfies the Slater constraint qualification (CQ).

3 Penalty function

Penalty method is one of the suitable approaches for solving nonlinear constrained optimization problems. The idea is achievable if constrained optimization is replaced by a single or a sequence of unconstrained problems. Ideally, the solutions of the transformed problem will always converge to the solution of the original problem. The primary role of the penalty term is to penalize the problem whenever a constraint is violated and to search for the optimum among the feasible points. There are several penalty functions in the literature, and the most popular among them was the absolute value penalty function introduced by Zangwill [1]. For a given constraint g _i (x) ≤ 0, the absolute value penalty function is (7)

Note that the function is defined by , penalty function (7) was later modified to quadratic form, popularly known as Courant-Beltrami penalty function [8,9](8)

Definition 4. [1] A continuous function p : R ⁿ  → R, is said to be a generalized penalty function (penalty function) for the constrained optimization problem (1) if it satisfied the following conditions:

• p(x) = 0 for all feasible points x to the problem (1)

• p(x) > 0 for infeasible points to the problem (1)

Note, that the conditions in Definition 4 are direct interpretations of whether the constraints function g _i is violated or not.

We modified a quadratic form of penalty function (8), popularly known as Courant-Beltrami penalty function, to a logarithmic form based on the new logarithmic penalty function that was restricted to equality constraints introduced by Hassan and Baharum [20]. The modified Courant-Beltrami (MCB) penalty function performs the same role as the existing penalty functions. The MCB penalty function can be express in the following form: (9)

Let a non-negative constant c be a penalty parameter, c _k  ≥ 0, k = 1, 2, … may be a sequence of penalty parameters with c _k+1 ≥ c _k  ∀ k and .

Accordingly, we converted the considered optimization problem (1) into the single of unconstrained problems based on the penalty function (9) as follows(10)

We should call the problem (10) modified Courant-Beltrami penalized optimization problem.

Theorem 2 [13]. Suppose that f, g, and p are continuous functions. Let {x _k }, k = 1, 2, … be a sequence of solutions in the penalized problem (10). Then any limit of the convergent subsequence {x _{k j} } solves the original nonlinear programming problem (1).

4 Karush-Kuhn-Tucker multiplier for the penalized problem

In optimization problems, the first order necessary conditions for a nonlinear optimization problem to be optimal is Karush-Kuhn-Tucker (KKT) conditions, or Kuhn-Tucker conditions if some of the constraint qualifications are satisfied. Nevertheless, Courant-Beltrami penalty function may not be differentiable at a point g _i  (x) = 0 for some i ∈ I. But for the constrained optimization both objective function and constraints may be partially differentiable on R ⁿ while the penalized problem is not, since the differentiability is not among the properties of max {0, g _i  (x)}. According to Proposition 1 [21], some additional assumptions may be imposed on the constraint function g _i  (x), i.e. if the constraint g _i  (x) has continuous first-order partial derivatives on R ⁿ , for this reason, admit the same. Therefore, (11)

Considering equation (11), if p (x): R ⁿ  → R is a modified Courant-Beltrami (MCB) penalty function and the constraints g _i  (x) has continuous first-order partial derivative on R ⁿ , then

Theorem 3. Let x* be an optimal solution to the problem (1) and it satisfies the first-order necessary optimality conditions of the constrained problem (1). Moreover, a suitable CQ be satisfied at x*, then x* is a solution to the penalized problem (10).

Proof. If x* is a feasible point which satisfies the first-order necessary optimality conditions of the problem, then

That is(12)

Let us define(*)

Then (12) can be rewritten aswhere is a vector of KKT multiplier and for all i ∈ I. Therefore, Lagrange multipliers for the penalized problem (10) can be represented as . □

5 Lagrangian duality

We consider the following dual problem for the considered nonlinear optimization problem (1) (13)

Definition 5. A vector ξ is said to be a feasible solution for the dual problem (13) if

Note that if the problem (13) has at least one feasible vector ξ then the problem is called a consistent and any feasible vector satisfying is an optimal solution to the problem (13).

The relationship between primal and dual problem for the invex problem (i.e. if all the functions constituting the problem are invex on R ⁿ w.r.t. the same function η) is either zero or a positive real number. Moreover, if a feasible solution of the dual problem returned a primal objective value lower bound, then it is referred as the weak duality, while in the absence of duality gap (when their difference is zero), then it is called strong duality.

Let P = inf {f (x) : g _i  (x) ≤ 0, i = 1, 2, … , m . x ∈ R ⁿ } and D = sup {ϕ (ξ) : ξ ∈ R ^m , ξ ≥ 0} be the primal and the dual optimal respectively. The following inequality related both optima: P ≥ D (if the problem (1) and (13) are consistent).

Let G represent the duality gap between the two problems that is, G = P − D ≥ 0.

Theorem 4. (Weak duality theorem): Let the functions constituting the problem (1) be continuously differentiable on R ⁿ . Suppose that the problem (1) and (13) are consistent, then their optima are finite and G ≥ 0.

Proof. Let problem (1) and (13) has any feasible solution x and ξ, respectively. The feasibility of x implies that g _i (x) ≤ 0, i = 1, 2, … , m. If ξ is feasible to the problem (13). Then ξ _i g _i  (x) ≤ 0, i = 1, 2, … , m. So,(14)

The right-hand side of the inequality (14) is Lagrange function. Therefore, f(x) ≥ L(x, ξ).

Since both x and ξ are randomly chosen feasible points in (1) and (13) respectively, then(15)

It follows directly from inequality (15) that(16)

Consequently,(17)

Therefore, (16) and (17) justified that P and D are finite if (1) and (13) are consistent and P ≥ D. This verified the relationship between the two problems. i.e. G ≥ 0. □

Definition 6. A continuous function f (x) that is defined on R ⁿ is coercive if

That is, for any constant M > 0 ∃ R _M  > 0 such that ||f (x)|| > M whenever ||x|| > R _M .

Theorem 5. (Strong duality theorem): Let the functions constituting the problem (1) be continuously differentiable on R ⁿ . Further, assume that those functions in the problem (1) are invex with respect to the same function η, also an objective function in (1) is coercive. If an optimization problem (1) is consistent then its dual problem (13) is also consistent and their optimal solutions coincide, that is, G = 0.

Proof. To prove Theorem 5, we use the modified Courant-Beltrami penalty function method. As described in this approach, we need to construct an unconstrained optimization problem as follows:

Suppose that at the kth iterations, x _k is an optimal solution to the penalized problem (10). Therefore, for every positive integer c _k , P(x _k ,c _k ) = min {P(x, c _k ) : x ∈ R ⁿ  } . Moreover, the sequence {x _k } is bounded and of all its convergent subsequences have limits as described in the penalty function method (see Prop. 15 [13]), these limits are the solutions to the original problem (1). By Theorem 3, it follows that

Since x _k is an optimal solution of the problem (10), let assume that is a convergent subsequence of {x _k }, then the condition below is satisfied.(18)

According to KKT multiplier defined in (*), the Lagrange multipliers are given by

Accordingly, for each j,

.

From (**) is non-negative. Therefore, for each j, Lagrange multipliers satisfy , then, by (18) and (**), we have .

Since the functions constituting the problem (1) are invex functions on R ⁿ with respect to the same function η. Thus, based on Definition 3, ∀x ∈ R ⁿ , we have(19)

Then, multiplying the second part of (19) by the Lagrange multiplier vector, we get(20)

Upon combining and rearranging the first part of (19) and (20), we have(21)

Then, according to (21) the Lagrange function is an invex function with respect to the same function η as in Definition 3 with stationary points according to equation , and the points are global minimum of the function L. Therefore,(22)

From (22), it follows that the Lagrange multiplier vector is feasible for the dual problem (13). By hypothesis, the optimization problem (1) is consistent with the coercive objective function. Then, the problem has a solution with primal optimal value P  > − ∞. Consequently, for each j (23)

The reason for (23) is based on the assumptions that the limit point of the convergent subsequence is an optimal solution to the original problem (1). By the construction of modified Courant-Beltrami penalized problem, we have(24)and considering the definition of g ⁺ (x), it is obvious that(25)

But is not feasible in the original optimization problem, then in (25) can be expanded and rewritten in the following form:(26)

Then, by (**) inequality (26) can be replaced with(27)

Therefore, according to definition of Lagrange function, we have

Since is a convergent subsequence of {x _k }, then by (22)

So,(28)

Consequently, by (23) and (28) (29)

Since the sequence {x _k } converge to , which is optimal to the original problem (1) and f is a continuous function on R ⁿ , then we conclude that ⇒P ≤ D. Also, by Theorem 4, P ≥ D. Combining the two results (i.e. G ≤ 0 and G ≥ 0), P = D. □

The results established in this paper will be illustrated with some examples, using a modified Courant-Beltrami penalty function method. Precisely, for invex optimization problem.

Example 1. [22] Consider the following optimization problem:

This problem can be verified that the objective function f and both constraints functions g ₁ and g ₂ are invex functions on the set X with respect to the same function η defined bywhere

Modified Courant-Beltrami penalty function method defined by (10) can be used to solve the problem. Converting the problem in to unconstrained problem, we obtained the following:(30)

Note that, the set of feasible solutions F = {(x ₁, x ₂) ∈ X : x ₁ ≥ 0, x ₂ ≥ 0}. The points (0, 0) is an optimal to the problem, since the conditions (2)–(4) are satisfied with Lagrange multipliers , and penalty parameter it is also a minimizer to penalized problem (30).

Furthermore, according to the definition of Lagrange function, the Lagrangian dual for the considered problem can be constructed as follows:

The optimal values of ϕ (ξ) and P (x, c) are the same considering that all the stated assumptions in Theorem 5 are satisfied, the duality gap is 0 (i.e. G = 0).

Let us now consider the case when some assumptions in theorem were not fulfilled. In this case, the duality gap may no longer be equal to 0 (G ≠ 0).

Example 2. [13] Consider the following optimization problem:

Obviously, the objective f is coercive, but it is not invex on R with respect to any function η : R × R → R, due to the facts that the stationary point x = 0 of f is not its global minimum point.

The penalized problem can be constructed as follows:(31)

The feasible point x = − 1 is an optimal in (31) with the optimal value . Thus, the Lagrangian dual as defined by (13) is as follows:(32)

Clearly, the dual problem (32) is consistent since with . Hence which is greater than 0.

6 Conclusion

In this paper, we modified a penalty function that should be called a modified Courant-Beltrami (MCB) penalty function method. We combined the concept of Lagrangian dual and penalty function approach to investigate and prove the relationship between an optimization problem (1) and its Lagrangian dual problem (13). The zero-duality gap for invex optimization problem has been established under some moderate assumptions. Some examples were presented which verified that those assumptions are essential to establish a zero-duality gap between the two problems. In the future research, MCB penalty function method will be applied to solve;

• Multi-objective constrained optimization problem and

• The practical problem from any of the following areas;

  • Engineering

  • Decision theory and

  • The chemical process, etc.

References