Multiparametric analysis of conic linear optimization based on lift-and-project procedure ^††thanks: Supported by the National Natural Science Foundation of China (11871118,12271061).

The original motivation for this study is the inductive proof of the strong duality theorem of CLOs (see Theorem LABEL:dualityt1 and its proof at the end of Subsection LABEL:otjg1). Indeed, such a proof requires that a pair of primal-dual optimal solutions remains the same in the lift-and-project procedure, in which the complement slackness property always holds. More precisely, a pair of optimal solutions $(x^{*}(u),y^{*}(v))$ of (P-lift) and (D-lift) satisfies the following equation

(see Theorem LABEL:interior2yy). A surprising aspect of this result is that it holds for some vector pairs $(u,v)\in\mathbb{R}^{r}\times\mathbb{R}^{r}$, under Slater’s type condition.

We exploit the special structure of the CLO problem to obtain a new algebraic representation of the Lagrangian dual problem (see Subsection 2.2). Such a dual, called a nonstandard dual, results in a unified representation of the feasible sets. Surprisingly, for (P-lift) and (D-lift), the nonstandard dual of one is a projection of the other; and their projections also satisfy the complement slackness property

under the same Slater’s type condition, where $(\bar{x}^{*}(v),\bar{y}^{*}(u))$ denotes a pair of optimal solutions of the projections (see Theorem LABEL:interior2yy).

These characterization results directly motivate us to explore in detail the relationship between the following two conic (linear inequality) representable sets,

(see Subsection LABEL:jzyss). This relationship helps us present a geometric framework that unifies and extends some properties of parametric LPs and SDPs to the case of mpCLOs.

Prior to parametric analysis in recent years, the actual invariancy region played an important role in the development of parametric LPs and SDPs. Adler and Monteiro [AD92] investigated the parametric analysis of LPs using the optimal partition approach, in which they identified the range of a single-parameter where the optimal partition remained invariant. Other parametric analysis treatments for LPs based on the optimal partition approach were reported in previous studies [Ber97, Deh07, GG08, Gre94, Ha10, RT05, JR03]. The actual invariancy region has been studied extensively in the SDP setting (Refs. [GS99, MT20]), the second-order conic optimization (Refs. [MT21]), and more generally in CLO (Refs. [Yil04]).

Gass and Saaty [GS55] proposed the first method for solving parametric LPs, and Gal and Nedoma [GN72] generalized this method. Recently, there has been growing interest in multiparametric optimizations arising from process engineering, such as process design, optimization, and control. The survey by Pistikopoulos et al.[Pis12] contributes to recent theoretical and algorithmic advances, and applications in the areas of multi-parametric programming, specifically explicit/multi-parametric model predictive control. Thus far, various types of invariances in parametric/multiparametric problems have been used, mainly in single-parametric or bi-parametric analyses. To the best of our knowledge, almost all approaches to multiparametric LPs reported in the literature (Refs [Bor03, Fil97, Fil04, Gal95, GG97, Sch87, WW90]) use bases to obtain a description of the invariancy regions.

This study investigates multiparametric optimization in general CLO problems in which either the objective function or the right-hand side is perturbed along many fixed directions. First, we establish the connection by showing that the conic representable set defined by (3a) or (3b) is viewed as a projection of the feasible set of an appropriately defined mpCLO problem, although this connection is not easily identifiable. We then develop classical duality theory using set-valued mappings to relate the two conic representable sets. This treatment makes it possible to combine some known, yet scattered, results and derive new ones. All these results can be used to develop the optimal partition approach given in [AD92] for parametric LPs and [GG08] for parametric SDPs.

The main contributions of this study are as follows:

(1) Characterization of the relationship between the primal and dual conic representable sets.

(2) Presentation of a novel duality in CLO.

(3) Identification of optimal partitions and development of parametric analysis technique.

In the first category, we define set-valued mappings between the primal and dual conic representable sets, which provide an important and useful tool. This tool plays a critical role in the analysis.

In the second category, we develop the classical duality theory of CLO. In addition to the complementary slackness properties mentioned earlier, we present the weak and strong duality properties for the pair of almost primal-dual problems (P-lift) and (D-lift). We show that the sum of their objective optimal values is a bilinear function with respect to the vectors of parameters $u$ and $v$ (see Corollary LABEL:sumtwop21). The corresponding multiparametric KKT (mpKKT) conditions are also given in Theorem LABEL:interior2yy.

In the third category, along with invariant region decomposition, our results capture and generalize the SDP cases of Mohammad-Nezhad and Terlaky [MT20]. We develop the concepts of the nonlinearity region and the transition point for the optimal partition to conic representable sets by means of set-valued mappings, and provide some sufficient conditions for the existence of a nonlinearity region and a transition point. Such concepts are very useful for the analysis of an mpCLO problem because the nonlinearity region can be regarded as a stability region and its identification has a significant influence on the post-optimal analysis of SDPs.

