Abbas Khademi

Keywords: Adjustable Robust Optimization, Fenchel Duality, Biconvex Programming, Perspective Function, Cutting Plane Methods, Quadratic Optimization, Decision Policy, Linearization-Relaxation Technique Adjustable Robust Optimization. Submitted

Robust Optimization (RO) is a popular approach for dealing with uncertain data in optimization. In static robust optimization, decision variables represent hereand-now decisions made without exact knowledge of uncertain parameters but must be feasible when the actual data is within the uncertainty set. However, one mechanism to overcome the limitations of the static RO approach is Adjustable Robust Optimization (ARO), which leverages adaptability. The main difference between static RO and ARO approaches is the decision-making manner. In ARO problems, some variables are here-and-now decisions, while others are wait-andsee decisions made later based on the observed parameters in the uncertainty set.

In this PhD thesis, we address two main topics in mathematical optimization.

The first topic concerns a class of nonlinear ARO problems with uncertainty in the objective function and constraints. By utilizing Fenchel's duality, we derive an equivalent dual reformulation that is a nonlinear static robust optimization problem. We then apply perspective relaxation and an alternating method to handle non-concavity and design a new dual-based cutting plane algorithm that can find a reasonable lower bound for the optimal objective value. Through numerical experiments, we show the effectiveness of the cutting plane algorithm in producing locally robust solutions with an acceptable optimality gap.

The second topic focuses on the reformulation of quadratic optimization problems using ARO. Quadratic Optimization (QO) has been extensively studied in the literature due to its practical applicability in numerous problems. Despite its practicality, QO problems are generally NP-hard. Consequently, researchers have developed various numerical methods for finding approximate optimal solutions. In this thesis, we analyze QO problems through the lens of robust optimization techniques. We first demonstrate that any QO problem can be reformulated as a disjoint bi-convex QO problem. Subsequently, we present an equivalent ARO reformulation and utilize some methods from the relevant literature to approximate this reformulation. Specifically, we show that employing a so-called decision rule technique to approximate the ARO reformulation can be interpreted as applying a linearization-relaxation technique to its bi-convex reformulation problem. Additionally, we have designed an algorithm capable of finding a solution that is close to optimal based on our new reformulations.

Our numerical results highlight the efficiency of our algorithm, particularly for large-sized instances, in comparison with standard off-the-shelf solvers. This work offers a novel perspective on quadratic problems and paves the way for further research in this domain of mathematical optimization.

iii TO THOSE WHO DID NOT AND DO NOT HAVE EDUCATIONAL FACILITIES AND COULD NOT STUDY Abbas Khademi February 6, 2024 v Writing a thesis is certainly not a solitary endeavor, but rather a collaborative effort involving numerous individuals who have contributed to its triumphant culmination. In this part, I am fortunate to have the opportunity to express my gratitude to these people.

First and foremost, I would like to express my deepest appreciation to my supervisor, Professor Majid Soleimani-damaneh. His guidance and support throughout the entire research process were invaluable. His intellectual insights, technical expertise, and unwavering commitment to excellence significantly enhanced my research skills and analytical thinking. I have learned a great deal from him, not only in the field of Optimization but also in research ethics and values that are essential in daily life.

I would also like to extend my profound gratitude to Dr. Ahmadreza Marandi for his astute discussions and unwavering support in exploring various research ideas. His guidance as my academic advisor was instrumental in fostering my intellectual curiosity. This thesis celebrates the amicable relationship I share with Ahmadreza, both as a mentor and a friend. I have derived significant intellectual benefits from his perspicacity and discerning approach to research.

His constant encouragement and motivational zeal have been an illuminating force in my research endeavors. Additionally, we did regular weekly meetings to discuss ongoing research projects and exchange new ideas, which helped me stay on track and make progress in my research.

I would also thank all my teachers. Each one has taught me valuable lessons and skills that helped me become who I am today. Specially, I would like to express my gratitude to Dr. Morteza Mirdehghan, who introduced me to the fascinating world of Optimization during my undergraduate studies and inspired me to pursue further research in this area. I am also thankful to Dr. Alireza Hosseini and Dr. Mohammad B. Asadi for deepening my knowledge and understanding of the subject matter by teaching some courses during my time as a graduate student.

In addition, I owe a debt of gratitude to my friends, Aliakbar Hosseini and Yaghoub Rahimi, for their insightful scientific discussions and feedback. I would also like to thank M. Reza Modares, M. Ali Asadi-vasfi, and Ava Azarshab for their encouragement. Special mention goes to Moslem Zamani, Hadi Abbaszadeh, and Sahand Asgharieh whose assistance during my stay in the Netherlands was invaluable. My sincere appreciation also goes to the family of the late Prof.

Ebrahim Ghasemi-Nejad for their 9-month financial contribution as a scholarship. Teaching at the University of Tehran was an enriching experience that allowed me to feel more connected to the academic community. I am also grateful to all of my students in these years.

Last but not least, I want to express my profound appreciation for my parents' unwavering love, trust, and understanding. Their constant support and encouragement have been a source of strength and motivation throughout my academic journey. In particular, my mother has played an instrumental role in shaping my personality, character, and academic pursuits. To show my heartfelt gratitude, I dedicate this thesis to my mother, who is the strongest woman in the world to me.

In conclusion, I am immensely grateful to all those who have played a part in my academic journey.

Abbas Khademi,

Preface

In light of human advancements in numerous fields and the increasing demand for resources on the one hand, and their limitations on the other hand, the need for optimal use of resources becomes more crucial. Mathematical optimization has become an important part of many decision-making problems in management, economics, medicine, engineering, etc. In classical optimization models, all parameters are considered to be exactly known, resulting in deterministic problems.

In real life, however, many of the parameters are not known at the moment of decision-making and have uncertainty in their essence. There are various approaches for dealing with uncertainty in the optimization and mathematical modeling literature. The most commonly used ones are stochastic optimization and robust optimization.

In stochastic optimization, probabilistic information (distribution) on the uncertain parameters is required and the decision-maker aims to optimize expected objective values; for a more detailed description of stochastic optimization, we refer to the textbook [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF]. The main disadvantage of stochastic optimization is that the exact distributions of uncertain parameters are often unknown. In contrast, Robust Optimization (RO) does not require any probabilistic information.

In RO, the best solution is chosen among those that are safe-guarded against all scenarios in a pre-specified set, called uncertainty set.

The concept of static RO was first proposed by Soyster in the 1970s, who studied a linear optimization problem with a box uncertainty set [START_REF] Soyster | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF]. Later in the 1990s, static RO was formally introduced [START_REF] Ben-Tal | Robust convex optimization[END_REF][START_REF]Robust solutions of uncertain linear programs[END_REF][START_REF] Ghaoui | Robust solutions to uncertain semidefinite programs[END_REF] and its computational advantage has resulted in its wide usage in applications, including in portfolio selection [START_REF] Koushki | LR-NIMBUS: an interactive algorithm for uncertain multiobjective optimization with lightly robust efficient solutions[END_REF][START_REF] Xidonas | Robust portfolio optimization: A categorized bibliographic review[END_REF], scheduling [START_REF] Breuer | Robust combined operating room planning and personnel scheduling under uncertainty[END_REF], operations management [START_REF] Lu | A review of robust operations management under model uncertainty[END_REF], etc.

