Semi-continuous quadratic optimization: existence conditions and duality scheme

Abstract

In this work, we study the class of problems called semi-continuous optimization, which contains constrained minimization (maximization) problems with lower (upper) semi-continuous objective functions. We show some existence conditions for solutions based on asymptotic techniques, as well as a duality scheme based on the Fenchel–Moreau conjugation specifically applied to semi-continuous problems. Promising results are obtained, when we apply this scheme to minimize quadratic functions (whose Hessians can be symmetric indefinite) over nonempty, closed and convex polyhedral sets.

1 Introduction

In this work, we study the semi-continuous minimization (SCM) problem that consists of minimizing a proper lower semi-continuous function over a nonempty and closed set. While, in the class of semi-continuous maximization problems, the objective function is proper and upper semi-continuous.

It is known that in classical optimization theory, the Weierstrass Theorem guarantees the existence of solutions for SCM, whenever its feasible set is compact, [1, 2]. In order to deal with unbounded feasible sets, existence of solutions is, in general, studied by using asymptotic techniques. In this sense, several coerciveness conditions have appeared in the literature, [1, 3–6]. However, we observe that coerciveness conditions rely on boundedness of lower level sets of the objective function of the optimization problem being studied. As the solution set of an optimization problem is exactly the intersection of all nonempty lower level sets, this idea of using coerciveness conditions comes up naturally, since compactness of lower level sets ensures a nonempty intersection.

In this work, we first study existence conditions for solutions of SCM problems based on asymptotic notions. The existence conditions for SCM, that will be introduced here, recover, in a simple way, the results of the Frank–Wolf Existence Theorem for the minimization of a quadratic objective function over a nonempty polyhedral set [7].

As the study of existence conditions is theoretical, it would be nice that some practical procedures could be introduced to find solutions of SCM problems. As we know, the SCM problem is hard to solve analytically, since it does not have enough mathematical structure to characterize its optimal solutions. An alternative is to investigate its associated dual problem.

For a convex optimization problem, the Fenchel conjugation plays a very important role in the duality theory, in which an associated convex dual problem can be formalized, [2, 8–11]. As we already know, the relation between primal and dual problems are very rich in the sense that many theoretical developments can be obtained, as well as it can devise competitive solution methods.

On the other hand, when the objective function of an optimization problem is not necessarily convex, as in the SCM problem, we turn our attention to the Fenchel–Moreau conjugation for lower semi-continuous functions, presented in [12], where a particular coupling function for the Moreau’s extension [13] of Fenchel’s conjugation is considered in order to present a convex conjugate function for a lower semi-continuous function. Regarding the Moreau’s extension for the conjugation of a convex function, depending on the choice of the coupling function, the conjugate function might be non-convex (see [12] for more details).

In fact, the Fenchel–Moreau conjugation has been already studied in a general manner in [10, 14–18], and it is implicit in [11]. However, here, we apply the general scheme specifically for the SCM problems.

In this work, we claim that, despite the lack of mathematical structure, whenever the SCM problem has solutions, its optimal solution value can be attained through the solution of its associated dual convex problem, using the Fenchel–Moreau conjugation, as in [12]. As the associated dual problem has an infinite dimensional feasible set, promising results are obtained, in particular, for minimization of quadratic functions over nonempty, closed and convex polyhedral sets, when we consider an alternative conjugate dual space with finite dimension.

This paper is organized as follows. Section 2 presents the background material, such as some notions on recession techniques and a summary of the main theoretical results, by applying Fenchel–Moreau conjugation for lower semi-continuous functions. Some existence conditions for solutions of SCM problems are given in Sect. 3. Section 4 presents the duality scheme in order to get a convex dual problem associated with the SCM problem. In particular, regarding the dual problem of a linearly constrained quadratic problem, we show that it is possible to work in an alternative conjugate dual space with finite dimension, when the polyhedral set is convex. Finally, some concluding remarks are drawn in Sect. 5.

2 Preliminaries

Before the presentation of the background material, we introduce the main notation used hereafter. The scalar product of two vectors $x$ and $y$ in $I\!R^n$ will be denoted by $\langle x, y \rangle$, and $\Vert x\Vert$ will denote the Euclidean norm $\langle x, x \rangle ^{1/2}$. $B(c,r)$ will denote the $n$-dimensional open ball with center $c$ and radius $r$.

For a set $K\subset I\!R^n$, the asymptotic or recession set of $K$ is

$$\begin{aligned} K^\infty :=\{x\in I\!R^n:~\exists ~\{t_i\}\downarrow 0,~~\exists ~\{x_i\}\in K,~~t_i x_i\rightarrow x\}, \end{aligned}$$

(1)

where $\downarrow$ means that the sequence $\{t_i\}$ converges to zero and $t_i > 0$ for all $i \in I\!N$ (see Definition 2.1.1 in [1]). By convention, $\emptyset ^\infty = \{ 0\}$, [1]. The set ${ clK}$ denotes the closure of $K$, whereas $conv K$ denotes the convex hull of K.

For a function $h : I\!R^n \rightarrow I\!R\cup \{+\infty \}$, the lower level set of $h$ associated with $\lambda \in I\!R$ is denoted by $L_h(\lambda ):=\{x\in I\!R^n : h(x)\le \lambda \}$. Observe that there are two particular cases in which we use the same notation; the first one is when $\lambda = -\infty$, and in this case we have $L_h(\lambda ) = \emptyset$. The second case is when $\lambda = +\infty$, and in this case $L_h(\lambda ) = I\!R^n$. We denote the effective domain of $h$ as $dom(h) := \{x\in I\!R^n : h(x) < +\infty \}$.

The key for devising asymptotic or recession techniques for existence conditions is the concept of asymptotic or recession sets. Next, we present some basic results with respect to recession sets, that will be used in the sequel.

Regarding the recession set of $K$, we have the following key property (see Proposition 2.1.2 in [1]):

$$\begin{aligned} K \text{ is } \text{ bounded } \text{ if } \text{ and } \text{ only } \text{ if } K^\infty = \{ 0 \}. \end{aligned}$$

In case $K$ is a nonempty, closed and convex subset of $I\!R^n$, it is known that, for any $x_0 \in K$

$$\begin{aligned} K^\infty =\{x\in I\!R^n: ~x_0+t x\in K, \quad \forall t>0\}. \end{aligned}$$

(2)

Note that the definition of $K^\infty$ in (2) considers only algebraic structure, while the definition in (1) considers algebraic and topological structures.

Now, we highlight the following basic properties on recession sets:

• 1. $K^\infty$ is a nonempty and closed cone;

• 2. $({ clK})^\infty = K^\infty$;

