# Solving Risk-Return Tradeoff Model with Galois Connection

Thu-Le Tran, Nhut-Tan Huynh, Thiet-Thu Mai, Tan-Hau Nguyen,
Thanh-Hung Nguyen

► To cite this version:

Thu-Le Tran, Nhut-Tan Huynh, Thiet-Thu Mai, Tan-Hau Nguyen, Thanh-Hung Nguyen. Solving Risk-Return Tradeoff Model with Galois Connection. 2025. hal-05326844

HAL Id: hal-05326844

https://hal.science/hal-05326844v1

Preprint submitted on 22 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solving Risk-Return Tradeoff Model with Galois Connection

Thu-Le Tran¹*, Nhut-Tan Huynh¹,

Thiet-Thu Mai¹, Tan-Hau Nguyen¹, and Thanh-Hung Nguyen¹

¹Can Tho University, Vietnam

*Corresponding Author ttle@ctu.edu.vn

20/09/2025

## Abstract

We propose a risk-return tradeoff problem that seeks to minimize risk while ensuring at least a prescribed level of return. We observe that this problem is equivalent to the inverse median problem on a tree under the Chebyshev (max) norm, which admits a parametric closed-form solution. Our main contribution is to uncover the hidden structure underlying this solution through a new duality framework fundamentally different from the classical Lagrange and Fenchel-Rockafellar duality frameworks. The key idea is to exchange the roles of the risk and return functions to formulate a dual problem. This perspective yields two insights. First, the parametric solution to the original problem can be interpreted as a trivial solution to the dual problem. Second, we establish a Galois connection between the two problems, showing that solving the dual problem provides an immediate way to recover the solution of the original problem.

# 1 Introduction

We consider a simple risk-return tradeoff model. Suppose there are $n$ objects indexed by $i = 1, \dots, n$. Each object can be modified with an amount $x_i \ge 0$ to enhance the system's performance. The return obtained from modifying object $i$ is $c_i x_i$, so the total return is $\sum_{i=1}^n c_i x_i$, where $c_i > 0$ for all $i = 1, \dots, n$. We require that this total return be at least a prescribed value $a \ge 0$. However, there is a tradeoff: modifications introduce risk, measured as the maximum modification magnitude across all objects, $\max_{i=1, \dots, n} x_i$, which we aim to minimize. In addition, each modification is subject to an upper bound, $x_i \le b_i$ for all $i = 1, \dots, n$.

This tradeoff gives rise to the following risk-return optimization problem:

$$ (P) \quad \min \quad \max_{i=1, \dots, n} x_i, \qquad (1a) $$

$$ \text{s.t.} \quad \sum_{i=1}^{n} c_i x_i \ge a, \qquad (1b) $$

$$ 0 \le x_i \le b_i, \quad i = 1, \dots, n. \qquad (1c) $$
The problem is feasible if and only if

$$ \sum_{i=1}^{n} c_i b_i \geq a. \qquad (2) $$

This problem is fundamental, as it exhibits structural connections with several classic models in operations research.

* The problem can be viewed as a special case of the *minimax resource allocation problem* through the variable transformation $y_i = b_i - x_i$ for all $i = 1, \dots, n$; see Luss [1992]. Unlike general formulations involving multiple linear constraints, our model contains only a single constraint, which enables an elegant analytical interpretation of the optimal solution and permits more efficient solution procedures.

* It is also closely related to the *continuous knapsack problem* [Korte and Vygen, 2008, Chap. 17]. A variant of this is the continuous knapsack problem with a min-sum objective Kuno et al. [1991]. These problems admit linear-time solution methods.

* By scaling the modification vector $x$, we can always assume that the equality in (1b) holds. Consequently, the problem becomes equivalent to the (simplified) *inverse median location problem on a tree under the Chebyshev norm*. In particular, the problem ($P$) can be solved in $O(n \log n)$ time using sorting-based methods Guan and Zhang [2010], and further improved to $O(n)$ time via a binary search approach Guan and Zhang [2012].

* Other models of inverse or upgrading median location models with budget constraints on trees can be regarded as variants of our formulation, see [Alizadeh and Afrashteh, 2020, Sec. 6], Nguyen-Thu et al. [2024], and Pham et al. [2025], which consider max-sum objectives and two linear constraints.