In static RO, all decision variables represent here-and-now decisions, meaning the decisions are made before realization of the uncertain parameters [START_REF] Ben-Tal | Robust optimization[END_REF]. However, in many practical applications, the value of some decisions can be adjusted after realization of (part of) uncertain parameters. These kinds of decisions are called wait-and-see decisions. Adjustable Robust Optimization (ARO) is an extension of the static RO wherein decision variables are divided into two types: here-and-now and wait-and-see [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. In recent years, the application of ARO has been widespread in many areas such as network design [START_REF] Zhang | A two-stage robust model for express service network design with surging demand[END_REF], locationtransportation problems [START_REF] Marandi | Robust location-transportation problems with integer-valued demand[END_REF], facility location problems [START_REF] Du | A two-stage robust model for a reliable p-center facility location problem[END_REF], chemical engineering [START_REF] Kammammettu | Two-stage robust optimization of water treatment network design and operations under uncertainty[END_REF][START_REF] Liang | Adjustable robust optimal control for industrial 2mercaptobenzothiazole production processes under uncertainty[END_REF], logistics [START_REF] Ke | Managing reliable emergency logistics for hazardous materials: A twostage robust optimization approach[END_REF], radiotherapy [START_REF] Roy | Value of intermediate imaging in adaptive robust radiotherapy planning to manage radioresistance[END_REF], to name a few.

Although ARO improves solution quality (in the sense of being less conservative), its computational complexity is higher than static RO [START_REF] Yanıkoğlu | A survey of adjustable robust optimization[END_REF]. Under some circumstances, ARO and static RO are equivalent [START_REF] Marandi | When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?[END_REF]; therefore, using the static RO viii ix model for some cases can be advantageous. Moreover, as wait-and-see decisions are chosen after realizing uncertain parameters, they can be considered as decision rules or functions of the uncertain parameters. A way to approximate an ARO problem is by restricting wait-and-see variables to be affine in uncertain parameters, and use the so-called affine decision rules (ADR). Under some conditions, ADR can provide a "good" approximation of an ARO problem [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF][START_REF] Bertsimas | On the power and limitations of affine policies in two-stage adaptive optimization[END_REF]. Next to ADR, there are also other decision rules, like piece-wise constant [START_REF] Romeijnders | Piecewise constant decision rules via branch-andbound based scenario detection for integer adjustable robust optimization[END_REF], quadratic [START_REF] Woolnough | Exact conic programming reformulations of two-stage adjustable robust linear programs with new quadratic decision rules[END_REF], and polynomial [START_REF] Bertsimas | A hierarchy of near-optimal policies for multistage adaptive optimization[END_REF], each has their own advantages and disadvantages.

In addition to decision rules, there are several other approximation techniques for solving linear ARO problems in the literature, including Benders decomposition [START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF], finite adaptability [START_REF] Hanasusanto | K-adaptability in two-stage robust binary programming[END_REF], partitioning the uncertainty set [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF][START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF], and copositive approach [START_REF] Xu | A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides[END_REF].

This thesis aims to contribute to the growing literature on robust optimization by proposing novel approaches to solving nonlinear ARO problems and indefinite Quadratic Optimization (QO) problems. Chapter 1 provides the necessary definitions and notations. Chapter 2 briefly goes over the initial idea and birth of the adjustable robustness concepts and reviews some approximations of linear ARO problems. Chapter 3 focuses on a class of nonlinear ARO problems with uncertainty in the objective function and constraints, proposing a cutting plane algorithm to obtain locally robust solutions. Chapter 4 presents a new reformulation technique for indefinite QO problems as ARO, offering new possibilities for solving large-scale problems in the field of mathematical optimization. Finally, Chapter 5 presents conclusions and future research. 1. [START_REF] Ardestani-Jaafari | Linearized robust counterparts of two-stage robust optimization problems with applications in operations management[END_REF] The robust feasible region.

Thesis Outline

1.5 Adjustable robust optimization. The blue square is the uncertainty set U.

1.6 Affine and piece-wise constant decision policies.

1.7 Classical uncertainty sets.

3.1 The comparison of the optimality gaps of the solutions obtained by Algorithm 1, Algorithm 2, and finite-scenario approach for the instances in Class One.

3.2 The comparison of the solution time of Algorithm 1, Algorithm 2, and finitescenario approach for the instances in Class One.

3.3

The comparison of the optimality gaps of the solutions obtained by Algorithm 1, Algorithm 2, and finite-scenario approach for the instances in Class Two.

3. [START_REF] Ardestani-Jaafari | Linearized robust counterparts of two-stage robust optimization problems with applications in operations management[END_REF] The comparison of solution times between Algorithm 1, Algorithm 2, and the finite-scenario approach for instances in Class Two.

xiv List of Tables 1. [START_REF] Ahmadi | On the complexity of finding a local minimizer of a quadratic function over a polytope[END_REF] Conjugate functions of some popular forms.

1.2 Support functions of some popular sets.

1.3 Convex quadratic problems and their corresponding Dorn duals.

3.1 Statistic of optimality gaps of instances in Class One.

3.2 Statistic of optimality gaps of instances in Class Two. "If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."

In this thesis, we use the following definitions and notations. We first recall some standard terminology from convex analysis.

Notation

We use [m] to denote the set {1, 2, . . . , m}, and [m 0 ] to denote the set {0, 1, . . . , m}. The column vector of all zeros will be denoted by 0. The sets of all non-negative and all extendedreal numbers are denoted by R + ∶= [0, ∞) and R ∶= [-∞, ∞], respectively. We denote by ri(S) the relative interior of a set S ⊆ R n .

Conjugacy and Perspective Function

An extended real-valued function is a function that can adopt the value plus infinity. Suppose that f ∶ R n → R ∪ {∞}, the set of points above the graph of an extended real-valued function f is called the epigraph of f , i.e., epi(f ) = {(x, t) ∶ f (x) ≤ t} ⊆ R n+1 . The projection of the epigraph onto the x space is referred to as the domain of f (see Figure 1.1).

An extended real-valued function f is proper if its domain is not empty, i.e., if f (x) > -∞ for all x ∈ R n and f (x) < +∞ for at least one x ∈ R n . A function f is closed if its epigraph is a closed set. The epigraph of a proper convex and closed function is convex, closed, non-empty, and contains no vertical line. Definition 1.1.1 (Conjugate Functions, [START_REF] Rockafellar | Convex analysis[END_REF]). 1 The conjugate of a function

x f (x) epi(f ) dom(f ) ∞ ∞
g ∶ R n → R is the function g * ∶ R n → R defined as g * (y) ∶= sup x∈R n {y ⊺ x -g(x)}, where y ∈ R n .
This definition with n = 1 is visually represented in Figure 1.2. For given y, the highest value of yxg(x) is achieved when the derivative of g(x) equals y. At this point, the tangent line of g intersects the y-axis at the coordinates (0, -g * (y)) [START_REF] Roos | A universal and structured way to derive dual optimization problem formulations[END_REF].

The indicator function of a set S ⊆ R n , denoted by δ S , is defined as

δ S (x) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0, x ∈ S, ∞, x ∉ S. The support function δ * S ∶ R n → R of a set S ⊆ R n is δ * S (y) ∶= sup x∈S {y ⊺ x}, where y ∈ R n .
It is worth mentioning that the support function corresponding to S is the conjugate of δ S .

Remark 1.1.1 (Support Function and Conjugacy). The conjugate function of g could be expressed by using support function of epi(g) as g * (y) = δ * epi(g) (y, -1).

Definition 1.1.2 (Perspective Functions, [START_REF] Rockafellar | Convex analysis[END_REF][START_REF] Zhen | A unified theory of robust and distributionally robust optimization via the primal-worst-equals-dual-best principle[END_REF]). The convex perspective of a proper,

∶ R n → R is the function g per ∶ R n × R + → R defined by g per (x, t) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ tg ( x t ) , t > 0, δ * dom(g * ) (x), t = 0.
The convex perspective of a proper, closed, and convex function is also proper, closed, and convex (more precisely, jointly in (x, t)); see [99, page 35] for convexity and properness, and In the convex analysis literature, g per (x, 0) is called the asymptotic function or recession function of g. Moreover, g per (x, 0) = lim inf Proof. Let x 0 ∈ R n . We have

x ′ →x t ′ ↓0 t ′ g ( x ′ t ′ ) [7, 69].
g per (x 0 , t 0 = 0) = lim inf (x i ,t i )→(x 0 ,0) g per (x i , t i > 0) ≤ sup (x i ,t i )→(x 0 ,0) g per (x i , t i > 0) ≤ sup t>0,x∈R n g per (x, t).
So, sup t>0,x∈R n g per (x, t) = sup t≥0,x∈R n g per (x, t).

As inf t>0,x g per (x, t) ≥ inf t≥0,x g per (x, t), let ℓ ∈ {g per (x, t)|t ≥ 0, x ∈ R n }. We want to show ℓ ≥ inf t>0,x g per (x, t).

1. If ℓ = g per (x 0 , t 0 ) for some x 0 ∈ R n and t 0 > 0, then ℓ ≥ inf t>0,x g per (x, t).

2. If ℓ = g per (x 0 , 0) for some x 0 ∈ R n , then ℓ = g per (x 0 , 0) = lim inf

(x i ,t i )→(x 0 ,0) g per (x i , t i > 0) ≥ inf (x i ,t i )→(x 0 ,0) g per (x i , t i ) ≥ inf t>0,x∈R n g per (x, t).
The proof is complete.

As a consequence of the above proposition, we have

sup t>0,x -g per (x, t) = sup t≥0,x -g per (x, t).
The definitions are extended to partial conjugate and perspective. The partial conjugate of a function g ∶ R nx × R ny → R with respect to its second argument (likewise for first argument) is the function g * 2 ∶ R nx × R ny → R defined as g * 2 (x, w) = sup y∈R ny {w ⊺ yg(x, y)}, and its domain is denoted by dom(g 2 * )(x, ⋅).

If h ∶ R nx × R nu → R is a proper,
closed, and concave function in its second argument, then its concave partial perspective

h per ∶ R nx × R + × R nu → R is defined as h per (x, t, u) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ th (x, u t ) , t > 0, -δ * dom((-h) 2 * (x,.)) (u), t = 0.
Henceforth, for ease of notation, we use 0h (x, u/0) instead of h per (x, 0, u).

Theorem 1 (Properties of conjugate functions, [START_REF] Rockafellar | Convex analysis[END_REF]). The conjugate of a function g is closed and convex. Moreover, if g is closed and convex, then g * * = g. Finally, a convex function g is proper if and only if g * is proper.

In Table 1.1, we present some transformation rules that are useful for the computation of conjugate functions.

Furthermore, support functions of several important sets are listed in Table 1.2.

2 f (x + a) f * (y) -a ⊺ y [99, page 107] 3 f (x) + a ⊺ x f * (y -a) [99, page 107] 4 af (x), a > 0 af * ( y a ) [99, page 140] 5 f (ax), a > 0 f * ( y a ) [99, page 107] 6 m ∑ i=1 f i (x) min y i { m ∑ i=1 f * i (y i ) | m ∑ i=1 y i = y} [99, page 145] 7 m ∑ i=1 f i (x i ) m ∑ i=1 f * i (y i ) [39, page 95] 8 f (Ax + b) a A nonsingular f * (A -⊺ y) -b ⊺ A -⊺ y [99, page 107] b otherwise inf {f * (z) -b ⊺ z | A ⊺ z = y} [101, Section B.4]
Note: The functions f (x) and f i (x) in this table are convex. In row 6, it is assumed that

∩ m i=1 ri(dom(f i )) ≠ ∅; if f i (x)
is linear for some i, then the corresponding ri(dom(f i )) can be replaced by dom(f i ) in this condition. This is called the sum rule for conjugate functions. In row 7, the partition of x is denoted as x 1 . . . x m . Row 8 is called the linear substitution rule.

1 {x | Ax = b} min z {b ⊺ z | A ⊺ z = y} [39, page 380] 2 {x | Ax ≤ b} min z {b ⊺ z | A ⊺ z = y, z ≥ 0} [39, page 380] 3 {x | ∥x∥ p ≤ ρ} ρ∥y∥ q , 1 p + 1 q = 1 [12, page 272] 4 S = m ⋂ i=1 S i min y i { m ∑ i=1 δ * S i (y i ) | m ∑ i=1 y i = y} [99, page 146] 7 S = S 1 × ⋯ × S m m ∑ i=1 δ * S i (y i ) , y 1 . . . y m is a partition of y [12, page 294]

Fenchel Duality

In mathematical programming, the duality concept provides a powerful tool for understanding and solving optimization problems. Identifying relationships between the primal and dual problems provides valuable insights and alternative formulations. Fenchel Duality is a specific form of duality based on the conjugate function. In this section, we provide a brief overview of Fenchel duality.

Preliminaries

Definition 1.2.1 (Fenchel's Dual of a Convex Programming, [START_REF] Roos | A universal and structured way to derive dual optimization problem formulations[END_REF][START_REF] Zhen | A unified theory of robust and distributionally robust optimization via the primal-worst-equals-dual-best principle[END_REF]). Consider the following primal convex optimization problem:

inf y g 0 (y) s.t. g i (y) ≤ 0, i ∈ [m], (P)
where the functions

g i ∶ R n → R, i ∈ [m 0 ]
, are proper, closed, and convex. The Fenchel dual of (P) is defined as

sup λ,{w i } m i=0 -g * 0 (w 0 ) - m ∑ i=1 (g * i ) per (w i , λ i ) s.t. λ ≥ 0, m ∑ i=0 w i = 0, w 0 ∈ dom(g * 0 ), (w i , λ i ) ∈ dom ((g * i ) per ) , i ∈ [m]. (D)
For the ease of notation in (D), we use λ i g * i ( w i λ i ) to denote (g * i ) per (w i , λ i ), even for λ i = 0. So, we write (D) as follows:

sup λ,{w i } m i=0 -g * 0 (w 0 ) - m ∑ i=1 λ i g * i ( w i λ i ) s.t. λ ≥ 0, m ∑ i=0 w i = 0, w 0 ∈ dom(g * 0 ), w i λ i ∈ dom(g * i ), i ∈ [m],
where

w i λ i ∈ dom(g * i ) for λ i = 0 means δ * dom(g i ) (w i ) < ∞. Remark 1.2.1.
In problem (D), the constraints corresponding to the domain are essential and in many cases, they also lead to convex constraints for (D). Moreover, since (D) is a maximization problem, these constraints hold explicitly. These constraints, in many cases, enable us to eliminate the variables w i . For brevity, in [START_REF] Roos | A universal and structured way to derive dual optimization problem formulations[END_REF][START_REF] Zhen | A unified theory of robust and distributionally robust optimization via the primal-worst-equals-dual-best principle[END_REF] the dual problem has been written as follows:

sup λ,{w i } m i=0 -g * 0 (w 0 ) - m ∑ i=1 λ i g * i ( w i λ i ) s.t. λ ≥ 0, m ∑ i=0 w i = 0.
Definition 1.2.2 (Slater regularity). Problem (P) is Slater regular if there exists some

y s ∈ ∩ i∈[m 0 ] ri (dom(g i )), such that g i (y s ) < 0 for all i ∈ [m].
It is important to note that if (P) is Slater regular, then the optimal values of (P) and (D)

are equal [START_REF] Zhen | A unified theory of robust and distributionally robust optimization via the primal-worst-equals-dual-best principle[END_REF].

The following example presents the Fenchel dual of a general linear programming problem.

Example 1.2.1 (Linear Programming). We consider the standard linear programming problem

inf x c ⊺ x s.t. Ax = b, x ≥ 0. (LP)
The objective function is f (x) ∶= c ⊺ x. Let δ S 1 (x) and δ S 2 (x) denote as the indicator functions of the sets S 1 ∶= {x| Ax = b}, and S 2 ∶= {x| x ≥ 0}, respectively. In this case, we consider the function h(x) defined by

h(x) ∶= f (x) + δ S 1 (x) + δ S 2 (x),
and get the unconstrained problem

inf x h(x) (LP 1 )
The Fenchel's dual is given by

sup w 0 -h * (w 0 ) s.t. w 0 = 0, w 0 ∈ dom(h * ).
Now according to the sum rule for conjugate functions (see Table 1.1), we get

sup y 0 ,y 1 ,y 2 -f * (y 0 ) -δ * S 1 (y 1 ) -δ * S 2 (y 2 ) s.t. y 0 + y 1 + y 2 = 0. Note that f * (y) = 0, dom(f * ) = {c}, δ * S 1 (y) = min z {b ⊺ z | A ⊺ z = y} , δ * S 2 (y) = 0, dom(δ * S 2 ) = {y | y ≤ 0}.
Substitution of the expressions for f * and δ * S i (i = 1, 2) yields the following formulation of the dual problem:

sup z,y 0 ,y 1 ,y 2 -b ⊺ z s.t. y 0 + y 1 + y 2 = 0, y 0 = c, A ⊺ z = y 1 , y 2 ≤ 0.
We can eliminate the vectors y i , which gives

sup z -b ⊺ z s.t. -A ⊺ z ≤ c.
Changing the sign of z leads to the following well-known duality problem for linear optimization

sup z b ⊺ z s.t. A ⊺ z ≤ c.

Robust Optimization

The concept of robust optimization was first introduced by Soyster in 1973, and later developed by El Ghaoui, Ben-Tal, Nemirovski, Bertsimas, and den Hertog [START_REF] Soyster | Convex programming with set-inclusive constraints and applications to inexact linear programming[END_REF][START_REF] Ben-Tal | Robust optimization[END_REF][START_REF] Bertsimas | Robust and adaptive optimization[END_REF].

Mathematically, robust optimization involves defining an uncertainty set that encompasses all potential parameter values that a decision-maker wants to protect against. The goal is to generate solutions that are feasible for all of these values or, in other words, for the worst-case scenario within the uncertainty set.

Static robust optimization assumes that decisions must be made before the value of uncertain parameters is known. Its objective is to find solutions that are robust to changes in the value of these uncertain parameters. In contrast, Adjustable Robust Optimization (ARO)

relaxes this assumption by allowing some decisions to be made before the values of uncertain parameters are known, referred to as "here-and-now" decisions, while other decisions, called "wait-and-see" decisions, can be made after (part of) the uncertain parameter values are revealed [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. Before delving into the mathematical definitions of these two optimization issues, it is important to briefly mention some sources of uncertainty.

There are various factors that contribute to uncertainty in parameters, with some of them being difficult to determine. For instance, measurement errors arise from inaccuracies in physical devices, such as thermometers or incomplete inventory data. On the other hand, forecast errors result from imprecise knowledge of future demand for products, discount rates, or resource prices. Implementation errors occur when there are inaccuracies in the application of devices, such as electrical power or metal component lengths. The reliability of past data, also known as veracity in the context of Big Data, is affected by various factors such as wrongly entered data, missing observations, and other forms of data unreliability.

Even slight deviations from assumed parameter values can have significant effects, leading to infeasible constraints or considerable losses in the objective function value. Therefore, it is essential to employ optimization methods that can effectively account for and accommodate uncertainty, as highlighted in [START_REF] Ben-Tal | Robust optimization[END_REF].

In the rest of this chapter, we recall some definitions for robust optimization. The general form of an uncertain nonlinear optimization problem is as follows

inf x∈X inf y∈Y(x,u) f 0 (x, y, u) (1.1)
where x ∈ R nx is a vector containing non-adjustable (also known as here-and-now or static)

decisions, y ∈ Y(x, u) ⊆ R ny is a vector containing adjustable (also known as wait-and-

Preliminaries see) decisions, Y(x, u) = {y ∈ R ny ∶ f j (x, y, u) ≤ 0, j ∈ [m]}, u ∈ U ⊆ R nu is an uncertain
parameter, U is the uncertainty set, and X ⊆ R nx is a set with additional constraints on x.

The static and adjustable robust counterparts corresponding to uncertain problem (1.1) can be defined as follows.

s.t. sup u∈U f j (x, y, u) ≤ 0, j ∈ [m]. (RC)
Notably, mandating the constraint to hold in the worst-case scenario is tantamount to enforcing a constraint that necessitates the proposition to hold for all feasible values of u within the uncertainty set U, i.e.,

sup u∈U f j (x, y, u) ≤ 0 ⇐⇒ f j (x, y, u) ≤ 0, ∀u ∈ U.
The first form of the constraint implies that it can be reformulated if f j exhibits concavity in its third argument, as optimizing a concave function is considered to be an easy task. When f j is concave in u, computationally tractable reformulations of the robust counterpart can be found [START_REF] Ben-Tal | Deriving robust counterparts of nonlinear uncertain inequalities[END_REF].

Example 1.3.1. We illustrate how parameter uncertainty affects the following problem min

x 1 ,x 2 -2x 1 -x 2 s.t. (2 + u)x 1 + 4x 2 ≤ 12, x 1 , x 2 ≥ 0,
with u as an uncertain parameter. If u = 0, as this is a simple instance, we can easily obtain the optimal solution, which is x 1 = 6, x 2 = 0, resulting in an objective value of -12. We consider u = 0 as nominal value. The corresponding optimal value (solution) is called the nominal optimal value (solution). It is evident that any value of u greater than 0 renders the nominal solution infeasible. In order to acquire a robust solution, we define an uncertainty set for the parameter u, and for now, we will adhere to set U = {u | 0 ≤ u ≤ 1}.

The feasible regions for different values of u within U exhibit overlapping sections. The darkest area in Figure 1.4 represents the robust feasible region, encompassing the solutions that are feasible for all u ∈ U.

In order to obtain a solution that is robust, meaning feasible regardless of the variation in u within the uncertainty set, we must solve the following model:

min x 1 ,x 2 -2x 1 -x 2 s.t. (2 + u)x 1 + 4x 2 ≤ 12, ∀u ∈ U x 1 , x 2 ≥ 0, (1.2)
The model has an infinite number of constraints. Fortunately, we can reformulate this constraint as below to overcome this issue

(2 + u)x 1 + 4x 2 ≤ 12, ∀u ∈ U ⇐⇒ 2x 1 + max u∈U {ux 1 } + 4x 2 ≤ 12, ⇐⇒ 2x 1 + min z {z | z ≥ x 1 , z ≥ 0} + 4x 2 ≤ 12, ⇐⇒ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 2x 1 + z + 4x 2 ≤ 12, z ≥ x 1 , z ≥ 0.
The equivalence in the second line arises from a worst-case perspective. In the third line, we employ strong duality in linear programming. Finally, in the last line, we utilize the fact that the constraint is satisfied for the minimizer z ≥ 0 if and only if there exists an x ≥ 0 that satisfies both 2x 1 + z + 4x 2 ≤ 12 and z ≥ x 1 . It should be noted that in the final statement, z is not necessarily required to be the minimizer. So, by employing duality, the whole optimization problem can be reformulated into an equivalent system of deterministic constraints min

x 1 ,x 2 ,z -2x 1 -x 2 s.t. 2x 1 + z + 4x 2 ≤ 12, x 1 -z ≤ 0, x 1 , x 2 , z ≥ 0.
Therefore, the optimal robust solution is x 1 = 4, x 2 = 0, and z = 4 with optimal objective value is -8. Note that, we know (1.2) is equivalent with

min x 1 ,x 2 -2x 1 -x 2 s.t. 2x 1 + 4x 2 + max u∈U {ux 1 } ≤ 12, x 1 , x 2 ≥ 0.
Another trick to reach a deterministic version is the fact that the worst-case problem is a linear programming problem, and we know that its optimal value lies among the vertices of the uncertainty region. By using vertex enumeration we get min

x 1 ,x 2 -2x 1 -x 2 s.t. 2x 1 + 4x 2 ≤ 12, 2x 1 + 4x 2 + x 1 ≤ 12, x 1 , x 2 ≥ 0.
The optimal robust solution of the last problem is x 1 = 4 and x 2 = 0 with the same optimal value as before.

Assumption 1. In (1.1), we assume that

f j ∶ R nx × R ny × R nu → R, j ∈ [m 0 ] are convex in x,
s.t. f j (x, y, u) ≤ 0, j ∈ [m], (ARC)
where x ∈ R nx is a vector containing static (or here-and-now) decisions, and y ∈ R ny is a vector containing adjustable (or wait-and-see) decisions.

Figure 1.5 provides a visual representation of (ARC). Here-and-now decision x should be chosen without knowledge of the uncertainty and here-and-now decision y can be adjusted according to realizing scenarios {u 1 , u 2 , u 3 , u 4 }.

s.t. ∀u ∈ U ∶ f j (x, y(u), u) ≤ 0, j ∈ [m] (1.3)
serves as an equivalent formulation of (ARC). While both the formulations (ARC) and (1.3) are commonly used in various papers without proof of their equivalence, [START_REF] Takeda | Adjustable robust optimization models for a nonlinear two-period system[END_REF] provides a formal proof establishing their equivalence. The formulation (1.3) is more intuitive when solving the models via decision rule policy.

Definition 1.3.3 (Fixed Recourse Problem, [START_REF] Marandi | When are static and adjustable robust optimization problems with constraint-wise uncertainty equivalent?[END_REF]). Problem (1.1) has fixed-recourse when

f j (x, y, u) = fj (x, u) + ĝj (x, y), j ∈ [m 0 ].
In this thesis, we consider a special case of the above notion defined as follows.

Definition 1.3.4 (Separable Fixed Recourse Problem). We say (1.1) has separable fixedrecourse when

f j (x, y, u) = fj (x, u) + g j (y), j ∈ [m 0 ].

Adjustable Robust Optimization Approximations

There is a wide range of methods available in the literature to tackle ARO problems. In this context, we will emphasize some of the most notable approaches.

• Finite Scenario Approach: This approach involves consideration of a limited subset, drawn from the uncertainty set, comprising a finite number of scenarios. Instead of making decision rules, one can introduce a new single optimization variable to each scenario. It should be noted that this approach does not serve as a complete solution method, as it only ensures feasibility for a portion of scenarios within the uncertainty set. The decisions derived from this approach may be infeasible in practice, and the objective value merely acts as a lower bound for the optimal objective value of the adjustable robust optimization model [START_REF] Bertsimas | Adaptability via sampling[END_REF]. Nevertheless, it remains a valuable approach for evaluating the effectiveness of other solution methods. With careful selection, a small set of scenarios within the subset can provide robust lower bounds. One possible strategy for scenario selection is to consider the set of scenarios that activate the affine adjustable robust model, as introduced in [START_REF] Hadjiyiannis | A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization[END_REF].

• Affine Decision Rules: For linear adjustable robust optimization problems this is an approximate solution technique. The wait-and-see decision can be uniquely adapted to individual scenarios via the use of affine decision rules for the variable y, which is a function of the scenario u ∈ U. The approximation for the wait-and-see decisions can be expressed as follows:

y(u) ∶= z + Zu,
where z ∈ R ny and Z ∈ R ny×nu are the auxiliary variables and jointly optimized alongside the here-and-now decision variable x. While an explicit theorem establishing the optimality gap between solving (ARC) problem with this affine decision rule is yet to be found, empirical evidence indicates its excellent performance, particularly in inventory problems [START_REF] Ben-Tal | Robust optimization[END_REF][START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF][START_REF] Bertsimas | Optimality of affine policies in multistage robust optimization[END_REF].

• Piece-wise Design Policies: Another strategy that can be employed to approach the upper bound for the optimal value of the (ARC) problem is the utilization of piece-wise decision policies. These methods involve partitioning the uncertainty set into smaller subsets and applying decision policies to adjustable (wait-and-see) variables.

In piece-wise constant policies, a distinct copy of the adjustable variable is assigned to each partition. This approach is commonly known as the finite adaptability or K-adaptability approach [START_REF] Hanasusanto | K-adaptability in two-stage robust binary programming[END_REF][START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF]. In piece-wise linear policies, a piece-wise affine decision rule is applied to the adjustable variables associated with each partition. As a result of using this decision strategy, an upper bound approximation to the (ARC) problem is obtained [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF]. These piece-wise design policies allow the decision-making process to be tailored to the different subsets of the uncertainty sets.

The decision rule showcased in Figure 1.6 illustrates how a decision rule can be constructed using piece-wise constant and affine policies. In piece-wise constant policies, the wait-and-see decisions do not follow a continuous pattern but remain constant for each subset of uncertainty. • Partitioning Uncertainty Set: Closely tied to piece-wise design policy, this scheme involves partitioning the uncertainty set into K distinct subsets and assigning decision rules to each partition. This concept was first introduced in [START_REF] Ben-Ameur | Between fully dynamic routing and robust stable routing[END_REF][START_REF] Vayanos | Decision rules for information discovery in multi-stage stochastic programming[END_REF], where a predetermined partitioning approach was initially emphasized. Subsequently, an algorithmic methodology for iterative partition refinement was introduced in [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF][START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF]. These papers provide compelling examples that highlight the strong performance of this method.

Affine Decision Policy

y(u) u ∈ U U Partitioning: Piece-wise Constant y(u) U = 3 ⋃ i=1 U i u ∈ U U 1 U 2 U 3
However, it is important to note that not every refinement guarantees improvement, and convergence may not be achieved for all problem instances. Furthermore, as the partition is further refined, the size of the model increases accordingly.

• Fourier-Motzkin Elimination: This approach provides a solution for addressing linear ARO problems with fixed recourse by employing Fourier-Motzkin elimination (FME) to eliminate adjustable variables. It is important to note that FME can introduce a significant number of additional constraints, potentially growing exponentially.

However, in the context of ARO in the linear case with a small number of adjustable variables, FME has demonstrated its effectiveness in determining the optimal solution by eliminating all adjustable variables [START_REF] Zhen | Adjustable robust optimization via fouriermotzkin elimination[END_REF]. When dealing with larger models, a possible strategy involves eliminating a specific subset of adjustable variables and applying decision rules to the remaining variables.

To conclude the discussion on solution approaches, we will illustrate the concepts we have discussed using the following example.

-x + y(u) ≤ u + 2, ∀u ∈ [0, 1] y(u) ≥ 1. ∀u ∈ [0, 1]
▷ Finite scenario approach: We restrict ourselves to only finite scenarios exclusively, as below

S = { 1 2 , 2 5 } ⊆ [0, 1].
Now, we can assign two individual variables y 1 and y 2 to each considered scenarios. The optimal objective value of the deterministic optimization model below represents a lower bound because we only guarantee feasibility for a strict subset of the uncertainty region.

min x,y 1 ,y 2 3x s.t. x -y 1 ≤ -1 2 , -x + y 1 ≤ 1 2 + 2, y 1 ≥ 1, x -y 2 ≤ -2 5 , -x + y 2 ≤ 2 5 + 2, y 2 ≥ 1.
The optimal value is z * 1 = -21 5 . ▷ Affine decision rule: This approximate approach provides an upper bound on the optimal value of the problem. By considering affine policy y(u) ∶= wu + z, we get the following static robust optimization model

min x,w,z 3x s.t. x -(wu + z) ≤ -u, ∀u ∈ [0, 1] -x + (wu + z) ≤ u + 1, ∀u ∈ [0, 1] (wu + z) ≥ 1. ∀u ∈ [0, 1]
We emphasize that w and z are the static (or here-and-now) decision variables. So, we can use static RO techniques to solve it. By using vertex enumeration, the optimal solutions are w * = 1, z * = 1, and x * = -1 with the optimal value z * 2 = -3. Overall, we get the upper bound and a decision rule:

y(u) = u + 1.
So, the moment we have the value of the uncertain parameter u, we have a value for the adjustable variable y.

▷ Finite adaptability approach: By partitioning the uncertainty set into smaller subsets [0, 1 2 ] and [ 1 2 , 1]. Instead of making decision policies, we apply constant decision rules to adjustable (wait-and-see) variables on each partition, i.e., we can attach two individual optimization variables y 1 and y 2 to each of the partitions. Therefor, we get the following static RO problem

min x,y 1 ,y 2 3x s.t. x -y 1 ≤ -u, ∀u ∈ [0, 1 2 ] -x + y 1 ≤ u + 2, ∀u ∈ [0, 1 2 ] x -y 2 ≤ -u, ∀u ∈ [ 1 2 , 1] -x + y 2 ≤ u + 2, ∀u ∈ [ 1 2 , 1] y 1 , y 2 ≥ 1.
By using the vertex enumeration technique, the optimal value of the last static RO problem is z * 3 = -3. Hitherto, the optimal value of the original problem is in [-21 5 , -3].

▷ Fourier-Motzkin elimination: Note that for given u ∈ [0, 1], in the main problem, we can eliminate adjustable variable y(u), since

xu ≤y(u),

y(u) ≤ u + x + 2,
1 ≤y(u).

So, we have

1 ≤ u + x + 2, ⇐⇒ 0 ≤ x + u + 1.
Note that other constraint in elimination process is u ≥ -1, due to u ∈ [0, 1], which is redundant. Finally, the next static RO problem is an equivalent reformulation of the main ARO problem

min x 3x s.t. 0 ≤ x + u + 1, ∀u ∈ [0, 1].
Obviously, the optimal value is z * = -3.

Uncertainty Sets

In this section, we delve into the classical choices for uncertainty sets in robust optimization.

These uncertainty sets play a crucial role in handling uncertain parameters and ensuring robustness in the optimization process. By carefully defining and selecting the appropriate uncertainty sets, we can proficiently manage uncertainties and make sound decisions that are resilient to adverse conditions.

One of the commonly used uncertainty sets is the box uncertainty set. Within this set, uncertain parameters are presumed to reside within predetermined bounds, creating a hyperrectangle or a box. It is mathematically described as follows

U box = {u ∈ R nu ∶ L ≤ u ≤ U } ,
where L, U ∈ R nu are given parameters. The box uncertainty set provides simplicity and tractability, but it may lead to overly conservative solutions if the actual uncertainty distribution significantly diverges from the assumed bounds.

Another classical option is the ellipsoidal uncertainty set. In contrast to the rigid box set, the ellipsoidal uncertainty set provides greater flexibility in representing uncertainty, allowing

for a wider range of potential parameter values. Formally, it is expressed as follows

U ellipsoid = {u ∈ R nu ∶ ∥Qu∥ 2 ≤ 1} ,
where Q ∈ R nu×nu is given shape matrix. One notable advantage is its capacity to manage conservatism. However, a limitation arises when incorporating nonlinear functions into the model, which can pose challenges.

Polyhedral uncertainty set is another widely favored option in robust optimization. The uncertain parameters are restricted to a polyhedron characterized by a collection of linear inequalities. It is expressed by given parameters D ∈ R r×nu and d ∈ R r , as follows

U polyhedral = {u ∈ R nu ∶ Du ≤ d} .
The polyhedral uncertainty set has the ability to capture intricate uncertainties and offers a versatile framework for modeling uncertainty, rendering it suitable for diverse applications.

Nevertheless, solving optimization problems involving polyhedral uncertainty sets can present computational difficulties, particularly in the case of high-dimensional problems.

In Figure 1.7, classical uncertainty sets are depicted in the two-dimensional space R 2 .

u 1 u 2 U box u 1 u 2 U ellipsoid D i u = d i U polyhedral

Convex Quadratic Problems

Convex quadratic problems and their corresponding duals are important issues in optimization theory. These types of problems involve minimizing a convex quadratic function subject to linear constraints, and their dual problems involve maximizing a concave quadratic function subject to linear constraints. In Table 1.3, we can see a list of different convex quadratic problems and their corresponding Dorn dual problems. Proof of Dorn duality theorems for quadratic programs has been shown using the duality theorem for linear programs [START_REF] Dorn | Duality in quadratic programming[END_REF].

x ⊺ Cx + p ⊺ x s.t. Ax ≥ b, x ≥ 0. max u,v -1 2 u ⊺ Cu + b ⊺ v s.t. A ⊺ v -Cu ≤ p, v ≥ 0. II min x 1 2 x ⊺ Cx + p ⊺ x s.t. Ax ≥ b. max u,v -1 2 u ⊺ Cu + b ⊺ v s.t. A ⊺ v -Cu = p, v ≥ 0. III min x 1 2 x ⊺ Cx + p ⊺ x s.t. Ax = b, x ≥ 0. max u,v -1 2 u ⊺ Cu + b ⊺ v s.t. A ⊺ v -Cu ≤ p. IV min x 1 2 x ⊺ Cx + p ⊺ x s.t. Ax = b. max u,v -1 2 u ⊺ Cu + b ⊺ v s.t. A ⊺ v -Cu = p.
Note: Notice that at the optimal solution, in all the types listed above, u * = x * .

Chapter 2

Linear Adjustable Robust Optimization

George Dantzig:

"... it is interesting to note that the original problem that started my research is still outstanding -namely the problem of planning or scheduling dynamically over time, particularly planning dynamically under uncertainty. If such a problem could be successfully solved it could eventually through better planning contribute to the well-being and stability of the world."

According to static Robust Optimization (RO), all decisions must be made before uncertainty is realized. However, this assumption does not hold true in many real-world problems. For example, a location-transportation problem can be complicated by the fact that while the locations of the production/storage facilities need to be decided as quickly as possible, it is possible to delay deciding how many goods to deliver to each customer until their respective uncertain demands are revealed. The Adjustable Robust Optimization (ARO) problem was introduced to address uncertainty in such problems [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]. The purpose of this chapter is to provide a short review of the literature relating to linear AROs.

Introduction

Consider the following family of uncertain Linear Programming problems:

{min z {c ⊺ z ∶ Az ≤ b}} ζ≡[A,b,c]∈Z (2.1)
the parameters ζ, which consist of A, b, and c, vary within a specified uncertainty set

Z ⊂ R m×n × R m × R n . Mathematically, the robust counterpart of uncertain problem (2.1) is min z ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ sup ζ≡[A,b,c]∈Z c ⊺ z ∶ Az ≤ b, ∀ζ ≡ [A, b, c] ∈ Z ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ . (2.2)
In the static robust optimization approach, all variables represent decisions that need to be made prior to obtaining knowledge about the uncertain actual parameter realization.

The decision-making process in the real world often consists of multiple stages, allowing for certain decisions to be made either after obtaining knowledge of the uncertain data or accurately predicting it. The next example clarifies this.

Example 2.1.1. Consider a factory that produces P (t) units to satisfy demand d t on day

t = 1, 2.
The actual value of d t becomes known only at the end of day t. The decision on how much to produce on day t must be made at the beginning of that day. When choosing P (1),

we have no information about the actual demand, so P (1) represents a static decision. For P (2), we already know the actual demand d 1 , so we can say P (2) is a function of d 1 . In other words, the adjustable variables depend on part of the uncertain data.

All variables that can be influenced by the realizations of the data are referred to as adjustable, while the remaining variables are categorized as static. This leads us to partition the vector z of variables in (2.1) as z = (x ⊺ , y ⊺ ) ⊺ , where the sub-vector x represents the static variables and y represents the adjustable variables.

By making a clear distinction between the static and adjustable variables, we can express problem (2.1) in an equivalent form as follows:

min (τ,x),y ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ ∶ c ⊺ ⎛ ⎜ ⎜ ⎜ ⎝ x y ⎞ ⎟ ⎟ ⎟ ⎠ ≤ τ, U x + V y ≤ b ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ [U,V,b,c]∈Z (2.3)
and treat (τ, x) as the static part of the solution. In the above reformulation (2.1), the objective function remains unaffected by both the uncertain data and the adjustable variables y. From this point onwards, without loss of generality, we can assume that an uncertain LP problem can be rewritten as follows: [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]). The adjustable robust counterpart of the uncertain problem LP Z is defined as

LP Z = {min x,y c ⊺ x ∶ U x + V y ≤ b} ζ=[U,V,b]∈Z . (2.4) Definition 2.1.1 ([
min x {c ⊺ x ∶ ∀(ζ = [U, V, b] ∈ Z)∃y ∶ U x + V y ≤ b} . (ARC-LP)
In contrast, the robust counterpart of LP Z is:

min x {c ⊺ x ∶ ∃y∀(ζ = [U, V, b] ∈ Z) ∶ U x + V y ≤ b} . (RC-LP)
The greater flexibility of the (ARC-LP) compared to the (RC-LP) is evident, as former has a larger robust feasible set that allows for a better optimal value while still adhering to all potential constraint realizations. The distinction between (ARC-LP) and (RC-LP) can be remarkably substantial, as illustrated in the two subsequent examples.

Example 2.1.2 (from [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]). Let us consider an uncertain LP problem with a single equality constraint:

αx + βy = 1,
where the uncertain data (α, β) can take values in the uncertainty set

Z = {(α, β) | α ∈ [ 1 2 , 1] , β ∈ [ 1 2 , 1]} .
Then the feasible set of (RC-LP) is {x | ∃y∀(α, β) ∈ Z ∶ αx + βy = 1} = ∅. This happens because in particular for α = 1, for each β ∈ [ 1 2 , 1] the constraint x + βy = 1 implies x = 1, y = 0 as the unique solution. And then for each α ∈ [ 1 2 , 1] , α(1) + β(0) = 1 does not hold. At the same time, the feasible set of the (ARC) is {x | ∀(α, β) ∈ Z ∃y ∶ αx + βy = 1} = R, since for any fixed x, the constraint can be satisfied by taking y = 1-αx β .

Example 2.1.3 (from [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF]). Consider the following uncertain LP:

min x,y {-x ∶ (1 -2ξ)x + y ≥ 0, ξx -y ≥ 0, x ≤ 1} 0≤ξ≤1
Note that here the uncertainty ξ influences both the first and second constraints. It can be easily seen that the optimal value of the robust counterpart of this problem is

min x {-x | ∃y∀(ξ ∈ [0, 1]) ∶ (1 -2ξ)x + y ≥ 0, ξx -y ≥ 0, x ≤ 1} = 0,
achieved at the unique solution x = 0 and y = 0. The optimal value of (ARC) is

min x {-x | ∀(ξ ∈ [0, 1])∃y ∶ (1 -2ξ)x + y ≥ 0, ξx -y ≥ 0, x ≤ 1} = -1,
where for any x ≤ 1 we can take y = ξ x to obtain feasibility.

Approximation of Linear ARO

In the rest of this short chapter will cover some of the methods and approaches that have been suggested in the literature to handle linear ARO problems. Several of these approaches have been reviewed in the previous chapter. Now, we will be reviewing a wide variety of non-decision policy approaches to solving linear ARO, which are presented here.

Dual Formulations

Along the lines of [START_REF] Bertsimas | Duality in two-stage adaptive linear optimization: Faster computation and stronger bounds[END_REF], consider the following ARO problem:

min x∈X c ⊺ x s.t. ∀ζ ∈ U, ∃y ≥ 0 ∶ Ax + By ≥ Rζ + r, (2.5)
where X ⊂ R n is a set with additional constraints on the here-and-now decisions. The wait-and-see variable y has dimension k and we denote the number of constraints in the

model by m. So, B ∈ R m×k . Furthermore, we have c ∈ R n , A ∈ R m×n , R ∈ R m×L and r ∈ R m .
The matrix R is chosen constant in this model, so the model only has uncertainty on the right-hand side. Furthermore,

U ∶= {ζ ∈ R L | Dζ ≤ d, ζ ≥ 0} is the polyhedral uncertainty set.
The main contributions of this part come from the following dual formulation of (2.5).

min x∈X c ⊺ x s.t. ∀w ∈ V, ∃λ ≥ 0 ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ w ⊺ (Ax -r) -d ⊺ λ ≥ 0, D ⊺ λ ≥ R ⊺ w, (2.6)
where

V = {w ≥ 0 ∶ B ⊺ w ≤ 0, e ⊺ w = 1}.
The above formulation is obtained by dual of (2.5) over y, and then over ζ, and exploits the scalar multiplicity of the adjustable dual variable λ.

The dual formulation (2.6) is again an adjustable linear optimization model. Therefore, all existing solution approaches for adjustable models can be used to solve or approximate the dual formulation. The new dual model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. The relation between the optimal primal affine policy can be directly obtained from the optimal affine policy in the dual formulation. The dual formulation can reduce computational time to solve the original problem.

Column-and-Constraint Generation

The approach of column-and-constraint generation was initially presented in [START_REF] Zeng | Solving two-stage robust optimization problems using a column-and-constraint generation method[END_REF] to address the challenges of solving adjustable robust linear optimization problems.

Consider the following linear adjustable robust problem

min x∈X max u∈U min y a ⊺ x + b ⊺ y s.t. Ax + By + Cu ≥ c, y ≥ 0. (2.7) where a ∈ R n , b ∈ R m , c ∈ R r , A ∈ R r×n , B ∈ R r×m , C ∈ R r×l are the problem's parameters and U is a polytope of the form {u ∈ R l ∶ Du ≤ d, u ≥ 0} such that D ∈ R q×l and d ∈ R q .
In general, the column-and-constraint generation algorithm is used to find an optimal solution to linearly adjustable problems. Based on a finite number of uncertainty realizations, it finds both a lower bound on the objective value and the corresponding here-and-now decision x, as well as an upper bound on the wait-and-see objective if x is known.

Before discussing the full algorithm, here we shortly present the optimization problem that will be used to obtain the lower bound in the first part of the algorithm. Given x, for any V = {u 1 , . . . , u k } ⊆ U , a lower bound for the second-stage cost of (2.7) can be obtained using the following optimization problem

Z(x, V ) = min θ,{y s } 1≤s≤k a ⊺ x + θ s.t. b ⊺ y s ≤ θ, s = 1, . . . , k Ax + By s + Cu s ≥ c, s = 1, . . . , k y s ≥ 0, s = 1, . . . , k.
Notice that given a here-and-now decision x and an uncertainty parameter u, the second-stage cost is given by

Z(x, {u}) = min y b ⊺ y s.t. Ax + By + Cu ≥ c, y ≥ 0.
Given a here-and-now decision x, an upper bound on the second-stage cost is given by

Z(x) = max u∈U Z(x, {u}) ≡ a ⊺ x + max u∈U min y b ⊺ y s.t. Ax + By + Cu ≥ c, y ≥ 0,
and the uncertainty realization that results in this cost is given by

u(x) ∈ arg max u∈U Z(x, {u}).
Given these notations, the column-and-constraint generation algorithm is presented below.

Column-and-Constraint Generation Method

Input:

X , A, B, C, a, b, c, D, d, ϵ > 0, u 0 ∈ U Initialization: U B 0 = ∞, LB 0 = -∞, V 0 = {u 0 } , k = 0 Repeat -Update k ← k + 1 -Compute x k = argmin x∈X Z (x, V k-1
) and the corresponding lower bound value

LB k = Z (x k , V k-1 ) -Compute u k = u (x k ) and the corresponding upper bound U B k = Z (x k ) ≡ Z (x k , {u k }). -Update V k ← V k-1 ⋃ {u k } Until: U B k -LB k max(min(|LB k |,|U B k |),1) < ϵ. Return: x k , U B k .
This approach sometimes, and in some applications often, produces infeasible here-and-now solutions, even though the problem is feasible. However, this concern was successfully addressed and resolved in a later work, documented in [START_REF] Bertsimas | A scalable algorithm for two-stage adaptive linear optimization[END_REF].

Copositive Approach

It is possible to reformulate the linear adjustable problem as a copositive optimization problem, which in turn leads to tractable, semi-definite-based approximations at least as good as the affine policy under some assumptions [START_REF] Xu | A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides[END_REF].

In this section, we consider a robust linear optimization problem with uncertainty on the right-hand side to review this approximation as follows:

min x∈X max u∈U min y c ⊺ x + d ⊺ y s.t. Ax + By ≥ F u, (2.8) where A ∈ R m×n 1 , B ∈ R m×n 2 , c ∈ R n 1 , d ∈ R n 2 , F ∈ R m×k and X ⊆ R n 1 is
a convex and closed set containing the here-and-know decision x. The nonempty full-dimensional uncertainty set

U ⊆ R k is convex and compact. Within (2.8), define π(x) ∶= max u∈U min y∈R n 2 {d ⊺ y| By ≥ F u -Ax} .
The dual of inner minimization is

max w∈W (F u -Ax) ⊺ w,
where W ∶= {w ≥ 0| B ⊺ w = d}. Hence, strong duality for linear programming implies

π(x) = max (u,w)∈U ×W (F u -Ax) ⊺ w.
In [START_REF] Xu | A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides[END_REF] it has been proved that the copositive representation of the above is

π(x) = max tr ((F -Axe ⊺ 1 ) ⊺ Z 21 ) s.t. diag (EZE ⊺ ) = 0, Z ∈ CPP ( Û × R m + ) , tr ((g 1 g ⊺ 1 ) ⊺ Z) = 1, (2.9)
where Û is the full-dimensional homogenization cone of U, CP P (⋅) denote completely positive cone, E ∈ R n 2 ×(k+m) is a matrix with structure E = (-de ⊺ 1 B ⊺ ), e 1 ∈ R k and g 1 ∈ R k+m are the first unit vector, and Z ∈ R (k+m)×(k+m) is a symmetric matrix with the block structure

Z = ⎛ ⎜ ⎜ ⎜ ⎝ Z 11 Z ⊺ 21 Z 21 Z 22 ⎞ ⎟ ⎟ ⎟ ⎠
. Then applying standard conic duality theory on (2.9) implies copositive relation of original ARO. See [START_REF] Xu | A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides[END_REF] for more details.

Conclusion

We conclude this chapter with the last sentence of the survey paper [START_REF] Yanıkoğlu | A survey of adjustable robust optimization[END_REF]: "Finally, adjustable robust nonlinear optimization appears to be very difficult, and since there is almost no literature about this topic, much more research is needed."

Chapter 3

A Dual-Based Cutting Plane Algorithm for Nonlinear Adjustable Robust Optimization Werner Heisenberg: "Uncertainty is NOT I don't know. It is I can't know. I am uncertain does not mean I could be certain."

Introduction

Most studies in Adjustable Robust Optimization (ARO) problems are focusing on linear and integer-linear [START_REF] Arslan | Decomposition-based approaches for a class of two-stage robust binary optimization problems[END_REF][START_REF] Bertsimas | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization[END_REF][START_REF] Hashemi Doulabi | Exploiting the structure of two-stage robust optimization models with exponential scenarios[END_REF]; for more additional details, see the survey paper [START_REF] Yanıkoğlu | A survey of adjustable robust optimization[END_REF]. There are only a few papers devoted to the nonlinear case due to its theoretical and computational challenges. In [START_REF] Takeda | Adjustable robust optimization models for a nonlinear two-period system[END_REF], the authors considered a nonlinear ARO problem with a polytope uncertainty set and proposed a method to solve such problems under some quasi-convexity conditions. ARO models with second-order cone constraints and ellipsoidal uncertainty sets are considered in [START_REF] Boni | Adjustable robust counterpart of conic quadratic problems[END_REF], where the authors show that applying the affine decision rule would result in a semi-definite optimization problem. In [START_REF] De Ruiter | Dual approach for two-stage robust nonlinear optimization[END_REF], the authors considered a nonlinear ARO model with linear uncertainty (the functions are linear in the uncertain parameters and the uncertainty set is a polyhedron), and derive an equivalent ARO problem, which is linear in the wait-and-see decisions.

In this chapter, we show how to use duality to reformulation a general nonlinear ARO problem and solve it. More specifically, the main contribution of our work can be summarized as follows:

• First, we consider a general nonlinear adjustable robust optimization problem. Applying Fenchel's duality and dualizing over the continuous wait-and-see decisions, we obtain an equivalent static robust optimization reformulation (dual reformulation). Then, we provide conditions under which the dual reformulation is convex on decision variables.

• Second, we show under some conditions that a convex relaxation of the dual reformulation is equivalent to approximating the ARO problem using constant decision rule.

• Finally, we design an algorithm based on the dual reformulation. The algorithm consists of two main phases: In the first phase, we use an alternating method exploiting the structure of the dual reformulation. We show under which conditions, the alternating method converges to a local worst-case scenario within the uncertainty set. In the second phase, we use finite-scenario approach, given the obtained scenarios in the first phase, to find a solution. Given this solution, we find new local worst-case scenarios and repeat this two-phase procedure until satisfying a stopping criterion. Using this algorithm, we have a lower bound on the original problem and obtain a locally robust solution (The term "local" is used as we obtain a robust solution taking a part of the uncertainty set into account). We further improve the lower bound by introducing new cuts. Our computational results show that our algorithm can provide a locally robust solution with an acceptable optimality gap.

The main results of this chapter have been appeared in The rest of the chapter is organized as follows. We reformulate a general nonlinear adjustable robust problem as a nonlinear static robust counterpart using Fenchel's duality in Section 3.2. In Section 3.3, we apply a convex relaxation technique on the dual reformulation to obtain an upper bound and show the relationship between the corresponding static robust counterpart of the ARO problem and this relaxation. Finally, we propose a new algorithm in Section 3.4 to construct a lower bound and obtain a locally robust solution. Our numerical results are presented in Section 3.5.

Dual Reformulation

In this section, we derive the dual formulation of (ARC). In the next theorem, we show how Fenchel duality is used for this goal.

Theorem 2. Let Assumption 1 hold. Also, in (ARC) let us assume that

∀(x ∈ X , u ∈ U), ∃y ∶ f j (x, y, u) < 0, j ∈ [m]. (3.1)
Then, (ARC) is equivalent to the nonlinear static robust counterpart

inf x∈X ,τ τ s.t. -f * 2 0 (x, w 0 , u) - m ∑ j=1 λ j f * 2 j (x, w j λ j , u) ≤ τ, ∀ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 u ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ∈ Z, (3.2)
where

Z = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 u ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ∈ R m+ny(m+1)+nu λ ≥ 0, u ∈ U, m ∑ j=0 w j = 0, w 0 ∈ dom (f * 2 0 (x, ⋅, u)) , w j λ j ∈ dom (f * 2 j (x, ⋅, u)) , j ∈ [m] ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ .
Proof. In (ARC), we consider the inner minimization problem over y for a given x ∈ X and u ∈ U. Because of (3.1) and Assumption 1, we know for the given x ∈ X and u ∈ U, the inner minimization is Slater regular. Therefore, we can apply Fenchel's duality (Definition 1.2.1), and rewrite (ARC) as follows:

inf x∈X sup u∈U sup λ,w j -f * 2 0 (x, w 0 , u) - m ∑ j=1 λ j f * 2 j (x, w j λ j , u) s.t. m ∑ j=0 w j = 0, λ ≥ 0, w 0 ∈ dom (f * 2 0 (x, ⋅, u)) , w j λ j ∈ dom (f * 2 j (x, ⋅, u)) , j ∈ [m].
Therefore, (ARC) can be reformulated as

inf x∈X sup u∈U ,λ,w j -f * 2 0 (x, w 0 , u) - m ∑ j=1 λ j f * 2 j (x, w j λ j , u) s.t. m ∑ j=0 w j = 0, λ ≥ 0, w 0 ∈ dom (f * 2 0 (x, ⋅, u)) , w j λ j ∈ dom (f * 2 j (x, ⋅, u)) , j ∈ [m].
Using the definition of Z and epigraph reformulation, we may rewrite problem (ARC) as (3.2), which completes the proof.

The above theorem shows that a nonlinear adjustable robust optimization can be reformulated as a nonlinear static robust optimization under a Slater condition. In the equivalent dual reformulation (3.2), the uncertain parameters include the dual multipliers (i.e., λ, {w j } m j=0 ), in addition to the original uncertain parameter u.

The conjugate functions and their domains can be easily computed for a wide range of convex functions; see, e.g., [101, Table E

.1].
In the proof of the above theorem, we did not use the convexity of f j functions on x and their concavity on u. However, we usually take convex functions on decision variables and concave functions on uncertain parameters to get tractable models. The benefit of the dual reformulation obtained in Theorem 2 is that we can get upper and lower bounds for the optimal objective value of the original model (ARC). Later, in Sections 3.3 and 3.4, we explain how to achieve these goals.

In the following corollary, we derive the formulation of the dual problem for cases where

f j (x, y, u), j ∈ [m 0 ] are separable.
s.t. fj (x) + h j (u) + g j (y) ≤ 0, j ∈ [m]. (3.3)
Let g j be proper, convex, and closed in y. Assume that there exists some y such that

g j (y) < -sup x∈X fj (x) -sup u∈U h j (u), j ∈ [m].
Then, the nonlinear ARC (3.3) is equivalent to the following static RO problem

inf x∈X ,τ τ s.t. m ∑ j=0 λ j fj (x) + m ∑ j=0 λ j h j (u) - m ∑ j=0 λ j g j * ( w j λ j ) ≤ τ, ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 u ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ∈ P,
where

P = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 u ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ u ∈ U, m ∑ j=0 w j = 0, λ 0 = 1, λ j ≥ 0, w j λ j ∈ dom(g * j ), j ∈ [m 0 ] ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ .
Proof. By setting f j (x, y, u) ∶= fj (x) + h j (u) + g j (y), for λ j > 0 we have

λ j f j * 2 (x, w j λ j , u) = λ j sup y {( w j λ j ) ⊺ y -f j (x, y, u)} = sup y {(w j ) ⊺ y -λ j ( fj (x) + h j (u) + g j (y))} = sup y {(w j ) ⊺ y -λ j fj (x) -λ j h j (u) -λ j g j (y)} = -λ j fj (x) -λ j h j (u) + sup y {(w j ) ⊺ y -λ j g j (y)} = -λ j fj (x) -λ j h j (u) + λ j sup y {( w j λ j ) ⊺ y -g j (y)} = -λ j fj (x) -λ j h j (u) + λ j g j * ( w j λ j ).
Furthermore, for λ j = 0 we have

λ j f j * 2 (x, w j λ j , u) = δ * dom((f j * 2 ) * 2 (x,⋅,u)) (w j ) = δ * dom(f j (x,⋅,u)) (w j ) = δ * dom(g j ) (w j ) = δ * dom(g j * ) * (w j ),
where the first equality follows from the definition of the partial convex perspective, the second equality holds because of the closedness and convexity of f j (x, ⋅, u). Therefore, Theorem 2 and the above equivalences concludes the corollary.

A natural question is whether (ARC) (or its equivalent form (3.2)) is convex with respect to x. In other words, for a given optimal decision rule and a worst-case scenario, whether optimization on x is convex. The following example shows that the answer to this question is negative in general. f 0 (x, y, u) = x 2 uy, and f 1 (x, y, u) = -x + 1 2 y 2u. The partial conjugate of f 0 and f 1 with respect to their second argument are given by

f * 2 0 (x, w 0 , u) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0, w 0 = x 2 u, ∞, w 0 ≠ x 2 u, f * 2 1 (x, w 1 , u) = x + (w 1 ) 2 2 + u.
Thus, the dual reformulation of (ARC) for this example is

inf x∈X sup u∈U ,λ,w 0 ,w 1 -f * 2 0 (x, w 0 , u) -λf * 2 1 (x, w 1 λ , u) s.t. w 0 + w 1 = 0, λ ≥ 0, w 0 ∈ dom (f * 2 0 (x, ⋅, u)) , w 1 λ ∈ dom (f * 2 1 (x, ⋅, u)) .
(3.4)

For fixed x and u, if λ = 0, then

-λf * 2 1 (x, w 1 λ , u) = -δ * dom((f j * 2 ) * 2 (x,⋅,u)) (w 1 ) = -δ * dom(f j (x,⋅,u)) (w 1 ) = -δ * R (w 1 ) = -δ {0} (w 1 ). Thus, -λf * 2 1 (x, w 1 λ , u) = -∞ when w 1 ≠ 0. Furthermore, w 1 = 0 is infeasible, due to w 1 = -w 0 = -x 2 u ≠ 0. So we can ignore λ = 0. So, (3.4) is equivalent to inf x∈X sup u∈U sup λ,w 0 ,w 1 - (w 1 ) 2 2λ -λ(x + u) s.t. w 0 + w 1 = 0, λ > 0, w 0 = x 2 u. (3.5)
Given x and u, the inner suprimum can be written as

sup λ>0 -x 4 u 2 2λ -λ(x + u), (3.6)
as we know x ≥ 1 and u ≥ 1. Moreover, the objective function is concave in λ. So, the supremum happens at λ = √

x 4 u 2 2(x+u) . Hence, (3.5) is equivalent to inf x∈X sup u∈U - √ 2x 2 u √ x + u. Given x ≥ 1, the inner suprimum is sup {- √ 2x 2 u √ x + u| u ∈ [1, 2]}, whose objective function
is decreasing on the given interval [START_REF] Ahmadi | On the complexity of finding a local minimizer of a quadratic function over a polytope[END_REF][START_REF] Andrianova | One algorithm for branch and bound method for solving concave optimization problem[END_REF]. Therefore, u = 1 is the worst-case scenario, and so

sup u∈U - √ 2x 2 u √ x + u = - √ 2x 2 √ x + 1.
Finally, we get

inf x {- √ 2x 2 √ x + 1| x ∈ X }, which is a non-convex problem. Remark 3.2.1. Note that f j * 2 (x, w j , u) = sup y {(w j ) ⊺ y -f j (x, y, u)} implies -f j * 2 (x, w j , u) = inf y {-(w j ) ⊺ y + f j (x, y, u)} .
Indeed, the function K w j ,y,u (x) ∶= -(w j ) ⊺ y + f j (x, y, u) is convex on x for any w j , y, u, but the inf operator breaks down the convexity. In other words, the conjugate function

-f j * 2 (x, w j , u) is not convex in x.
Therefore, based on the dual formulation, we see if the conjugate function -f j * 2 (x, w j , u) is convex in x, then the problem is a convex optimization problem in x. In the next theorem, we show this for separable fixed-recourse problems.

Theorem 3. Under the assumption of Theorem 2, if (ARC) is separable fixed-recourse, then the dual reformulation of (ARC) is convex in x.

Proof. Since f j (x, y, u) = fj (x, u) + g j (y) for all j ∈ [m 0 ], according to Theorem 2, (ARC) is equivalent to

inf x∈X sup u∈U ,λ j ,w j m ∑ j=0 λ j fj (x, u) - m ∑ j=0 λ j g j * ( w j λ j ) s.t. m ∑ j=0 w j = 0, λ 0 = 1, λ j ≥ 0, j ∈ [m], w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m]. (3.7)
Note that fj (x, u) is convex on x for each j ∈ [m 0 ]. By denoting

F u,λ,w j (x) ∶= m ∑ j=0 λ j fj (x, u) - m ∑ j=0 λ j g j * ( w j λ j ), and F(x) ∶= sup u,λ,w j F u,λ,w j (x), which are convex on x, problem (3.7) is equivalent to inf x∈X F(x) which is a convex optimization problem.
Considering Theorem 3, we focus on separable fixed-recourse case in the rest of the chapter.

On Upper Bound Calculation

In this section, we assume that the non-empty uncertainty set U has the following structure:

U ∶= {u ∈ R nu | c i (u) ≤ 0, i ∈ [t]} ,
where the function

c i ∶ R nu → R is proper, closed, and convex for each i ∈ [t].
In the next theorem, we show how using perspective functions result in an upper bound for (3.7).

Theorem 4. For any fixed x ∈ X , let fj (x, u) be proper and concave in u for each j ∈ [m 0 ].

Then, sup u,λ j ,w j ,θ j m ∑ j=0 λ j fj (x, θ j λ j ) - m ∑ j=0 λ j g j * ( w j λ j ) s.t. m ∑ j=0 w j = 0, λ 0 = 1, θ 0 = u, λ j ≥ 0, j ∈ [m], w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m], λ j c i ( θ j λ j ) ≤ 0, j ∈ [m 0 ], i ∈ [t], (3.8)
provides an upper bound on the optimal value of

sup u,λ j ,w j m ∑ j=0 λ j fj (x, u) - m ∑ j=0 λ j g j * ( w j λ j ) s.t. m ∑ j=0 w j = 0, λ 0 = 1, λ j ≥ 0, j ∈ [m], w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m], c i (u) ≤ 0, i ∈ [t]. (3.9)
Proof. We show that any feasible solution to (3.9) corresponds to a feasible solution to (3.8) with the same objective value. For this goal, for any solution (u, λ, {w j } m j=0 ), define θ j ∶= λ j u for each j ∈ [m]. We prove that (u, λ, {w j } m j=0 , {θ j } m j=1 ) is a feasible solution to (3.8). For each j ∈ [m] and i ∈ [t] with λ j > 0 obviously we have λ j c i ( θ j λ j ) ≤ 0. If λ j = 0 for some j ∈ [m], we get θ j = 0 and

0c i (0/0) = δ * dom(c * i ) (0) = 0, ∀i ∈ [t],
where the first equality follows from the definition of the convex perspective, and the second equality holds because the conjugate function of a proper convex function is also proper (from [9, Theorem 4.5]), and so dom(c * i ) ≠ ∅. All other constraints of (3.8) are clearly satisfied. Now, we show that the objective value at (u, λ, {w j } m j=0 ) in (3.9) equals to that value at (u, λ, {w j } m j=0 , {θ j } m j=1 ) in (3.8). To this end, it is sufficient to show that

λ j fj (x, θ j λ j ) = λ j fj (x, u) for all j ∈ [m].
It is trivial for the case λ j > 0. If λ j = 0 for some j ∈ [m], then θ j = 0, and so

0 fj (x, 0/0) = -δ * dom((-fj ) * 2 (x,.)) (0) = 0 = 0 fj (x, u),
where the first equality follows from the definition of the partial concave perspective, and the second equality holds because (for any x) the partial conjugate (-fj ) * 2 (x, .) of proper convex functionfj (x, .) is also proper, leading to dom ((-fj ) * 2 (x, .)) ≠ ∅.

Problem (3.9) is not a convex programming in general, while problem (3.8) is. More specifically, by lifting the problem to a higher dimension and using the perspective functions, we obtain a concave relaxation on λ j , w j , θ j . This approach has been recently used in the literature of nonlinear optimization for other purposes [START_REF] Combettes | Perspective functions: Properties, constructions, and examples, Set-Valued and Variational Analysis[END_REF][START_REF] Lee | Gaining or losing perspective[END_REF][START_REF] Wei | Ideal formulations for constrained convex optimization problems with indicator variables[END_REF]]. In the next example, we