• 3. If $K$ is a cone, then $K^\infty = { clK}$;

• 4. $(K+x)^\infty =K^\infty$ for all $x\in I\!R^n$;

• 5. Let $K_1$ and $K_2$ be subsets of $I\!R^n$; then $K_1\subset K_2$ implies $K_1^\infty \subset K_2^\infty$;

• 6. Let $I$ be an index set and $K_i$, $i\in I$, be any family of nonempty sets in $I\!R^n$; then

  $$\begin{aligned} \Big (\cap _{i\in I}K_i\Big )^\infty \subset \cap _{i\in I} K_i^\infty . \end{aligned}$$

  (3)

  If, in addition, each set $K_i$ is closed and convex, and $\cap _{i\in I} K_i \not = \emptyset$, then we obtain an equality in the previous inclusion.

In particular, if $K \subset I\!R^n$ is a nonempty polyhedral set and $\{x^k\} \subset K$ is a sequence, such that $\Vert x^k\Vert \rightarrow +\infty$ and $x^k/\Vert x^k\Vert \rightarrow d$ as $k \rightarrow +\infty$, then, for any $t > 0$, there exists $k \in I\!N$ sufficiently large, such that

$$\begin{aligned} x^k - t d \in K, \quad \text{ and } \quad \Vert x^k - t d\Vert < \Vert x^k\Vert \end{aligned}$$

(4)

(see Proposition 2.3 in [4], for more details see [1] and [5]). These results will be used later, when we will consider minimization of quadratic objective functions over polyhedral sets.

On the other hand, the key for devising a duality scheme for the SCM problem, formulated as

$$\begin{aligned} \text{ minimize }\ f(x) \ \ \text{ subject } \text{ to }\ \ x \in X, \end{aligned}$$

(5)

where $f:I\!R^n \rightarrow I\!R\cup \{+ \infty \}$ is proper and lower semi-continuous, and $X$ is a nonempty and closed subset of $I\!R^n$, is the specific application of the Fenchel–Moreau conjugation for lower semi-continuous functions, presented in [12]. Denoting by $C(I\!R^n,I\!R^n)$ the class of continuous operators $p: I\!R^n \rightarrow I\!R^n$, the authors proposed a particular coupling function for the Moreau’s extension [13] of Fenchel’s conjugation, that is,

$$\begin{aligned} \rho : I\!R^n \times C(I\!R^n,I\!R^n) \rightarrow I\!R, \ \ \ \rho (x,p) = \langle p(x),x\rangle , \end{aligned}$$

in order to present a convex conjugate function for $f$. Next, the main results of [12] are summarized as follows.

Consider $C(I\!R^n,I\!R^n)$, the class of continuous operators from $I\!R^n$ to $I\!R^n$. For simplicity, we will denote this class by $P_n$ in the sequel. Let $f : I\!R^n \rightarrow I\!R\cup \{+\infty \}$ be a proper lower semi-continuous function. The Fenchel–Moreau conjugate function of $f$ is given by $f^* : { P_n} \rightarrow I\!R\cup \{+\infty \}$, defined as

$$\begin{aligned} f^*(p) := \sup _{x \in I\!R^n} \{ \langle p(x),x\rangle - f(x)\}, \end{aligned}$$

(6)

which is a proper and convex function.

Note that, in this setting, we shall consider $P_n$ as a real vector space so that, for each $x \in I\!R^n$, the function $l_x:P_n \rightarrow I\!R$, defined as $l_x(p) = \langle p(x),x\rangle$, is linear.

Moreover, observe that, from (6), for all $x \in I\!R^n$ and all $p \in P_n$, we obtain an extension of the Fenchel’s inequality

$$\begin{aligned} \langle p(x),x\rangle \le f(x) + f^*(p). \end{aligned}$$

Consider now the biconjugate function $f^{**}: I\!R^n \rightarrow I\!R\cup \{+\infty \}$, defined by

$$\begin{aligned} f^{**} (x) := \sup _{p \in P_n} \{ \langle p(x),x\rangle - f^*(p)\}. \end{aligned}$$

In this setting, the involution property ($f(x) = f^{**}(x), \forall x \in I\!R^n$) is ensured, whenever $f$ is proper and lower semi-continuous (see Definitions 3.4 and 4.3, and Theorem 4.6 in [12]).

If $f$ and $f^*$ are Fenchel–Moreau conjugate functions, then the function $f$ is proper and lower semi-continuous, and the function $f^*$ is proper and convex (see Lemma 3.5 in [12]).

Let the class of constant operators of $P_n$ be denoted by

$$\begin{aligned} F_n := \{ p \in P_n : p \text{ constant }\}. \end{aligned}$$

(7)

Considering $f : I\!R^n \rightarrow I\!R\cup \{+\infty \}$ a proper and lower semi-continuous function, we say that a real vector space $S$ is a conjugate dual space if $f (x) = f_S^{**}(x)$ for all $x \in I\!R^n$ and $F_n \subset S \subseteq P_n$, where

$$\begin{aligned} f^{**}_S(x) := \sup _{p \in S} \{ \langle p(x),x\rangle - f^*(p)\}. \end{aligned}$$

Furthermore, from Lemma 4.1 in [12], if $F_n \subset S \subset P_n$, then, for all $x \in I\!R^n$

$$\begin{aligned} f^{**}_{F_n}(x) \le f^{**}_S(x) \le f^{**}(x) \le f(x), \end{aligned}$$

(8)

using the simplified notation $f^{**}(x)=f^{**}_{P_n}(x)$. Later, we shall see that the duality scheme will benefit from an alternative conjugate dual space instead of $P_n$.

In case $f$ is also convex, besides being proper and lower semi-continuous, then its Fenchel–Moreau conjugate function $f^* : { F_n} \rightarrow I\!R\cup \{+\infty \}$ is also convex, proper and lower semi-continuous, having $F_n$ (7) as the conjugate dual space. It is also interesting to mention that, in this case, Fenchel’s conjugation could be recovered due to the enlargement of the domain of the Fenchel–Moreau conjugate function.

3 Existence conditions

In this section, we study some existence conditions for solutions of SCM problems, formulated as (5). Furthermore, we investigate the particular case, when $X$ is a nonempty, closed and convex polyhedral set.

Let us denote the solution set of SCM by

$$\begin{aligned} S(f,X) := \{ x \in X : f(x) \le f(y), ~ \forall y \in X\}. \end{aligned}$$

Note that

$$\begin{aligned} S(f,X) = \bigcap _{x\in X} (X\cap L_f(f(x))). \end{aligned}$$