The goal of this paper is to investigate the structure of the optimal solution for problem ($P$). As discussed earlier, this structure plays a central role in designing a linear-time algorithm for the problem. Our main contribution is to reveal a new duality framework that explains the form of this solution. The proposed duality framework is fundamentally different from the classical Lagrange and Fenchel-Rockafellar duality frameworks. The key idea is to exchange the roles of the risk and return functions to formulate a dual problem. Notably, similar ideas have appeared in recent works, see e.g., [Alizadeh and Afrashteh, 2020, Sec. 6], Nguyen-Thu et al. [2024], and Pham et al. [2025]; however, a formal characterization of the relationship between the two problems has been lacking. In this paper, we formalize this connection, which leads to two key insights. First, the parametric closed-form solution of the original problem can be viewed as a trivial solution of the dual problem. Second, we establish a Galois connection between the primal and dual formulations, showing that solving the dual problem immediately yields the solution of the original one.

In Section 2, we present a direct proof of the parametric closed-form solution, following a water-filling approach. In Section 3, we reformulate the risk-return model in an abstract form and introduce the novel duality framework. Finally, in Section 4, we establish a Galois connection between the primal and dual problems to fully characterize the structure of the solution's parameter.

## 2 Optimal Solution

The risk-return model admits a parametric closed-form solution, which we derive below. Define for any $\beta \in \mathbb{R}$ the vector $x^{(\beta)} \in \mathbb{R}^n$ by

$$ x_i^{(\beta)} = \min(b_i, \beta), \quad i = 1, \dots, n. \qquad (3) $$
In other words, $x^{(\beta)}$ assigns the maximum allowed value $b_i$ to each $x_i$ whose bound $b_i$ is below $\beta$, and sets $x_i = \beta$ for all remaining items. Intuitively, one may think of $\beta$ as a “water level” up to which all items are filled, capped by their individual heights $b_i$—this is the classic water-filling interpretation.

We continue to increase the level until the total return reaches the prescribed value $a$. Let $\beta_0$ denote the unique value of $\beta$ such that the total return of $x^{(\beta)}$ is exactly $a$, that is,

$$ \sum_{i=1}^{n} c_i \min(b_i, \beta_0) = a. \qquad (4) $$

It is important to note that the left-hand side of (4), viewed as a function of $\beta$, is continuous and strictly increasing on $(0, \max_{i=1,...,n} b_i)$ since $c_i > 0$ for all $i$. Therefore, the existence of $\beta_0$ is guaranteed under the feasibility condition (2), and its uniqueness follows from the strict monotonicity of the total return function.

The corresponding allocation $x^{(\beta_0)}$ is then an optimal solution of problem (P). We provide in the following a simple and direct proof for this claim.

**Theorem 1.** Problem (P) has an optimal solution given by $x^{(\beta_0)}$, where $\beta_0$ is the unique value satisfying (4).

*Proof.* The feasibility of $x^{(\beta_0)}$ follows directly from the definition of $\beta_0$. To establish optimality, suppose for contradiction that the minimum risk of (P) is some $\beta^* < \beta_0$. Then there exists a feasible solution $\tilde{x} \in \mathbb{R}^n$ such that $\max_{i=1,...,n} \tilde{x}_i = \beta^*$. We have

$$ \sum_{i=1}^{n} c_i \tilde{x}_i \le \sum_{i=1}^{n} c_i \min(b_i, \beta^*) < \sum_{i=1}^{n} c_i \min(b_i, \beta_0) = a, \qquad (5) $$

where the first inequality holds since $\tilde{x}_i \le \beta^*$ and $\tilde{x}_i \le b_i$ for all $i = 1, ..., n$, the second follows from the assumption $\beta^* < \beta_0$ and the strict monotonicity of the total return on $(0, \max_{i=1,...,n} b_i)$, and the last equality holds by the definition of $\beta_0$ in (4). Hence, $\sum_{i=1}^{n} c_i \tilde{x}_i < a$, contradicting the feasibility of $\tilde{x}$. Therefore, no feasible solution can achieve a risk smaller than $\beta_0$, and since $x^{(\beta_0)}$ attains risk $\beta_0$, it is indeed optimal. $\square$

We have shown that problem (P) admits a solution $x^{(\beta_0)}$, which arises naturally from the water-filling intuition, and we have established this result in a constructive manner. In the following sections, we will see that Theorem 1 is in fact a direct consequence of a deeper duality structure, within which the parametric solution $x^{(\beta)}$ emerges naturally. This perspective also provides further insight into why $\beta_0$ must satisfy equation (4).

## 3 A dual setting

To uncover the underlying structure of the risk-return model, we adopt an abstract viewpoint. Define

$$ \begin{aligned} f(x) &= \max_{i=1,...,n} x_i, \\ g(x) &= -\sum_{i=1}^{n} c_i x_i, \\ X &= [0, b] = \{x \in \mathbb{R}^n : 0 \le x_i \le b_i, i = 1, ..., n\}, \\ \alpha &= -a. \end{aligned} $$
The original risk-return tradeoff problem can then be reformulated in a parametric form as