show that this relaxation may not be tight.

Example 3.3.1. Let x ∈ X . Consider an instance of problem (3.9) with t = m = 1, n u = 1, n y = 2, f0 (x, u) = -u 2 , f1 (x, u) = 1 u , c 1 (u) = u + 1, g 0 (y) = y 1 , and g 1 (y) = 1 2 y ⊺ y + y 2 . Set p 0 ∶= (1, 0) ⊺ , p 1 ∶= (0, 1) ⊺ .
The conjugates of g 0 and g 1 are given by

g * 0 (w 0 ) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 0, w 0 = p 0 , ∞, w 0 ≠ p 0 , g * 1 (w 1 ) = 1 2 (w 1 -p 1 ) ⊺ (w 1 -p 1 ) .
Hence, problem (3.9) in this example reads as

sup u,λ 1 ,w 0 ,w 1 f0 (x, u) + λ 1 f1 (x, u) -g * 0 (w 0 ) -λ 1 g * 1 ( w 1 λ 1 ) s.t. λ 1 ≥ 0, w 0 + w 1 = 0, u ≤ -1, w 0 = p 0 .
If λ 1 = 0 in some feasible solution of the above problem, then

-λ 1 g * 1 ( w 1 λ 1 ) = -δ * dom(g 1 ) (w 1 ) = -δ {0} (w 1 ). So, -λ 1 g * 1 ( w 1 λ 1 ) = -∞ when w 1 ≠ 0. Furthermore, w 1 = 0 is infeasible, due to w 1 = -w 0 = -p 0 = (-1, 0) ⊺ .
Hence, we can ignore λ 1 = 0. Now, due to w 0 = p 0 and w 0 + w 1 = 0, the last problem can be rewritten as

z 1 ∶= sup u,λ 1 -u 2 + λ 1 u -1 2 (λ 1 + 1 λ 1 ) s.t. λ 1 > 0, u ≤ -1.
Let us denote the objective function of the last problem by

J(u, λ 1 ) = -u 2 + λ 1 u -1 2 (λ 1 + 1 λ 1 ) .
This function is bounded above over the feasible set

K = {(u, λ 1 )| u ≤ -1, λ 1 > 0}.
To obtain z 1 , first we examine the points for which the gradient of J(⋅, ⋅) vanishes. We have

∇J(u, λ 1 ) = (-2u -λ 1 u 2 , 1 u -1 2 + 1 2λ 2 1 ) ⊺ .
Thus, ∇J(u, λ 1 ) = 0 implies λ 1 = -2u 3 , and -4u 6 + 8u 5 + 1 = 0. On the other hand, u ≤ -1

(feasibility) leads -4u 6 + 8u 5 + 1 < 0. So, the maximizers of J(u, λ 1 ) are not in the interior of the feasible set K. They are on the boundary of K, i.e., λ 1 = 0 or u = -1. As λ 1 > 0, we continue with u = -1, and we have sup

λ 1 >0 -1 -λ 1 -1 2 (λ 1 + 1 λ 1 ) .
The optimal solution of the above problem occurs at

λ 1 = 1 √ 3
, and hence

z 1 = -1 - √ 3.
Analogously, problem (3.8) in this example is

z 2 ∶= sup u,λ 1 ,θ 1 -u 2 + (λ 1 ) 2 θ 1 -1 2 (λ 1 + 1 λ 1 ) s.t. λ 1 > 0, u ≤ -1, θ 1 ≤ -λ 1 .
It is not difficult to see that -2 is an upper bound for the objective function of the above problem on its feasible region. Furthermore, the objective value at the feasible sequence

{u n = -1, (λ 1 ) n = 1, (θ 1 ) n = -n} n≥1 equals to -2 -1 n which goes to -2 as n → +∞. This implies z 2 = -2. Therefore, z 1 = -1 - √ 3 < -2 = z 2 .
In Theorem 4, x ∈ X is fixed and arbitrary. Now, by taking minimum over all x ∈ X in (3.9) and (3.8), we obtain an upper bound for the separable fixed-recourse version of the dual reformulation of (ARC) as follow:

inf x∈X sup u,λ j ,w j ,θ j m ∑ j=0 λ j fj (x, θ j λ j ) - m ∑ j=0 λ j g j * ( w j λ j ) s.t. m ∑ j=0 w j = 0, λ 0 = 1, θ 0 = u, λ j ≥ 0, j ∈ [m], w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m], λ j c i ( θ j λ j ) ≤ 0, j ∈ [m 0 ], i ∈ [t].
(PERS)

We call this problem (PERS) as it is obtained by using a perspectification approach corresponding to problem (3.7). Moreover, (PERS) is a convex-concave programming, while it is not the case for (3.7).

Problem (PERS) can be seen as a relaxation of the dual reformulation of (ARC) when it has fixed-recourse. So, it is important to know the interpretation of such a relaxation for the primal problem, i.e., (ARC). The next theorem shows that (PERS) is actually equivalent to the static robust counterpart (RC) in the separable fixed-recourse case when the uncertainty set is compact.

Theorem 5. Consider (RC) with separable fixed-recourse as follows:

inf x∈X ,y sup u∈U f0 (x, u) + g 0 (y) s.t. sup u∈U fj (x, u) + g j (y) ≤ 0, j ∈ [m].
(3.10)

Suppose that the uncertainty set U is compact, fj is proper concave in u, and g j is closed convex and real-valued, for each j

∈ [m 0 ]. If ∀x ∈ X ∃y such that sup u∈U fj (x, u) + g j (y) < 0, j ∈ [m],
then (PERS) and static robust counterpart (3.10) are equivalent.

Proof. Without loss of generality, since U is compact, we assume that there exists some i,

s.t. F j (x) + g j (y) ≤ 0, j ∈ [m]. (3.11)
By applying the Fenchel's duality over y, (3.11) is equivalent to

inf x∈X sup λ j ,w j m ∑ j=0 λ j F j (x) - m ∑ j=0 λ j g j * ( w j λ j ) s.t. m ∑ j=0 w j = 0, λ 0 = 1, λ j ≥ 0, j ∈ [m], w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m].
(RC-1)

Now, we show that, for a given x ∈ X , the inner suprimums of (RC-1) and (PERS) have the same optimal value. To prove this claim, let x ∈ X be fixed. Let (u, λ, {w j } m j=0 , {θ j } m j=1 ) be a feasible solution for the inner suprimum in (PERS).

If λ j > 0, then

λ j c i ( θ j λ j ) ≤ 0, ∀i ∈ [t] ⇒ c i ( θ j λ j ) ≤ 0, ∀i ∈ [t] ⇒ θ j λ j ∈ U ⇒ fj (x, θ j λ j ) ≤ F j (x) ⇒ λ j fj (x, θ j λ j ) ≤ λ j F j (x).
If λ j = 0, then θ j = 0. To prove this, as c i (u) = ∥u∥ 2ρ for some ρ > 0 and some i ∈ [t], by taking λ j = 0 into account, we have

0 ≥ λ j c i ( θ j λ j ) = δ * dom(c * i ) (θ j ) = sup ∥γ∥ 2 ≤1 {γ ⊺ θ j } = ∥θ j ∥ 2 ≥ 0.
This implies θ j = 0. Hence, in this case

λ j fj (x, θ j λ j ) = -δ * dom((-f j ) * 2 (x,.)) (0) = 0 = λ j F j (x),
where first equality comes from the definition of the partial concave perspective, and the second equality holds as dom ((-f k ) * 2 (x, .)) ≠ ∅. So,

λ j fj (x, θ j λ j ) ≤ λ j F j (x), j ∈ [m 0 ].
Summing over j yields ∑ j λ j fj (x, θ j λ j ) ≤ ∑ j λ j F j (x). Thus,

m ∑ j=0 λ j fj (x, θ j λ j ) - m ∑ j=0 λ j g j * ( w j λ j ) ≤ m ∑ j=0 λ j F j (x) - m ∑ j=0 λ j g j * ( w j λ j ).
Therefore, the optimal value of the objective function of the inner suprimum in (PERS) is less than or equal to that in (RC-1).

Conversely, let ( λ, { wj } m j=0 ) be a feasible solution for inner suprimum of (RC-1). By choosing

ūj ∈ argmax{ fj (x, u)| u ∈ U}, j ∈ [m 0 ],
and setting

θj = ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ λj ūj , λ j > 0, 0, λ j = 0, j ∈ [m],
and then setting θ0 = ū0 , the vector (ū 0 , λ, { wj } m j=0 , { θj } m j=1 ) is feasible for (PERS). Furthermore, for λj > 0, λj

F j (x) = λj sup u∈U fj (x, u) = λj fj (x, ūj ) = λj fj (x, θj λj
).

This equality is trivial for λj = 0. Hence,

m ∑ j=0 λj F j (x) - m ∑ j=0 λj g j * ( wj λj ) = m ∑ j=0 λj fj (x, θj λj ) - m ∑ j=0 λ j g j * ( wj λj
).

This implies that the optimal value of the objective function of (RC-1) is less than or equal to that in (PERS). This completes the proof.

Theorem 5 states that, under some assumptions, the upper bound obtained based on the perspective relaxation of the dual reformulation of (ARC) is the same as the robust counterpart, which is a conservative approximation. In other words, the perspectification approach yields an upper bound for (ARC); nevertheless, there are stronger upper bounds in the literature of adjustable robust optimization, such as K-adaptability or finite adaptability approaches [START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF][START_REF] Subramanyam | K-adaptability in twostage mixed-integer robust optimization[END_REF], which can straightforwardly be extended to nonlinear problems. One way to obtain a stronger upper bound is by applying a piece-wise constant decision rule to (ARC) using finite adaptability approach. In this approach, the uncertainty set is partitioned into subsets and a constant decision rule is obtained for each of the subsets. In the numerical experiments, we show how much stronger the upper bound obtained by finite adaptability compared to the one obtained from (PERS).

Lower Bound Calculation

In Section 3.2, we showed that the dual reformulation of (ARC) in the fixed-resource case is a convex programming on here-and-now decision variables. We have also shown how to construct an upper bound. In this section, we design methods to approximate (ARC) from below. Let us set

v ∶= ⎛ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 ⎞ ⎟ ⎟ ⎟ ⎠ ∈ R m × R ny(m+1) , G(v) ∶= -g * 0 (w 0 ) - m ∑ j=1 λ j g j * ( w j λ j ), V ∶= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ v = ⎛ ⎜ ⎜ ⎜ ⎝ λ {w j } m j=0 ⎞ ⎟ ⎟ ⎟ ⎠ m ∑ j=0 w j = 0, λ ≥ 0, w 0 ∈ dom(g * 0 ), w j λ j ∈ dom(g * j ), j ∈ [m] ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ .
Since λ j g j * ( w j λ j ) is jointly convex in (w j , λ j ), the set V is convex and G is a concave function. The next proposition proves the convexity of the set V and the concavity of the function G. Proposition 3.4.1. The set V is convex, and G is a concave function on V.

Proof. We consider two points

v = ⎛ ⎜ ⎜ ⎜ ⎝ λ { wj } m j=0 ⎞ ⎟ ⎟ ⎟ ⎠ , ṽ = ⎛ ⎜ ⎜ ⎜ ⎝ λ { wj } m j=0 ⎞ ⎟ ⎟ ⎟ ⎠ ∈ V and ℓ ∈ [0, 1]. Since wj λj , wj λj
∈ dom(g * j ), and λ j g j * ( w j λ j ) for each j is jointly convex in (w j , λ j ), we have the following possible cases:

Case 1. ℓ λj + (1 -ℓ) λj > 0 ∶ In this case, (ℓ λj + (1 -ℓ) λj )g * j ( ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ) ≤ ℓ λj g * j ( wj λj ) + (1 -ℓ) λj g * j ( wj λj ) < ∞ ⇒ ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ∈ dom(g * j )
Case 2. ℓ λj + (1ℓ) λj = 0 ∶ In this case, if 0 < ℓ < 1, then λj = 0 = λj , and so

(ℓ λj + (1 -ℓ) λj )g * j ( ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ) = δ * dom(g j ) (ℓ wj + (1 -ℓ) wj ) ≤ δ * dom(g j ) (ℓ wj ) + δ * dom(g j ) ((1 -ℓ) wj ) < ∞.
If ℓ = 0, then λj = 0, and hence

(ℓ λj + (1 -ℓ) λj )g * j ( ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ) = δ * dom(g j ) (ℓ wj + (1 -ℓ) wj ) = δ * dom(g j ) ( wj ) < ∞.
If ℓ = 1, then λj = 0, and thus

(ℓ λj + (1 -ℓ) λj )g * j ( ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ) = δ * dom(g j ) (ℓ wj + (1 -ℓ) wj ) = δ * dom(g j ) ( wj ) < ∞
So, in all above three cases, we get

(ℓ λj + (1 -ℓ) λj )g * j ( ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ) = δ * dom(g j ) (ℓ wj + (1 -ℓ) wj ) < ∞ ⇒ ℓ wj + (1 -ℓ) wj ℓ λj + (1 -ℓ) λj ∈ dom(g * j ).
Convexity in all other constraints of V obviously holds. So, ℓv + (1ℓ)ṽ ∈ V which shows that V is a convex set. The function G on the convex set V is a concave function due to the concavity of each -λ j g j * ( w j λ j ).

Also, let us set

F (x, u) ∶= ( f0 (x, u), . . . , fm (x, u), 0, . . . , 0) ⊺ ∈ R m+1 × R ny(m+1) , L(x, u, v) ∶= (1, v ⊺ )F (x, u) + G(v).
Thus, the dual formulation of (ARC) in the separable fixed-recourse case reads as

inf x∈X sup u∈U v∈V L(x, u, v). (3.12) Given x ∈ X , we define L x(u, v) ∶= (1, v ⊺ )F (x, u) + G(v). Clearly, L x(u, v) is concave in u and concave in v. Therefore, sup {L x(u, v) | u ∈ U, v ∈ V} , (3.13)
is a disjoint biconcave maximization problem. A common way to find a solution for such problems is by using alternating methods, which obtain a local optimizer. In these methods, a decision variable is divided into several blocks, and optimization can be performed explicitly in each block when the variables of other blocks are fixed (see Chapter 14 of [START_REF] Beck | First-order methods in optimization[END_REF] for more details). These methods also appears in the literature as block coordinate methods. The performance of the alternating method is closely related to finding the optimizers for each block.

Alternating Iterative Algorithm

As was mentioned above, we use a two-block alternating method to solve (3.13). In this method, we alternatively fix u to find v and fix v to find u until no improvement is achieved or the prescribed computational limit is reached. This method is described follow in detail.

Alternating Method

Input: initial value ū(0) ∈ U Initialization:

Set iteration counter k ← 0, choose v(0) ∈ argmax v∈V L x(ū (0) , v).

Repeat

Find optimal u: ū(k+1

) ∈ argmax u∈U L x(u, v(k) ), Find optimal v: v(k+1) ∈ argmax v∈V L x(ū (k+1) , v), Update iteration counter k ← k + 1,
Until: time limit is reached, or no improvement is possible.

Return: (ū (k) , v(k) ).
In Theorem 6 below, we discuss the convergence of the addressed alternating method.

It is done assuming some appropriate conditions, under which the alternating method is well-defined and the sequence {(u k , v k )} k≥0 admits limit point(s).

Theorem 6. Let L x(⋅, ⋅) be continuously differentiable and bounded above on Cartesian product of two closed convex sets U and V. Suppose that every sub-problem of the alternating method has an optimal solution and {z k ≡ (u k , v k )} k≥0 , as the sequence generated by the alternating method, has at least a limit point. Then, every limit point of {z k } k≥0 is a stationary point of problem (3.13).

We first recall optimality condition for a constrained differentiable problem (for more details see e.g., [START_REF]Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with Python and MATLAB[END_REF]). Consider a (non-convex) problem of the form

sup y {g(y)| y ∈ S} , (3.14)
where g is a real-valued continuously differentiable function, and S is a nonempty closed convex set. A vector y * ∈ S is called a stationary point of problem (3.14) if

∇g(y * ) ⊺ (y -y * ) ≤ 0, ∀y ∈ S,
where ∇g(y * ) is the gradient of g at y * . Lemma 6.1. Let g be a real-valued continuously differentiable function defined on the Cartesian product of two closed convex sets

C 1 ⊆ R n 1 , C 2 ⊆ R n 2 . Suppose that ȳ = (ȳ 1 , ȳ2 ) ∈ C 1 × C 2 . Then ∇g(ȳ) ⊺ (y -ȳ) ≤ 0, ∀y ∈ C 1 × C 2 , (3.15)
if and only if the following properties hold:

(i) ∇ 1 g(ȳ) ⊺ (y 1 -ȳ1 ) ≤ 0, ∀y 1 ∈ C 1 , (ii) ∇ 2 g(ȳ) ⊺ (y 2 -ȳ2 ) ≤ 0, ∀y 2 ∈ C 2 ,
where the vector y is partitioned into two component vectors

y 1 ∈ R n 1 , y 2 ∈ R n 2 , as y ≡ (y 1 , y 2 ),
and ∇ 1 g(ȳ) = ( ∂g ∂y 1 (ȳ)), and ∇ 2 g(ȳ) = ( ∂g ∂y 2 (ȳ)) denote the corresponding gradient vectors.

Proof. (⇒) Let y = (y 1 , y 2 ) ∈ C 1 × C 2 . By setting y ∶= (y 1 , ȳ2 ) and y ∶= (ȳ 1 , y 2 ) in inequality (3.15), inequalities (i) and (ii) are derived.

(⇐) Clearly, (i) and (ii) lead (3.15). Now we are ready to prove Theorem 6. The main line of reasoning can be found in [START_REF] Grippo | On the convergence of the block nonlinear gaussseidel method under convex constraints[END_REF] but given here for completeness.

Proof of Theorem 6. Suppose that z * = (z 1 * , z 2 * ) is a limit point of the sequence {z k } k≥0 . Without loss of generality, we assume that

z k = (u k , v k ) → (z 1 * , z 2 * ). Our goal is to show that for any ζ = (ζ 1 , ζ 2 ) ∈ U × V, we have ∇L x(z * ) ⊺ (ζ -z * ) ≤ 0.
According to Lemma 6.1, the above inequality is equivalent to

∇ 1 L x(z * ) ⊺ (ζ 1 -z 1 * ) ≤ 0, ∀ζ 1 ∈ U, (3.16
)

∇ 2 L x(z * ) ⊺ (ζ 2 -z 2 * ) ≤ 0, ∀ζ 2 ∈ V, (3.17)
where

∇L x(z * ) = (∇ 1 L x(z * ) ⊺ , ∇ 2 L x(z * ) ⊺ ) ⊺ is the gradient of L x at z * . By contradiction,
suppose that there exists a vector ζ2 ∈ V, such that

∇ 2 L x(z * ) ⊺ ( ζ2 -z 2 * ) > 0. (3.18) Set r k ∶= ζ2 -v k .
As the sequence {v k } k≥0 converges to z 2 * , the sequence {r k } k≥0 converges to ζ2z 2 * . Thus, due to the continuity of the gradient, there exists N > 0 such that for all k > N we have

∇ 2 L x(z k ) ⊺ r k > 0.
So, d k ∶= (0 ⊺ , (r k ) ⊺ ) ⊺ is an ascent direction of L x at z k . By backtracking line search [10, Lemma 4.3], for given parameter α ∈ (0, 1), there exists a step size t k ∈ (0, 1) such that

L x(z k + t k d k ) -L x(z k ) ≥ αt k ∇L x(z k ) ⊺ d k , ∀k > N. Therefore L x(u k , v k + t k r k ) -L x(u k , v k ) ≥ αt k ∇ 2 L x(z k ) ⊺ r k > 0, ∀k > N. (3.19)
Since V is convex, we have

v k + t k r k = (1 -t k )v k + t k ζ2 ∈ V, ∀k > N.
Hence,

L x(u k+1 , v k+1 ) ≥ L x(u k , v k+1 ) ≥ L x(u k , v k + t k r k ) > L x(u k , v k ), ∀k > N.
So, the sequence of function values {L x(u k , v k )} is non-decreasing and also bounded above.

Therefore, it is convergent. The last inequality and the convergence of

{L x(u k , v k )} implies lim k→∞ L x(u k , v k + t k r k ) -L x(u k , v k ) = 0.
The above equation and (4.17) gives

∇ 2 L x(z * ) ⊺ ( ζ2 -z 2 * ) = 0,
which contradicts (3.18). This prove (3.17). The inequality (3.16) can be proved similarly.

Theorem 6 provides conditions under which the limit points of the sequence obtained by the alternating method are helpful in solving problem (3.13). These conditions can be checked for (1.1). More specifically, L is continuously differentiable if fj and g * j are so. Furthermore, it is bounded above if static robust counterpart (3.10) has an optimal solution. Finally, V is a closed set when dom(g * j ) is closed for all j.

Remark 3.4.1. In Theorem 6, it is established that all limit points of the sequence generated by the alternating method are stationary. Generally, stationarity is necessary for local optimality [START_REF]Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with Python and MATLAB[END_REF]. However, stationary points are not necessarily optimal solutions. Such a property requires (generalized) concavity assumption to hold. Under generalized concavity assumptions on problem (3.13), the alternating method globally converges; For more details, see [START_REF] Grippo | On the convergence of the block nonlinear gaussseidel method under convex constraints[END_REF]Proposition 6] and [START_REF] Zadeh | Note-a note on the cyclic coordinate ascent method[END_REF].

Using this theorem, we can find a lower bound for (ARC) in the following way: starting from initial solution x (0) and initial scenario u (0) , we can find the limit points of {z k }, denoted by z(0) . Let us denote by W the set of limit points after each iteration. Limiting ourselves to W, we can find a here-and-now solution x (ℓ) using the following optimization problem

inf x,τ τ s.t. L(x, ū(i) , v(i) ) -τ ≤ 0, 1 ≤ i ≤ | W|,
x ∈ X .

(P-1)

By fixing this decision, we can find new limit point z(ℓ) to be added to W. Algorithm 1 provides the pseudo-code of this procedure.

Algorithm 1

Input: ϵ > 0, initial value x (0) ∈ X , u (0) ∈ U.

Initialization: Set iteration counter ℓ ← 0, and set W = ∅.

Repeat: Execute the following steps:

(Step 1) obtain (ū (ℓ) , v(ℓ) ) as a stationary point of L x (ℓ) (u, v) by applying Alternating Method. Set W = W ∪ {(ū (ℓ) , v(ℓ) )}.
(Step 2) Find (x * , τ * ) by solving (P-1).

Update iteration counter ℓ ← ℓ + 1, and set

x (ℓ) ← x * , τ (ℓ) ← τ * , Until: ∥τ (ℓ) -τ (ℓ-1) ∥ ≤ ϵ.
Return: x (ℓ) , τ (ℓ) .

It can be seen that the optimal value of (P-1) in Algorithm 1 is a lower bound for problem (3.12). Since, we add one more constraint to (P-1) in each iteration, the sequence of the lower bounds is non-decreasing.

Another way to generate lower bounds is to use finite-scenario approach. In the next section, we show how we can improve the lower bounds obtained by finite-scenario approach using the results we have.

Dual-Based Cutting Plane Algorithm

Based on the original form of (ARC), one can find a lower bound by using finite-scenario approach and only considering a finite subset {u 1 , ..., u ℓ } of U. This idea leads to the following convex programming problem:

inf x∈X ,τ {y k } k τ s.t. f j (x, y k , u k ) ≤ 0, j ∈ [m], k ∈ [ℓ], f 0 (x, y k , u k ) ≤ τ, k ∈ [ℓ], (3.20)
which is called finite-scenario approach of the (ARC) problem. A technique to obtain a finite set of scenarios is by (i) approximating (ARC) with a suitable decision rule and (ii) finding the active scenarios in the uncertainty set [START_REF] Hadjiyiannis | A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization[END_REF]. Since we are considering a nonlinear problem, we use constant decision rule. So, we first find an optimal solution (x * , y * ) of (RC) with the optimal value t * . After that, by fixing the obtained (x * , y * ), we take an active (binding) scenario on each constraint

f j (x * , y * , u) ≤ 0, j ∈ [m],
f 0 (x * , y * , u) ≤ t * .

(3.21)

The optimal value of the finite-scenario approach problem is a lower bound for the optimal objective value of the original (ARC) model since feasibility is fulfilled for only a subset of the uncertainty set.

In Theorem 7 we show how to construct a better lower bound by means of dual cuts.

Theorem 7. Let {u 1 , ..., u ℓ } ⊆ U and {v 1 , ..., v ℓ } ⊆ V. Then optimal value of

inf x∈X ,τ {y k } k τ s.t. f j (x, y k , u k ) ≤ 0, j ∈ [m], k ∈ [ℓ], f 0 (x, y k , u k ) ≤ τ, k ∈ [ℓ], L(x, u k , v k ) ≤ τ, k ∈ [ℓ], (3.22)
provides a lower bound for (ARC).

Proof. Let us denote the optimal value of (ARC) by Opt. Also, we have the following inequality due to the weak duality

∀x ∈ X sup u∈U T (x, u) ≥ sup u∈U v∈V L(x, u, v),
where T (x, u) ∶= inf y∈R ny {f 0 (x, y, u) ∶ f j (x, y, u) ≤ 0, j ∈ [m]}. Therefore,

Opt = inf x∈X τ ∈R τ s.t. sup u∈U T (x, u) ≤ τ, sup u∈U v∈V L(x, u, v) ≤ τ,
where the second constraint is redundant. Let Ū ⊆ U and V ⊆ V. Then

Opt ≥ inf x∈X ,τ τ s.t. sup u∈ Ū T (x, u) ≤ τ, sup u∈ Ū v∈ V L(x, u, v) ≤ τ.
So, if Ū = {u 1 , ..., u ℓ } and V = {v 1 , ..., v ℓ }, then we have

Opt ≥ inf x∈X ,τ τ s.t. inf y∈R ny {f 0 (x, y, u k ) ∶ f j (x, y, u k ) ≤ 0, j ∈ [m]} ≤ τ, k ∈ [ℓ], L(x, u k , v k ) ≤ τ, k ∈ [ℓ], (3.23)
which is equivalent to (3.22).

Using Theorem 7, we develop Algorithm 2, which generates potentially better lower bounds compared to Algorithm 1 and finite-scenario approach.

Algorithm 2 (Step 1) Find (x * , y * ) as a static solution.

(Step 2) Given (x * , y * ), find the active scenarios {u 0 , u 1 , ..., u m }.

(

Step 3) Use Alternating Method, to find (ū (k) , v(k) ) as a stationary point of

L x * (u, v) starting from u k (k ∈ [m 0 ]). (Step 4) Given {(ū (k) , v(k) )} k , solve inf x∈X ,τ {y k } k τ s.t. f 0 (x, y k , ū(k) ) ≤ τ, k ∈ [m 0 ], f j (x, ū(k) , y k ) ≤ 0, j ∈ [m], k ∈ [m 0 ], L(x, v(k) , ū(k) ) ≤ τ, k ∈ [m 0 ].
We emphasize that the algorithms to construct a sequence of lower bounds are applicable for any nonlinear ARO problem.

Numerical Experiments

In this section, we illustrate the performance of the discussed algorithms. All the numerical results were carried out on a laptop featuring Intel(R) Core(TM) i5-3210M CPU, 2.50 GHz processor, and 8 GB of RAM. We implemented the algorithms in MATLAB (2022a) and used YALMIP toolbox [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF] to pass the optimization problems to MOSEK as a solver [START_REF] Mosek Aps | The MOSEK optimization toolbox for MATLAB manual[END_REF].

All results of this section are presented with four decimals.

Problem Setting

We consider the following uncertain problem:

inf x∈X inf y∈Y(x,u) f0 (x, u) + ∥A 0 y -b 0 ∥ 2 -(p 0 ) ⊺ y + q 0 , (3.24)
where

Y(x, u) = {y ∶ fj (x, u) + ∥A j y -b j ∥ 2 -(p j ) ⊺ y + q j ≤ 0, j ∈ [m]} ⊆ R ny , A j ∈ R r×ny , b j ∈ R r
, and p j ∈ R ny . For j ∈ [m], let us set

g j (y) ∶= ∥A j y -b j ∥ 2 -(p j ) ⊺ y + q j .
Thus, the perspective functions corresponding to the conjugate of g j (y) is given by

λ j > 0 ∶ λ j g * j ( w j λ j ) = inf z j {λ j ((b j ) ⊺ z j -q j )| ∥z j ∥ 2 ≤ 1, (A j ) ⊺ z j -p j = w j λ j } , λ j = 0 ∶ λ j g * j ( w j λ j ) = δ * dom(g j ) (w j ) = δ * R ny (w j ) = δ {0} (w j ).

Now we consider (ARC) version of the uncertain problem (3.24). According to Theorem 2,

after dualizing over the wait-and-see variable y, with some algebra (see Section 6.4 of [START_REF] Roos | A universal and structured way to derive dual optimization problem formulations[END_REF]), we get the following equivalent dual reformulation:

inf x∈X sup u∈U ,λ j ,z j m ∑ j=0 λ j fj (x, u) + m ∑ j=0 (λ j q j -λ j (b j ) ⊺ z j ) s.t. m ∑ j=0 (λ j (A j ) ⊺ z j -λ j p j ) = 0, ∥z j ∥ 2 ≤ 1, λ 0 = 1, λ j ≥ 0, j ∈ [m 0 ]. (3.25)
Let us consider the parameters in a matrix form, i.e.,

A ⊺ ∶= [(A 0 ) ⊺ . . . (A m ) ⊺ ] ∈ R ny×r(m+1) , P ∶= [p 0 . . . p m ] ∈ R ny×(m+1) , b ⊺ ∶= [( b 0 ) ⊺ . . . ( b m ) ⊺ ] ∈ R r(m+1) , zj ∶= λ j z j , z⊺ ∶= [( z0 ) ⊺ . . . ( zm ) ⊺ ] ∈ R r(m+1) .
In addition, by setting

v ⊺ ∶= (λ ⊺ , z⊺ ) , V ∶= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ v A ⊺ z -P ⎛ ⎜ ⎜ ⎜ ⎝ 1 λ ⎞ ⎟ ⎟ ⎟ ⎠ = 0, λ ≥ 0, ∥z 0 ∥ 2 ≤ 1, ∥[z] j ∥ 2 ≤ λ j , j ∈ [m] ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ , L(x, u, v) ∶= (1, λ ⊺ ) f (x, u) + (1, λ ⊺ )q -z⊺ b,
where f (x, u) is a vector-valued function with components fj (x, u), and We use the optimality gap to compare the quality of the lower bounds obtained by applying the finite-scenario approach (3.20), Algorithm 1, and Algorithm 2:

OptGap = ( U B -LB |LB| + 10 -4 ) × 100,
where LB is the obtained lower bound, and U B is the best obtained upper bound for a given instance. Note that the constant 10 -4 is added to the denominator to avoid division over zero.

We consider two classes of randomly generated instances, each containing 100 instances.

Class One: In this class, we consider small-sized instances. We consider n y = 2, n x = 2, m = 2, and r = 5. Furthermore,

U = U 1 ∶= {u ∈ R 2 ∶ ∥u∥ 2 ≤ 1}, X = X 1 ∶= {x ∈ R 2 ∶ x 1 + 2x 2 ≤ 3, 2x 1 + x 2 ≤ 3, x 1 , x 2 ≥ 0} , and
fj (x, u) ∶= c j ⊺ x + α j ⊺ u, j ∈ [m 0 ].
In this class, we obtained upper bounds by solving the static robust counterpart problem, which is equivalent to the perspectification approach. Additionally, we employed the Kadaptability approach to obtain upper bounds. The K-adaptability approach involves splitting the uncertainty set U into K partitions (U = ∪ K k=1 U k ) and solves the following

problem inf x∈X ,τ {y k } k τ s.t. fj (x, u) + ∥A j y k -b j ∥ 2 -(p j ) ⊺ y k + q j ≤ 0, j ∈ [m], k ∈ [K], ∀u ∈ U k , f0 (x, u) + ∥A 0 y k -b 0 ∥ 2 -(p 0 ) ⊺ y k + q 0 ≤ τ, k ∈ [K], ∀u ∈ U k .
We set K = 8 and partitioned the uncertainty set into eight regions, each being an octant.

Class Two: This class contains large-sized instances. We consider n y = 100, n x = 100, m = 5, and r = 120. Furthermore,

U = U 2 ∶= {u ∈ R 20 ∶ ∥u∥ 2 ≤ 1}, X = X 2 ∶= {x ∈ R 100 ∶ ∥x∥ 2 ≤ 1, e ⊺ x ≤ 1, d ⊺ x ≥ 0} ,
where e ∈ R nx is the vector of all ones, d ∈ R nx is a random vector, and

fj (x, u) ∶= c j ⊺ x + α j ⊺ u, j ∈ [m 0 ].
We use static approximation to obtain an upper bound on the optimal value of the instances in this class.

To generate random instances, for each j ∈ [m 0 ], we randomly generate A j , p j , b j , α j , c j , and d by drawing their (entries) values from a standard normal distribution using a built-in MATLAB function "randn".

Numerical results

In this section, we present the results of the numerical experiments.

Class One: We present the statistic on the optimality gaps of the finite-scenario approach (3.20), Algorithm 1, and Algorithm 2 in Table 3.1 (details can be found in Table 3.3). Since the upper bound obtained using the K-adaptability approach for the instances of this class is lower than the one from the perspectification approach, which is equivalent to the static approximation, we report the gap using the former. As one can see, Algorithm 2 outperforms the other methods on average. However, these two methods do not generate the same scenarios. Additionally, Figure 3.1c

shows that the solutions obtained by Algorithm 2 have a similar or better optimality gap to the ones obtained from Algorithm 1.

Next to the quality of the approaches, we also report their solution times.

The average solution times for Algorithm 1, Algorithm 2, and finite-scenario approach are 0.0500, 0.0483, and 0.2253 seconds, respectively. Class Two: We present the statistic on the optimality gaps of the solutions obtained by different algorithms in Table 3.2 (details can be found in Table 3.4). As one can see, 7.5085, 3.6327, and 0.5417 seconds, respectively. Figure 3.4 presents the scatter plot of the solution times of these approaches on each instance. In this class, the computation times of Algorithms 1 and 2 are higher than the finite-scenario approach because they solve more (sub-)optimization problems than the finite-scenario approach to reach a lower bound (as shown in Figures 3.4a and 3.4b). From Figure 3.4c, across a significant proportion of instances within this classification, it is evident that Algorithm 2 exhibited notable performance in achieving solutions faster than Algorithm 1.

Overall for Class Two, our findings demonstrate the competitive performance of both

Conclusions

This chapter studied a general nonlinear ARO model with objective and constraint uncertainty.

We obtained an equivalent dual formulation by applying Fenchel's duality on the wait-and-see variable, a nonlinear static robust optimization. We investigated when the dual formulation is convex in the decision variables. Also, we explored reaching upper and lower bounds for the original problem based on the dual formulation. Thanks to the equivalent dual reformulation, we presented and analyzed two algorithms. These algorithms aimed to find a lower bound on the optimal objective value of the general nonlinear ARO model. We demonstrated by numerical results that our algorithm could produce a locally robust solution with an acceptable optimality gap. Due to the NP-hardness of indefinite QO problems, there has been a lot of research on constructing upper bounds via finding "good" solutions [START_REF] Bentobache | New LP-based local and global algorithms for continuous and mixed-integer nonconvex quadratic programming[END_REF][START_REF] Cuong | On a solution method in indefinite quadratic programming under linear constraints[END_REF], and lower bounds to identify the quality of a candidate solution, which are mainly based on linear or conic approximations [START_REF] Mitchell | Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs[END_REF][START_REF] Rostami | A convex reformulation and an outer approximation for a large class of binary quadratic programs[END_REF][START_REF] Zamani | New bounds for nonconvex quadratically constrained quadratic programming[END_REF]. A customary way to approximate a QO problem is by relaxing it into linear optimization problems, which is achieved through Reformulation-Linearization Techniques (RLT) [START_REF] Anstreicher | Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming[END_REF][START_REF] Sherali | A reformulation-convexification approach for solving nonconvex quadratic programming problems[END_REF]. For an overview of RLTs, we refer the reader to the chapter [START_REF] Sherali | Reformulation-linearization methods for global optimization[END_REF] and the references therein.

Among the conic relaxations, copositive relaxations have been considered the most powerful as it was shown that they result in tight bounds [START_REF]Copositive relaxation beats lagrangian dual bounds in quadratically and linearly constrained quadratic optimization problems[END_REF][START_REF] Burer | On the copositive representation of binary and continuous nonconvex quadratic programs[END_REF]. In such relaxations, the primary computational challenge shifts to deal with the copositive cone using tractable inner and outer approximations [START_REF] Bundfuss | An adaptive linear approximation algorithm for copositive programs[END_REF][START_REF] Gouveia | Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices[END_REF][START_REF] Kim | A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems[END_REF], or use a KKT-based branch-and-bound method [START_REF] Chen | Globally solving nonconvex quadratic programming problems via completely positive programming[END_REF].

Another important conic relaxation for QO problems is the positive semi-definite relaxations.

In the last thirty years, the field of semi-definite optimization (SDO) has undergone significant and swift advancement [START_REF] Wolkowicz | Handbook of semidefinite programming: theory, algorithms, and applications[END_REF]. The SDO framework has led to many semi-definite relaxations due to their efficiency; these relaxations are reviewed and compared in [START_REF] Bao | Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons[END_REF][START_REF] Wang | On the tightness of SDP relaxations of QCQPs[END_REF][START_REF] Zheng | Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation[END_REF]. Moreover, [START_REF] Burer | A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations[END_REF][START_REF]Globally solving box-constrained nonconvex quadratic programs with semidefinitebased finite branch-and-bound[END_REF] develop branch-and-bound approaches based on semi-definite relaxations to solve a QO problem.

In addition to directly approximating QOs, a research direction is to reformulate them into other well-studied problems. In [START_REF] Hu | An lpcc approach to nonconvex quadratic programs[END_REF] and [START_REF] Xia | Globally solving nonconvex quadratic programs via linear integer programming techniques[END_REF], the authors show how a QO problem is reformulated as a mixed-integer linear optimization (MILO) problem. Moreover, since any quadratic function can be written as the difference between two convex quadratic functions (see, e.g. [START_REF] Fampa | On global optimization with indefinite quadratics[END_REF] and [START_REF] Park | Sparsity-preserving difference of positive semidefinite matrix representation of indefinite matrices[END_REF] for different representations and their properties), a QO can be reformulated as a difference-of-convex (DC) optimization problem.

Next to methods developed for general QO problems, there are techniques to solve or approximate special classes. One class is when the matrix Q has a few negative eigenvalues.

In [START_REF] Cen | A new global optimization scheme for quadratic programs with low-rank nonconvexity[END_REF], the authors propose a solution scheme that involves solving a series of convex QO problems over the original feasible region. Additionally, [START_REF] Luo | New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation[END_REF] introduces an alternative direction-based method to solve QO problems in this class.

Another class is standard QO problems, where the feasible region is the unit simplex. For more details on lower bound approximations for this class of QO problems, we refer the reader to [START_REF] Bomze | Solving standard quadratic optimization problems via linear, semidefinite and copositive programming[END_REF][START_REF] Bomze | New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability[END_REF][START_REF] Bonami | Solving quadratic programming by cutting planes[END_REF][START_REF] Gökmen | On standard quadratic programs with exact and inexact doubly nonnegative relaxations[END_REF][START_REF] Gondzio | Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations[END_REF][START_REF] Selvi | A reformulation-linearization technique for optimization over simplices[END_REF].

In this paper, we focus on the relation between QO problems and adjustable robust optimization problems. The adjustable robust optimization (ARO) framework, initially introduced in [START_REF] Ben-Tal | Adjustable robust solutions of uncertain linear programs[END_REF], has gained significant attention among researchers due to its ability to handle decision-making problems in the presence of uncertain parameters. This approach involves adaptive decision-making by considering two types of decision variables: static and adjustable decisions. Static (or 'here-and-now') decisions are made based on available information, while adjustable (or 'wait-and-see') decisions are made in response to the actual values of uncertain parameters. In recent years, the ARO framework has been successfully applied to tackle complex optimization problems such as convex maximization [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] and bi-linear optimization [START_REF] Zhen | Disjoint bilinear optimization: A two-stage robust optimization perspective[END_REF].

To obtain an approximate solution for an ARO problem, various techniques, such as the finite scenario approach [START_REF] Hadjiyiannis | A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization[END_REF], partitioning method [START_REF]Multistage robust mixed-integer optimization with adaptive partitions[END_REF][START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF], Fourier-Motzkin elimination [START_REF] Zhen | Adjustable robust optimization via fouriermotzkin elimination[END_REF],

decision rules [START_REF] Housni | On the optimality of affine policies for budgeted uncertainty sets[END_REF], can be employed, particularly in the case of linear ARO problems. By using these methods, one can estimate the optimal value or obtain an approximated solution for the original problem. For more information on ARO, we refer to the tutorial by [START_REF] Delage | Robust multistage decision making[END_REF] and the survey paper by [START_REF] Yanıkoğlu | A survey of adjustable robust optimization[END_REF].

However, while linear ARO has effective approximation tools, the literature sparsely covers non-linear ARO problems due to their inherent complexity. In [START_REF] De Ruiter | Dual approach for two-stage robust nonlinear optimization[END_REF], the authors show a class of non-linear ARO problems featuring a polyhedral uncertainty set that can be transformed into an equivalent linear ARO problem, thereby enabling the application of approximations techniques available for linear cases. In a recent study [START_REF] Khademi | A new dual-based cutting plane algorithm for nonlinear adjustable robust optimization[END_REF], the authors employ Fenchel's duality to convert a non-linear ARO problem into its dual formulation and introduce a cutting-plane algorithm to find locally robust solutions.

In this chapter, we make a four-fold contribution to the literature to connect the two fields of quadratic optimization and adjustable robust optimization. First, we show that any QO problem can be reformulated as a disjoint bi-convex quadratic optimization problem. Using this new reformulation, we further show that any QO problem can be reformulated as an ARO problem, where the objective functions and constraints are convex quadratic on the decision variables and linear on the uncertain parameter. Moreover, the ARO reformulation has right-hand-side uncertainty, implying that available ARO techniques are applicable to approximate it.

Second, we show how one can interpret an approximation of the ARO reformulation on the original QO problem. More specifically, we prove that applying a structured affine decision rule to approximate the ARO formulation is equivalent to applying an RLT to approximate the disjoint bi-convex reformulation.

Third, we design an algorithm to construct a bound on the optimal value of (QO). More specifically, we apply a decision-rule approximation to obtain a lower bound. Then, based on the solution and the structure of the ARO problem, we construct "good" feasible solutions.

In the final step, we apply the mountain-climbing procedure to improve the quality of the solution.

Finally, we conduct an extensive numerical experience to illustrate the efficiency of our algorithm. Based on the numerical results, we see that the solution obtained from the algorithm is close to optimum and, in most cases, has the optimality gap of 1%. Regarding speed, our algorithm is computationally efficient and significantly outperforms the available off-the-self solvers.

The main results of this chapter have been appeared in The rest of this chapter is structured as follows: in Section 4.1.1, we define the notation used throughout this chapter. Section 4.2 introduces the reformulation of a QO problem as a bi-convex optimization problem and outlines its equivalent ARO problem. In Section 4.3, we approximate this problem using available techniques and prove the equivalence to an RLT for the original QO problem. Subsequently, in Section 4.4, we design an algorithm that provides a near-optimal solution for a QO problem using the ARO reformulation. Section 4.5 presents numerical results, demonstrating the efficiency of our ARO-based algorithm, particularly for large-sized instances. Finally, in Section 4.6, we summarize our findings and present our conclusions.

Notation

In this section, we introduce notations used in this chapter. For a symmetric matrix B, we use B ⪰ 0 (B ≻ 0) to show B is positive semi-definite (positive definite), i.e., that it has non-negative (positive) eigenvalues. The smallest and largest eigenvalues of a symmetric matrix B are denoted by λ min (B) and λ max (B), respectively. For a given matrix B, and integers i and j, we denote by B i , B j , and B ij , the i-th row, the j-th column, and the ij-th entry of B, respectively. For a matrix B, vec(B) denotes the vector formed by concatenating all of the rows of the matrix B. We use (⋅) ⊺ to refer to the transpose operator for both matrices and vectors. We denote the n × n identity matrix by I n , the vector of all ones by e, and the i-th unit vector by e i . To avoid overcomplicating notation, we do not specify the dimensions of e and e i but make sure they are always evident from the context. We misuse the notation and denote the real number zero, the vector of all zeroes, and the matrix of all zeroes by 0.

We use R n to refer to the n-dimensional real-valued Euclidean space, where ∥ ⋅ ∥ 2 is the Euclidean norm. The standard or unit simplex in R n , given by {x ∈ R n ∶ e ⊺ x = 1, x ≥ 0}, is denoted by ∆.

New Reformulations for Quadratic Optimization Problems

In this section, we propose two reformulations for a quadratic optimization problem (QO).

We first show how we can reformulate (QO) to a disjoint bi-convex quadratic optimization problem. Using this reformulation, we further provide an equivalent adjustable robust optimization problem. So, we start with the following theorem.

Theorem 8. Let Q + , -Q -⪰ 0, and X ⊆ R nx be an arbitrary set. Then,

min x∈X x ⊺ (Q + + Q -)x + c ⊺ x (4.1)
is equivalent to

min x,y∈R nx { 1 2 x ⊺ Q + x + 1 2 y ⊺ Q + y + x ⊺ Q -y + 1 2 c ⊺ x + 1 2 c ⊺ y ∶ x, y ∈ X } . (Bi-QO) Proof. It is clear that min x∈X x ⊺ (Q + + Q -)x + c ⊺ x = min x,y∈R nx { 1 2 x ⊺ Q + x + 1 2 y ⊺ Q + y + x ⊺ Q -y + 1 2 c ⊺ x + 1 2 c ⊺ y ∶ x = y, x, y ∈ X } ≥ min x,y∈R nx { 1 2 x ⊺ Q + x + 1 2 y ⊺ Q + y + x ⊺ Q -y + 1 2 c ⊺ x + 1 2 c ⊺ y ∶ x, y ∈ X } ,
where the inequality is due to the fact that the feasible region of the last optimization problem is contained in the feasible region of the middle optimization problem.

To show "≤", we use the negative semi-definiteness of Q -. Let x, y ∈ R nx be arbitrary. Because

Q -⪯ 0, we have (x -y) ⊺ Q -(x -y) ≤ 0. Hence, x ⊺ Q -x + y ⊺ Q -y ≤ 2x ⊺ Q -y.
This implies that for any x, y ∈ R nx ,

x ⊺ (Q + + Q -)x + y ⊺ (Q + + Q -)y ≤ x ⊺ Q + x + y ⊺ Q + y + 2x ⊺ Q -y.
So,

x ⊺ (Q + + Q -)x + y ⊺ (Q + + Q -)y + c ⊺ x + c ⊺ y ≤ x ⊺ Q + x + y ⊺ Q + y + 2x ⊺ Q -y + c ⊺ x + c ⊺ y.
Now, by taking the minimum over x, y ∈ X , we have

min x∈X {x ⊺ (Q + + Q -)x + c ⊺ x} + min y∈X {y ⊺ (Q + + Q -)y + c ⊺ y} ≤ min x,y∈X {x ⊺ Q + x + y ⊺ Q + y + 2x ⊺ Q -y + c ⊺ x + c ⊺ y} .
The fact that

min x∈X {x ⊺ (Q + + Q -)x + c ⊺ x} = min y∈X {y ⊺ (Q + + Q -)y + c ⊺ y} , completes the proof.
It is worth noting that the proof of Theorem 8 does not rely on the specific structure of the feasible set X . If X is convex, then the proposition asserts that any indefinite QO can be reformulated as a disjoint bi-convex quadratic optimization problem, where the variables x and y are linked only in the objective function.

Remark 4.2.1. In (QO), we can assume, without loss of generality, that the matrix Q is symmetric; otherwise, we can replace the objective function with x ⊺ ( Q ⊺ +Q 2 )x + c ⊺ x. Now, for a symmetric matrix Q, we know that the eigenvalues are real [START_REF] O'nan | Linear Algebra, Eagle mathematics series[END_REF]. So, for an indefinite matrix Q, we can construct the matrices in Theorem 8 as follows:

Representation 1:

Q + ∶= Q -(λ min (Q) -ϵ)I, and Q -∶= (λ min (Q) -ϵ)I, Representation 2: Q + ∶= (λ max (Q) + ϵ)I, and Q -∶= Q -(λ max (Q) + ϵ)I,
where ϵ is a small positive constant chosen to ensure that Q + , -Q -⪰ 0. Later, we discuss which of these formulations can provide a better approximation.

The next proposition aims to establish a relation between the optimal solutions of the (QO) and (Bi-QO) problems, showcasing how solutions from one problem can be used to obtain optimal solutions for the other.

Proposition 4.2.1. Let Q = Q + + Q -where Q ∈ R nx×nx , and Q + , -Q -≻ 0. If x * is an
optimal solution of (QO), then (x * , x * ) is an optimal solution of (Bi-QO). If (x, ŷ) is an optimal solution of (Bi-QO), then x and ŷ are optimal solutions of (QO).

Proof. Suppose x * is an optimal solution to (QO). It is clear that the tuple (x * , x * ) is also an optimal solution to (Bi-QO). To prove the reverse direction, assume that (x, ŷ) is an optimal solution of (Bi-QO). Therefore,

1 2 (x ⊺ Q + x + ŷ⊺ Q + ŷ + c ⊺ x + c ⊺ ŷ) + x⊺ Q -ŷ ≤ 1 2 (x ⊺ Q + x + x⊺ Q + x + c ⊺ x + c ⊺ x) + x⊺ Q -x, 1 2 (x ⊺ Q + x + ŷ⊺ Q + ŷ + c ⊺ x + c ⊺ ŷ) + x⊺ Q -ŷ ≤ 1 2 (ŷ ⊺ Q + ŷ + ŷ⊺ Q + ŷ + c ⊺ ŷ + c ⊺ ŷ) + ŷ⊺ Q -ŷ. (4.2)
When these inequalities are combined, the result is:

2x ⊺ Q -ŷ ≤ x⊺ Q -x + ŷ⊺ Q -ŷ. (4.3) Now, note that x⊺ (-Q -)ŷ = ((-Q -) 1 2 x) ⊺ ((-Q -) 1 2 ŷ), where (-Q -) 1 2
is the square roots of the matrix (-Q -). Therefore, we can apply the Cauchy-Schwarz inequality, which implies that

2x ⊺ (-Q -)ŷ ≤ 2 ∥(-Q -) 1 2 x∥ . ∥(-Q -) 1 2 ŷ∥ = 2 √ x⊺ (-Q -)x √ ŷ⊺ (-Q -)ŷ ≤ x⊺ (-Q -)x + ŷ⊺ (-Q -)ŷ, (4.4)
where the reason for the last inequality is that, for any two non-negative scalars a and c, 2 √ ac ≤ (a + c). Hence, we have

2x ⊺ Q -ŷ ≥ x⊺ Q -x + ŷ⊺ Q -ŷ. (4.5)
Thus, by (4.3) and (4.5), we obtain that

2x ⊺ Q -ŷ = x⊺ Q -x + ŷ⊺ Q -ŷ, (4.6)
which is the same as

(x -ŷ) ⊺ Q -(x -ŷ) = 0. (4.7)
From -Q -≻ 0, we have xŷ = 0, i.e. x = ŷ. So, x is an optimal solution of (QO).

A straightforward result, which follows from the proof of the above proposition, is that when (x, ŷ) represents an optimal solution to problem (Bi-QO), x and ŷ must be equal. The next corollary states this fact.

Corollary 4.2.1.

Let Q = Q + + Q -where Q ∈ R nx×nx , and Q + , -Q -≻ 0. If (x * , y * ) is an
optimal solution to problem (Bi-QO), then x * = y * .

From now on, let us restrict the feasible region of (QO) to polytopes. So, we assume that

X = {x ∈ R nx | Ax = b, x ≥ 0} for some A ∈ R mx×nx and b ∈ R mx ,
so that X is compact. In the next theorem, we show that we can reformulate (QO) problem to an adjustable robust optimization problem.

Theorem 9. Let Q = Q + + Q -where Q ∈ R nx×nx , and Q + , -Q -⪰ 0. Assume that X = {x ∈ R nx | Ax = b, x ≥ 0} is non-empty compact.
Then, the optimal value of (QO) is equal to the optimal value of the following problem:

max τ ∈R τ s.t. ∀x ∈ X , ∃(u x , w x ) ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x ≤ Q -x + 1 2 c.
(ARO-QO)

Proof. Based on the assumption, we have that (QO) is equivalent to

min x∈X x ⊺ (Q + + Q -)x + c ⊺ x,
which is, using Theorem 8, equivalent to

min x,y∈R nx { 1 2 x ⊺ Q + x + 1 2 y ⊺ Q + y + x ⊺ Q -y + 1 2 c ⊺ x + 1 2 c ⊺ y ∶ x, y ∈ X } . (4.8)
We can write (4.8) as

min x∈X { 1 2 x ⊺ Q + x + 1 2 c ⊺ x+ min y∈X 1 2 y ⊺ Q + y + x ⊺ Q -y + 1 2 c ⊺ y}. (4.9)
We consider the inner minimization problem over y for a given x ∈ X . Since X non-empty compac, we can apply Dorn duality [START_REF] Dorn | Duality in quadratic programming[END_REF], and rewrite (4.9) as follows:

min x∈X 1 2 x ⊺ Q + x + 1 2 c ⊺ x+ max ux,wx -1 2 u ⊺ x Q + u x + b ⊺ w x (4.10) s.t. A ⊺ w x -Q + u x ≤ Q -x + 1 2 c.
Let x ∈ X . If the inner maximization is infeasible, its optimal value is -∞, implying that (4.10) is unbounded. So, in this case, (QO) is unbounded, which contradicts the compactness of X . So, for any x ∈ X , there is a feasible (u x , w x ) for the inner maximization. Thus, using the epigraph reformulation of the objective function, we can rewrite (4.10) as

max τ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ τ ∀x ∈ X , ∃(u x , w x ) ∶ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x ≤ Q -x + 1 2 c. ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ , (4.11)
which completes the proof.

Problem (ARO-QO) is a quadratic ARO problem with fixed recourse and right-hand-side uncertainty. In this problem, τ is the static variable, x ∈ X is the uncertain parameter, and

(u x , w x ) is the adjustable variable. The adjustable variables can be seen as functions of x, and are known as decision policies [START_REF] Khademi | A new dual-based cutting plane algorithm for nonlinear adjustable robust optimization[END_REF][START_REF] Yanıkoğlu | A survey of adjustable robust optimization[END_REF].

It is important to note that concave QO, i.e., when dealing with a negative semi-definite matrix Q, is characterized by its NP-hard nature. This complexity primarily arises from the crucial relationship between achieving optimality and enumerating the extreme points within the feasible region [START_REF] Pardalos | Checking local optimality in constrained quadratic programming is np-hard[END_REF]. Predominant strategies for addressing concave QO problems typically involve cutting plane methods, branch and bound approaches, or iterative computational techniques [START_REF] Audet | Essays and Surveys in Global Optimization[END_REF][START_REF] Andrianova | One algorithm for branch and bound method for solving concave optimization problem[END_REF][START_REF] Chinchuluun | Global minimization algorithms for concave quadratic programming problems[END_REF][START_REF] Phillips | A parallel algorithm for constrained concave quadratic global minimization[END_REF]. Furthermore, recent studies in this area have focused on establishing bounds from a robust optimization perspective [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF], and some have adopted approaches based on gradient descent principles [START_REF] Ben-Tal | An algorithm for maximizing a convex function based on its minimum[END_REF]; the application of these techniques has been instrumental in deriving high-quality bounds for the optimal solution.

In the subsequent corollary, we present the ARO reformulation for concave QO.

Corollary 4.2.2. Let Q be a negative semi-definite matrix. Assume that

X = {x ∈ R nx | Ax = b, x ≥ 0} is non-empty compac.
Then, the optimal value of (QO) is equal to the optimal value of the following problem:

max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x ≤ Q -x + 1 2 c. (4.12)
Proof. Immediate result from Theorem 9 by setting Q + ∶= 0 and Q -∶= Q.

Note that (4.12) is a linear adjustable robust optimization problem and all techniques in the literature can be used to solve or approximate it.

Remark 4.2.2. Tables 4.8 and 4.9 present the equivalent ARO formulations if the polytope X is formulated in another form than canonical.

To approximate (ARO-QO) problem, we can use customary techniques to deal with adjustable variables, such as eliminating the adjustable variables via Fourier-Motzkin Elimination or using decision rules to approximate the adjustable variables. In the next section, we focus on such approximation methods.

ARO Based Approximations

In this section, we show how the available techniques to approximate an ARO problem can be employed and what their interpretations are concerning (QO).

Decision Rules

In (ARO-QO) problem, the adjustable variables u x and w x are, in essence, functions of the uncertain parameter x. One of the popular methods to approximate an ARO problem is by restricting the adjustable variables to belong to a specific class of functions. For example, we can restrict them to be constants, resulting in a static formulation, or to be affine, known as affine decision rule (ADR), which is a good approximation for linear ARO problems (see, e.g., [START_REF] Bertsimas | On the power and limitations of affine policies in two-stage adaptive optimization[END_REF] and [START_REF] Bertsimas | A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization[END_REF][START_REF] Bertsimas | Optimality of affine policies in multistage robust optimization[END_REF]).

Since (ARO-QO) contains a non-linear convex term u ⊺ x Q + u x , using ADR to approximate u x results in an intractable approximation. Therefore, to have a tractable approximation, we apply a hybrid decision rule. More specifically, we restrict u x to be constant and w x to be affine:

u x ∶= u and w x ∶= z + Zx,
where u ∈ R nx , z ∈ R mx , and Z ∈ R mx×nx are static variables. Using this decision rule in (ARO-QO) leads to the following static robust counterpart, which gives a lower bound on the optimal value of (QO):

max u,z,Z,τ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ Q + u + b ⊺ (z + Zx) ≥ τ, ∀x ∈ X A ⊺ (z + Zx) -Q + u ≤ Q -x + 1 2 c, ∀x ∈ X ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ , (4.13)
where u, z, and Z are simultaneously optimized together with the static decision variable τ .

In the previous section, we demonstrated that the (QO) problem is equivalent to both the (Bi-QO) and (ARO-QO) problems. In Problem (4.13) we approximate (ARO-QO). In the rest of this section, we show that this approximation, in fact, is equivalent to applying a reformulation-linearization (RL) technique to (Bi-QO).

RL techniques have also been considered in the literature to approximate an ARO problem.

More specifically, it is shown in [START_REF] Ardestani-Jaafari | Linearized robust counterparts of two-stage robust optimization problems with applications in operations management[END_REF] that using duality techniques, a linear ARO problem can be reformulated as a bi-linear optimization problem. The authors then show that using an RL technique to approximate the bi-linear optimization reformulation is equivalent to applying ADR to the original problem. In [START_REF] Zhen | Disjoint bilinear optimization: A two-stage robust optimization perspective[END_REF], the same results are shown for disjoint bi-linear problems with convex feasible regions.

Considering (Bi-QO), using the RL technique proposed in [START_REF] Sherali | A new reformulation-linearization technique for bilinear programming problems[END_REF] and [START_REF] Sherali | A reformulation-convexification approach for solving nonconvex quadratic programming problems[END_REF] results in the following linear optimization problem:

min γ,x,y 1 2 (x ⊺ Q + x + y ⊺ Q + y + c ⊺ x + c ⊺ y) + nx ∑ i,j=1 Q - ij γ ij s.t. Ax = b, Ay = b, Aγ = by ⊺ , Aγ ⊺ = bx ⊺ , x ≥ 0, y ≥ 0, γ ≥ 0. (4.14)
In the next theorem, we show that (4.14) is the dual of the deterministic reformulation of the robust counterpart (4.13).

Theorem 10. Assume that X is a non-empty compact set. Then, the optimal value of (4.13) is equal to the optimal value of (4.14).

Proof. We can rewrite (4.13) as

max u,z,Z,τ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ min x∈X { 1 2 x ⊺ Q + x + ( 1 2 c ⊺ + b ⊺ Z)x} + b ⊺ z -1 2 u ⊺ Q + u ≥ τ, min x∈X {(-A ⊺ Z + Q -) i x} + ( 1 2 c + Q + u -A ⊺ z) i ≥ 0, i = 1, . . . , n x ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ . (4.15)
Since X is a polytope, the inner minimizations are convex optimization problems. Since X is a non-empty compact set, strong duality holds [START_REF] Boyd | Convex optimization[END_REF][START_REF] Dorn | Duality in quadratic programming[END_REF]. Therefore, (4.15) is equivalent to

max u,z,Z,τ τ s.t. max α,β {b ⊺ β -1 2 α ⊺ Q + α | A ⊺ β -Q + α ≤ (b ⊺ Z) ⊺ + 1 2 c} + b ⊺ z -1 2 u ⊺ Q + u ≥ τ, max θ i {b ⊺ θ i |A ⊺ θ i ≤ ((-A ⊺ Z + Q -) i ) ⊺ } + ( 1 2 c = Q + u -A ⊺ z) i ≥ 0, i = 1, . . . , n x . (4.16)
We can omit the inner maximization operator in the above constraints. Thus, we have

max u,z,Z,α,β,θ b ⊺ β -1 2 α ⊺ Q + α + b ⊺ z -1 2 u ⊺ Q + u s.t. A ⊺ β -Q + α ≤ (b ⊺ Z) ⊺ + 1 2 c, b ⊺ θ i + ( 1 2 c + Q + u -A ⊺ z) i ≥ 0, i = 1, . . . , n x , A ⊺ θ i ≤ ((-A ⊺ Z + Q -) i ) ⊺ , i = 1, . . . , n x . (4.17)
Now, we show that (4.17) is the dual problem of (4.14). To do this, we first write (4.14) in the matrix form:

min vec (γ),x,y 1 2 ⎛
⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x y vec(γ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⊺ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Q + 0 0 0 Q + 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x y vec(γ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ + ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ c 2 c 2 vec(Q -) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⊺ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x y vec(γ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ s.t. ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ A 0 0 0 A 0 0 B C B 0 D ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x y vec(γ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ b b 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ x y vec(γ) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ≥ 0, (4.18)
where B ∶= -

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ b 1 I nx b 2 I nx ⋮ b mx I nx ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , C ∶= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ A 11 I nx A 12 I nx . . . A 1nn I nx ⋮ ⋮ ⋱ ⋮ A mx1 I nx A mx2 I nx . . . A mxnx I nx ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
, and .19) is the matrix form of (4.17). Hence, (4.14) is the dual of the deterministic reformulation of (4.13).

D ∶= ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ A 1 . . . 0 ⋮ ⋱ ⋮ 0 . . . A 1 ⋮ ⋮ A mx . . . 0 ⋮ ⋱ ⋮ 0 . . . A mx ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . The dual of (4.18) is max Y,W -1 2 Y ⊺ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Q + 0 0 0 Q + 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ Y + ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ b b 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⊺ W s.t. - ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ Q + 0 0 0 Q + 0 0 0 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ Y + ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ A 0 0 0 A 0 0 B C B 0 D ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⊺ W ≤ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ c 2 c 2 vec(Q -) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . (4.19) Setting Y ≡ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ α u Y 3 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , W ≡ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ β z vec(θ) vec(Z) ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ , ( 4
We have shown that applying the RL technique to the disjoint bi-convex reformulation (Bi-QO) is equivalent to using a hybrid static-affine decision rule to approximate the adjustable robust reformulation (ARO-QO). As mentioned, the ADR approximation is shown to be an efficient approximation for a class of linear ARO problems. For example, for a linear ARO problem with a right-hand-side uncertainty, the ADR approximation is tight when the uncertainty set is simplex [START_REF] Bertsimas | On the performance of affine policies for two-stage adaptive optimization: a geometric perspective[END_REF]. The translation of this setting for the original problem (QO) is to have a concave quadratic objective function with X being a simplex. Even though this class seems not to be interesting (we know that enumerating the n x number of vertices provides us with the optimal value), it generates insights into the quality of (4.14).

As mentioned in Remark 4.2.1, we can have multiple representations of Q based on Q + and Q -. Considering Representation 1, we see that Q -is a diagonal matrix, but Q + has a similar density as Q. Therefore, in (ARO-QO), all entries of u x are linked together via

Q + u x .
However, in Representation 2, Q + is a diagonal matrix, implying that the entries of u x are only linked together via u ⊺ x Q + u x and not in the constraints. In the numerical result section, we will use this representation.

Fourier-Motzkin Elimination

In linear ARO problems with fixed recourse, an adjustable variable may be eliminated by employing Fourier-Motzkin elimination (EME). This approach allows for the effective handling of problems involving a limited number of adjustable variables [START_REF] Zhen | Adjustable robust optimization via fouriermotzkin elimination[END_REF].

Note that for a given x ∈ X , in (ARO-QO), we have the ability to eliminate the adjustable variable w x ∈ R mx . We assume without loss of generality that b ≥ 0. Let k ∈ {1, . . . , m x }. To eliminate w x k , the k-th component of the vector w x , we first isolate it in the constraints: If A ki ≠ 0 and b k > 0, then both sides of their respective constraints can be divided by A ki and b k . This yields an equivalent representation of the feasible region, involving the following constraints:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ b k w x k ≥ τ -1 2 x ⊺ Q + x -1 2 c ⊺ x + 1 2 u ⊺ x Q + u x - mx ∑ j=1 j≠k b j w x j , A ki w x k ≤ (Q -x + 1 2 c + Q + u x ) i - mx ∑ j=1 j≠k A ji w x j . i = 1, . . . , m x .
w x k ≥ 1 b k (τ -1 2 x ⊺ Q + x -1 2 c ⊺ x + 1 2 u ⊺ x Q + u x - mx ∑ j=1 j≠k b j w x j ) if b k > 0, 0 ≥ τ -1 2 x ⊺ Q + x -1 2 c ⊺ x + 1 2 u ⊺ x Q + u x - mx ∑ j=1 j≠k b j w x j if b k = 0, w x k ≥ 1 A ki ((Q -x + 1 2 c + Q + u x ) i - mx ∑ j=1 j≠k
A ji w x j ) for i = 1, . . . , m x , where A ki < 0,

1 A kr ((Q -x + 1 2 c + Q + u x ) i - mx ∑ j=1 j≠k
A jr w x j ) ≥ w x k for r = 1, . . . , m x , where A kr > 0,

(Q -x + 1 2 c + Q + u x ) i - mx ∑ j=1 j≠k
A js w x j ≥ 0 for s = 1, . . . , m x , where A ks = 0.

After the adjustable variable w x k is eliminated, the feasible set becomes:

1 A kr ((Q -x + 1 2 c + Q + ux) i - mx ∑ j=1 j≠k A ji wx j ) ≥ 1 b k (τ -1 2 x ⊺ Q + x -1 2 c ⊺ x + 1 2 u ⊺ x Q + ux - mx ∑ j=1 j≠k b j wx j )
where b k > 0 and A kr > 0,

0 ≥ τ -1 2 x ⊺ Q + x -1 2 c ⊺ x + 1 2 u ⊺ x Q + ux - mx ∑ j=1 j≠k b j wx j where b k = 0, 1 A kr ((Q -x + 1 2 c + Q + ux)r - mx ∑ j=1 j≠k A jr wx j ) ≥ 1 A ki ((Q -x + 1 2 c + Q + ux) i - mx ∑ j=1 j≠k
A ji wx j ) where A ki < 0 and A kr > 0,

(Q -x + 1 2 c + Q + ux)s - mx ∑ j=1 j≠k
A js wx j ≥ 0 where A ⊺ sk = 0.

By continuing the process of FME, the adjustable variable w x (or some part of it) is eliminated, resulting in a problem with fewer adjustable variables but potentially many more constraints. If the number of constraints in (QO) is limited, then it is computationally efficient to eliminate w x .

Finite Scenario Approach

One of the approximation approaches for the ARO problem is the Finite Scenario Approach (FSA). In this approach, we restrict ourselves to only finite scenarios of uncertainty set.

Instead of making decision rules, one can introduce a new single optimization variable to each scenario. This approach only assures feasibility for a subset of scenarios from the uncertainty set, so the objective value found with this approach only provides an upper bound to the optimal objective value of the ARO model. The (FSA) is computationally efficient because it only considers a finite number of scenarios, rather than trying to optimize over all possible scenarios. This reduces the number of variables and constraints in the optimization problem, making it easier to solve. By identifying a set of potential scenarios, we are able to utilize this technique that results in a deterministic convex optimization problem as below:

max {u k } k ,{w k } k ,τ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ 1 2 (x k ) ⊺ Q + x k + 1 2 c ⊺ x k + b ⊺ w k -1 2 (u k ) ⊺ Q + u k ≥ τ, k = 1, . . . , |W| -Q + u k + A ⊺ w k ≤ Q -x k + 1 2 c, k = 1, . . . , |W| ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ , (FSA-QO)
where W = {x 1 , . . . , x r } is a finite sub-set of X .

The following proposition states that if the optimal value of (FSA-QO) for a finite subset of scenarios is identical to the optimal value of (QO), then the optimal solution for (QO) must be included within that subset.

Proposition 4.3.1. Let Q = Q + + Q -where Q ∈ R nx×nx , and Q + , -Q -≻ 0.
If the optimal value of (FSA-QO) for a given finite subset of scenarios is equal to the optimal value of (QO), then the finite subset of scenarios contains the optimal solution for (QO).

Proof. Let (τ , {ū k } k , { wk } k ) be an optimal solution of problem (FSA-QO), and suppose that in this solution, the following constraint of problem (FSA-QO) is binding for some

x s ∈ W ⊊ X :

1 2 (x s ) ⊺ Q + x s + 1 2 c ⊺ x s + b ⊺ ws -1 2 (ū s ) ⊺ Q + ūs = τ .
We claim that x s is an optimal solution of (QO). To show this, we have

τ = 1 2 (x s ) ⊺ Q + x s + 1 2 c ⊺ x s + max w,u {b ⊺ w -1 2 u ⊺ Q + u ∶ -Q + u + A ⊺ w ≤ Q -x s + 1 2 c} = 1 2 (x s ) ⊺ Q + x s + 1 2 c ⊺ x s + min z { 1 2 z ⊺ Q + z + 1 2 c ⊺ z + z ⊺ Q -x s | z ∈ X } , (4.21)
The validity of the last equality follows from the fact that strong duality holds. If we denote the optimal solution of the above minimization problem by z s , then we can conclude that (x s , z s ) is optimal for (Bi-QO). Furthermore, according to Corollary 4.2.1, we have x s = z s , and therefore x s is optimal for the original (QO) problem.

Solution Method

In the previous section, we explained how to obtain a lower bound using the techniques from ARO literature. In this section, we provide an algorithm to obtain a feasible solution of construct an upper bound.

After solving the approximated problem (4.13), we use the obtained solution to extract worst-case scenarios from each constraint of the robust counterpart problem (4.13). Among these scenarios, we select the one that yields the best objective value for the original QO problem. After identifying the most favorable scenario, our attention is redirected to the bi-convex reformulation of the QO problem. Given the selected scenario, we employ the mounting claiming algorithm for (Bi-QO) to improve the quality of the solution. This process ultimately leads us to an upper bound for (QO) problem.

Mountain Climbing Procedure

Input: Matrix Q, vector c, and starting point x 0 .

Initialization:

Decompose Q = Q + + Q -such that Q + , -Q -⪰ 0.
Repeat: Execute the following steps:

x (k+1) ← argmin x∈R nx { 1 2 x ⊺ Q + x + x ⊺ Q -x (k) + 1 2 c ⊺ x ∶ x ∈ X } .
Until: No further improvement is possible.

Output: Solution candidate x (end) .

By employing the ARO reformulation, bi-convex reformulation, and the mounting claiming method, we can efficiently explore and improve the solution space, thereby obtaining an upper bound that closely approaches the optimal value. This approach allows us to make significant progress in refining the solution quality while mitigating computational challenges

We implement the numerical experiments using MATLAB 2022a. The computations are executed on a laptop equipped with an Intel(R) Core(TM) i5-3210M CPU at 2.50 GHz and 8 GB of RAM. We use YALMIP to pass optimization problems to suitable solvers [START_REF] Löfberg | YALMIP: A toolbox for modeling and optimization in MATLAB[END_REF].

We emphasize that the computational times reported in our experiments We use state-of-the-art global solvers to solve the QO problems, namely Gurobi [65, version 10.0] and CPLEX [72, version 12.9]. Given that our bounds requires solving multiple linear optimization problems, we specifically employ Gurobi for this purpose. Moreover, MOSEK [91, version 10.1.15] is used to solve second-order cone optimization problems.

Concave Quadratic Minimization

Let us consider a concave quadratic minimization over a polyhedron

min x≥0 x ⊺ Qx + c ⊺ x s.t. Ax ≥ b, (4.22)
where Q ∈ R nx×nx , and

-Q ⪰ 0, c ∈ R nx , A ∈ R mx×nx ,
max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x ≤ Qx + 1 2 c, w x ≥ 0, (4.23)
where X ∶= {x ∈ R nx |Ax ≥ b, x ≥ 0}. To obtain a lower bound, we consider the following decision rule:

w x ∶= ⎛ ⎜ ⎜ ⎜ ⎝ z + Zx w ⎞ ⎟ ⎟ ⎟ ⎠
, where for given r ∈ {1, 2, . . . , m x }, z ∈ R r , Z ∈ R r×nx , and w ∈ R (mx-r) are static variables. It is important to note that for r = m x , we obtain a full affine decision rule, while for r = 0, we have a static decision rule. For other values, we have a partial affine decision rule. Each of these decision rule types has its own set of advantages and disadvantages, which we address later in this section.

In [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF], the authors propose an approximation solution approach for solving a concave minimization problem via ARO by providing upper and lower bounds, where the lower bound is formulated as a second-order cone optimization problem. To solve this, we employed the MOSEK solver.

In this section, we compare the quality of the solution obtained by ARO-QO Algorithm with Gurobi and CPLEX, and [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] method. In all of our numerical experiments, we set a maximum time limit of 3,000 seconds.

We analyze the performance of the upper and lower bound in terms of the optimality gap, which is measured as follows:

Gap(%) = ( UB -LB |UB| + 10 -4 ) × 100,
where 'LB' is the lower bound and 'UB' is the upper bound for a given instance. The addition of the small constant 10 -4 in the denominator is to ensure the prevention of division by zero.

Problem Instances

First, we consider the seven test instances from Section 4.3 of [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF]. We undertake a detailed comparison of three versions of ARO-QO Algorithm (static, partial, and fully affine), [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] method, and global solvers Gurobi and CPLEX. In the lower bound approximation of the ARO-QO Algorithm, applying full static, partial affine (restricting the first r = [ mx 7 ] + 1 of w x to be affine and the remaining m xr to be constant), and full affine decision rules has distinct effects on the optimality gaps. Table 4.1 illustrates that increasing the number of affine decision rules correlates with tighter optimality gaps within the ARO-QO Algorithm.

Particularly, the Affine ARO-QO Algorithm consistently achieves the smallest optimality gaps among its variants. However, this precision incurs longer solver time, notably in larger problems, such as Problem 5, which required 900.48 seconds, and Problems 6 and 7, where it exceeded the time limit. However, the Static and Partial ARO-QO Algorithms have the lowest optimality gap in Problem 7 and do so within a reasonable time.

In addition, it is noteworthy that the [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] method typically leads to larger optimality gaps compared to the ARO-QO algorithms, while the solver times for this method are longer than static ARO-QO Algorithms. Gurobi and CPLEX achieve optimality for Problems 1-6.

However, CPLEX often requires more time, especially in larger problems. Both Gurobi and CPLEX reached their time limits on Problem 7, highlighting the difficulty in solving large-size problems. Notes. In this table, the first column presents the problem numbers along with their corresponding dimensions. The symbol "-" indicates that it was not possible to determine bound within 3,000 seconds.

Even though the static policy yields the highest optimality gap among the three decision rules, it stands out for its minimal computation time required to derive both lower and upper bounds. This becomes the problem after applying a static decision rule that has no extra variables and constraints, and the upper bound is calculated independently of the solution of the lower bound. Notably, the computation of the upper bound in the static policy is independent of the lower bound solution. This independence is based on the structure of problem (4.23). In Step 2 of the ARO-QO Algorithm, where worst-case scenarios are generated from problem (4.23), an optimal decision rule is not required. Remarkably, in the seven instances, the calculated upper bound aligns with the global optimal value, and is obtained quickly, as reported in Table 4.7. When compared with alternative approaches, such as applying partial or full affine decision rules or using the [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] method (which also achieves optimal upper bounds), the full static decision rule demonstrates a faster computation process to reach a candidate solution. This increased speed is attributed to the fact that mentioned methods, necessitate optimal solutions for the lower bound to determine the upper bound, which inherently increases their computational demand as opposed to the more streamlined process observed in the static policy.

After considering the seven test instances of [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF], we randomly generate large-size instances.

For a meaningful comparison of the mentioned approaches, we evaluate the quality of the bounds on the objective value of problem (4.22) using 15 groups of random instances, with the dimension n x taking value in {50, 100, . . . , 600, 700} and the number of constraints m x spanning a range in {100, 150, . . . , 750, 800}. Each group contains five instances of the same size, and these instances are generated in a similar manner to those created in [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF].

For each group, ranging from #1 to #15, Table 4.2 lists the mean optimality gap and solver time, with standard deviations included in brackets (details can be found in Table 4.10).

Based on the above discussions we use a static decision rule for the lower bound approximation in ARO-QO Algorithm. We observe that our ARO-QO Algorithm maintains a consistent performance level across different problem complexities. CPLEX demonstrates reasonable performance up to Group 6. Furthermore, the method by [START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF] displays more consistent optimality gaps across all problem groups, despite them being significantly higher compared to those of Gurobi and CPLEX in the initial groups. Gurobi achieved very low optimality gaps in Groups 1-3, in particular, showing an increasing trend in solver times with higher problem groups, often reaching the 3,000-second limit. Gurobi for the instances in groups 14 and 15, and CPLEX for the instances in groups 8-15, it was not possible to determine the presence of a feasible solution within the time limit.

From a computation time perspective, in each group, the ARO-QO Algorithm demonstrates the lowest time to reach the bounds compared to other methods. Overall, the ARO-QO Algorithm showcases efficiency in computation time and maintains acceptable gaps in all groups. This underscores the ARO-QO Algorithm's proficiency in balancing time efficiency and gap management across these problems. Notes: This table categorizes problems into groups in the first column. The subsequent columns display "mean [standard deviation]" values of the optimality gaps and solver time for each sub-group. The symbol "-" indicates that it was not possible to determine upper bounds for all instances of the corresponding group within the maximum the time limit.

Standard Quadratic Optimization

Let us consider a standard quadratic optimization problem

min x∈∆ x ⊺ Qx + c ⊺ x.
In general, a standard QO problem is NP-hard [START_REF] Bomze | Solving standard quadratic optimization problems via linear, semidefinite and copositive programming[END_REF]. We remark that the quadratic function

x ⊺ Qx + c ⊺ x over the unit-simplex can be described as a homogeneous quadratic function:

x ⊺ Qx, where Q ∶= Q + 1 2 ec ⊺ + 1 2 ce ⊺ . Hence, without loss of generality, the standard QO problem can be represented as follows:

min x∈∆ x ⊺ Qx. (StQO)
Let Q ∈ R nx×nx be an indefinite symmetric matrix. The (StQO) problem is equivalent to the following problem

max τ ∈R τ s.t. ∀x ∈ ∆, ∃(u x ∈ R nx , w x ∈ R) ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x -1 2 u ⊺ x Q + u x + w x ≥ τ, -Q + u x + ew x ≤ Q -x, (ARO-StQO)
where τ is the static variable, x ∈ ∆ is the uncertain parameter, and (u x , w x ) ∈ R nx × R is the adjustable variable.

As mentioned in previous sections, we address two types of approximations of (ARO-StQO).

First, the following problem is an approximation of (ARO-StQO) by applying the hybrid static and affine decision rule

max z,u,z 0 ,τ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ 1 2 x ⊺ Q + x + (z 0 + z ⊺ x) -1 2 u ⊺ Q + u ≥ τ, ∀x ∈ ∆ -Q + u + e(z 0 + z ⊺ x) ≤ Q -x, ∀x ∈ ∆ ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ , (L1-StQO)
which is equivalent to the following deterministic convex quadratic optimization problem

max z,u,z 0 ,τ,α,β,θ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ τ -1 2 α ⊺ Q + α + β + z 0 -1 2 u ⊺ Q + u ≥ τ, eβ -Q + α ≤ z, Q + u + θ -ez 0 ≥ 0, eθ ⊺ ≤ (-ez ⊺ + Q -) ⊺ , ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ . ( 4.24)
Second, using Fourier-Motzkin elimination on (ARO-StQO) to eliminate w x ∈ R, we have

max τ ∈R τ s.t. ∀x ∈ ∆, ∃u x ∶ 1 2 x ⊺ Q + x -1 2 u ⊺ x Q + u x + (Q -) i x + (Q + ) i u x ≥ τ, i = 1, . . . , n x . (FME-StQO)
In (FME-StQO), applying a constant decision rule on u x (i.e., u x = u) result in

max τ ∈R,u∈R nx τ s.t. 1 2 x ⊺ Q + x -1 2 u ⊺ Q + u + (Q -) i x + (Q + ) i u ≥ τ. ∀x ∈ ∆ i = 1, . . . , n x (L2-StQO)
The lower bound obtained from problem (L2-StQO) is better than the one via (L1-StQO).

It is imperative to note, however, that the computational effort associated with this superior bound may be elevated due to an augmented set of constraints.

We now offer a more detailed examination of the ARO-QO Algorithm employed for solving StQOs. Utilizing decision rules, we have successfully approximated the original problem.

The optimal values extracted from each of these approximated problems serve as lower bounds. Subsequently, we discuss selected worst-case scenarios, which are derived based on the optimal solutions of these lower-bound problems.

Scenario Based on L1-StQO. Let (z * , v * , z * 0 , τ * , α * , β * , θ * ) be an optimal solution for (4.24) which is the deterministic reformulation of (L1-StQO). We select scenarios using the following optimization problems

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ x0 ∈ argmin x∈∆ { 1 2 x ⊺ Q + x + z * ⊺ x} , xi ∈ argmin x∈∆ {(-ez * ⊺ + Q -) i x} , i = 1, . . . , n x . (4.25)
Note that, we do not need to solve linear optimization problems in (4.25) to find {x i } nx i=1 and just need to consider the extreme points of the unit-simplex set, i.e., {e i } nx i=1 . These points provide the natural upper bound (i.e., e i ⊺ Qe i = Q ii ), which exists in the literature, see [62, Lemma 2.1 part (iv)]. We choose the best scenario, denote it by x * 1 , as the one with the lowest objective value, i.e.,

x * 1 ∈ argmin

x {x ⊺ Qx| x ∈ {x i } nx i=0 } .
Scenario Based on L2-StQO. We can find scenarios from the uncertainty set ∆ according to (L2-StQO) as follows

xi ∈ argmin x∈∆ { 1 2 x ⊺ Q + x + Q - i x} , i = 1, . . . , n x . (4.26)
We denote by x * 2 the scenario with the lowest objective value, i.e.,

x * 2 ∈ argmin

x {x ⊺ Qx| x ∈ {x i } nx i=1 } .
In this subsection, our method will be compared with the global solvers Gurobi and CPLEX, as well as with the local solver IPOPT. It is worth noting that IPOPT, a local primaldual-based interior point solver [START_REF] Wächter | On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[END_REF] is renowned for its time computational efficiency but functions exclusively as a local solver. To solve convex quadratic sub-problems in ARO-QO Algorithm, we employed MOSEK.

To implement our ARO-based method on StQOs, we need to compute lower bounds on the optimal objective value of StQO as discussed above. We consider two best scenarios, x * 1 and

x * 2 , obtained from the lower bound approximations (L1-StQO) and (L2-StQO). By using these two initial points, we can improve the initial solutions, and the best solution obtained becomes the candidate solution, with its corresponding objective value serving as an upper bound.

Problem Instances

It is of paramount importance to note that with a high probability, global solutions of a randomly generated StQO instances are located either at vertices or edges of the standard simplex [START_REF] Bomze | The complexity of simple models-a study of worst and typical hard cases for the standard quadratic optimization problem[END_REF]. In order to make a fair comparison based on this information, we do not generate naive random instances in our study, as our upper-bound methodology would be optimal in these cases. Instead, we concentrate on using instances from well-known datasets or employing their patterns to generate new instances, as outlined by [START_REF] Bonami | Solving quadratic programming by cutting planes[END_REF][START_REF] Liuzzi | A new branch-and-bound algorithm for standard quadratic programming problems[END_REF], and [START_REF] Scozzari | A clique algorithm for standard quadratic programming[END_REF].

We analyze the performance of the upper bound in terms of the solution gap, which is measured as follows:

SGap(%) = ( UB -UB (best) |UB| + 10 -4 ) × 100,
where UB (best) represents the best upper bound obtained from all approaches, and UB is the upper bound for a given instance.

Detailed Results

As mentioned in Remark 4.2.1, multiple representations of Q can be obtained based on Q + and Q -. Here we utilize Representation 2 and apply the ARO-QO Algorithm to find upper bounds. Furthermore, we consider the upper bounds obtained from global solvers, when setting their time limit to the time taken by ARO-QO Algorithm. We use SGap1 and Time1

to refer this upper bound. We also set the time limit at the solvers to 3,000 seconds to which we refer by SGap 2 and Time2.

A statistical analysis of solution gaps for two classes of test problems is presented in Table 4.3 and 4.4. Both classes consist of 150 instances, with a dimension of n x = 30 for Class One and n x = 50 for Class Two. Notes. Test instances from [START_REF] Bonami | Solving quadratic programming by cutting planes[END_REF].

In Tables 4.3 and 4.4, we observe that within the time taken by ARO-QO Algorithm, CPLEX exhibits the best performance, and our approach better than Gurobi. As the time limit extends to a maximum of 3,000 seconds for global solvers Gurobi and CPLEX, they demonstrate superior performance, particularly in these two casses of small-sized instances,

Notes. This table categorizes problems into groups in the first column. The subsequent columns display 'mean [standard deviation]' values of the solution gaps for each sub-group. SGap1 represents the solution gap with the time limit equals to that needed by the ARO-QO Algorithm, while SGap2 denotes the solution gap within a 3,000-second time frame. Instances, where Gurobi failed to find solutions within its allotted time, are marked with a "-", indicating its inability to establish feasible solutions (upper bounds) for all instances in the respective group.

Conclusions

We introduce a novel reformulation technique that enables the Quadratic Optimization problem (QO) to be recast as an Adjustable Robust Optimization problem (ARO). This process begins by demonstrating that any QO problem can be transformed into a disjoint bi-convex QO problem. Following this, we propose an equivalent ARO reformulation.

Specifically, we illustrate that employing a so-called decision rule technique to approximate the ARO reformulation equates to using a linearization-relaxation technique on its bi-convex form. The ARO reformulation offers a new approach to solving non-convex QO problems by transferring the complexity from the original problem to its equivalent ARO counterpart.

Specifically, in the concave QO problem, our ARO model transforms into a linear ARO, whereas in the indefinite QO problem, it becomes a non-linear ARO. Moreover, we develop an algorithm capable of identifying near-optimal solutions using our novel reformulations.

We demonstrate the effectiveness of our ARO-based method in solving a class of quadratic optimization problems through numerical experiments, showing that it can yield high-quality

X = {x ∈ R nx | Ax = b, x ≥ 0} max τ ∈R τ s.t. ∀x ∈ X , ∃(u x , w x ) ∶ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x ≤ Q -x + 1 2 c. II X = {x ∈ R nx | Ax = b} max τ ∈R τ s.t. ∀x ∈ X , ∃(u x , w x ) ∶ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x = Q -x + 1 2 c. III X = {x ∈ R nx | Ax ≥ b, x ≥ 0} max τ ∈R τ s.t. ∀x ∈ X , ∃(u x , w x ) ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x ≤ Q -x + 1 2 c, w x ≥ 0. IV X = {x ∈ R nx | Ax ≥ b} max τ ∈R τ s.t. ∀x ∈ X , ∃(u x , w x ) ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 x ⊺ Q + x + 1 2 c ⊺ x -1 2 u ⊺ x Q + u x + b ⊺ w x ≥ τ, A ⊺ w x -Q + u x = Q -x + 1 2 c, w x ≥ 0.

Feasible Region

Type ARO Problem Notes. In the table, we applied the ARO-QO Algorithm with a static decision rule in the lower bound approximation step. The 'NA' indicates that the solver could not find any feasible solution within the time limit, which was set at 3,000 seconds.

I X = {x ∈ R n x | Ax = b, x ≥ 0} max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x ≤ Q -x + 1 2 c. II X = {x ∈ R n x | Ax = b} max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x = Q -x + 1 2 c. III X = {x ∈ R n x | Ax ≥ b, x ≥ 0} max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x ≤ Q -x + 1 2 c, w x ≥ 0. IV X = {x ∈ R n x | Ax ≥ b} max τ ∈R τ s.t. ∀x ∈ X , ∃w x ∶ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 1 2 c ⊺ x + b ⊺ w x ≥ τ, A ⊺ w x = Q -x + 1 2 c, w x ≥ 0.

  to the Department of Industrial Engineering and Innovation Sciences for their warm hospitality during my visiting research period at Eindhoven University of Technology.

February

Optimization 3 4 1 . 1

 311 Quadratic Optimization Through the Lens of Adjustable Robust Opti-Domain and epigraph of an extended real-valued function. 1.2 Convex conjugate function. 1.3 A proper, closed, and convex function and its convex perspective function.

3. 3 4 . 6 1 Preliminaries

 3461 Detailed numerical results from Class One. 3.4 Detailed numerical results from Class Two. 4.1 Optimality gaps and solver times of concave minimization instances from [105]. 4.2 Statistic of optimality gaps and solver times for randomly generated concave minimization instances. 4.3 Statistic of solution gaps and solution times of (StQO) instances in Class One. 4.4 Statistic of solution gaps and solution times of (StQO) instances in Class Two. 4.5 Statistic of solution gaps and solution times of generated large-sized (StQO) instances. Comparison result on concave quadratic minimization test instances from [105]. 4.7 Time Results for concave quadratic minimization test instances from [105]. 4.8 Other classes of ARO reformulations of indefinite QO problem. 4.9 Other classes of ARO reformulations of concave QO minimization. 4.10 Detailed result on concave quadratic minimization. 4.11 Detailed numerical results on standard quadratic optimization. xv Chapter John von Neumann:

Figure 1 . 1 :

 11 Figure 1.1: Domain and epigraph of an extended real-valued function.

Figure 1 . 2 :

 12 Figure 1.2: Convex conjugate function.

[ 99 ,

 99 page 67 and Theorem 13.3] for closedness. Figure 1.3 displays a proper, closed, and convex function along with its convex perspective function. Remark 1.1.2 ([27]). A proper, closed, and convex function g conforms to the following relation with its convex conjugate and perspective functions g per (x, t) = sup y {y ⊺ xtg * (y) | y ∈ dom(g * )} .

Figure 1 . 3 :

 13 Figure 1.3: A proper, closed, and convex function and its convex perspective function.

1 Figure 1 . 4 :

 114 Figure 1.4: The robust feasible region.

4 Figure 1 . 5 :Remark 1 . 3 . 1 .

 415131 Figure 1.5: Adjustable robust optimization. The blue square is the uncertainty set U.

Figure 1 . 6 :

 16 Figure 1.6: Affine and piece-wise constant decision policies.

Example 1 . 4 . 1 .

 141 Let us consider the following linear ARO problem min x,y(.) 3x s.t. xy(u) ≤ -u, ∀u ∈ [0, 1]

Figure 1 . 7 :

 17 Figure 1.7: Classical uncertainty sets.

[ 76 ]

 76 Khademi, A., Marandi, A., & Soleimani-damaneh, M. (2023). A New Dual-Based Cutting Plane Algorithm for Nonlinear Adjustable Robust Optimization. Journal of Global Optimization.

Corollary 3 . 2 . 1 .

 321 Consider the following ARC: inf x∈X sup u∈U inf y f0 (x) + h 0 (u) + g 0 (y)

Example 3 . 2 . 1 .

 321 Consider an instance of (ARC) with m = 1, X = [1, +∞), U = [1, 2],

  for which c i (u) = ||u|| 2ρ, for some ρ > 0. By setting F j (x) ∶= sup u { fj (x, u)| u ∈ U} for each j ∈ [m 0 ] and x ∈ X , we can rewrite (3.10) as inf x∈X ,y∈R ny F 0 (x) + g 0 (y)

  [z] j = [z] jr+1,...,(j+1)r , we can write (3.25) as inf x∈X sup u∈U ,v∈V L(x, u, v).

Figure 3 .

 3 2 depicts a scatter plot comparing the solution times in each instance. Illustrated in Figures 3.2a and 3.2b, Algorithms 1 and 2 reach lower bounds more rapidly compared to the finite-scenario approach. In Figure 3.2c, each point represents an instance, with the horizontal and vertical axes indicating the solution times of Algorithm 1 and Algorithm 2, respectively. For most of the instances in this class, we observe that Algorithm 2 reached a solution faster than Algorithm 1. Hitherto, we have seen that Algorithm 2 performs well in the instances in Class One. In what follows, we analyze the performance of the algorithms in the instances of Class Two.

Figure 3 . 1 :

 31 Figure 3.1: The comparison of the optimality gaps of the solutions obtained by Algorithm 1, Algorithm 2, and finite-scenario approach for the instances in Class One.

Figure 3 . 2 :

 32 Figure 3.2: The comparison of the solution time of Algorithm 1, Algorithm 2, and finitescenario approach for the instances in Class One.

Figure 3 . 3 :

 33 Figure 3.3: The comparison of the optimality gaps of the solutions obtained by Algorithm 1, Algorithm 2, and finite-scenario approach for the instances in Class Two.

Figure 3 . 4 :

 34 Figure 3.4: The comparison of solution times between Algorithm 1, Algorithm 2, and the finite-scenario approach for instances in Class Two.

[ 75 ]

 75 [START_REF] Khademi | Quadratic optimization through the lens of adjustable robust optimization[END_REF]. Quadratic Optimization Through the Lens of Adjustable Robust Optimization. Submitted.

(4. 20 )

 20 Since X = {x| Ax = b, x ≥ 0} is non-empty, so we cannot have b k > 0 and A ki ≤ 0 for any i = 1, . . . , m x .

  exclude the time required by YALMIP to build the model and pass it to solvers, and we merely consider the time consumed by the solvers themselves. In what follows, we present the numerical experiments, specifically focusing on concave quadratic minimization and standard quadratic optimization. All the instances and the code are available at: [Link].

Table 1 . 1 :

 11 Conjugate functions of some popular forms.

	Number Function and assumptions Conjugate function	Reference
	1	f (x) + a	f * (y) -a	[39, page 95]

Table 1 . 2 :

 12 Support functions of some popular sets.

	Number S, S ≠ ∅	δ * S (y)	Reference

  proper, closed, and convex in y, and concave in u.

	Definition 1.3.2 (Adjustable Robust Optimization, [87]). The Adjustable Robust Counter-
	part (ARC) for uncertain problem (1.1) is defined by
	inf x∈X	sup u∈U	inf y	f 0 (x, y, u)

Table 1 . 3 :

 13 Convex quadratic problems and their corresponding Dorn duals.

	Primal Problem	Type	Dual Problem
			I
	min x	1 2

Table 3 . 1 :

 31 Statistic of optimality gaps of instances in Class One.

	Method	Mean	Standard deviation
	Algorithm 1	26.4925	75.3803
	Algorithm 2	22.2883	72.4447
	Finite-scenario approach 49.7797	336.4677
	Figure 3.1 compares the optimality gaps of the solutions obtained by Algorithm 1, Algorithm

2, and the finite-scenario approach, where each point corresponds to an instance. As shown in Figures 3.1a and 3.1b, Algorithms 1 and 2 outperform the finite-scenario approach. More specifically, in 84 instances, Algorithm 2 generates better lower bounds, while the finitescenario approach generates better lower bounds in only 15 instances. We should emphasize that if the scenarios considered in both approaches are the same, Theorem 7 shows that the lower bound obtained by Algorithm 2 should outperform the finite-scenario approach.

Table 3 . 2 :

 32 Statistic of optimality gaps of instances in Class Two.

	Method	Mean	Standard deviation
	Algorithm 1	56.5417	83.8414
	Algorithm 2	57.7425	88.1209
	Finite-scenario approach 64.5980	114.8234
	To have a clearer comparison, we illustrate the optimality gaps in Figure 3.3. Remarkably,
	both algorithms exhibit better performance in nearly all instances compared to the finite-
	scenario approach (Figures 3.3a and 3.3b). Furthermore, as one can see in Figure 3.3c, the
	optimality gap of the solutions obtained by Algorithms 1 and 2 are close, and in all instances

(except two of them), Algorithm 1 provides a solution with a slightly lower optimality gap compared to Algorithm 2.

The average solution times for Algorithm 1, Algorithm 2, and finite-scenario approach are

Table 3 . 3 :

 33 Detailed numerical results from Class One.

	Case	LB 1	LB 2	LB 3	U B 8	U B 1	Case	LB 1	LB 2	LB 3	U B 8	U B 1
	1	259.1977 259.1977 259.1946 260.0564 261.3407	51	3.3127	3.3127	3.3122	3.3225	3.3274
	2	9.3817	9.3817	9.3658	9.6877	10.0478	52	0.4577	0.5206	0.5252	1.1068	3.6220
	3	6.9970	6.9935	6.7271	7.5588	7.9666	53	2.9971	2.9971	2.9971	2.9971	3.0049
	4	2.7486	2.7486	2.7103	2.9390	3.0800	54	0.8657	0.8657	0.8653	1.6291	1.9446
	5	11.0089	11.0090	10.8160	11.4931	11.8715	55	8.7115	8.7115	8.7114	8.7119	8.7119
	6	15.3520	15.3520	15.2586	16.3023	17.8020	56	0.8995	0.8865	1.2330	1.8994	3.1152
	7	-1.9373	-1.9373	-1.9373 -1.9357	-1.9357	57	3.3758	3.3751	3.3751	3.3934	3.4227
	8	9.3109	9.3109	9.3063	10.2061	11.1458	58	2.8508	2.8508	2.8508	2.8508	3.3457
	9	10.6770	10.6762	11.7674 13.5560	15.4325	59	3.4591	3.4590	3.4419	3.5102	3.5223
		5.4643	5.4643	5.3333	6.6699	8.1682	60	4.7327	4.7327	4.7325	10.3711	19.4164
		5.4997	5.4970	5.4996	5.5553	5.7042	61	2.1088	2.1088	1.9812	2.2950	2.4424
		4.8946	4.8946	4.4919	5.4370	5.6290	62	2.4899	2.4899	2.4305	2.6931	2.8786
		-1.7771	-1.2453	-1.2531	-0.7450	-0.2057	63	3.5704	3.5704	3.5606	4.3928	5.2596
		15.0970	15.0970	14.8494	15.7447	16.1069	64	2.4027	2.4027	2.4027	2.4027	2.4215
		3.1803	3.1803	3.1792	3.1816	3.1816	65	4.0104	4.0104	3.9697	4.0845	4.1758
		32.7964	32.7964 32.7964 32.7979	32.8014	66	3.4362	3.4362	3.3095	4.4646	5.5969
		0.1421	0.1421	0.0323	1.1248	2.3101	67	18.8952	18.8952	17.9105	20.1629	21.3240
		16.5824	16.5824	15.0801	18.8211	19.4832	68	2.8023	2.8023	2.8023	2.8025	2.9026
		3.6685	3.6685	3.3255	4.7357	5.8387	69	1.6128	1.5944	1.5914	1.9228	1.9755
		7.0912	8.6052	8.5969	8.9749	9.3419	70	3.9882	3.9882	3.9630	4.0116	4.0224
		49.5685	49.5685	49.5664	50.9667	52.7088	71	31.4786	31.4786	31.3828	32.6877	33.7343
		7.3621	7.3621	7.3552	8.8104	11.2659	72	756.1827 756.1827 756.1826 756.2022 756.2175
		21.5784	28.4078	28.3726	31.0675	38.7033	73	6.4255	6.4255	6.2120	6.9449	7.2463
		12.5946	12.5946	12.5854	15.6238	20.4960	74	2.4011	2.4010	2.4000	2.4714	2.6531
		14.1311	14.1311	14.1301	14.1403	14.1403	75	2.0766	2.0766	2.0765	2.3492	2.4106
		52.2638	52.2638	52.2504	53.0016	53.6820	76	3.0271	3.0215	3.1531	3.2083	3.5310
		-0.4110	-0.4110	-0.4118	-0.4073	-0.3732	77	2.2849	2.2849	2.2849	2.3563	2.4955
		393.0423 393.0423 377.7744 436.0650 452.3473	78	1.3092	1.3092	1.3092	1.3112	1.3126
		7.9651	7.9651	7.6756	9.2498	10.8485	79	7.8062	7.8062	5.9023	15.1441	23.1083
		30.2205	30.2205	28.6526	34.9758	38.2203	80	3.3318	3.4906	3.4497	3.8514	4.1593
		7.2094	7.2094	7.1337	7.3583	7.3583	81	2.6656	2.8999	2.8545	3.1747	3.6565
		6.6596	6.6595	6.6530	6.7380	6.9949	82	7.9201	7.9201	7.9107	7.9570	8.3552
		95.2210	95.2210	94.9450 102.2506 110.4956	83	4.1187	4.1080	3.9211	4.6071	4.9426
		21.5530	21.5530	21.5225	21.7216	21.9525	84	3.4734	3.4734	3.2243	3.7412	3.9954
		4.7314	4.7314	4.6987	4.8901	4.9057	85	3.5410	3.6188	3.5939	4.3623	5.8730
		18.2915	18.2916	18.2899	18.5365	19.1278	86	11.5812	11.5660	10.9026	13.7476	15.7727
		5.8375	16.7701	16.7202	17.6550	18.3373	87	10.9663	10.9663	10.9658	10.9887	10.9990
		5.6850	7.2390	6.4109	9.2046	11.3974	88	14.1618	14.1618	14.1615	14.1639	14.1641
		86.3898	86.3898	86.3881	86.5066	86.5195	89	5.0708	5.0023	5.0490	6.0166	7.0369
		-0.3083	-0.3083	-0.3084	-0.1944	0.0310	90	4.8473	4.8461	4.8483	5.5185	5.8588
		75.7971	75.7971	75.7851	76.0008	76.6293	91	9.3160	9.3160	9.2139	9.6205	10.2391
		10.9392	10.9392	10.8825	12.9686	18.0775	92	45.8951	45.8951	45.3398	48.8046	50.3318
		32.2960	32.2960	32.2940	32.3780	32.3964	93	1.9520	1.9519	3.8607	4.0389	4.4740
		-0.6766	-0.6766	-0.6766 -0.6766	-0.6185	94	0.7561	0.7561	0.6361	1.3990	2.2513
		1.1652	1.1652	1.1425	1.3013	1.4361	95	-0.7423	-0.6797	-0.6980	-0.4079	0.0277
		2.5419	2.5419	2.5418	2.8630	3.2250	96	22.3622	22.3622	22.2758	23.3531	23.9807
		1.0582	1.0582	1.0431	1.3847	2.2834	97	3.6372	5.7130	5.6500	6.8904	7.9793
		3.6334	3.6334	3.5831	4.1290	4.8998	98	6.6315	6.6315	6.3300	6.9888	7.1655
		22.1946	22.1946	22.1167	24.3342	27.4000	99	18.9985	18.9985	18.9977	19.5478	20.0648
		3.3475	3.3475	3.3208	3.4439	3.4843	100	2.7358	2.7358	2.7216	2.8101	2.8288

Note. The column Case contains the instance number, columns LB 1 , LB 2 , and LB 3 are the lower bounds obtained by Algorithm 1, 2, and the finite-scenario approach, respectively, and the columns U B 1 and U B 8 are the upper bounds obtained by perspectification approach and 8-adaptability approach respectively. The accuracy digit is four. In this table, for each instance, the best lower bound is in boldface.

Table 3 . 4 :

 34 Detailed numerical results from Class Two.

	Case	LB 1	LB 2	LB 3	U B 1	Case	LB 1	LB 2	LB 3	U B 1
	1	3.9001	3.8934	3.8854	4.8279	51	-2.9744 -2.9971 -3.0021 -1.9376
	2	9.6268	9.6178	9.6015 10.4601	52	3.5619	3.5499	3.5264	4.6196
	3	1.6344	1.6123	1.6121	2.8872	53	-1.7460 -1.7904 -1.8189 -0.3012
	4	10.8829 10.8773 10.8506 11.6009	54	3.2074	3.1680	3.1807	4.5110
	5	12.2019 12.1472 12.1530 13.5152	55	-1.0219 -1.0273 -1.0839	0.0784
	6	2.7891	2.7762	2.7543	3.8914	56	-5.9077 -5.9099 -6.0075 -4.5074
	7	4.2798	4.2738	4.2123	5.3923	57	9.0173	8.9964	9.0082	10.0026
	8	-1.6253 -1.6291 -1.6727 -0.7387	58	-5.3944 -5.4257 -5.4375 -4.3260
	9	3.5420	3.5370	3.5318	4.2847	59	5.9016 5.9016	5.8349	6.3315
		0.2770	0.2365	0.1944	1.6372	60	0.9850	0.9656	0.8858	2.2989
		-1.3185 -1.3505 -1.3593 -0.3106	61	7.2530	7.2352	7.2083	8.2546
		-2.0551 -2.1027 -2.1003 -0.5346	62	0.5393	0.5800	0.5150	2.0891
		8.1494	8.1280	8.1285	8.9722	63	5.2223	5.1960	5.1005	6.5493
		8.3511	8.3408	8.3322	8.8412	64	-8.0248 -8.0617 -8.0568 -6.4983
		-1.9698 -2.0357 -1.9960 -0.9572	65	7.0972	7.0572	6.9516	8.5001
		7.3853	7.3711	7.3958	8.3874	66	-0.4458 -0.5322 -0.5025	1.1889
		16.0063 15.9723 15.9882 17.1185	67	-0.5969 -0.6999 -0.6607	1.2182
		2.9578	2.9267	2.9187	4.1038	68	-1.1199 -1.1293 -1.1896 -0.0657
		2.4222	2.4132	2.4054	3.4077	69	2.2536	2.2530	2.1678	3.1326
		-1.6671 -1.6730 -1.7801 -0.5029	70	7.2135	7.2085	7.1412	8.6105
		1.0836	1.0649	1.0506	1.8063	71	9.6860	9.6677	9.6259	10.3959
		9.8687	9.8084	9.8125 11.3247	72	4.5704	4.5428	4.5342	5.5110
		0.6145	0.5376	0.5527	1.9393	73	-3.7698 -3.7862 -3.7970 -2.8077
		-9.4925 -9.5133 -9.5277 -8.5633	74	-5.0022 -5.0044 -5.1230 -3.4930
		2.1541	2.1525	2.0924	2.9331	75	-1.3936 -1.4183 -1.4138 -0.2234
		9.5053	9.4669	9.4446 10.8387	76	5.3090	5.2698	5.2504	6.7112
		-1.2397 -1.2863 -1.3041 0.8808	77	-2.0718 -2.0727 -2.0879 -1.5332
		10.8428 10.8244 10.7536 11.8421	78	16.0217 16.0155 15.9792 16.7758
		4.6773	4.6652	4.6285	5.9266	79	8.1416	8.1328	8.1075	8.9623
		9.9538	9.9512	9.8376 11.3559	80	0.7576	0.7532	0.7278	1.4189
		0.6215	0.6172	0.5307	1.6204	81	4.5890	4.5885	4.4751	5.6660
		4.5631	4.5559	4.5147	5.2915	82	6.3865	6.3751	6.3194	7.4986
		7.0305	6.9845	6.9944	8.0498	83	6.1873	6.1780	6.0546	7.2406
		9.9680	9.8466	9.9100 11.3081	84	2.9913	2.9078	2.9352	4.7038
		0.8044	0.7829	0.7239	2.0848	85	10.6753 10.6411 10.6368 11.7620
		-4.8340 -4.9150 -4.8925 -3.5569	86	-7.7191 -7.7389 -7.7566 -6.2191
		4.9906	4.9789	4.9619	5.9426	87	11.0850 11.0523 11.0027 12.4703
		-7.6116 -7.6907 -7.7910 -6.0688	88	10.3312 10.2796 10.3872 12.3348
		15.8386 15.8279 15.8049 16.7978	89	8.9459	8.9313	8.8954	10.1933
		0.3786	0.3694	0.2224	1.7918	90	7.6131	7.6069	7.5995	8.3429
		-2.2577 -2.2625 -2.3401 -0.9587	91	4.7490	4.6998	4.6915	5.9225
		0.8659	0.8557	0.8168	1.9483	92	10.1188 10.0803 10.0249 11.2766
		12.2575 12.2277 12.2335 13.1937	93	-1.0054 -1.0080 -1.0731 -0.2399
		4.7063	4.7037	4.6871	5.1994	94	-2.3783 -2.3824 -2.5552 -1.1306
		7.1076	7.0944	7.0682	8.0319	95	1.3148	1.2884	1.2675	2.9579
		-1.0208 -1.0213 -1.3427 0.4856	96	-2.4070 -2.4142 -2.4486 -1.4270
		5.6107	5.5709	5.5854	6.8776	97	3.6744	3.6589	3.6323	4.6726
		7.9571	7.9486	7.9025	9.0604	98	1.8353	1.8244	1.7627	3.2556
		5.8116	5.8047	5.7952	6.4533	99	-5.3745 -5.4029 -5.4231 -4.3001
		2.9529	2.9124	2.8474	4.2576	100	7.8266	7.8138	7.7616	8.7882

Note. The column Case contains the instance number, columns LB 1 , LB 2 , and LB 3 are the lower bounds obtained by Algorithm 1, 2, and the finite-scenario approach, respectively, and the columns U B 1 is the upper bound obtained by perspectification approach. In this table, for each instance, the best lower bound is in boldface.

  and b ∈ R mx are given. From Corollary 4.2.2 and Table 4.8, we have the following linear ARO reformulation of (4.22):

Table 4 . 1 :

 41 Optimality gaps and solver times of concave minimization instances from[START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF].

		Static ARO-QO Algorithm	Partial ARO-QO Algorithm	Affine ARO-QO Algorithm	Selvi et al. method [105]	Gurobi	CPLEX
	Problem	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time	Gap	Time
	#1 (mx = 10, nx = 20)	30.38	0.08	27.97	0.15	0.02	1.05	77.85	0.17	0.00	0.11	0.00	0.12
	#2 (mx = 10, nx = 20)	9.13	0.08	8.94	0.15	0.01	1.06	34.77	0.15	0.00	0.12	0.00	0.11
	#3 (mx = 15, nx = 10)	0.42	0.04	0.29	0.06	0.00	0.12	1.68	0.15	0.00	0.03	0.00	0.06
	#4 (mx = 62, nx = 50)	0.12	0.27	0.09	0.48	0.00	11.46	1.10	1.32	0.00	0.56	0.00	1.56
	#5 (mx = 130, nx = 100) 0.08	1.28	0.07	4.81	0.00	900.48	2.15	8.27	0.00	12.03	0.00	43.64
	#6 (mx = 240, nx = 200) 0.02	8.98	0.02	44.83	-	3000*	1.52	59.60	0.00 528.99	0.00 1165.38
	#7 (mx = 280, nx = 240) 0.04	30.47	0.04	104.90	-	3000*	5.71	80.90	15.22 3000*	14.17 3000*

Table 4 . 2 :

 42 Statistic of optimality gaps and solver times for randomly generated concave minimization instances.

		ARO-QO Algorithm	Selvi et al. method [105]	Gurobi		CPLEX
	Group	Gap	Time	Gap	Time	Gap	Time	Gap	Time

Table 4 . 3 :

 43 Statistic of solution gaps and solution times of (StQO) instances in Class One.

		ARO-QO Algorithm		Gurobi			CPLEX		IPOPT
	Class One	SGap	Time	SGap1 Time1 SGap2 Time2	SGap1 Time1 SGap2 Time2	SGap Time
	Mean	3.11	0.70	3.89	0.65	0.00	22.28	0.90	0.73	0.00	226.46	11.09 0.04
	Standard deviation 6.12	0.60	10.22	0.45	0.00	111.73	1.94	0.61	0.04	714.40	20.78 0.02
	Notes. Test instances from [37].

Table 4 . 4 :

 44 Statistic of solution gaps and solution times of (StQO) instances in Class Two.

		ARO-QO Algorithm		Gurobi			CPLEX		IPOPT
	Class Two	SGap	Time	SGap1 Time1 SGap2 Time2	SGap1 Time1 SGap2 Time2	SGap Time
	Mean	3.33	1.08	8.56	1.07	0.05	233.36	1.88	1.11	0.02	721.48	14.03 0.09
	Standard deviation 6.36	0.96	15.34	0.97	0.32	743.15	4.14	0.98	0.10	1258.62	21.98 0.05

Table 4 .

 4 5 presents a detailed evaluation of the solution gap (SGap) percentages obtained

	The ARO-QO Algorithm demonstrates consistently low solution gap percentages in various
	large-sized groups, especially notable in groups 3, 5, 7, and 12. Within a 3,000-second span,
	Gurobi shows commendable performance in groups 1, 8, 10, and 11, while CPLEX excels
	in groups 2 and 4. The local solver IPOPT in class 6 has good performance. However,
	CPLEX exhibits less satisfactory performance in groups 7 to 12. Moreover, across all groups,
	the ARO-QO Algorithm significantly surpasses the global solvers in terms of efficiency,
	considering its shorter time requirement. A minimal SGap is indicative of the algorithm's
	proficiency in approximating solutions that are closer to the optimal or best-known solutions,
	an essential objective in optimization problems. Conclusively, the ARO-QO Algorithm stands
	out for having the lowest mean gap percentage across all evaluated problems, highlighting
	its superior performance.

by various algorithms in multiple large-sized instances. The table outlines the mean and standard deviation of the SGap for each algorithm, providing a clear perspective on their average effectiveness.

Even though our lower bound were loose for small instances based on Table

4

.11, it is evident that these bounds surpass the lower bounds in groups 10, 11, and 12, thereby outperforming the global solvers CPLEX and Gurobi overall.

Table 4 . 7 :

 47 Time Results for concave quadratic minimization test instances from[START_REF] Selvi | Convex maximization via adjustable robust optimization[END_REF].Notes. In this table, the 'LB' column represents the lower bound time, the 'UB' column displays the upper bound time, and the 'Time' column indicates the total corresponding solver times. Additionally, the columns for global solvers also report the time taken by Gurobi and CPLEX solvers to reach bounds.

		Static ARO-QO	Partial affine ARO-QO	Full affine ARO-QO	Selvi et al. method [105]	Global Solver
	Problem	LB	UB Time	LB	UB	Time	LB	UB Time	LB	UB	Time	Gurobi CPLEX
	#1 (mx = 10, nx = 20)	0.02 0.06 0.08	0.07	0.08	0.15	0.94	0.11	1.05	0.07 0.10	0.17	0.11	0.12
	#2 (mx = 10, nx = 20)	0.02 0.06 0.08	0.07	0.08	0.15	0.95	0.11	1.06	0.05 0.10	0.15	0.12	0.11
	#3 (mx = 15, nx = 10)	0.01 0.03 0.04	0.01	0.05	0.06	0.04	0.08	0.12	0.06 0.09	0.15	0.03	0.06
	#4 (mx = 62, nx = 50)	0.11 0.16 0.27	0.26	0.22	0.48	11.06 0.40 11.46	0.89 0.43	1.32	0.56	1.56
	#5 (mx = 130, nx = 100) 0.88 0.40 1.28	4.25	0.56	4.81	899.42 1.06 900.48	7.07 1.20	8.27	12.03	43.64
	#6 (mx = 240, nx = 200) 7.49 1.49 8.98	43.15 1.68	44.83	3000*	-	3000*	56.08 3.82	59.60	528.99 1165.38
	#7 (mx = 280, nx = 240) 28.44 2.04 30.47	102.52 2.38 104.90	3000*	-	3000*	76.44 4.46	80.90	3000*	3000*

Table 4 . 8 :

 48 Other classes of ARO reformulations of indefinite QO problem.

	Feasible Region	Type	ARO Problem
		I

Table 4 . 9 :

 49 Other classes of ARO reformulations of concave QO minimization.

Table 4 .

 4 10: Detailed result on concave quadratic minimization.

	Problem (size)	ARO-QO Algorithm		Selvi et al. method [105]		Gurobi			CPLEX
		LB	UB	Time	LB	UB	Time	LB	UB	Time	LB	UB	Time
	# 1 (mx = 100, nx = 50)	-21226.05	-20906.11	0.55	-23918.61	-20906.11	2.19	-20907.98	-20906.11	46.51	-20908.66	-20906.11	20.31
	# 2 (mx = 100, nx = 50)	-19999.47	-19801.12	0.54	-22281.13	-19801.12	2.21	-19801.12	-19801.12	142.38	-10803.73	-19801.12	16.31
	# 3 (mx = 100, nx = 50)	-21924.71	-21516.59	0.53	-24468.84	-21514.54	1.93	-21518.39	-21516.59	36.52	-21520.18	-21516.59	16.50
	# 4 (mx = 100, nx = 50)	-19796.92	-19504.56	0.55	-22192.55	-19504.56	2.01	-19505.00	-19504.46	37.70	-19508.39	-19504.56	14.43
	# 5 (mx = 100, nx = 50)	-19938.54	-19588.64	0.55	-22004.72	-19617.58	2.65	-19619.28	-19617.58	69.52	-19620.01	-19617.58	17.07
	# 6 (mx = 150, nx = 100)	-43503.68	-42817.73	2.90	-48917.86	-42817.73	8.97	-42821.91	-42817.73	398.47	-42824.07	-42817.73	421.30
	# 7 (mx = 150, nx = 100)	-44023.17	-43288.39	2.67	-49478.74	-43295.39	9.09	-43298.91	-43295.39 1138.38	-43304.86	-43295.39	523.09
	# 8 (mx = 150, nx = 100)	-44509.83	-43708.24	2.94	-50215.65	-43746.44	9.61	-43753.45	-43749.45	832.73	-43756.27	-43749.36	578.56
	# 9 (mx = 150, nx = 100)	-40043.22	-39464.10	2.53	-44570.54	-39479.17	8.72	-39479.86	-39477.46 1195.30	-39489.34	-39479.17	228.30
	# 10 (mx = 150, nx = 100) -50419.80	-49987.08	2.79	-56409.90	-49987.08	8.59	-49991.33	-49987.08	315.52	-49992.08	-49987.08	161.97
	# 11 (mx = 200, nx = 100) -36365.81	-35824.95	4.47	-41378.67	-35824.95	18.51	-35828.39	-35824.95	484.97	-35829.88	-35824.95	366.40
	# 12 (mx = 200, nx = 100) -36273.69	-35835.66	4.32	-41252.42	-35828.10	18.44	-35839.10	-35835.66	726.90	-35841.34	-35835.67	501.42
	# 13 (mx = 200, nx = 100) -34758.56	-34055.57	4.45	-39847.86	-34055.40	19.59	-34057.88	-34055.76 1636.05	-34135.30	-34055.76	301.26
	# 14 (mx = 200, nx = 100) -35864.55	-35262.45	4.58	-41288.01	-35289.22	16.38	-35310.24	-35289.70	3,000*	-35410.68	-35289.49	3,000*
	# 15 (mx = 200, nx = 100) -39351.10	-38553.98	4.67	-45260.71	-38619.98	16.24	-38628.29	-38624.93 2165.88	-38631.30	-38624.93 2256.70
	# 16 (mx = 250, nx = 200) -114818.87 -113258.29 14.88	-129138.55 -113258.34	48.23	-113269.93	-113258.34 3,000*	-113282.68	-113258.34 3,000*
	# 17 (mx = 250, nx = 200) -92364.54	-90802.03	13.38	-103508.71	-90833.68	47.94	-109407.37	-90185.44	3,000*	-91059.89	-90848.24	3,000*
	# 18 (mx = 250, nx = 200) -102592.36 -101763.08 16.13	-115061.49 -101763.08	48.82	-102331.34	-101763.08 3,000*	-101797.00	-101763.08 2638.61
	# 19 (mx = 250, nx = 200) -110848.56 -109342.56 16.27	-124919.22 -109342.56	52.02	-121382.85	-109342.56 3,000*	-109354.94	-109342.56 3,000*
	# 20 (mx = 250, nx = 200) -124939.05 -122854.09 15.89	-145278.15 -122854.09	59.25	-148108.59	-122854.09 3,000*	-123861.93	-122854.09 3,000*
	# 21 (mx = 300, nx = 200) -90379.80	-89076.48	24.68	-104968.70	-89054.41	83.60	-115882.61	-89076.79	3,000*	-89728.32	-89076.86	3,000*
	# 22 (mx = 300, nx = 200) -83366.49	-82259.34	26.20	-95965.30	-82256.29	97.87	-102793.52	-82259.34	3,000*	-82661.52	-82259.34	3,000*
	# 23 (mx = 300, nx = 200) -82027.18	-81016.91	24.37	-93726.28	-81008.71	138.95	-97987.79	-81016.91	3,000*	-81178.61	-81016.91	3,000*
	# 24 (mx = 300, nx = 200) -84667.10	-83459.67	24.30	-98686.53	-83457.97	102.20	-105898.98	-83459.67	3,000*	-83953.38	-83459.67	3,000*
	# 25 (mx = 300, nx = 200) -81894.50	-80966.99	23.75	-94430.77	-80966.99	82.63	-102639.56	-80966.99	3,000*	-81059.07	-80966.99	3,000*
	# 26 (mx = 350, nx = 300) -171137.64 -168437.60 50.91	-194844.52 -168438.92	170.15	-210038.17	-168194.52 3,000*	-5605813.93 -168194.52 3,000*
	# 27 (mx = 350, nx = 300) -164141.28 -161444.77 44.66	-186697.76 -161462.55	158.70	-205946.65	-161142.30 3,000*	-5128394.30 -161463.49 3,000*
	# 28 (mx = 350, nx = 300) -158477.21 -156089.67 59.39	-184476.06 -156064.84	146.55	-196949.54	-156089.67 3,000*	-372519.82	-156089.67 3,000*
	# 29 (mx = 350, nx = 300) -163020.17 -159968.26 37.23	-186943.98 -159857.19	149.84	-192162.18	-159559.82 3,000*	-295635.77	-159985.69 3,000*
	# 30 (mx = 350, nx = 300) -179027.10 -176570.47 59.21	-203873.39 -176564.79	144.81	-211848.25	-176570.47 3,000*	-694837.69	-176570.47 3,000*
	# 31 (mx = 400, nx = 300) -130525.34 -128324.26 80.92	-151936.50 -1238322.77 262.92	-171188.37	-128323.25 3,000*	-5164971.42 -128310.81 3,000*
	# 32 (mx = 400, nx = 300) -122185.75 -120302.84 71.80	-142516.23 -120310.31	230.07	-165499.48	-120287.00 3,000*	-5232838.82 -120308.58 3,000*
	# 33 (mx = 400, nx = 300) -120417.62 -118873.22 76.78	-139741.15 -118868.50	220.00	-163195.52	-118573.02 3,000*	-5201602.88 -118873.22 3,000*
	# 34 (mx = 400, nx = 300) -121135.65 -118904.01 70.01	-140455.45 -118869.00	281.14	-166977.00	-118898.47 3,000*	-5223379.15 -118898.58 3,000*
	# 35 (mx = 400, nx = 300) -135783.77 -134180.30 84.87	-157376.81 -134180.24	287.99	-182483.43	-134135.73 3,000*	-5207186.87 -134180.24 3,000*
	# 36 (mx = 450, nx = 400) -239708.24 -236691.08 69.61	-267620.18 -236691.08	292.47	-308141.60	-236632.22 3,000*	-1.02268×10 9	NA	3,000*
	# 37 (mx = 450, nx = 400) -219201.30 -215007.32 97.31	-252589.43 -215005.17	308.21	-401192.82	-213758.53 3,000*	-1.02521×10 9	NA	3,000*
	# 38 (mx = 450, nx = 400) -231523.46 -227609.94 94.57	-265032.88 -227619.86	307.32	-322874.67	-169857.26 3,000*	-1.02639×10 9	NA	3,000*
	# 39 (mx = 450, nx = 400) -225364.42 -221535.08 86.43	-258200.84 -221537.39	291.19	-623239.89	-169708.85 3,000*	-1.02626×10 9	NA	3,000*
	# 40 (mx = 450, nx = 400) -248061.41 -243641.36 129.44	-286303.36 -243639.15	278.68	-353455.02	-161208.64 3,000*	-1.02815×10 9	NA	3,000*
	# 41 (mx = 500, nx = 400) -162882.47 -160300.05 176.57	-191340.70 -160278.14	559.34	-604066.17	-159909.39 3,000*	-1.02268×10 9	NA	3,000*
	# 42 (mx = 500, nx = 400) -172886.97 -169806.25 164.70	-202411.67 -169805.29	586.96	-267361.99	-169267.40 3,000*	-1.02521×10 9	NA	3,000*
	# 43 (mx = 500, nx = 400) -161267.75 -158235.56 165.39	-187056.39 -158223.56	555.60	-425931.05	-110899.09 3,000*	-1.02626×10 9	NA	3,000*
	# 44 (mx = 500, nx = 400) -173508.69 -170210.36 156.92	-203828.67 -170199.68	534.90	-350152.46	-169666.30 3,000*	-1.02626×10 9	NA	3,000*
	# 45 (mx = 500, nx = 400) -177296.71 -173532.58 161.32	-208668.91 -173433.65	546.23	-404418.89	-173127.83 3,000*	-1.02815×10 9	NA	3,000*
	# 46 (mx = 550, nx = 500) -254620.02 -250228.59 140.01	-292466.45 -250227.15	269.22	-386062.82	-165730.74 3,000*	-2.00381×10 9	NA	3,000*
	# 47 (mx = 550, nx = 500) -283033.14 -278009.50 143.87	-326626.69 -277934.32	263.27	-13261942.44 -111018.29 3,000*	-1.99773×10 9	NA	3,000*
	# 48 (mx = 550, nx = 500) -267476.07 -262965.87 144.32	-305398.64 -262965.87	270.19	-738574.46	-153507.88 3,000*	-2.00129×10 9	NA	3,000*
	# 49 (mx = 550, nx = 500) -268766.57 -264084.34 160.95	-309881.77 -264016.01	244.89	-449419.26	-197858.04 3,000*	-2.00369×10 9	NA	3,000*
	# 50 (mx = 550, nx = 500) -293060.47 -287527.81 129.89	-335443.85 -287498.36	236.11	-423238.78	-191541.98 3,000*	-2.00595×10 9	NA	3,000*
	# 51 (mx = 600, nx = 500) -217416.92 -213705.89 366.84	-256282.73 -213683.16	515.61	-1127074.64 -166459.89 3,000*	-2.00381×10 9	NA	3,000*
	# 52 (mx = 600, nx = 500) -230918.43 -227145.96 336.32	-270398.12 -227144.69	514.71	-525624.12	-151916.19 3,000*	-1.99773×10 9	NA	3,000*
	# 53 (mx = 600, nx = 500) -211637.44 -207961.86 389.37	-247423.31 -207918.89	484.56	-11832043.00 -111613.71 3,000*	-2.00129×10 9	NA	3,000*
	# 54 (mx = 600, nx = 500) -240876.42 -236788.53 379.21	-283777.93 -236783.30	517.46	-8878852.73 -111854.65 3,000*	-2.00369×10 9	NA	3,000*
	# 55 (mx = 600, nx = 500) -220691.08 -217845.10 341.90	-257822.62 -217845.30	490.03	-8732517.01 -108571.64 3,000*	-2.00595×10 9	NA	3,000*
	# 56 (mx = 650, nx = 600) -391433.86 -384919.90 326.00	-455449.56 -384880.07	483.69	-4971784.16 -134292.50 3,000*	-3.45702×10 9	NA	3,000*
	# 57 (mx = 650, nx = 600) -403904.96 -398018.32 239.91	-463747.58 -398018.32	445.72	-14155023.89 -146383.96 3,000*	-3.45533×10 9	NA	3,000*
	# 58 (mx = 650, nx = 600) -329953.17 -324832.60 254.45	-381469.39 -324788.61	416.11	-3241488.76 -127909.30 3,000*	-3.45744×10 9	NA	3,000*
	# 59 (mx = 650, nx = 600) -344749.19 -339970.74 251.05	-394538.13 -339907.86	406.65	-18755129.41 -134434.84 3,000*	-3.46041×10 9	NA	3,000*
	# 60 (mx = 650, nx = 600) -344458.62 -338774.49 246.62	-397930.12 -338767.55	370.98	-20611553.36 -150155.61 3,000*	-3.46327×10 9	NA	3,000*
	# 61 (mx = 700, nx = 600) -282346.92 -278274.80 636.29	-332396.86 -278196.53	910.18	-12550163.40 -146157.71 3,000*	-3.45702×10 9	NA	3,000*
	# 62 (mx = 700, nx = 600) -255125.93 -252049.75 588.72	-297435.47 -252019.04	734.42	-13717479.02 -135118.87 3,000*	-3.45533×10 9	NA	3,000*
	# 63 (mx = 700, nx = 600) -268578.12 -265180.15 551.67	-310071.57 -265179.26	751.89	-17742893.76 -136924.49 3,000*	-3.45744×10 9	NA	3,000*
	# 64 (mx = 700, nx = 600) -271077.81 -265854.53 678.98	-321255.53 -265784.91	847.24	-13671678.23 -137967.52 3,000*	-3.46041×10 9	NA	3,000*
	# 65 (mx = 700, nx = 600) -265786.65 -261964.40 633.24	-312133.44 -261960.96	863.81	-13511151.74 -134274.22 3,000*	-3.46327×10 9	NA	3,000*
	# 66 (mx = 750, nx = 700) -453938.25 -445745.52 334.48	-522337.64 -445739.49	500.72	-30556778.77	NA	3,000*	-5.49163×10 9	NA	3,000*
	# 67 (mx = 750, nx = 700) -392258.28 -383657.82 362.86	-449380.91 -385644.74	455.94	-29261626.30 -161772.44 3,000*	-548510×10 9	NA	3,000*
	# 68 (mx = 750, nx = 700) -446958.57 -441833.49 350.21	-512918.35 -441818.13	559.76	-29099763.10	NA	3,000*	-5.48474×10 9	NA	3,000*
	# 69 (mx = 750, nx = 700) -437897.81 -430075.17 332.64	-507811.80 -429904.39	501.20	-28450230.87	NA	3,000*	-5.48958×10 9	NA	3,000*
	# 70 (mx = 750, nx = 700) -396137.17 -388867.26 336.34	-461346.54 -388657.60	497.99	-28394163.71	NA	3,000*	-5.50234×10 9	NA	3,000*
	# 71 (mx = 800, nx = 700) -311760.73 -306985.03 987.30	-366078.98 -306837.21	938.07	-28336162.67	NA	3,000*	-5.49163×10 9	NA	3,000*
	# 72 (mx = 800, nx = 700) -331384.65 -326264.31 972.63	-392327.23 -326243.53	950.99	-29520962.09	NA	3,000*	-548510×10 9	NA	3,000*
	# 73 (mx = 800, nx = 700) -302347.42 -297341.90 925.81	-358956.95 -297338.12	939.47	-28577654.37	NA	3,000*	-5.48474×10 9	NA	3,000*
	# 74 (mx = 800, nx = 700) -317298.48 -312825.99 802.18	-371677.77 -312807.92 2086.76	-29767062.12	NA	3,000*	-5.48958×10 9	NA	3,000*
	# 75 (mx = 800, nx = 700) -325810.25 -322123.47 845.32	-376710.09 -322132.66	906.84	-28979308.79	NA	3,000*	-5.50234×10 9	NA	3,000*

Table 4 .

 4 11: Detailed numerical results on standard quadratic optimization. Abbas Khademi (Shiraz, 1993) received his Bachelor's degree in Mathematics and Applications from Shiraz University, graduating as the 1st Rank student in 2016. He then pursued a Master's degree in Applied Mathematics (Operations Research and Optimization) from the University of Tehran, again graduating as the 1st Rank student in 2018. Following that, he embarked on a PhD journey in Applied Mathematics during which he visited as a visiting researcher at Eindhoven University of Technology from mid-March to mid-September 2021, within the duration of his PhD period.This thesis presents two significant contributions to mathematical programming: Firstly, a novel dual-based cutting plane method is proposed for solving nonlinear Adjustable Robust Optimization (ARO) problems, addressing uncertainty in sequential decision-making. The study involves a general nonlinear ARO model with uncertain objectives and constraints. Fenchel's duality is applied to the wait-and-see variable, yielding an equivalent dual formulation. Algorithms are developed to find lower bounds on the optimal objective value, showcasing the approach's efficacy in producing locally robust solutions with acceptable optimality gaps. Secondly, a new reformulation technique transforms Quadratic Optimization (QO) problems into maximization adjustable robust optimization formulations. This innovative approach shifts the complexity from the original QO problem to the equivalent ARO problem. Numerical experiments validate the effectiveness of the ARO-based method in solving non-convex QO problems, offering high-quality solutions at reasonable computational costs. This connection between QO and ARO presents a fresh perspective on addressing non-convex QO challenges and opens avenues for future research in mathematical optimization.

			ARO-QO Algorithm			Gurobi				CPLEX			IPOPT
	Problem	LB1	LB2	UB	Time	LB1	UB1	LB2	UB2	LB1	UB1	LB2	UB2	UB	Time
	#1 100(0.50)	-141.3034 -70.4688 -6.1407 3.21	-8.3740	-6.0793	-6.8351	-6.1300	-19568.7553	1.4379	-9.4376	-5.8325	-6.0793	0.18
	#2 100(0.50)	-129.2121 -64.4946 -6.0452 1.41	-206.8990	-6.2006	-7.0153	-6.2006	-20689.9017	0.1291	-9.6186	-6.0611	-6.2006	0.17
	#3 100(0.50)	-128.5047 -64.1669 -5.9070 3.73	-93.9099	-5.9070	-7.1628	-5.9070	-20289.6140	1.9297	-9.2160	-5.9789	-5.7568	0.15
	#4 100(0.50)	-132.9374 -66.3307 -5.3757 2.34	-105.4804	-5.4065	-7.0147	-5.9348	-19603.0830	0.3966	-9.1551	-5.9122	-5.7282	0.19
	#5 100(0.50)	-132.0628 -65.9230 -6.1510 1.96	-208.1827	-5.5674	-7.1317	-6.0872	-20818.2732	1.4012	-9.4403	-6.0872	-5.7499	0.15

February 6, 2024

Acknowledgments

Chapter 4

Quadratic Optimization Through the Lens of

Adjustable Robust Optimization

Ralph Tyrrell Rockafellar:

"The great watershed in optimization isn't between linearity and nonlinearity, but convexity and non-convexity."

Introduction

Various practical problems in different domains, including financial mathematics [START_REF] Markowitz | Protfilio selection[END_REF], machine learning [START_REF] Cevikalp | Local classifier weighting by quadratic programming[END_REF], resource allocation [START_REF] Ibaraki | Resource allocation problems: algorithmic approaches[END_REF], computer vision [START_REF] Bhanja | Non-boolean computing with nanomagnets for computer vision applications[END_REF], game theory [START_REF] Bomze | Regularity versus degeneracy in dynamics, games, and optimization: a unified approach to different aspects[END_REF], robotic systems [START_REF] Khadivar | Self-correcting quadratic programming-based robot control[END_REF], graph theory [START_REF] Gibbons | Continuous characterizations of the maximum clique problem[END_REF], and image processing [START_REF] Bulo | Graph-based quadratic optimization: A fast evolutionary approach[END_REF], to mention few, can be formulated as quadratic optimization problems. Thus, developing efficient techniques to solve general quadratic optimization problems is of great importance.

Let us consider a quadratic optimization (QO) problem of the form:

where X ⊆ R nx is a nonempty convex set, Q ∈ R nx×nx is a real matrix, and c ∈ R nx is a real vector. Without loss of generality, we assume that Q is a symmetric matrix. If Q is a positive semi-definite matrix, we have a convex QO, which is solvable in polynomial time [START_REF] Kozlov | The polynomial solvability of convex quadratic programming[END_REF][START_REF] Renegar | A mathematical view of interior-point methods in convex optimization[END_REF]. In contrast, even when Q has only one negative eigenvalue, (QO) is NP-hard [START_REF] Pardalos | Quadratic programming with one negative eigenvalue is NP-hard[END_REF].

Besides, identifying local minimizers of (QO) over a polyhedron is not simpler than finding global minimizers from a complexity perspective [START_REF] Ahmadi | On the complexity of finding a local minimizer of a quadratic function over a polytope[END_REF].

often associated with large-scale optimization problems.

We present an ARO-based approach designed to find a good candidate solution for the QO problem. The "ARO-QO Algorithm" provides the pseudo-code for executing this procedure.

ARO-Based Algorithm to Solve QO (ARO-QO Algorithm)

Input: Matrix Q, vector c, matrix A, and vector b. (

Step 2) Generation of Worst-Case Scenarios: Generate a finite set of worst-case scenarios by substituting the optimal decision rule into (4.13).

(

Step 3) Set Initial Point: Select from these scenarios the one that yields the best objective value for the original QO problem. Denote this point by x (0) .

(Step 4) Improve the Initial Solution: Execute the mountain climbing algorithm starting with the initial solution x (0) : Output: Final solution candidate x * ∶= x (end) , and the corresponding upper-bound

Numerical Experiments

In this section, we conduct a comprehensive numerical experiment to evaluate the efficacy of ARO-QO Algorithm. The efficiency of a particular bound on the optimal value of a mathematical optimization problem is influenced by two key aspects: the precision of the generated bound and the required computational time.

achieving the best solutions. While IPOPT shows the fastest solution times, it presents significantly higher mean solution gap values in both classes. This situation reflects a trade-off between speed and accuracy. Currently, it is apparent that global solvers are generally effective in handling small-sized problems.

The next step involves comparing instances of larger sizes. We consider 12 groups of instances with the dimension n x taking values in {100, 300, 500, 700}. Since the density of the matrices may also affect the performance of the considered solution methods, we examine three density values for each dimension -50%, 75%, and 90% -for the matrix Q in the objective function.

For these test problems, some are sourced from [START_REF] Liuzzi | A new branch-and-bound algorithm for standard quadratic programming problems[END_REF], while others are generated using the pattern described in [START_REF] Liuzzi | A new branch-and-bound algorithm for standard quadratic programming problems[END_REF] and [START_REF] Scozzari | A clique algorithm for standard quadratic programming[END_REF].

In Table 4.5, the average solution gaps for each instance group are provided (the details can be found in Table 4.11). Notes. In this table, the first column presents the problem numbers along with their corresponding dimensions.

For each problem, we applied the ARO-QO Algorithm: one with a full static decision rule, another with a partial affine decision rule, and the last one with a full affine decision rule on adjustable variables. In each approach, the 'LB' column represents the lower bound values, the 'UB' column displays the upper bounds.

Notes. This table presents problem numbers, dimensions, and matrix densities in the first column. For the ARO-QO Algorithm, 'LB1', 'LB2', 'UB', and 'Time' represent the lower bounds with partial decision rules on the ARO version, the upper bound values, and the computation times of all solvers, respectively. The results for Gurobi and CPLEX are divided into four subcolumns: the first two show bounds within the time limit required by the ARO-QO Algorithm, while the last two display bounds within a fixed 3,000-second limit.

The IPOPT columns detail the upper bounds and the solver times achieved by IPOPT solvers. The 'NA' indicates the absence of a feasible solution within the given time.

Chapter 5

Conclusions and Future Research

Pliny the Elder:

"The only certainty is that nothing is certain."

In this thesis, two noteworthy contributions are presented in the field of mathematical programming.

The first contribution introduces an innovative dual-based cutting plane method as a solution methodology for nonlinear Adjustable Robust Optimization (ARO) problems. This research introduces novel tools and techniques for robust optimization to address sequential decisionmaking under uncertainty, specifically in nonlinear cases. Indeed, we studied a general nonlinear ARO model with uncertainty in the objective and constraints. We obtained an equivalent dual formulation by applying Fenchel's duality on the wait-and-see variable. We investigated when the dual formulation is convex in the decision variables and explored reaching upper and lower bounds for the original problem based on the dual formulation.

Thanks to the equivalent dual reformulation, we presented and analyzed two algorithms.

These algorithms aimed to find a lower bound on the optimal objective value of the general nonlinear ARO model. We demonstrated by numerical results that our algorithm could produce a locally robust solution with an acceptable optimality gap.

Future Directions

The findings outlined in this thesis offer exciting possibilities for advancing the methodology in nonlinear adjustable robust optimization and exploring problems in applied domains that have had limited exposure to sophisticated robust modeling techniques. This research prompts an immediate inquiry into integrating decision rules within nonlinear adjustable robust optimization and approximating this complex problem. Although incorporating decision rules presents both theoretical and computational challenges, it holds the promise of capturing the underlying structure more effectively.

Another future research avenue might explore how ARO can be applied to deriving new reformulations for disjoint biconvex programming problems. Disjoint biconvex problems are known to be complex and challenging to solve. We hope to develop innovative reformulations that can improve solvability and efficiency by leveraging the power of ARO techniques. This future research has the potential to advance the field of disjoint biconvex programming and contribute to the development of more robust optimization techniques.