If $\lambda := \inf \{ f(x) : x \in X \}$, then $S(f,X) = X\cap L_f(\lambda )$. In case $\lambda = -\infty$, as we remarked in Sect. 2, we have $L_f(\lambda ) \;= \;\emptyset$, and so $S(f,X) \;=\; X \cap L_f(\lambda ) \;=\; \emptyset$. Moreover, if $\lambda \in Im(f)$, then $S(f,X) = X\cap L_f(f(x))$ $\forall x\in L_f(\lambda )$. On the other hand, in case $\lambda = +\infty$, we have $f(x) = +\infty$ for each $x\in X$, and, as we also remarked in Sect. 2, we get $L_f(f(x)) = I\!R^n$, and so $S(f,X) = X\cap L_f(f(x))=X$, for each $x\in X$.

Regarding asymptotic sets, an immediate consequence of relation (3) is that

$$\begin{aligned} S(f,X)^\infty \subset (X\cap L_f(f(x)))^\infty , \quad \forall x\in X. \end{aligned}$$

(9)

The following result shows a relation between the recession cones of the lower level sets, which can be theoretically built or generated by algorithms.

Lemma 1

Let $\{\lambda _i\}_{i\in I\!N}$ be a sequence such that $\lambda _i \rightarrow \lambda := \inf \{ f(x) : x \in X \}$ as $i \rightarrow +\infty$. If $X\cap L_f(\lambda ) = \emptyset$ and $X\cap L_f(\lambda _i) \ne \emptyset$ $\forall i\in I\!N$, then

$$\begin{aligned} \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty = \bigcap _{i\in I\!N} (X\cap L_f(\lambda _i))^\infty . \end{aligned}$$

Proof

First, let us show that $\displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty \subset \displaystyle \bigcap _{i\in I\!N} (X\cap L_f(\lambda _i))^\infty$. Indeed, since $X\cap L_f(\lambda ) = \emptyset$ and $X\cap L_f(\lambda _i) \ne \emptyset$ $\forall i\in I\!N$, then $\lambda _i > \lambda$ $\forall i\in I\!N$. Here, there exists $x^i\in (X\cap L_f(\lambda _i))$ for each $i$. So, $\displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty \subset \displaystyle \bigcap _{i\in I\!N} (X\cap L_f(f(x^i)))^\infty \subset \displaystyle \bigcap _{i\in I\!N} (X\cap L_f(\lambda _i))^\infty$, because $(X\cap L_f(f(x^i)))^\infty \subset (X\cap L_f(\lambda _i))^\infty$ $\forall i$.

Conversely, to show that $\displaystyle \bigcap _{i\in I\!N} (X\cap L_f(\lambda _i))^\infty \subset \displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$ take an element $u \in \displaystyle \bigcap _{i\in I\!N} (X\cap L_f(\lambda _i))^\infty$. Thus, we get $u \in (X\cap L_f(\lambda _i))^\infty$ $\forall i \in I\!N$. For each $x \in X$ arbitrarily fixed, we have that $\lambda < f(x)$, because $X\;\cap \; L_f(\lambda ) \;=\; \emptyset$. Since $\lim _{i\rightarrow +\infty } \lambda _i = \lambda$ and $X\cap L_f(\lambda _i) \ne \emptyset$ $\forall i\in I\!N$, there exists $m\in I\!N$ such that $\lambda _m \le f(x)$. So, it follows that $X\cap L_f(\lambda _m) \subset X\cap L_f(f(x))$, which implies that $(X\cap L_f(\lambda _m))^\infty \subset (X\cap L_f(f(x)))^\infty$, and so $u \in (X\cap L_f(f(x)))^\infty$. As $x \in X$ was arbitrarily fixed, the statement follows. $\square$

Next, we show that, even though $X$ is just nonempty and closed, the result is theoretically analogous to the one for convex feasible sets.

Theorem 1

Consider the SCM problem, as in (5), where $f:I\!R^n \rightarrow I\!R\cup \{+ \infty \}$ is proper and lower semi-continuous, and $X$ is a nonempty and closed subset of $I\!R^n$. Then,

• 1. if $S(f,X)\ne \emptyset$, then $S(f,X)^\infty = \displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$.

• 2. Otherwise, if $S(f,X) = \emptyset$, then $\displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty \ne \{0\}$.

Proof

If $S(f,X)\ne \emptyset$, then $S(f,X)=X\cap L_f(\lambda )\ne \emptyset$, where $\lambda \;= \;\inf \;\{ f(x): x\in X\}$. It implies that

$$\begin{aligned} \displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty \subset (X\cap L_f(\lambda ))^\infty = S(f,X)^\infty . \end{aligned}$$

So, combining relation (9) with the above inclusion, we get the desired result.

Now, suppose $S(f,X) = \emptyset$, then $X\cap L_f(f(x))$ is unbounded $\forall x \in I\!R^n$. So, take $u^i \in (X\cap L_f(\lambda _i))^\infty$ with $||u^i|| = 1$ $\forall i \in I\!N$, where $\lambda _i \rightarrow \lambda$ with $\lambda _i \ge \lambda _{i+1} > \lambda$ and $\lambda := \inf \{f(y): y \in X\}$. Since $\lambda _k \le \lambda _i$ $\forall i \in I\!N$ and $\forall k \ge i$, it follows that $(X\cap L_f(\lambda _k))^\infty \subset (X\cap L_f(\lambda _i))^\infty$ and $\{u^k\}_{k\ge i} \subset (X\cap L_f(\lambda _i))^\infty$ $\forall i \in I\!N$. So, any cluster point of $\{u^k\}_{k\in I\!N}$ belongs to $(X\cap L_f(\lambda _i))^\infty$ $\forall i\in I\!N$, or, equivalently, from Lemma 1, any cluster point of $\{u^k\}_{k\in I\!N}$ belongs to $\displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$, showing that

$$\begin{aligned} \{0\} \ne \displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty . \end{aligned}$$

$\square$

We should remark that, regarding property 6 on recession sets in (3), Theorem 1 generalizes the result of convex analysis, when the sets $K_i$ are sublevel sets of a lower semi-continuous function. Also, note that the nonemptiness condition for the intersection of the sets $K_i$ is necessary for the result of classical convex analysis, whereas, in this setting, this condition is necessary and sufficient.

The following result applies to the particular case, when the solution set is also compact.

Theorem 2

Consider the SCM problem, as in (5), where $f:I\!R^n \rightarrow I\!R\cup \{+ \infty \}$ is proper and lower semi-continuous, and $X$ is a nonempty and compact subset of $I\!R^n$. Then, the following statements are equivalent:

• (a) $\displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty = \{0\}$.

• (b) There exists $x \in X$ such that $X\cap L_f(f(x))$ is bounded.

• (c) There exists $x \in X$ such that $cl (conv (X\cap L_f(f(x))))$ is bounded.

Proof

We just need to prove that (a) implies (b), because the other implications follow from the results of classical convex analysis. Consider that (a) holds. From relation (9), we have $\{0\} \subset S(f,X)^\infty \subset \displaystyle \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty = \{0\}$ and, from Theorem 1, we know that $S(f,X) \ne \emptyset$. Thus, the statement follows from the fact that $S(f,X) = X\cap L_f(\lambda )$, where $\lambda = \inf \{f(x): x\in X\}$. $\square$

Given a function $h : I\!R^n \rightarrow I\!R\cup \{+\infty \}$ and the indicator function of a set $X\subset I\!R^n$, defined as

$$\begin{aligned} i_X(x) := \left\{ \begin{array}{ll} 0, &{} \quad \text{ if } x\in X \\ +\infty , &{} \quad \text{ otherwise }, \end{array} \right. \end{aligned}$$

(10)

consider the following assumptions:

• 1. for all $\{x^k\}_{k\in I\!N}\subset X \cap dom(h)$ with $\lim _{k\rightarrow +\infty } ||x^k|| = +\infty$ and $\lim _{k\rightarrow +\infty } x^k/||x^k|| = u \in \bigcap _{x \in X} (X\cap L_h(h(x)))^\infty ,$ $\exists k_0\in I\!N$ large enough, such that $X\cap L_h(h(x^{k_0}))\cap B(0,||x^{k_0}||) \ne \emptyset$. This assumption will be referred as $A1(h,X)$ in the sequel.

• 2. For all $\{x^k\}_{k\in I\!N}\subset I\!R^n$ with $\lim _{k\rightarrow +\infty } ||x^k|| = +\infty$, $\exists {k_0} \in I\!N$ large enough, such that $L_{h+i_X}(h(x^{k_0})+i_X(x^{k_0}))\cap B(0,||x^{k_0}||) \ne \emptyset$; where, for a fixed ${k_0}$, $B(0,||x^{k_0}||)$ denotes the $n$-dimensional open ball centered at zero with radius $||x^{k_0}||$. This assumption will be referred as $A2(h+i_X)$ in the sequel.

Observe that conditions related to $A1(h,X)$ have been already exploited by many authors and can be found, for instance, in [3–6, 19, 20]. Now, we are able to show a technical procedure in order to check nonemptiness of the solution set of SCM.

Theorem 3

Consider the SCM problem, as in (5), where $f:I\!R^n \rightarrow I\!R\cup \{+ \infty \}$ is proper and lower semi-continuous, and $X$ is a nonempty and closed subset of $I\!R^n$. Then, the following conditions are equivalent:

• (a) A1(f, X) is satisfied.

• (b) $S(f,X) \ne \emptyset$.

Proof

In order to prove that (a) implies (b), as $f$ is a proper function by assumption, consider, without any loss of generality, for all $m \in I\!N$, the following proper function $f_m : I\!R^n \rightarrow I\!R\cup \{+\infty \}$, defined by

$$\begin{aligned} f_m(x) := \left\{ \begin{array}{ll} f(x), &{}\quad \Vert x\Vert \le m,\\ +\infty , &{}\quad \text{ otherwise }. \end{array} \right. \end{aligned}$$

So, by construction of $f_m$, we have that $S(f_m,X)$ is nonempty and also compact. Take $x^m \in \text{ argmin }\{ \Vert x\Vert : x \in S(f_m,X) \}\subset X\cap dom(f)$. Supposing that the sequence $\{x^m\}$ is unbounded, without any loss of generality, we can assume that $\Vert x^m\Vert \rightarrow \infty$ as $m \rightarrow \infty$ and $x^m/\Vert x^m\Vert \rightarrow u$ as $m \rightarrow \infty$. We claim that $u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$. Indeed, take $x \in X$ arbitrary fixed; then, for all $m \ge \Vert x\Vert$, we have that $x^m \in L_f(f(x))$. Now, taking $t_m = 1/\Vert x^m\Vert$, we have that $t_mx^m \rightarrow u$ as $m \rightarrow \infty$, and so $u \in (L_f(f(x)))^\infty$. Since $x$ was arbitrarily fixed, then $u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$. As condition $A1(f,X)$ holds, $\exists \; m_0\in I\!N$ large enough such that $X \; \cap \;L_f(f(x^{m_0}))\cap B(0,||x^{m_0}||) \ne \emptyset$. Now, taking $x \in X\cap L_f(f(x^{m_0}))\cap B(0,||x^{m_0}||)$, then $x\in X$, $f(x) \le f(x^{m_0})$ and $\Vert x\Vert < \Vert x^{m_0}\Vert$, and so $x \in S(f_{m_0},X)$, which is a contradiction, showing that the sequence $\{x^m\}$ is bounded. Thus, any cluster point of $\{x^m\}$ is a minimizer of $f$, and the statement follows.

For proving that (b) implies (a), take a sequence $\{x^k\}_{k\in I\!N} \subset X\cap dom(f)$ such that $\lim _{k\rightarrow +\infty } ||x^k|| = +\infty$ and $\lim _{k\rightarrow +\infty } x^k/||x^k|| = u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$. The statement follows from taking $\bar{x} \in S(f,X)$ and $k_0\in I\!N$ such that $\Vert x^{k_0}\Vert > \Vert \bar{x}\Vert$. $\square$

Theorem 4

Consider the SCM problem, as in (5), where $f:I\!R^n \rightarrow I\!R\cup \{+ \infty \}$ is proper and lower semi-continuous, and $X$ is a nonempty and closed subset of $I\!R^n$. Then, $A1(f,X)$ is equivalent to $A2(f+i_X)$.

Proof

We only need to prove that $A1(f,X)$ implies $A2(f+i_X)$, since the converse follows from the fact that $dom(f+i_X)=X\cap dom(f)$. Take $\{x^k\}_{k\in I\!N}\subset I\!R^n$ with $\lim _{k\rightarrow +\infty } ||x^k|| = +\infty$. As condition $A1(f,X)$ holds, then, from Theorem 3, we have that $S(f,X)\ne \emptyset$. The statement follows from taking $\bar{x} \in S(f,X)$ and $k_0 \in I\!N$ such that $\Vert x^{k_0}\Vert > \Vert \bar{x}\Vert$. $\square$

Since conditions $A1(h,X)$ and $A2(h+i_X)$ are equivalent, when $h$ is proper and lower semi-continuous, and $X$ is nonempty and closed, then from now on, we refer to both of them as just $A(h,X)$.

3.1 The quadratic case

We finish this section studying the existence of solutions of the minimization of a quadratic function over a nonempty, closed and convex polyhedral set.

Given $A \in I\!R^{m\times n}$, $b \in I\!R^m$, $c \in I\!R$, $g\in I\!R^n$, and $H \in I\!R^{n\times n}$ symmetric, define the set $X:= \{ x \in I\!R^n : A x \le b\}$ and consider the following problem:

$$\begin{aligned} \text{ minimize }\ \ f(x) \ \ \text{ subject } \text{ to }\ \ x \in X, \end{aligned}$$

(11)

where $f : I\!R^n \rightarrow I\!R$ is a continuous function, given by:

$$\begin{aligned} f(x) = 1/2\langle x, H x \rangle + \langle g, x\rangle + c. \end{aligned}$$

(12)

It is worth mentioning that no other assumption on the Hessian $H$ of $f$ is made.

Lemma 2

Let $f$ be a quadratic function, as in (12). If $\inf \{ f(x): x \in X\} =\beta > -\infty$, then, for each $x \in X$ and each $u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$ both fixed, the mapping $l : [0,+\infty [ \rightarrow I\!R$, defined by $l(t) = f(x + t u)- f(x)$ is linear, and $l(t) \ge 0$, for all $t \in [0,+\infty [$.

Proof

Suppose $\inf \{ f(x): x \in X\} =\beta > -\infty$. Take $u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$ arbitrary fixed, and so $u \in (X \cap L_f(f(x)))^\infty$ $\forall x \in I\!R^n$. Now, take $x \in X$ arbitrarily fixed. Thus, $\exists \{y^k\}_{k\in I\!N} \subset L_f(f(x))$, $\exists \{t_k\}_{k\in I\!N}\downarrow 0$ such that $t_k y^k \rightarrow u$ as $k \rightarrow +\infty$. So, $u \in X^\infty$ and $-\infty < \beta \le f(y^k) = 1/2 \langle y^k, H y^k \rangle + \langle g, y^k\rangle + c \le f(x) < +\infty$ $\forall k \in I\!N$, implying that $\langle u, H u\rangle = 0$. Since $x + t u \in X$, for all $t > 0$, we have, for all $t>0$, that

$$\begin{aligned} l(t) = f(x+tu) - f(x) = t \langle Hx+ g, u \rangle = t \langle \nabla f(x), u\rangle , \end{aligned}$$

where $l$ is a linear mapping over $[0,+\infty [$. Finally, since $\inf \{ f(x): x \in X\} =\beta > -\infty$, it follows that $l(t) \ge 0$, $\forall t \ge 0$. $\square$

From the proof of Lemma 2 and since $l(t)/t=\langle \nabla f(x), u\rangle \ge 0 \ \forall t > 0$, we observe the following result.

Corollary 1

For each $x\in X$, it follows that

$$\begin{aligned} (S(f,X))^\infty \subset \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty \subset \nabla f(X)^{+}\cap \{d: \langle Hd, d \rangle \ge 0\}, \end{aligned}$$

where $\nabla f(X)^{+}= \{ d \in I\!R^n : \langle \nabla f(x), d \rangle \ge 0, \forall x \in X\}$.

Theorem 5

Consider the minimization of a quadratic function over a nonempty, closed and convex polyhedral set, as formulated in (11–12). The following conditions are equivalent.

• (i) $\inf \{ f(x): x \in X \}=\beta > -\infty$.

• (ii) $A(f,X)$ is satisfied.

Proof

Let us prove first that (i) implies (ii). If $X$ is bounded, then condition $A(f,X)$ holds. If not, take the sequence $\{x^m\}_{m\in I\!N} \subset X$ such that the conditions $\Vert x^m\Vert \rightarrow +\infty$ and $x^m/\Vert x^m\Vert \rightarrow u \in \bigcap _{x \in X} (X\cap L_f(f(x)))^\infty$ as $m \rightarrow +\infty$ hold. So, from Lemma 2, for each $x \in X$, we have that $f(x) \le f(x + t u)$ $\forall t \ge 0$. From Proposition 2.3 in [4], rewritten in (4), we have that, for any $t > 0$, there exists $k \in I\!N$ large enough such that $x^k - tu \in X$. Now, taking $y = x^k - tu$, we have that $f(y) \le f(y + tu) = f(x^k)$. Note that, for $k$ large enough, $\Vert y\Vert = \Vert x^k - tu\Vert < \Vert x^k\Vert$, and so $A(f,X)$ holds.

The proof that (ii) implies (i) follows directly from the fact that $f$ is a proper and lower semi-continuous function and that $A(f,X)$ holds, and also from Theorem 3. $\square$

We note that both Theorem 3 and Theorem 5 retrieve, in a simple way, the results of Frank and Wolfe’s Theorem (1956) (Chapter 2 in [7]) for existence of solutions for minimization of quadratic functions constrained to nonempty and convex polyhedral sets.

We point out that there exist in the literature other results related to Frank and Wolfe’s Theorem, such as, for instance [21], where assumptions $(b)$ and $(c)$ of Theorem 4.1 therein would be interpreted as a specialization of our assumption $A(f,X)$ for the quadratic case.

4 The duality scheme

In this section, we apply the general duality scheme, that can be found in [10, 15, 18], in the setting of SCM problems with a particular choice for the coupling function. Without any loss of generality, we can redefine $f$ considering, in addition, $f(x)=+\infty$ when $x \notin X$, and, equivalently, rewrite the SCM problem (5) as

$$\begin{aligned} \text{ minimize }\ \ f(x) \ \ \text{ subject } \text{ to }\ \ x \in I\!R^n. \end{aligned}$$

(13)

For this, we need first the following definition.

Definition 1

We say that $\phi :I\!R^n\times I\!R^m\rightarrow I\!R\cup \{+\infty \}$ is a perturbation function of $f$, if, and only if, $\phi$ is proper and lower semi-continuous, and $\phi (x,0) = f(x)$ for each $x\in I\!R^n$.

Consider now the Fenchel–Moreau conjugation of a perturbation function $\phi$ of $f$ restricted to the subspace $S=P_n \times P_m$, instead of the natural choice $P_{n+m}$. Clearly,

$$\begin{aligned} F_{n+m}=F_n\times F_m \subset S \subset P_{n+m}, \end{aligned}$$

with $S\ne P_{n+m}$. The following result is the key to define the dual problem associated with SCM.

Proposition 1

Given f and $\phi$, a perturbation function of f, we have

$$\begin{aligned} -\phi ^*(0,p) \le f(x), \end{aligned}$$

for all $x \in I\!R^n$ and $p\in {P}_m$.

Proof

According to [12], the Fenchel–Moreau conjugate function of the perturbation function of $f$, $\phi :I\!R^n \times I\!R^m \rightarrow I\!R\cup \{+ \infty \}$ restricted to $S=P_n \times P_m$ is the function $\phi ^*: S \rightarrow I\!R\cup \{+ \infty \}$, defined by

$$\begin{aligned} \begin{array}{rcl} \phi ^*(q,p) &{} := &{} \displaystyle \sup _{(x,y)}\{ \hat{\rho }((x,y),(q,p)) - \phi (x,y)\} \\ &{} := &{} \displaystyle \sup _{(x,y)}\{\langle q(x),x\rangle + \langle p(y),y\rangle - \phi (x,y)\}, \end{array} \end{aligned}$$

where the coupling function is given as

$$\begin{aligned} \hat{\rho }: (I\!R^n\times I\!R^m) \times (P_n\times P_m) \rightarrow I\!R, \ \ \ \ \hat{\rho }((x,y),(q,p)) := \langle q(x),x\rangle + \langle p(y),y\rangle . \end{aligned}$$

So, it follows that

$$\begin{aligned} \phi ^*(q,p) \ge \langle q(x),x\rangle + \langle p(y),y\rangle - \phi (x,y). \end{aligned}$$

As $\phi (x,0) = f(x)$, for each $x \in I\!R^n$, the statement follows taking $q = 0$ and $y = 0$. $\square$

Definition 2

The dual problem associated with SCM is formulated as follows

$$\begin{aligned} (\textit{DSCM}) \ \ \ \text{ maximize }\ \ \ -\phi ^*(0,p) \ \ \ \text{ subject } \text{ to }\ \ \ p \in P_m. \end{aligned}$$

(14)

For convenience, the dual problem will be formulated hereafter as a minimization problem.

Lemma 3

The dual of SCM (14), formulated as a minimization problem, is a convex optimization problem.

Proof

Applying the Fenchel–Moreau conjugation for $\phi (x,y)$, for all $p\in P_m$, we have

$$\begin{aligned} \phi ^*(0,p) = \sup _{(x,y)\in I\!R^n\times I\!R^m} \{ \langle p(y),y\rangle - \phi (x,y)\}, \end{aligned}$$

and we observe that, for each $(x,y) \in I\!R^n \times I\!R^m$, the mapping $a_{(x,y)} : P_m \rightarrow I\!R$, defined by $a_{(x,y)}(p) = \langle p(y),y\rangle - \phi (x,y)$ is affine linear. Since $P_m$ is convex, the statement follows completely from the fact that the supremum of an affine linear function is convex. $\square$

Now, for a given perturbation function $\phi$ of $f$, consider an auxiliary function, called the marginal function $h:I\!R^{m} \rightarrow I\!R\cup \left\{ -\infty , +\infty \right\}$, defined as

$$\begin{aligned} h(y):=\inf _{x\in I\!R^{n}}\phi (x,y). \end{aligned}$$

(15)

Observe that, by definition of $h$, $h(0)$ is the optimal value of the SCM problem in (13), since $\phi (x,0)=f(x) \ \forall x \in I\!R^n$.

Theorem 6

Given the SCM problem (13) and a perturbation function $\phi$ of $f$, if the dual conjugation space associated with $\phi$ is $S=P_n \times P_m$, then the dual of DSCM (14) is SCM.

Proof

Given the perturbation function $\phi$ of $f$, define the marginal function $h$ as in (15). Thus, the Fenchel–Moreau conjugate of the marginal function $h$ is given by $h^*:P_m \rightarrow I\!R\cup \{-\infty ,+\infty \}$, where

$$\begin{aligned} h^*(p)= & {} \sup _{y \in I\!R^m} \{ \langle p(y), y \rangle - h(y) \}\\= & {} \sup _{y \in I\!R^m} \{ \langle p(y), y \rangle - \inf _{x \in I\!R^n}\phi (x,y) \}\\= & {} \sup _{(x,y) \in I\!R^n\times I\!R^m } \{ \langle p(y), y \rangle - \phi (x,y) \}\\= & {} \sup _{(x,y) \in I\!R^n\times I\!R^m } \{ \langle \hat{\rho }((x,y),(0,p)) \rangle - \phi (x,y) \}\\= & {} \phi ^*(0,p). \end{aligned}$$

Consider $g: P_n \rightarrow I\!R\cup \{-\infty ,+\infty \}$ a marginal function of $\phi ^*$. Let us make explicit the main points of the duality scheme between SCM and DSCM as follows:

$$\begin{aligned} \begin{array}{ccc} \begin{array}{c} \textit{SCM} \\ \begin{array}{l} f(x) = \phi (x,0), \quad \forall x \in I\!R^n \\ h(y) = \inf \;\{ \phi (x,y) \;|\; x \in I\!R^n \} \\ \alpha := \ h(0) \end{array} \end{array} &{} &{} \begin{array}{c} \textit{DSCM} \\ \begin{array}{l} h^*(p) = \phi ^*(0,p), \quad \forall (0,p) \in S \\ g(q) := \inf \;\{ \phi ^*(q,p) \;|\; p \in P_m \}\\ \beta := \ g(0). \end{array} \end{array} \end{array} \end{aligned}$$

As $\phi ^*_S$ is the perturbation function of $h^*$, we claim that $\phi ^{**}_S$ will be a perturbation function of the objective function of the dual of DSCM. Likewise the previous outlined scheme, the main points of the duality scheme between DSCM and its associated dual problem are as follows:

$$\begin{aligned} \begin{array}{ccc} \begin{array}{c} \textit{DSCM} \\ \begin{array}{l} h^*(p) = \phi ^*(0,p), \quad \forall (0,p) \in S \\ g(q) = \inf \;\{ \phi ^*(q,p) \;|\; p \in P_m \}\\ \beta = \ g(0) \end{array} \end{array} &{} \ \ \ \ &{} \begin{array}{c} \textit{DDSCM} \\ \begin{array}{l} k(x) := \phi ^{**}(x,0), \quad \forall x \in I\!R^n \\ j(y) := \inf \;\{ \phi ^{**}(x,y) \;|\; x \in I\!R^n \} \\ \delta := \ j(0). \end{array} \end{array} \end{array} \end{aligned}$$

Since $\phi$ is proper and lower semi-continuous, we have $\phi ^{**}_S = \phi$, according to the involution property of the Fenchel–Moreau conjugation. Hence, it follows directly that $k=f$, $j=h$ and $\delta = \alpha$, completing the proof. $\square$

Consider the Lagrangian function $L: I\!R^n\times P_m \rightarrow I\!R\cup \{-\infty , +\infty \}$, defined by

$$\begin{aligned} L(x,p):=\inf _{y\in I\!R^m} \{\phi (x,y) - \langle p(y),y\rangle \}, \end{aligned}$$

where $\phi$ is a perturbation function of $f$, i.e., $\phi$ is a proper and lower semi-continuous function with $\phi (x,0)=f(x)$. We should mention that some results on the Lagrangian function can be recovered directly in this particular setting. For instance, one can show easily that $(\bar{x},\bar{p})$ is a saddle point of $L$ if, and only if, $\bar{x}$ is a solution of SCM and $\bar{p}$ is a solution of DSCM.

Furthermore, we should remark that the involution property is not satisfied for all problems in the SCM class. In next section, we identify a family of SCM problems in which this property holds. We also observe that, for the convex optimization case, the above scheme is already presented in [9].

4.1 The quadratic case

After applying the duality scheme for SCM problems, we realize that we still face some difficulty. Although the dual problem is convex, the dimension of the conjugate dual space is infinite. The good news is that we can overcome this difficulty, in particular, when addressing a family of quadratic optimization problems, by constructing a convex dual optimization problem in finite dimensional space, provided by the results on conjugate dual spaces with the specific application of the Fenchel–Moreau conjugation for lower semi-continuous functions, as in [12].

In the sequel, we present theoretical results that support the construction of a convex dual problem in finite dimensional space associated with the minimization of a quadratic function constrained to a nonempty, closed and convex set. For this, let us define first the following real vectorial spaces:

$$\begin{aligned} H_n := \{ H \in I\!R^{n\times n} : H \text{ is } \text{ symmetric } \}, \end{aligned}$$

(16)

with dimension $n(n+1)/2$, and

$$\begin{aligned} S_n := \{ p \in P_n : p(x) = H x + g, \ H\in H_n, \;g\in F_n\}, \end{aligned}$$

(17)

with dimension $n(n+3)/2$.

Proposition 2

Consider a quadratic function $f : I\!R^n \rightarrow I\!R$; then $S_n$, as defined in (17), is an associated conjugate dual space with finite dimension.

Proof

As $S_n \subset P_n$, from the definition of conjugate dual spaces, we just need to show that, for all $x \in I\!R^n$, $f(x)=f^{**}_{S_n}(x)$. Since $f$ is a quadratic function, there exist $H \in H_n$, as defined in (16), $g \in F_n$ as in (7), and $c \in I\!R$, such that

$$\begin{aligned} f(x)= \left\langle x,Hx \right\rangle +\left\langle g,x\right\rangle +c. \end{aligned}$$

Now, take $p_0\in S_n$, defined by $p_0(x)=H x + g$. Then, it follows that

$$\begin{aligned} f^{*}(p_0)= & {} \sup _{x\in I\!R^n}\lbrace \langle p_0(x),x\rangle -f(x)\rbrace \\= & {} \sup _{x\in I\!R^n}\lbrace \langle x,H x\rangle +\langle g,x \rangle - \langle x,Hx \rangle - \langle g,x\rangle -c \rbrace = -c. \end{aligned}$$

Thus, we have, for all $x\in I\!R^n$, that

$$\begin{aligned} f_{S_n}^{**}(x) = \sup _{p\in S_n }\left\{ \left\langle x,p(x) \right\rangle -f^{*}(p)\right\} \ge \left\langle x,p_0(x) \right\rangle -f^{*}(p_0) = f(x). \end{aligned}$$

However, from Lemma 4.1 [12] (which is rewritten in (8)), $f^{**}_{S_n} \le f^{**} \le f$. Hence, for all $x\in I\!R^n$, we get $f^{**}_{S_n}(x) = f(x)$, completing the proof. $\square$

From now on, given a nonempty and closed set $X\subset I\!R^n$, we denote by $T_X \subset P_n$ the conjugate dual space of the functional $i_X$ (10). One can show easily that, if $X$ is also convex, then $T_X$ coincides with $F_n$, the class of all constant operators from $I\!R^n$ to $I\!R^n$.

Now, let us consider a quadratic function constrained to a nonempty and closed set $X \subset I\!R^n$.

Proposition 3

If $f : I\!R^n\rightarrow I\!R$ is a quadratic function and $i_X : I\!R^n\rightarrow I\!R\cup \{+\infty \}$ is the indicator function of the nonempty and closed set $X\subset I\!R^n$, then $S_n+T_X$ is a conjugate dual space of the functional $f+i_X$.

Proof

For each $r\in T_X$, consider $p_r\in S_n+T_X$, defined by $p_r(x) = H x + g + r(x)$ $\forall x\in I\!R^n$; so

$$\begin{aligned} (f+i_X)^*(p_r)= & {} \sup _{x\in I\!R^n}\{\langle p_r(x),x\rangle -f(x)-i_X(x)\}\\= & {} \sup _{x\in I\!R^n}\{\langle r(x),x\rangle -c-i_X(x)\}\\= & {} \sup _{x\in I\!R^n}\{\langle r(x),x\rangle -i_X(x)\}-c\\= & {} (i_X)^*(r)-c. \end{aligned}$$

Thus, it follows that

$$\begin{aligned} (f+i_X)^{**}_{S_n+T_X}(x)= & {} \sup _{p\in S_n+T_X}\{\langle p(x),x\rangle -(f+i_X)^*(p)\}\\\ge & {} \sup _{r\in T_X}\{ \langle p_r(x),x\rangle -(f+i_X)^*(p_r)\}\\= & {} \sup _{r\in T_X}\{ \langle x,H x\rangle +\langle g,x\rangle +\langle r(x),x\rangle -(i_X)^*(r)+c\}\\= & {} f(x)+\sup _{r\in T_X}\{ \langle r(x),x\rangle -(i_X)^*(r)\}\\= & {} f(x)+(i_X)^{**}(x)\\= & {} f(x)+i_X(x), \end{aligned}$$

where the last equality follows from the involution property of the Fenchel–Moreau conjugation for proper and lower semi-continuous functions. The statement follows considering, in addition, the fact that $(f+i_X)^{**}_{S_n+T_X}(x) \le f(x)+i_X(x) \ \forall x$, from (8). $\square$

Theorem 7

If $f : I\!R^n\rightarrow I\!R$ is a quadratic function and $i_X : I\!R^n\rightarrow I\!R\cup \{+\infty \}$ is the indicator function of the nonempty, closed and convex set $X\subset I\!R^n$, then $S_n$ is a conjugate dual space of the functional $f+i_X$.

Proof

It follows directly from Proposition 3 and the fact that $F_n$ is the conjugate dual space associated with the functional $i_X$, whenever $X$ is a nonempty, closed and convex set. $\square$

We now focus our attention on the class of minimization problems with quadratic objective functions over nonempty, closed and convex polyhedral sets, with the purpose to build the convex dual problem by choosing as feasible set an alternative finite dimensional conjugate dual space. Without any loss of generality, a problem in this class can be formulated as

$$\begin{aligned} (Q) \ \ \ \text{ minimize }\ \ \ \langle x,H x\rangle + \langle g,x\rangle + c \ \ \ \text{ subject } \text{ to }\ \ \ Bx=d, \ \ x \ge 0, \end{aligned}$$

(18)

where $H\in H_n$, $g\in F_n$, $c\in I\!R$, $B\in I\!R^{m\times n}$ and $d\in I\!R^m$ are given data, and the feasible set $X := \{x\in I\!R^n : B x = d, \ x\ge 0\}$ is a nonempty, closed and convex polyhedral set. So, define $f : I\!R^n \rightarrow I\!R\cup \{+\infty \}$ by $f(x) := \langle x,Hx\rangle + \langle g,x\rangle + c + i_X(x)$.

The function $\phi : I\!R^n\times I\!R^m\rightarrow I\!R\cup \{+\infty \}$, needed for the duality scheme, is defined by

$$\begin{aligned} \phi (z) := \langle z,\bar{H} z\rangle +\langle \bar{g},z\rangle +c +i_{\bar{X}}(z), \end{aligned}$$

(19)

where $z := (x,y) \;\in \;I\!R^{n+m}$, the matrix $\bar{H} := \left[ \begin{array}{cc} H &{} 0 \\ 0 &{} 0 \end{array}\right] \;\in \;I\!R^{(n+m)\times (n+m)}$ is symmetric, $\bar{g} := (g,0)\;\in \;I\!R^{n+m}$, and $\bar{X} := \{ z = (x,y) \in I\!R^{n+m} : \bar{B} z = d \text{ and } z\ge 0\}$, where the matrix $\bar{B}$ is defined as $\bar{B} := \left[ \begin{array}{cc} B&-I \end{array}\right] \in I\!R^{m\times (n+m)}$ and $I \in I\!R^{m\times m}$ is the identity matrix, and $i_{\bar{X}}$ is the indicator function of $\bar{X}$.

Of course, this function $\phi$ is proper and lower semi-continuous, and satisfies $\phi (x,0) = f(x)\ \forall x \in X$, meaning that $\phi$ is a perturbation function of $f$.

We point out that, if $H \in H_n$ and $g\in I\!R^n\times I\!R^m$, then $p: I\!R^n\times I\!R^m \rightarrow I\!R^n\times I\!R^m$ defined by $p(z)=\bar{H} z +g$ is an operator in $S_n\times S_m$, since $p=(p_1, p_2)$, with $p_1 \in S_n$, $p_1(x)=Hx+g_1 \in I\!R^n$, $p_2 \in S_m$, $p_2(y)=g_2 \in I\!R^m$, $g=(g_1,g_2)$ and $z=(x,y)$.

Lemma 4

$S_n\times S_m$ is a dual conjugate space of $\phi$ as defined in (19).

Proof

For each $r \in I\!R^n\times I\!R^m$, consider $p_r \in S_n\times S_m$ defined by $p_r(z)=\bar{H} z + \bar{g} +r$. So, we have that

$$\begin{aligned} \phi ^{*}(p_r)= & {} \sup _{z\in I\!R^n\times I\!R^m}\lbrace \langle p_r(z),z\rangle -\phi (z)\rbrace \\= & {} \sup _{z\in I\!R^n\times I\!R^m}\lbrace \langle z,\bar{H} z +\bar{g} +r \rangle - \langle z,\bar{H}z \rangle - \langle \bar{g},z\rangle -c -i_{\bar{X}}(z)\rbrace \\= & {} \sup _{z\in I\!R^n\times I\!R^m}\lbrace \langle r,z \rangle -i_{\bar{X}}(z)\rbrace -c \\= & {} (i_{\bar{X}})^*(r) -c. \end{aligned}$$

Thus, it follows that

$$\begin{aligned} \phi _{S_n\times S_m}^{**}(z)= & {} \sup _{p\in S_n\times S_m}\{\langle p(z),z\rangle -\phi ^*(z)\}\\\ge & {} \sup _{r\in I\!R^n\times I\!R^m}\{ \langle p_r(z),z\rangle -\phi ^*(p_r)\}\\= & {} \sup _{r\in I\!R^n\times I\!R^m}\{ \langle z,\bar{H} z\rangle +\langle \bar{g} + r,z\rangle +c-(i_X)^*(r)\}\\= & {} \langle z,\bar{H} z\rangle +\langle \bar{g},z\rangle +c+\sup _{r\in I\!R^n\times I\!R^m}\{ \langle r,z\rangle -(i_{\bar{X}})^*(r)\}\\= & {} \langle z,\bar{H} z\rangle +\langle \bar{g},z\rangle +c+(i_{\bar{X}})^{**}(z)=\phi (z). \end{aligned}$$

The statement follows from the fact that $\phi ^{**}_{S_n\times S_m}(z) \le \phi (z)$ for all $z\in I\!R^n\times I\!R^m$. $\square$

All the above results are summarized as follows.

Theorem 8

Under our general assumptions of problem (18), i.e., assuming that $X$ is a nonempty, closed and convex polyhedral set, the convex dual problem generated from the perturbation function $\phi$, as defined in (19), is the following:

$$\begin{aligned} (DQ) \ \ \ \text{ minimize }\ \ \ \phi ^*(0,p) \ \ \ \text{ subject } \text{ to }\ \ \ p\in S_m. \end{aligned}$$

Proof

It suffices to combine Lemma 4 and Theorem 6. $\square$

5 Conclusions

This paper studies the general problem consisting of minimizing a lower semi-continuous function over a closed set, and considers the particular case when the objective function is quadratic and the constraint set is a convex polyhedron. Existence conditions in terms of asymptotic sets are presented. Moreover, a duality scheme is proposed, in which the dual problem is convex. Applying the proposed duality scheme with an alternative conjugate dual space to the minimization of a quadratic function over a convex polyhedral, whose Hessian can be symmetric indefinite, we get an associated convex dual problem with a finite dimensional feasible set. We believe that the development of solution methods for nonlinear optimization can benefit from the results of this work.