$$F(\alpha) = \min\{f(x) : x \in G_{\alpha}\}, \quad \text{where } G_{\alpha} = \{x \in X : g(x) \le \alpha\}.$$

We refer to this as the *primal problem* and interpret $\alpha$ as a parameter associated with the required return. In the following, we treat $\alpha$ as a dynamic variable while $a$ remains fixed, and the original risk-return model is recovered when $\alpha = -a$.

By exchanging the roles of risk and return, we can similarly define a *dual problem*:

$$G(\beta) = \min\{g(x) : x \in F_{\beta}\}, \quad \text{where } F_{\beta} = \{x \in X : f(x) \le \beta\},$$

for a risk level parameter $\beta$.

We now show that the solution of the risk-return optimization (P) is a solution for the dual problem. Note that $F_{\beta} = \emptyset$, when $\beta < 0$. We therefore only consider $\beta \ge 0$. The dual problem for (P) can be rewritten as:

$$(D) \quad \max \sum_{i=1}^{n} c_i x_i, \\ \text{s.t.} \quad x_i \in [0, \min(b_i, \beta)], \quad i = 1, \dots, n.$$

We will refer to this specific dual problem as *return-risk model*, where $\beta$ is a given risk limit, i.e., $x_i \le \beta$ for all $i = 1, \dots, n$. This simply means that for a fixed $\beta$, we choose each $x_i$ as large as possible to maximize return while respecting both the cap $b_i$ and the common risk limit $\beta$. It follows that the optimal solution for a given $\beta$ is exactly $x^{(\beta)}$ defined in (3). The corresponding dual optimal value is

$$G(\beta) = - \sum_{i=1}^{n} c_i \min(b_i, \beta).$$

and thus the definition of $\beta_0$ in (4) can be rewritten as

$$G(\beta_0) = -a.$$

We can now provide new interpretation of $x^{(\beta)}$ and $\beta_0$:

* $x^{(\beta)}$ emerges as a trivial solution to the dual problem (D).

* $\beta_0$ represents the risk level at which the corresponding optimal return $-G(\beta_0)$ attains the prescribed value $a$.

In the next section, we establish the optimality relationship between the primal and dual problems. This result plays a pivotal role in interpreting Theorem 1 as a direct consequence and in explaining why $\beta_0$ must satisfy equation (4).

# 4 Dual optimality conditions

For the analysis, we assume that for each $\alpha$ and $\beta$ of interest, the minima defining $F(\alpha)$ and $G(\beta)$ are attained. This assumption is justified since $X$ is compact and $f, g$ are continuous. We will show that the functions $F(\cdot)$ and $G(\cdot)$ possess some useful monotonicity and duality properties.

As one might expect, increasing the return requirement can only increase the minimum risk, and conversely increasing the risk allowance can only increase the achievable return. Formally:
**Lemma 1.** The functions $F(\alpha)$ and $G(\beta)$ are both non-increasing functions.

*Proof.* We prove the statement for $F(\alpha)$, the proof for $G(\beta)$ is analogous. If $\alpha_1 \le \alpha_2$ then the feasible set $G_{\alpha_1} = \{x : g(x) \le \alpha_1\}$ is a subset of $G_{\alpha_2} = \{x : g(x) \le \alpha_2\}$. Therefore

$$F(\alpha_1) = \min_{x \in G_{\alpha_1}} f(x) \ge \min_{x \in G_{\alpha_2}} f(x) = F(\alpha_2),$$

This establishes the monotonicity of $F$.

<figure><img src="image_2.png" /></figure>

We next show that the primal and dual formulations are linked by a Galois connection in the lattice-theoretic sense. Intuitively, the statement will relate the condition $F(\alpha) \le \beta$ to $G(\beta) \le \alpha$, revealing a type of “inverse” relationship between the two functions.

**Lemma 2 (Galois connection).** For any $\alpha$ and $\beta$, we have

$$F(\alpha) \le \beta \iff \alpha \ge G(\beta). \qquad (6)$$

*Proof.* We only prove (⇒). Assume $F(\alpha) \le \beta$. By definition of $F(\alpha)$, there exists an optimal solution $x_\alpha \in G_\alpha$ such that $f(x_\alpha) = F(\alpha) \le \beta$. This means $x_\alpha \in F_\beta$. Now $x_\alpha \in F_\beta$ implies $g(x_\alpha) \ge G(\beta)$, because $G(\beta)$ is the minimum value of $g$ on $F_\beta$ and $x_\alpha$ is a feasible solution in $F_\beta$. On the other hand, $x_\alpha \in G_\alpha$ implies $g(x_\alpha) \le \alpha$. Combining these, we get $\alpha \ge g(x_\alpha) \ge G(\beta)$. □

<figure><img src="image_3.png" /></figure>

Note that a direct consequence of Lemma 2 is that when taking $\beta = F(\alpha)$, we have

$$G(F(\alpha)) \le \alpha. \qquad (7)$$

The Lemma 2 suggests an approach to recover a solution of the primal problem by instead solving a dual problem. The following theorem formalizes this approach.

**Theorem 2 (Primal solution via dual).** For a given $\alpha$, let

$$\beta_1 = \min\{\beta \in \mathbb{R} : G(\beta) \le \alpha\}. \qquad (8)$$

Then $\beta_1$ is the objective for primal problem, i.e., $\beta_1 = F(\alpha)$, and moreover any optimal solution corresponding to $\beta_1$ in the dual problem is an optimal solution for the primal problem $F(\alpha)$.

*Proof.* We have $\beta_1 = \min\{\beta : G(\beta) \le \alpha\} = F(\alpha)$ due to the Galois connection (6) and inequality (7). Now let $x^*$ be an optimal solution for the dual problem $G(\beta_1)$, so $x^* \in F_{\beta_1}$ and $g(x^*) = G(\beta_1) \le \alpha$. The latter implies $x^* \in G_\alpha$. Thus $x^*$ is feasible for the primal problem $F(\alpha)$. Furthermore, since $x^* \in F_{\beta_1}$, we have $f(x^*) \le \beta_1 = F(\alpha)$. But $F(\alpha)$ is the minimum possible value of $f(x)$ for $x \in G_\alpha$, so it must be that $f(x^*) = F(\alpha)$. Therefore $x^*$ attains the minimum in the primal problem $F(\alpha)$ as well. □

<figure><img src="image_4.png" /></figure>

Now, applying Theorem 2 with $\alpha = -a$ to the original problem, we obtain $\beta_1$ as the minimum risk level $\beta$ satisfying

$$\beta_1 = \min \left\{ \beta \in \mathbb{R} : \sum_{i=1}^{n} c_i \min(b_i, \beta) \ge a \right\}. \qquad (9)$$

Recall that the total return in (9), viewed as a function of $\beta$, is continuous and strictly increasing on $(0, \max_{i=1,...,n} b_i)$. Therefore, $\beta_1$ coincides with the unique point at which the equality holds, i.e.,

$$\beta_0 = \beta_1.$$

This establishes the equivalence between the primal and dual viewpoints, confirming that the water-filling solution is a direct consequence of the dual structure.
Conclusion

We studied a fundamental minimax allocation problem that balances risk and return, showing that it admits
a unique parametric closed-form, water-filling-type solution computable in linear time.

We further uncovered the deep structure underlying this simple setting by introducing a new duality framework, fundamentally different from the classical Lagrange and Fenchel-Rockafellar dualities. This framework clarifies the relationship between risk and return: for any risk level $\beta$, the allocation $x^{(\beta)}$ is an optimal solution of the dual problem $G(\beta)$, while $\beta_0$ is characterized as the minimal risk level required to achieve the target return $a$. The key idea in our analysis lies in establishing a Galois connection between the two problems.

Finally, the proposed duality framework can be extended to more complex settings, where it is expected
to yield structural insights and serve as a foundation for designing efficient algorithms.

References

Behrooz Alizadeh and Esmaeil Afrashteh. Budget-constrained inverse median facility location problem on tree networks. *Applied Mathematics and Computation*, 375:125078, 2020.

Xiucui Guan and Binwu Zhang. Inverse 1-median problem on trees under weighted max norm. In *International Conference on Algorithmic Applications in Management*, pages 150–160. Springer, 2010.

Xiucui Guan and Binwu Zhang. Inverse 1-median problem on trees under weighted hamming distance. *Journal of Global Optimization*, 54(1):75–82, 2012.

Bernhard Korte and Jens Vygen. *Combinatorial optimization: theory and algorithms*. Springer, 2008.

Takahito Kuno, Hiroshi Konno, and Eitan Zemel. A linear-time algorithm for solving continuous maximin knapsack problems. *Operations Research Letters*, 10(1):23–26, 1991.

Hanan Luss. Minimax resource allocation problems: Optimization and parametric analysis. *European Journal of Operational Research*, 60(1):76–86, 1992.

Huong Nguyen-Thu, Kien Trung Nguyen, and Nguyen Thanh Toan. The max-sum inverse median location problem on trees with budget constraint. *Applied Mathematics and Computation*, 460:128296, 2024.

Van Huy Pham, Ngan Nguyen, Minh-Quang Cao, Hong-Phuong Dang, and Thu-Le Tran. Stability radius and an upgrading model of median location on trees. *Asia-Pacific Journal of Operational Research*, 2025.