In addition, we study the behavior of the optimal value function in its domain; and partially answer the open question proposed by Hauenstein et al. [Hau19].

In the next section, we review some useful results from convex analysis and the duality theory of CLO, and introduce nonstandard Lagrange dual and lift-and-project procedures. In Section 3, we define the set-valued mappings between the aforementioned conic representable sets and develop duality theory in CLOs. In Section 4, some fundamental concepts are introduced and several examples are presented to illustrate these concepts. The extension of the corresponding approach to the multiparametric analysis of CLOs is discussed in Section 5. The identification of the optimal partitions of a conic representable set is discussed and the behavior of the optimal value function in its domain is studied in this section. Finally, in Section 6, we conclude the paper with some remarks.

First, we review some useful facts regarding convex sets and cones. A standard reference for convex analysis is a book by Rockafellar [Roc70].

The (topological) boundary of a set $C\in\mathbb{R}^{q}$ is denoted as $\partial C$ and defined as $\partial C=\operatorname{cl}(C)\backslash\operatorname{int}(C)$, where cl($C$) and int($C$) denote the closure and interior of $C$, respectively. $\operatorname{dim}(C)$ denotes the affine dimension of $C$. A set $C$ is called simply connected if for any two points $x,y\in C$, there is a continuous curve $\Gamma\subset C$ connecting $x$ and $y$. A singleton set is referred to as simply connected set. A set $C$ is called convex if for any $x,y\in C$, the linear segment $[x,y]=\{\alpha x+(1-\alpha)y|\alpha\in[0,1]\}$ is contained in $C$. The convex hull of $C$, denoted as $\operatorname{conv}(C)$, is a set of all the convex combinations from $C$.

Let $C$ be a nonempty convex set in $\mathbb{R}^{q}$. The vector $0\neq h\in\mathbb{R}^{q}$ is called the recession direction of $C$ if $c+\lambda h\in C$ for all $c\in C$ and $\lambda>0$. The set of all recession directions of $C$ is called the recession cone of $C$, and is denoted as $0^{+}(C)$. Given a boundary point $\bar{x}$ of $C$, its normal cone $\operatorname{Normal}(C,\bar{x})$ is defined as

A point $\bar{x}$ is a vertex of $C$ if its normal cone is full-dimensional.

Mapping $\Phi(\xi):\mathbb{R}^{r}\rightrightarrows\mathbb{R}^{r}$ is called set-valued mapping if it assigns a subset of $\mathbb{R}^{r}$ to each element of $\mathbb{R}^{r}$. The following set

denotes the image of set $C\in\mathbb{R}^{r}$ under set-valued mapping $\Phi$.

The notations $R(A)=\{Ax|x\in\mathbb{R}^{q}\}$ and $N(A)=\{x|Ax=0,x\in\mathbb{R}^{q}\}$ denote the range and kernel space of the matrix $A$, respectively.

Let $U$ be an open subset of $\mathbb{R}^{r}$. We say that the mapping $f:U\rightarrow\mathbb{R}$ is G$\hat{a}$teaux differentiable at a point $u\in U$ in a direction $h\in\mathbb{R}^{r}$ if there exists $f^{\prime}(u,h)\in\mathbb{R}$ such that

where $f^{\prime}(u,h)$ is called the directional derivative of $f$ at $u$ in the direction $h$. The mapping $f$ is called G$\hat{a}$teaux differentiable at $u$, provided that $f^{\prime}(u,h)$ exists for all $h\in\mathbb{R}^{r}$ and the mapping $f^{\prime}(u,\cdot):\mathbb{R}^{r}\rightarrow\mathbb{R}$ is a continuous linear operator.

Recall that (P-lift), without perturbation is the typical form of the CLO

and its Lagrangian dual problem is expressed as follows:

For clarity and elegance (another crucial reason is given in the next section), we use an equivalent form instead of (D). In other words, (D) is rewritten as a new objective function with new constraints. This can be implemented through the following process.

Left multiplying both sides of the equality constraint in (D) by the matrix $B$ and $M$, respectively, one has $By=Bc$ and $My=Mc$ if $y=c-A^{T}w$. Conversely, if $y\in K^{*}$ satisfies both $By=Bc$ and $My=Mc$, $w\in\mathbb{R}^{m}$ exists, such as $y=c-A^{T}w$. Thus, the feasible set of (D) can be expressed equivalently as in $\{y\in K^{*}|By=a,My=Mc\}$. On the other hand, if a pair of vectors $(x;w)$ is feasible, and if $b=Ad$ and $y=c-A^{T}w$,

That is, (D) can be rewritten as follows:

where $a=Bc$. This is essentially the dual of (P), where $y$ denotes the slackness vector variable in (D). Therefore, (D) and (D-non) are the standard dual and nonstandard dual of (P), respectively.

For the primal and dual programs (P) and (D), the weak duality property holds. Then, from the equality (4), the following result holds: