Theory of Mathematical Optimization for Delegated Portfolio Management Citation Tao, Zijian (2022) Theory of Mathematical Optimization for Delegated Portfolio Management. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/km2b-er60. https://resolver.caltech.edu/CaltechTHESIS:05272022-034901698 Abstract We study the optimization problem of finding closed convex sets Γ ⊆ R d containing the origin that minimize F(Γ) = ∑ i=1 k w i | θ i /2 - p Γ (θ i ) | 2 , where w 1 , ..., w k > 0, θ 1 , ..., θ k in R d are given, and p Γ (θ i ) are the closest points in Γ to θ i , i = 1, ..., k. This problem is motivated by the topic of delegated portfolio management in finance. In Chapter 2, we will explore this connection. To approach the problem, we first prove existence of a solution for the general problem. To further study properties of the solution, we next introduce the semidefinite programming relaxation, for which we have a first-order characterization of optimality. We then explore the question of exactness of this relaxation, which turns out to be equivalent to the notion of localizability: the shape optimization problem embedded in higher dimensions must have solutions in the original dimension. Finally, we present special cases for which localizability holds. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: mathematical finance, screening, mathematical optimization, semidefinite programming Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Awards: Apostol Award for Excellence in Teaching in Mathematics, 2021. Thesis Availability: Public (worldwide access) Research Advisor(s): Cvitanić, Jakša Thesis Committee: Tamuz, Omer (chair) Cvitanić, Jakša Makarov, Nikolai G. Sandomirskiy, Fedor Defense Date: 19 May 2022 Record Number: CaltechTHESIS:05272022-034901698 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:05272022-034901698 DOI: 10.7907/km2b-er60 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 14634 Collection: CaltechTHESIS Deposited By: Zijian Tao Deposited On: 02 Jun 2022 19:57 Last Modified: 03 Aug 2022 21:14 Thesis Files PDF - Final Version See Usage Policy. 420kB Repository Staff Only: item control page

Theory of Mathematical Optimization for Delegated Portfolio Management Thesis by Zijian Tao In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy CALIFORNIA INSTITUTE OF TECHNOLOGY Pasadena, California 2022 Defended May 19, 2022 ii © 2022 Zijian Tao All rights reserved iii ACKNOWLEDGEMENTS I am deeply grateful to my advisor Jakša Cvitanić for his support throughout my studies. He sparked my interest in mathematical finance, allowed me freedom to explore, and provided patient guidance when I got stuck. I would not be able to develop as an independent researcher without him. I thank Fedor Sandomirskiy and Omer Tamuz for their commitment to my project. I benefited greatly from our meetings, each of which brought a fresh supply of ideas and excitement. I thank Kim Border and Nikolai Makarov for serving on my committee, and for their interest in my research. With their support, I never felt alone. Sadly, Professor Border passed away in 2020. I will miss him. I thank the mathematics department and the larger Caltech community for providing an ideal academic environment. Here, I met brilliant people, learned cool topics, and had a great time. iv ABSTRACT We study the optimization problem of finding closed convex sets Γ ⊆ R𝑑 containing the origin that minimize F (Γ) = 𝑘 ∑︁ 𝑖=1 𝑤𝑖 2 𝜃𝑖 − 𝑝 Γ (𝜃 𝑖 ) , 2 where 𝑤 1 , . . . , 𝑤 𝑘 > 0, 𝜃 1 , . . . , 𝜃 𝑘 ∈ R𝑑 are given, and 𝑝 Γ (𝜃 𝑖 ) are the closest points in Γ to 𝜃 𝑖 , 𝑖 = 1, . . . , 𝑘. This problem is motivated by the topic of delegated portfolio management in finance. In Chapter 2, we will explore this connection. To approach the problem, we first prove existence of a solution for the general problem. To further study properties of the solution, we next introduce the semidefinite programming relaxation, for which we have a first-order characterization of optimality. We then explore the question of exactness of this relaxation, which turns out to be equivalent to the notion of localizability: the shape optimization problem embedded in higher dimensions must have solutions in the original dimension. Finally, we present special cases for which localizability holds. v TABLE OF CONTENTS Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter I: Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter II: Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 2.1 The Shape Optimization Problem . . . . . . . . . . . . . . . . . . . 2.2 The Financial Model . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 The Correspondence between Shape Optimization and Optimal Fund Menus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter III: Existence of Solution . . . . . . . . . . . . . . . . . . . . . . . Chapter IV: Mathematical Optimization for the Discrete Problem . . . . . . . 4.1 The Quadratically Constrained Quadratic Program . . . . . . . . . . 4.2 The SDP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Relation between SDP and QCQP . . . . . . . . . . . . . . . . . . . 4.4 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Appendix A: Gamma Convergence . . . . . . . . . . . . . . . . . . . . . . . Appendix B: Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . iii iv v 1 5 5 6 9 13 17 17 22 27 31 37 39 41 1 Chapter 1 INTRODUCTION In this paper we study the following optimization problem. Let 𝜃 1 , . . . , 𝜃 𝑘 be points in Euclidean space R𝑑 . Given a closed convex set Γ and a point 𝜃 ∈ R𝑑 , let 𝑝 Γ (𝜃) be the unique closest point in Γ to 𝜃. One wishes to find, among all closed convex sets containing the origin, one that minimizes the objective functional F (Γ) = 𝑘 ∑︁ 𝑖=1 𝑤𝑖 2 𝜃𝑖 − 𝑝 Γ (𝜃 𝑖 ) , 2 where 𝑤 𝑖 > 0 are positive weights. Optimization problems of this type, where the decision variable is a set, is often known as shape optimization. Examples of such problems can be found in [2], [7], and [10]. Our approach to the problem consists of three steps. First, we establish a general existence theorem for optimality via techniques analogous to the direct method of calculus of variations. Actually characterizing the solution, on the other hand, is nontrivial. To the best of our knowledge, there is no applicable theory such as “shape calculus” that permits a first-order characterization of the optimal solution. This difficulty necessitates our second step. We switch the decision variable from the convex set Γ to the closest points 𝑝𝑖 in Γ to 𝜃 𝑖 . The geometric constraints of the shape optimization problem will be recast as a family of quadratic inequalities involving 𝑝𝑖 . The problem now simplifies to a quadratic program with quadratic constraints (QCQP). Unfortunately, the constraints are nonconvex, making the problem intractable. In the third step, we convexify the problem using semidefinite programming (SDP) relaxation. This relaxed problem is much more tractable. In particular, it is possible to obtain a first-order characterization of solutions, as well as compute a numerical solution to arbitrary accuracy in polynomial time. This SDP relaxation provides a non-trivial lower bound for the optimal value of the complete problem. The issue that remains is whether the relaxation can recover an exact solution to the original quadratic program. This question turns out to be equivalent to the following problem about localizability. It asks whether the solution to the optimization problem would change when 𝜃 1 , . . . , 𝜃 𝑘 are embedded in a higher dimensional space ′ ′ R𝑑 , and Γ is allowed to vary over all closed convex sets in R𝑑 containing the origin. We establish localizability in certain special cases, including (i) when 𝜃 1 , . . . , 𝜃 𝑘 are 2 linearly independent, and (ii) when 𝜃 1 , . . . , 𝜃 𝑘 lie on a line and are sufficiently far from the origin. The general problem, however, remains open. Our optimization problem has its roots in the finance of delegated portfolio management. Specifically, consider a mutual fund facing a set {1, . . . , 𝑘 } of potential investors. The mutual fund is a monopoly: investors do not have to invest their money, but if they choose to, they must invest through the mutual fund. The market consists of several risky assets, and all investors have the same mean-variance utility function with the same risk aversion. Investors are heterogeneous, characterized by their initial endowment in the risky assets (henceforth referred to as types, denoted 𝜃). Knowing the distribution of investor types, the mutual fund designs a menu of funds to be offered, each of which charges a fee. Here, we assume fees are linear, and that investors are free to allocate their wealth across multiple funds. Thus, if fund 𝑥 1 is available with fee 𝜋1 , 𝑥 2 is available with fee 𝜋2 , then for 𝑞 1 , 𝑞 2 ≥ 0. 𝑞 1 𝑥 1 + 𝑞 2 𝑥 2 must be available with fee 𝑞 1 𝜋1 + 𝑞 2 𝜋2 . The mutual fund’s problem is to decide the set of funds to offer and their associated fees in a way that maximizes the aggregate fee collected. This is the optimal fund menus problem (OFM). As it turns out, OFM is equivalent to minimizing F (Γ). In Chapter 1, we will prove a correspondence theorem that establishes the precise relation between the two problems. Under this formulation, the aforementioned notion of localizability also has important implications. Financially, if the mutual fund is allowed to introduce assets with new sources of risk, would the optimal menu entail investors (whose goal is to hedge their original risk exposures) taking on these new risks? The answer is “no” if and only if localizability holds. Our paper contributes to the literature of mathematical programming, especially semidefinite programming (SDP). Semidefinite programming is a subclass of convex optimization problems which generalizes linear programming. It is widely applicable to problems in engineering and applied sciences. Many nonconvex problems admit an SDP relaxation, which produces an approximate optimal solution of the original problem, and in some cases, an exact solution. The classic example is [8], where SDP relaxation is used to find a near optimal solution to the max cut problem. Examples of SDP relaxation providing an exact solution to the original problem can be found in [15], [9], [4], [3] and [14]. In particular, certain techniques in our paper are inspired by [14] in which the authors study the sensor network localization (SNL) problem. The problem involves finding a feasible configuration of points in a Euclidean space of a given dimension, subject to constraints on the 3 pairwise distances. The authors relax certain constraints of SNL to form an SDP, and show that this relaxation is exact if and only if adding additional dimensions does not change the optimal configuration. In our paper, we use SDP to relax the optimal fund menu problem, and show that the relaxation is exact if and only if adding zero-return assets to which the investors have no exposure does not change the optimal menu. However, we currently do not know if SDP relaxation always provides an exact solution to the optimal fund menus problem. There is no general criterion in mathematical programming that guarantees exactness. The aforementioned examples all exploit very special structures in their respective problems. At this point, we can only establish exactness for our problem for special cases. On the other hand, numerical experiments suggest that exactness might hold in general, prompting further work in this direction. Our paper also contributes to the literature of screening and asset bundling. It can be seen as a generalization of the model proposed in [6], where a monopolistic mutual fund manager faces investors with different beliefs in the return of one asset. In their paper, the dual approach is used. That is, rather than optimize directly over fund menus, they optimize over the space of indirect utility functions induced by all possible fund menus. Such indirect utility functions are not arbitrary, and must satisfy certain incentive compatibility constraints. To solve the optimization problem, the authors temporarily drop the incentive compatibility constraints on the indirect utility function, solve a calculus of variations problem, and show that at optimum, the constraint does not bind. In contrast, the heterogeneity of investors in our paper involves differing initial exposures to possibly more than one asset. While we also adopt the general dual approach by considering all indirect utility functions induced by menus, our method of study is significantly different. For our model, incentive compatibility requires that an indirect utility function be of the form squared distance to a convex region. The exclusion of this constraint will, in general, not give a feasible solution to the complete problem. Our model also provides a linear pricing analog to the ones studied in [11], [12], and [5], in which a monopoly is allowed to use nonlinear pricing to screen customers with heterogeneous preferences across one or multiple dimensions. In these models, the space of all feasible indirect utility functions forms a convex cone, making the problem amenable to conic optimization techniques. In contrast, the linear pricing constraint in our paper gives rise to a nonconvex problem. Hence, the techniques developed in the aforementioned papers do not directly apply here. 4 The structure of this paper is as follows. Chapter 2 describes the problem, the financial model that motivates it, and establishes a precise correspondence between the two. Chapter 3 adapts the direct method of calculus of variations to prove general existence of an optimal solution. Chapter 4 seeks to characterize the solution. In Section 4.1, we derive the quadratic programming formulation of the problem. In Section 4.2, we study the SDP relaxation and its associated properties. Section 4.3 studies the relation between the relaxation and the complete problem, which leads to the notion of localizability. Finally, Section 4.4 explores particular cases in which the SDP relaxation provides an exact solution to the complete problem. 5 Chapter 2 PROBLEM FORMULATION 2.1 The Shape Optimization Problem Consider a finite set of points 𝜃 1 , . . . , 𝜃 𝑘 in Euclidean space R𝑑 , and let 𝑤 1 , . . . , 𝑤 𝑘 > 0 be positive weights. For any closed convex set Γ and any point 𝜃 ∈ R𝑑 , there exists a unique point in Γ that is closest to 𝜃, which we denote by 𝑝 Γ (𝜃). Among all closed convex sets Γ containing the origin, we wish to find one that minimizes F (Γ) = 𝑘 ∑︁ 𝑖=1 𝑤𝑖 2 𝜃𝑖 − 𝑝 Γ (𝜃 𝑖 ) . 2 While we are mainly concerned with the case of finitely many points, the problem can be formulated more generally. Given a subset Ω of R𝑑 and a finite measure 𝜇 on Ω, one may consider the problem ∫ 2 𝜃 − 𝑝 Γ (𝜃) 𝑑𝜇(𝜃) maximizeΓ F (Γ) := Ω 2 (2.1) 𝑑 s.t. Γ ⊆ R closed and convex, 0 ∈ Γ. Note that for the finite case, Ω = {𝜃 1 , . . . , 𝜃 𝑘 }, and 𝜇 = Í𝑘 𝑖=1 𝑤 𝑖 𝛿 𝜃 𝑖 . Our central question concerns localizability, which we define now. Definition. We say that (Ω, 𝜇) is localizable if it satisfies the following condition: ′ Let 𝑑 ′ ≥ 𝑑 be arbitrary, and let Γ be a closed convex set in R𝑑 with 0 ∈ Γ. Let ∫ 2 𝑝(𝜃) = 𝑝 Γ (𝜃) be the closest point to 𝜃 in Γ. If Ω 2𝜃 − 𝑝 Γ (𝜃) 𝑑𝜇(𝜃) = 𝑠∗ , where 𝑠∗ is the optimal value for Problem (2.1) then 𝑝 Γ (𝜃) ∈ R𝑑 for all 𝜃 ∈ Ω. Essentially, localizability guarantees that the optimal solution does not change when the problem is embedded in higher dimensions. As will be discussed in Chapter 3, this property is key to establishing uniqueness and first-order characterization of the solution. For the remainder of this chapter, we will describe the financial problem of optimal fund menus that motivated the study of (2.1) and establish their correspondence. 6 2.2 The Financial Model We consider a one-period model. The market consists of the riskless asset with return 𝑟, and 𝑑 risky assets with excess return (over the risk-free rate) 𝜖 ∈ R𝑑 . The excess return 𝜖 = (𝜖1 , . . . , 𝜖 𝑑 ) is a random vector. The coordinates 𝜖1 , . . . , 𝜖 𝑑 are independent, each having variance 1. We let 𝜁 = (𝜁1 , . . . , 𝜁 𝑑 ) := E[𝜖]. The market is populated by a monopolistic risk-neutral mutual fund manager and heterogeneous risk-averse investors. Each investor is associated with a type 𝜃 ∈ R𝑑 . An investor with type 𝜃 = (𝜃 1 , . . . , 𝜃 𝑑 ) initially owns 𝜃 𝑖 dollars worth of the 𝑖-th risky asset. All investors have mean-variance utility given by 1 E[𝑤 1 ] − var[𝑤 1 ], 2 where 𝑤 1 is the terminal wealth. The set of all investor types is Ω ⊆ R𝑑 , and the distribution of types is 𝜇—a finite measure on Ω. We assume 𝜇 is known to the mutual fund manager. A monopolistic mutual fund manager can offer a menu of funds. Each fund is described by (𝑥, 𝜋), where 𝑥 = (𝑥 1 , . . . , 𝑥 𝑑 ), 𝑥𝑖 indicating the dollar amount invested in the 𝑖-th risky asset, and 𝜋 is the fee charged to investors. We assume that investors are free to allocate their wealth to multiple funds, and that the fees are subject to linear pricing. It’s not possible, however, to take short position in a fund. Hence, if funds (𝑥 1 , 𝜋1 ) and (𝑥2 , 𝜋2 ) are available, then for 𝑞 1 , 𝑞 2 ≥ 0, (𝑞 1 𝑥 1 + 𝑞 2 𝑥 2 , 𝑞 1 𝜋1 + 𝑞 2 𝜋2 ) must also be available. To capture these properties, we define a fund menu as follows. Definition. A fund menu is a closed convex cone in M ⊆ R𝑑 × R+ that is closed upward. Consider an investor of type 𝜃 = (𝜃 1 , . . . , 𝜃 𝑑 ). Suppose, in addition to the risky assets, she owns an additional 𝐶 amount of cash (this amount turns out to be irrelevant for utility maximization purpose). Thus, her initial wealth is 𝑤 0 = 𝐶 + 𝜃 1 + · · · + 𝜃 𝑑 . If she buys one unit of fund (𝑥, 𝜋), her terminal wealth is 𝑤 1 = 𝑤 0 (1 + 𝑟) + (𝜃 + 𝑥) · 𝜖 − 𝜋. 7 She derives utility 1 1 E[𝑤 1 ] − var[𝑤 1 ] = E[𝑤 0 (1 + 𝑟) + (𝜃 + 𝑥) · 𝜖 − 𝜋] − var[𝑤 0 (1 + 𝑟) + (𝜃 + 𝑥) · 𝜖 − 𝜋] 2 2 1 = 𝑤 0 (1 + 𝑟) + (𝜃 + 𝑥) · 𝜁 − 𝜋 − |𝜃 + 𝑥| 2 2   1 2  1 = 𝑤 0 (1 + 𝑟) + 𝜃 · 𝜁 − |𝜃| + 𝑥 · 𝜁 − 𝜋 − |𝑥| 2 − 𝑥 · 𝜃 . 2 2 The investor’s goal is to choose a fund (𝑥, 𝜋) in the menu that maximizes E[𝑤 1 ] − 1 1 2 2 var[𝑤 1 ]. Note that only the part 𝑥 · 𝜁 − 𝜋 − 2 |𝑥| − 𝑥 · 𝜃 is relevant for the investor’s utility maximization problem. Henceforth, we shall write 𝑈𝜃 (𝑥, 𝜋) = 𝑥 · 𝜁 − 𝜋 − 21 |𝑥| 2 − 𝑥 · 𝜃. With this notation, the type 𝜃 investor’s problem is maximize (𝑥,𝜋)∈M 𝑈𝜃 (𝑥, 𝜋). (2.2) Now we consider the fund manager’s problem. Loosely, the manager seeks to design a fund menu that maximizes the aggregate fee collected across all investors. More precisely, let (𝑥 M (𝜃), 𝜋M (𝜃)) ∈ arg max (𝑥,𝜋)∈M 𝑈𝜃 (𝑥, 𝜋). We will show in the next section that the maximizer is unique. Thus, the manager’s fee collected from type 𝜃 is well-defined, given by 𝜋M (𝜃). The aggregate fee collected across all investors is ∫ 𝜋 (𝜃)𝑑𝜇(𝜃). Thus the manager’s problem is M M ∫ maximizeM 𝜋M (𝜃)𝑑𝜇(𝜃). (2.3) Ω Remark 1. We impose the assumption that the asset returns are independent with unit variance to simplify computation. In general, suppose there are 𝑘 risky assets 𝑥 1 , . . . , 𝑥 𝑑 whose returns have covariance matrix Σ. Let Σ = 𝑍 𝑍 𝑇 be the Cholesky decomposition. Provided Σ is nonsingular, we may create 𝑑 new assets 𝑦 1 , . . . , 𝑦 𝑑 Í with uncorrelated, unit variance returns, given by 𝑦𝑖 = 𝑑𝑗=1 𝑎𝑖 𝑗 𝑥 𝑗 , where 𝐴 = 𝑍 −1 . A fund investing (𝑞 1 , . . . , 𝑞 𝑑 ) in (𝑥 1 , . . . , 𝑥 𝑑 ) at fee rate 𝜋 is equivalent to one © 𝑝1 ª ©𝑞1 ª ­ .. ® ­.® 𝑇 investing ( 𝑝 1 , . . . , 𝑝 𝑑 ) in (𝜉1 , . . . , 𝜉 𝑑 ) with the same fee, where ­ . ® = 𝑍 ­ .. ®. ­ ® ­ ® 𝑝 « 𝑑¬ «𝑞 𝑑 ¬ Remark 2. Instead of differing in initial risk exposure, we can also consider a model in which investor type is characterized by his subjective evaluations of the assets’ expected returns 𝜂 = (𝜂1 , . . . , 𝜂 𝑑 ) ∈ R𝑑 . The utility of an investor with type 𝜂 investing quantity 𝑥 at fee 𝜋 is 1 𝜂 · 𝑥 − 𝜋 − |𝑥| 2 . 2 8 The manager’s problem is to design a menu M that maximizes ∫ 𝜋M (𝜂)𝑑𝜇(𝜂), Ω n 𝜂 · 𝑥 − 𝜋 − 21 |𝑥| 2 o where (𝑥(𝜂), 𝜋(𝜂)) ∈ arg max (𝑥,𝜋)∈M . In particular, the model of [6] is of this form, with 𝜇 being the uniform distribution on the line segment {(𝜂1 , 𝜂2 ) ∈ R2 | 𝜂1 = 𝜉, 0 ≤ 𝜂2 ≤ 𝜃 𝐻 }, where 𝜉 and 𝜃 𝐻 are constants. Here, 𝜉 is the true mean return rate of the index asset, and 𝜃 𝐻 is the most optimistic investor’s subjective estimate of the non-index asset’s return. This is mathematically equivalent to the main model where the heterogeneity is initial risk exposure. They are related by a change of variable 𝜃 = 𝜁 − 𝜂. The model of [6] corresponds to uniform distribution on the segment {(𝜃 1 , 𝜃 2 ) ∈ R2 | 𝜃 1 = 𝜁1 − 𝜉, 𝜁2 − 𝜃 𝐻 ≤ 𝜃 2 ≤ 𝜁2 }. Remark 3. One could try to apply the method of [6] to the model of the present paper. Define the indirect utility function o n 1 𝑢 M (𝜃) := sup 𝑥 · 𝜁 − 𝜋 − |𝑥| 2 − 𝑥 · 𝜃 . 2 (𝑥,𝜋)∈M By a direct calculation, we can express the manager’s aggregate fee collected as ∫ 1 {−𝑢 M (𝜃) − |∇𝑢 M (𝜃)| 2 + (𝜃 − 𝜁) · ∇𝑢 M (𝜃)}𝑑𝜇(𝜃). (2.4) 2 Ω Moreover, 𝑢 M is convex, and satisfies the eikonal equation 2𝑢 M (𝜃) = |∇𝑢 M (𝜃)| 2 . The aggregate fee can be rewritten as ∫ {−|∇𝑢 M (𝜃)| 2 + (𝜃 − 𝜁) · ∇𝑢 M (𝜃)}𝑑𝜇(𝜃). (2.5) Ω In the special case when 𝑑 = 2, 𝜃 1 is constant, and 𝜃 2 is uniformly distributed in M [𝜃 𝐿 , 𝜃 𝐻 ], let 𝑣 M (𝜃 2 ) = 𝑢 M (𝜃 1 , 𝜃 2 ). From the eikonal equation, we find 𝜕𝑢 𝜕𝜃 1 = √︁ 2𝑣 M (𝜃 2 ) − [ 𝑣 M ¤ (𝜃 2 )] 2 . The aggregate fee is ∫ 𝜃𝐻 √︁ 1 {(𝜃 2 − 𝜁2 ) 𝑣 M ¤ (𝜃 2 ) − 2𝑣 M (𝜃 2 ) + (𝜃 1 − 𝜁1 ) 2𝑣 M (𝜃 2 ) − [ 𝑣 M ¤ (𝜃 2 )] 2 }𝑑𝜃. 𝜃𝐻 − 𝜃 𝐿 𝜃𝐿 This coincides with the manager’s value function appearing in [6], after making a change of variable (see Remark 2). In this special case, we may proceed by calculus of variations over all possible functions 𝑣 M . In the general case, however, we cannot use calculus of variations to maximize (2.5). Calculus of variations does not take into account the eikonal constraint 9 2𝑢 M (𝜃) = |∇𝑢 M (𝜃)| 2 . One cannot temporarily drop this constraint, and hope that the optimal solution of the relaxed problem automatically satisfies it. In fact, this is never true. 𝜃 − 𝜁 2 |𝜃 − 𝜁 | 2 −|∇𝑢 M (𝜃)| 2 + (𝜃 − 𝜁) · ∇𝑢 M (𝜃) = − ∇𝑢 M (𝜃) − + 2 4 2 |𝜃−𝜁 | so (2.5) is maximized when ∇𝑢 M (𝜃) = 𝜃−𝜁 2 . This implies 𝑢 M (𝜃) = 4 +𝐶, which 2 does not satisfy 2𝑢 M (𝜃) = |∇𝑢 M (𝜃)| . 2.3 The Correspondence between Shape Optimization and Optimal Fund Menus In this section, we give a characterization of fund menus in terms of their nonparticipation regions. This reduces the problem of finding the optimal menu M to one of finding an optimal convex region. Definition. Given a fund (𝑥, 𝜋) ∈ R𝑑 × R+ , we define its non-participation halfspace by H(𝑥, 𝜋) = {𝜃 ∈ R𝑑 | (𝜁 − 𝜃) · 𝑥 − 𝜋 ≤ 0}. More generally, given a fund menu M ⊆ R𝑑 × R+ , we define the non-participation region induced by this menu Ñ to be 𝜑(M) = (𝑥,𝜋)∈M H(𝑥, 𝜋). Remark 4. H(𝑥, 𝜋) is a closed half-space in R𝑑 containing 𝜁 (unless 𝑥 = 0, in which case, H(𝑥, 𝜋) = R𝑑 ). Since 𝜑(M) is an intersection of closed half-spaces, all of which containing 𝜁, 𝜑(M) is a closed convex set in R𝑑 containing the point 𝜁. The non-participation region is so-called because it represents all types 𝜃 ∈ R𝑑 for which it is optimal to not invest in the fund menu. Theorem 1. There is a bijection {fund menus M} ↔ {closed convex sets Γ ⊆ R𝑑 𝑐𝑜𝑛𝑡𝑎𝑖𝑛𝑖𝑛𝑔 𝜁 } given by 𝜑 M→ − Ù H(𝑥, 𝜋) (𝑥,𝜋)∈M 𝜓 {(𝑥, 𝜋) ∈ R𝑑 × R+ | Γ ⊆ H(𝑥, 𝜋)} ← − Γ. Moreover, given a fund menu M, let Γ = 𝜑(M). (𝑥 M (𝜃), 𝜋M (𝜃)) = arg max (𝑥,𝜋)∈M 𝑈𝜃 (𝑥, 𝜋) is unique, given by 𝑥 M (𝜃) = 𝑝 Γ (𝜃) − 𝜃 𝜋M (𝜃) = (𝜁 − 𝑝 Γ (𝜃)) · ( 𝑝 Γ (𝜃) − 𝜃), where 𝑝 Γ (𝜃) denotes the (unique) closest point to 𝜃 in Γ. 10 Lemma 2. Let Γ = M. Ñ (𝑥,𝜋)∈M H(𝑥, 𝜋). If (𝑥, 𝜋) satisfies Γ ⊆ H(𝑥, 𝜋), then (𝑥, 𝜋) ∈ Proof. Let N = {(𝑥, 𝜋) ∈ R𝑑 × R | Γ ⊆ H(𝑥, 𝜋)}. It’s clear that M ⊆ N . It remains to show that N ⊆ M. Suppose (𝑥, 𝜋) ∈ N \M. Since M is a closed convex cone, there exists a nonzero (𝑣, −𝑡) ∈ R𝑑 × R such that (𝑣, −𝑡) · (𝑥, 𝜋) > 0 ≥ sup (𝑥 ′,𝜋 ′)∈M (𝑣, −𝑡) · (𝑥 ′, 𝜋′). Since M is closed upward, we must have 𝑡 ≥ 0. (Otherwise, (𝑣, −𝑡) · (𝑥 ′, 𝜋′) → +∞ when we take 𝜋′ → +∞.) If 𝑡 > 0, then let e 𝑣 = 𝑣𝑡 , e 𝜃 = 𝜁 −e 𝑣 . Then (e 𝑣 , −1) · (𝑥, 𝜋) > 0 ≥ sup (𝑥 ′,𝜋 ′)∈M (e 𝑣 , −1) · (𝑥 ′, 𝜋′). We deduce that e 𝜃 ∈ Γ, and (𝑥, 𝜋) ∉ N . If 𝑡 = 0, then ′ 𝑣 ≠ 0, and 𝑣 · 𝑥 > 0 ≥ sup (𝑥 ′,𝜋 ′)∈M 𝑣 · 𝑥 . Let e 𝑣 = 𝛼𝑣, where 𝛼 > 0 is large so that e 𝑣 · 𝑥 > 𝜋. Since M ⊆ R𝑑 × R+ , e 𝑣 · 𝑥 − 𝜋 > 0 ≥ sup (𝑥 ′,𝜋 ′) e 𝑣 · 𝑥 ′ ≥ sup (𝑥 ′,𝜋 ′) e 𝑣 · 𝑥 ′ − 𝜋′. Once again, put e 𝜃 = 𝜁 −e 𝑣 , and we see that e 𝜃 ∈ Γ, but (𝑥, 𝜋) ∉ N . □ Lemma 3. If a subset Γ of R𝑑 is closed, convex, and contains 𝜁, then there exists a Ñ fund menu M such that Γ = (𝑥,𝜋)∈M H(𝑥, 𝜋). Proof. Suppose Γ is closed, convex, and contains 𝜁. Let M = {(𝑥, 𝜋) ∈ R𝑑 × R | Γ ⊆ H(𝑥, 𝜋)}. It’s clear that M satisfies the requirements of a fund menu, and Ñ Ñ Γ ⊆ (𝑥,𝜋)∈M H(𝑥, 𝜋). To show that Γ = (𝑥,𝜋)∈M H(𝑥, 𝜋), suppose 𝜃 0 ∉ Γ. Then 𝜁 − 𝜃 0 and 𝜁 − Γ are disjoint. By the separating hyperplane theorem, there exists (𝑥 0 , 𝜋0 ) ∈ R𝑑 × R such that sup (𝜁 − 𝜃) · 𝑥 0 − 𝜋0 ≤ 0 < (𝜁 − 𝜃 0 ) · 𝑥 0 − 𝜋0 . 𝜃∈Γ This implies (𝑥0 , 𝜋0 ) ∈ M, and 𝜃 0 ∉ H(𝑥 0 , 𝜋0 ). Consequently, 𝜃 0 ∉ Ñ (𝑥,𝜋)∈M H(𝑥, 𝜋). □ Lemma 4. Let 𝜃 0 ∈ R𝑑 . Then [(𝜁−𝜃 0|𝑥|)·𝑥−𝜋] + is the distance from 𝜃 0 to H(𝑥, 𝜋), provided 𝑥 ≠ 0. Proof. If (𝜁 − 𝜃 0 ) · 𝑥 − 𝜋 ≤ 0, then 𝜃 0 ∈ H(𝑥, 𝜋), and the distance to H(𝑥, 𝜋) is zero. In this case, we have [(𝜁−𝜃 0|𝑥|)·𝑥−𝜋] + = 0, as desired. Consider the case (𝜁 − 𝜃 0 ) · 𝑥 − 𝜋 > 0. We find the closest point 𝑝 in H(𝑥, 𝜋) to 𝜃 0 . It is clear that 𝑝 must be on the boundary of H(𝑥, 𝜋). Consider the problem minimize s.t. | 𝑝 − 𝜃0 |2 (𝜁 − 𝑝) · 𝑥 − 𝜋 = 0. 11 Solving the Lagrange multiplier system 2( 𝑝 − 𝜃 0 ) = 𝜆𝑥 (𝜁 − 𝑝) · 𝑥 − 𝜋 = 0, we find solution 𝑝 = 𝜃 0 + (𝜁−𝜃|𝑥|0 )·𝑥−𝜋 𝑥. The distance from 𝜃 0 to H(𝑥, 𝜋) is |𝜃 0 − 𝑝| = 2 |(𝜁−𝜃 0 )·𝑥−𝜋| = [(𝜁−𝜃 0|𝑥|)·𝑥−𝜋] + . |𝑥| □ + = dist(𝜃, Γ), where Lemma 5. Let M be a fund menu. Then sup (𝑥,𝜋)∈M [(𝜁−𝜃)·𝑥−𝜋] |𝑥| Ñ Γ = H(𝑥, 𝜋). Moreover, if dist(𝜃, Γ) > 0, then there is a unique (𝑥 ∗ , 𝜋 ∗ ) (up to scalar multiple) such that dist(𝜃, Γ) = dist(𝜃, H(𝑥 ∗ , 𝜋 ∗ )). Proof. If dist(𝜃, Γ) = 0, then 𝜃 ∈ Γ = Γ. For any (𝑥, 𝜋) ∈ M, 𝜃 ∈ Γ ⊆ H(𝑥, 𝜋), so dist(𝜃, H(𝑥, 𝜋)) = 0. If dist(𝜃, Γ) > 0, let 𝑝 ∗ be the unique closest point in Γ to 𝜃. Let 𝑥 ∗ = 𝑝 ∗ − 𝜃, 𝜋 ∗ = (𝜁 − 𝑝 ∗ ) · ( 𝑝 ∗ − 𝜃). Then H(𝑥 ∗ , 𝑝 ∗ ) is the supporting halfspace of Γ at 𝑝 ∗ with outward normal 𝜃 − 𝑝 ∗ . It’s clear that Γ ⊆ H(𝑥 ∗ , 𝜋 ∗ ). By Lemma 2, (𝑥 ∗ , 𝜋 ∗ ) ∈ M. For any (𝑥, 𝜋) ∈ M, 𝑝 ∗ ∈ H(𝑥, 𝜋), so dist(𝜃, Γ) = |𝜃 − 𝑝 ∗ | ≥ dist(𝜃, H(𝑥, 𝜋)). Moreover, the inequality is strict unless H(𝑥, 𝜋) = H(𝑥 ∗ , 𝜋 ∗ ). □ Proof of theorem 1. It’s clear that 𝜓(𝜑(M)) ⊇ M. By Lemma 2, 𝜓(𝜑(M)) ⊆ M, so 𝜓 ◦ 𝜑 = id. In particular, 𝜑 is injective. Lemma 3 shows that 𝜑 is surjective. Consequently, 𝜑, 𝜓 establish a bijection. Now fix a type 𝜃, and consider Problem (2.2). If 𝜃 ∈ Γ, then (𝜁 − 𝜃) · 𝑥 − 𝜋 ≤ 0 for all (𝑥, 𝜋) ∈ M, and 1 𝑈𝜃 (𝑥, 𝜋) = (𝜁 − 𝜃) · 𝑥 − 𝜋 − |𝑥| 2 ≤ 0 for all (𝑥, 𝜋) ∈ M, 2 with equality if and only if 𝑥 = 0 and 𝜋 = 0. In this case, the unique maximizer is 𝑥 = 0, 𝜋 = 0. [(𝜁−𝜃)·𝑥−𝜋] 2 + If 𝜃 ∉ Γ, put 𝑉𝜃 (𝑥, 𝜋) = . We claim that 𝑈𝜃 (𝑥, 𝜋) ≤ 𝑉𝜃 (𝑥, 𝜋), with 2|𝑥| 2 equality if and only if [(𝜁 − 𝜃) · 𝑥 − 𝜋] + = |𝑥| 2 . Indeed, 𝑈𝜃 (𝑥, 𝜋) ≤ max 𝑈𝜃 (𝑞𝑥, 𝑞𝜋) 𝑞≥0 n o 1 = max 𝑞(𝜁 − 𝜃) · 𝑥 − 𝑞𝜋 − 𝑞 2 |𝑥| 2 𝑞≥0 2 2 [(𝜁 − 𝜃) · 𝑥 − 𝜋] + = 2|𝑥| 2 = 𝑉𝜃 (𝑥, 𝜋). 12 + Maximum on the right-hand side is achieved if and only if 𝑞 = [(𝜁−𝜃)·𝑥−𝜋] . But |𝑥| 2 equality holds if and only if the right-hand maximizer is 𝑞 = 1. Hence, we have proven the claim. √︁ Note that (𝑥, 𝜋) ∈ M maximizes 𝑉𝜃 (𝑥, 𝜋) if and only if it maximizes 2𝑉𝜃 (𝑥, 𝜋) = [(𝜁−𝜃)·𝑥−𝜋] + . By Lemma 4 and Lemma 5, |𝑥| arg max (𝑥,𝜋)∈M 𝑉𝜃 (𝑥, 𝜋) = arg max (𝑥,𝜋)∈M [(𝜁 − 𝜃) · 𝑥 − 𝜋] + = {𝛼(𝑥 ∗ , 𝜋 ∗ ) | 𝛼 > 0}, |𝑥| where 𝑥 ∗ = 𝑝 Γ (𝜃) − 𝜃, 𝜋 ∗ = (𝜁 − 𝑝 Γ (𝜃)) · ( 𝑝 Γ (𝜃) − 𝜃). Finally, arg max (𝑥,𝜋)∈M 𝑈𝜃 (𝑥, 𝜋) = arg max (𝑥,𝜋)∈M 𝑉𝜃 (𝑥, 𝜋) ∩ {(𝑥, 𝜋) ∈ M | [(𝜁 − 𝜃) · 𝑥 − 𝜋] + = |𝑥| 2 } = {(𝑥 ∗ , 𝜋 ∗ )}. □ Theorem 1 allows us reformulate the manager’s problem (2.3) into the following shape optimization problem: ∫ maximizeΓ (𝜁 − 𝑝 Γ (𝜃)) · ( 𝑝 Γ (𝜃) − 𝜃)𝑑𝜇(𝜃) Ω (2.6) 𝑑 s.t. Γ ⊆ R closed and convex, 𝜁 ∈ Γ. Without loss of generality, by shifting the origin of R𝑑 to 𝜁 if necessary, we may assume that 𝜁 = 0 and focus on the problem ∫ maximizeΓ F (Γ) := (−𝑝 Γ (𝜃)) · ( 𝑝 Γ (𝜃) − 𝜃)𝑑𝜇(𝜃) Ω (2.7) 𝑑 s.t. Γ ⊆ R closed and convex, 0 ∈ Γ. 2 2 Note that −𝑝 Γ (𝜃) · ( 𝑝 Γ (𝜃) − 𝜃) = − 2𝜃 − 𝑝 Γ (𝜃) + |𝜃|4 , so (2.7) is equivalent to ∫ minimizeΓ s.t. 2 𝜃 − 𝑝 Γ (𝜃) 𝑑𝜇(𝜃) Ω 2 𝑑 Γ ⊆ R closed and convex, 0 ∈ Γ. (2.8) 13 Chapter 3 EXISTENCE OF SOLUTION Proposition 6. Assume Ω is bounded. Then there exists a closed convex set Γ containing the origin such that F (Γ) is minimized. Proof. Let 𝑝 ∗ = infΓ closed convex,0∈Γ F (Γ). Then there exists a sequence of closed convex sets Γ𝑛 containing 0 such that F (Γ𝑛 ) → 𝑝 ∗ . Since 0 ∈ Γ𝑛 , we must have (𝜃 − 𝑝 Γ𝑛 (𝜃)) · (0 − 𝑝 Γ𝑛 (𝜃)) ≤ 0. Hence, | 𝑝 Γ𝑛 (𝜃)| 2 = | 𝑝 Γ𝑛 (𝜃)| 2 − 𝑝 Γ𝑛 (𝜃) · 𝜃 + 𝑝 Γ𝑛 (𝜃) · 𝜃 = 𝑝 Γ𝑛 (𝜃) · ( 𝑝 Γ𝑛 (𝜃) − 𝜃) + 𝑝 Γ𝑛 (𝜃) · 𝜃 ≤ | 𝑝 Γ𝑛 (𝜃)||𝜃|. We see that | 𝑝 Γ𝑛 (𝜃)| ≤ |𝜃|. Now let 𝑅 = sup𝜃∈Ω |𝜃|, and 𝐾𝑛 = Γ𝑛 ∩ 𝐵(0, 𝑅). Then each 𝐾𝑛 is a closed convex set containing 0, 𝑝 Γ𝑛 (𝜃) = 𝑝 𝐾𝑛 (𝜃) for all 𝜃, hence F (𝐾𝑛 ) → 𝑝 ∗ . By the Blaschke selection theorem, there exists a subsequence 𝐾𝑛 𝑘 and a closed convex set 𝐾 such that Δ𝐻 (𝐾𝑛 𝑘 , 𝐾) → 0. Here, Δ𝐻 (𝑋, 𝑌 ) = max{sup𝑥∈𝑋 dist(𝑥, 𝑌 ), sup𝑦∈𝑌 dist(𝑦, 𝑋)} is the Hausdorff distance. By passing to subsequence, we may assume Δ𝐻 (𝐾𝑛 , 𝐾) → 0. Claim 1: 0 ∈ 𝐾. Proof. 0 ∈ 𝐾𝑛 for each 𝑘, so dist(0, 𝐾) ≤ Δ𝐻 (𝐾𝑛 , 𝐾). We find dist(0, 𝐾) = 0. Since 𝐾 is closed, 0 ∈ 𝐾. □ Claim 2: For any 𝜃 ∈ R𝑑 , dist(𝜃, 𝐾𝑛 ) → dist(𝜃, 𝐾). Proof. There exists a 𝑝 𝑛 ∈ 𝐾𝑛 such that | 𝑝 𝑛 − 𝑝 𝐾 (𝜃)| ≤ Δ𝐻 (𝐾𝑛 , 𝐾). So dist(𝜃, 𝐾𝑛 ) ≤ |𝜃 − 𝑝 𝑛 | ≤ |𝜃 − 𝑝 𝐾 (𝜃)| + | 𝑝 𝐾 (𝜃) − 𝑝 𝑛 | ≤ dist(𝜃, 𝐾) + Δ𝐻 (𝐾𝑛 , 𝐾). 14 On the other hand, for each 𝑛 there exists 𝑞 𝑛 ∈ 𝐾 such that |𝑞 𝑛 − 𝑝 𝐾𝑛 (𝜃)| ≤ Δ𝐻 (𝐾𝑛 , 𝐾). So dist(𝜃, 𝐾) ≤ |𝜃 − 𝑞 𝑛 | ≤ |𝜃 − 𝑝 𝐾𝑛 (𝜃)| − | 𝑝 𝐾𝑛 (𝜃) − 𝑞 𝑛 | ≤ dist(𝜃, 𝐾𝑛 ) + Δ𝐻 (𝐾𝑛 , 𝐾). We find |dist(𝜃, 𝐾𝑛 ) − dist(𝜃, 𝐾)| ≤ Δ𝐻 (𝐾𝑛 , 𝐾) → 0. □ Claim 3: For any 𝜃 ∈ R𝑛 , 𝑝 𝐾𝑛 (𝜃) → 𝑝 𝐾 (𝜃). Proof. Suppose, for contradiction, this does not hold. Then there exists some 𝜀 > 0 such that | 𝑝 𝐾𝑛 (𝜃) − 𝑝 𝐾 (𝜃)| ≥ 𝜀, after passing to some subsequence. If 𝜃 ∈ 𝐾, then 𝑝 𝐾 (𝜃) = 𝜃. Since | 𝑝 𝐾𝑛 (𝜃) − 𝜃| > 𝜀, 𝐾𝑛 ∩ 𝐵(𝜃, 𝜀) = ∅. But then Δ𝐻 (𝐾𝑛 , 𝐾) ≥ dist( 𝑝 𝐾 (𝜃), 𝐾𝑛 ) ≥ 𝜀. If 𝜃 ∉ 𝐾, then 𝑝 𝐾 (𝜃) ≠ 𝜃. (𝜃 − 𝑝 𝐾 (𝜃)) · ( 𝑝 𝐾𝑛 (𝜃) − 𝑝 𝐾 (𝜃))  1 1 2 2 2 = | 𝑝 𝐾 (𝜃) − 𝑝 𝐾𝑛 (𝜃)| − |𝜃 − 𝑝 𝐾𝑛 (𝜃)| − |𝜃 − 𝑝 𝐾 (𝜃)| 2 2  𝜀2 1  ≥ − dist(𝜃, 𝐾𝑛 ) − dist(𝜃, 𝐾) . 2 2 Since dist(𝜃, 𝐾𝑛 ) → dist(𝜃, 𝐾), 21 |dist(𝜃, 𝐾𝑛 ) − dist(𝜃, 𝐾)| < 𝜀 2 /4 for sufficiently large 𝑛. Hence, 𝜀2 (𝜃 − 𝑝 𝐾 (𝜃)) · ( 𝑝 𝐾𝑛 (𝜃) − 𝑝 𝐾 (𝜃)) ≥ 4 for sufficiently large 𝑛. Let H be the supporting halfspace of 𝐾 at 𝑝 𝐾 (𝜃) with normal 𝜃 − 𝑝 𝐾 (𝜃). We find Δ𝐻 (𝐾𝑛 , 𝐾) ≥ dist( 𝑝 𝐾𝑛 (𝜃), 𝐾) ≥ dist( 𝑝 𝐾𝑛 (𝜃), H) ≥ This is a contradiction. 𝜀2 . 4|𝜃 − 𝑝 𝐾 (𝜃)| □ 2 2 Finally, we now know that 2𝜃 − 𝑝 𝐾𝑛 (𝜃) → 2𝜃 − 𝑝 𝐾 (𝜃) pointwise. Moreover, 2 | 𝑝 𝐾𝑛 (𝜃)| ≤ 𝑅, and |𝜃| ≤ 𝑅. So 2𝜃 − 𝑝 𝐾𝑛 (𝜃) ≤ 94 𝑅 2 . Since 𝜇(Ω) < +∞, we conclude ∫ ∫ 2 2 𝜃 𝜃 ∗ 𝑝 = lim − 𝑝 𝐾𝑛 (𝜃) 𝑑𝜇(𝜃) = − 𝑝 𝐾 (𝜃) 𝑑𝜇(𝜃) Ω 2 Ω 2 by the dominated convergence theorem. □ 15 The proof of Proposition 6 can be extended to unbounded regions Ω, provided 𝜇 decays sufficiently fast. Theorem 7. Let Ω ⊆ R𝑑 be arbitrary, and assume 𝜇 is a measure on Ω such that ∫ |𝜃| 2 𝑑𝜇(𝜃) < +∞. Then there exists a closed convex set Γ containing the origin Ω such that F (Γ) is minimized. Proof. Let 𝑝 ∗ = inf Γ closed convex,0∈Γ F (Γ). Then there exists a sequence of closed convex sets Γ𝑛 containing 0 such that F (Γ) → 𝑝 ∗ . Since {Γ𝑛 ∩ 𝐵(0, 1)}∞ 𝑛=1 is a bounded sequence of convex sets containing 0, the Blaschke selection theorem implies that there exists a subsequence 𝑛1,1 , 𝑛1,2 , 𝑛1,3 , . . . such that Γ𝑛1, 𝑗 ∩ 𝐵(0, 1) → 𝐾1,∞ in Hausdorff distance, where 𝐾1,∞ is a closed convex set containing 0, and contained in 𝐵(0, 1). Since {Γ𝑛1, 𝑗 ∩ 𝐵(0, 2)}∞ 𝑗=1 is a bounded sequence of convex sets containing 0, using the Blaschke selection theorem again, we obtain a further subsequence 𝑛2,1 , 𝑛2,2 , 𝑛2,3 , . . . such that Γ𝑛2, 𝑗 ∩ 𝐵(0, 1) → 𝐾1,∞ and Γ𝑛2, 𝑗 ∩ 𝐵(0, 2) → 𝐾2,∞ , where 𝐾2,∞ is a closed convex set containing 0, and contained in 𝐵(0, 2). By the Cantor diagonalization method, we find a subsequence 𝑛𝑖,𝑖 such that Γ𝑛𝑖,𝑖 ∩ 𝐵(0, 𝑗) → 𝐾 𝑗,∞ for all 𝑗 = 1, 2, 3, . . . . Claim 1: Suppose 𝑋, 𝑌 are compact convex sets containing 0, and Δ𝐻 (𝑋, 𝑌 ) ≤ 𝜀. Then for any 𝑖 > 0, Δ𝐻 (𝑋 ∩ 𝐵(0, 𝑖), 𝑌 ∩ 𝐵(0, 𝑖)) ≤ 2𝜀. Proof. Let 𝑥 ∈ 𝑋 ∩ 𝐵(0, 𝑖), and let 𝑦 ∈ 𝑌 so that |𝑥 − 𝑦| = dist(𝑥, 𝑌 ). If 𝑦 ∈ 𝐵(0, 𝑖), then dist(𝑥, 𝑌 ∩ 𝐵(0, 𝑖)) ≤ 𝜀. Consider the case 𝑦 ∉ 𝐵(0, 𝑖). Then 𝜀 ≥ |𝑥 − 𝑦| ≥ 𝑦 |𝑦| − |𝑥|, so |𝑦| ≤ |𝑥| + 𝜀 ≤ 𝑖 + 𝜀. Put 𝑦 = 𝑦′ + ℎ, where 𝑦′ = 𝑖 |𝑦| , and ℎ = 𝑦 − 𝑦′. Then |ℎ| ≤ 𝜀, and |𝑦′ | = 𝑖. Note that since 0 ∈ 𝑌 ∩ 𝐵(0, 𝑖) and 𝑌 ∩ 𝐵(0, 𝑖) is convex, 𝑦′ ∈ 𝑌 ∩ 𝐵(0, 𝑖). So |𝑥 − 𝑦′ | ≤ |𝑥 − 𝑦| + |ℎ| ≤ 2𝜀. In either case, we find sup𝑥∈𝑋∩𝐵(0,𝑖) dist(𝑥, 𝑌 ∩ 𝐵(0, 𝑖)) ≤ 2𝜀. Switching the roles of 𝑋 and 𝑌 , we conclude that Δ𝐻 (𝑋 ∩ 𝐵(0, 𝑖), 𝑌 ∩ 𝐵(0, 𝑖)) ≤ 2𝜀. □ Claim 2: 𝐾𝑖,∞ = 𝐾 𝑗,∞ ∩ 𝐵(0, 𝑖) for all 𝑖 < 𝑗. Proof. We know that Γ𝑛 𝑘,𝑘 ∩ 𝐵(0, 𝑗) → 𝐾 𝑗,∞ . By Claim 1, Γ𝑛 𝑘,𝑘 ∩ 𝐵(0, 𝑗) ∩ 𝐵(0, 𝑖) → 𝐾 𝑗,∞ ∩ 𝐵(0, 𝑖). But Γ𝑛 𝑘,𝑘 ∩ 𝐵(0, 𝑗) ∩ 𝐵(0, 𝑖) = Γ𝑛 𝑘,𝑘 ∩ 𝐵(0, 𝑖) → 𝐾𝑖,∞ . So 𝐾𝑖,∞ = 𝐾 𝑗,∞ ∩ 𝐵(0, 𝑖). □ Claim 3: Let 𝐾∞ = Ð∞ 𝑖=1 𝐾𝑖,∞ . Then 𝐾∞ is closed, convex, and contains 0. 16 Proof. It’s clear that 𝐾∞ is convex and contains 0. To show that 𝐾∞ is closed, ∞ is a sequence in 𝐾 and 𝑝 → 𝑝 . Without loss of generality, suppose {𝑝𝑖 }𝑖=1 ∞ 𝑖 ∞ we may assume that 𝑝 1 , 𝑝 2 , 𝑝 3 , . . . , 𝑝 ∞ ∈ 𝐵(0, 𝑛) for some 𝑛. Since 𝐾𝑛,∞ = 𝐾∞ ∩ 𝐵(0, 𝑛), we must have 𝑝𝑖 ∈ 𝐾𝑛,∞ . But 𝐾𝑛,∞ is closed, so the limit 𝑝 ∞ ∈ 𝐾𝑛,∞ ⊆ 𝐾∞ . □ 2 Claim 4: Denote 𝑓Γ (𝜃) = 2𝜃 − 𝑝 Γ (𝜃) . Then 𝑓Γ𝑖,𝑖 (𝜃) → 𝑓𝐾∞ (𝜃) pointwise. Proof. Fix 𝜃. For any closed convex set Γ containing 0, we must have | 𝑝 Γ (𝜃)| ≤ |𝜃|. Therefore, for sufficiently large 𝑛, 𝑝 Γ𝑛 ∩𝐵(0,𝑛) (𝜃) = 𝑝 Γ𝑛𝑖,𝑖 (𝜃) for all 𝑖 = 1, 2, 3, . . . , 𝑖,𝑖 and 𝑝 𝐾𝑛,∞ (𝜃) = 𝑝 𝐾∞ (𝜃). Since Γ𝑛𝑖,𝑖 ∩ 𝐵(0, 𝑛) → 𝐾𝑛,∞ , we have 𝑓Γ𝑛𝑖,𝑖 (𝜃) = 𝑓Γ𝑛 ∩𝐵(0,𝑛) (𝜃) → 𝑓𝐾𝑛,∞ (𝜃) = 𝑓𝐾∞ (𝜃). 𝑖,𝑖 □ Finally, | 𝑓Γ𝑛𝑖,𝑖 (𝜃)| ≤ 94 |𝜃| 2 . By the dominated convergence theorem, ∫ ∗ 𝑝 = lim 𝑖→∞ Ω ∫ 𝑓Γ𝑛𝑖,𝑖 (𝜃)𝑑𝜇(𝜃) = 𝑓𝐾∞ (𝜃)𝑑𝜇(𝜃). Ω □ 17 Chapter 4 MATHEMATICAL OPTIMIZATION FOR THE DISCRETE PROBLEM 4.1 The Quadratically Constrained Quadratic Program To the best of our knowledge, no existing theory is applicable to the specific shape optimization problem (2.8). To make the problem more tractable, we convert it into a quadratically constrained quadratic program. The key to this conversion is the following result: Proposition 8. Let {𝜃 𝑖 }𝑖∈𝐼 , {𝑝𝑖 }𝑖∈𝐼 be two collections of points in R𝑑 , where 𝐼 is an arbitrary index set. There exists a closed convex set Γ ⊆ R𝑑 containing 0 such that 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ) for all 𝑖 ∈ 𝐼 if and only if (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0 (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0 for all 𝑖, 𝑗 ∈ 𝐼, 𝑖 ≠ 𝑗, for all 𝑖 ∈ 𝐼. Proof. (⇐) Suppose for all 𝑖, 𝑗 ∈ 𝐼, we have (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0, and (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0. For each 𝑖 ∈ 𝐼, define H𝑖 = {𝜃 ∈ R𝑑 | (𝜃 𝑖 − 𝑝𝑖 ) · (𝜃 − 𝑝𝑖 ) ≤ 0}. This is a halfspace with normal vector 𝜃 𝑖 − 𝑝𝑖 (or the full space R𝑑 in the case 𝑝𝑖 = 𝜃 𝑖 ). It’s clear that dist(𝜃 𝑖 , H𝑖 ) = |𝜃 𝑖 − 𝑝𝑖 |. Since (𝜃 𝑖 − 𝑝𝑖 ) · (0 − 𝑝𝑖 ) ≤ 0, we deduce that 0 ∈ H𝑖 . Ñ Let Γ := 𝑖∈𝐼 H𝑖 . This is a closed convex set that contains 0. It remains to show that for each 𝑖 ∈ 𝐼, 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ). Fix 𝑖 ∈ 𝐼. Then for any 𝑗 ≠ 𝑖, (𝜃 𝑗 − 𝑝 𝑗 ) · ( 𝑝𝑖 − 𝑝 𝑗 ) ≤ 0. Ñ This implies that 𝑝𝑖 ∈ H 𝑗 . Since 𝑗 is arbitrary, 𝑝𝑖 ∈ 𝑗 ∈𝐼 H 𝑗 = Γ. We find dist(𝜃 𝑖 , Γ) ≤ |𝜃 𝑖 − 𝑝𝑖 | = dist(𝜃 𝑖 , H𝑖 ) ≤ dist(𝜃 𝑖 , Γ). All inequalities above become equalities, and we deduce that dist(𝜃 𝑖 , Γ) = |𝜃 𝑖 − 𝑝𝑖 |. Since 𝑝𝑖 ∈ Γ, 𝑝𝑖 is the closest point in Γ to 𝜃 𝑖 . That is, 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ). 18 (⇒) Assume Γ is a closed convex set containing 0 such that 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ) for 𝑖 ∈ 𝐼. Since 0 ∈ Γ, (𝜃 𝑖 − 𝑝𝑖 ) · (0 − 𝑝𝑖 ) ≤ 0, hence (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0. Next, fix a pair 𝑖, 𝑗 with 𝑖 ≠ 𝑗. Since 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ), it must be that for any 𝑞 ∈ Γ, (𝜃 𝑖 − 𝑝𝑖 ) · (𝑞 − 𝑝𝑖 ) ≤ 0. In particular, since 𝑝 𝑗 = 𝑝 Γ (𝜃 𝑗 ) ∈ Γ, we have (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0. □ Thus, rather than seek an optimal convex set Γ, we merely need to find the optimal points 𝑝𝑖 corresponding to each 𝜃 𝑖 ∈ Ω. Our shape optimization Problem (2.8) becomes ∫ 2 𝜃 − 𝑝(𝜃) 𝑑𝜇(𝜃) minimize 𝑝:Ω→R𝑑 Ω 2 (4.1) s.t. (𝜃 − 𝑝(𝜃)) · ( 𝑝(𝜃 ′) − 𝑝(𝜃)) ≤ 0 for all 𝜃, 𝜃 ′ ∈ Ω, (𝜃 − 𝑝(𝜃)) · (−𝑝(𝜃)) ≤ 0 for all 𝜃 ∈ Ω. As a corollary, we identify a class of problems for which Problem (2.7) has trivial solution. Corollary 9. If Ω is a subset of a sphere in R𝑑 centered at 0 with some radius 𝑟 > 0, then the optimal value of Problem (2.8) is 0. 2 Proof. Let 𝑝(𝜃) = 2𝜃 for 𝜃 ∈ Ω. Then 𝜃 − 𝑝(𝜃) = 2𝜃 . (𝜃 − 𝑝(𝜃)) · (−𝑝(𝜃)) = − |𝜃|4 ≤ 0. For any 𝜃 ′ ∈ Ω, 1 (𝜃 − 𝑝(𝜃)) · ( 𝑝(𝜃 ′) − 𝑝(𝜃)) = 𝜃 · (𝜃 ′ − 𝜃) 4 1 ≤ [|𝜃||𝜃 ′ | − |𝜃| 2 ] 4 = 0. ∫ 2 We see that 𝑝(𝜃) = 2𝜃 is feasible, and Ω 2𝜃 − 𝑝(𝜃) 𝑑𝜇(𝜃) = 0. □ Henceforth, we will restrict attention to the case when 𝜇 is finitely supported (that Í𝑘 is, Ω = {𝜃 1 , . . . , 𝜃 𝑘 } ⊆ R𝑑 , 𝜇 = 𝑖=1 𝑤 𝑖 𝛿𝜃 𝑖 , 𝑤 𝑖 > 0). In this case, Problem (4.1) takes the following form: minimize 𝑝1 ,...,𝑝 𝑘 ∈R𝑑 𝑘 ∑︁ 𝑖=1 s.t. 𝑤𝑖 2 𝜃𝑖 − 𝑝𝑖 2 (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0, (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0, 𝑖, 𝑗 = 1, . . . , 𝑘, 𝑖 ≠ 𝑗, 𝑖 = 1, . . . , 𝑘. (4.2) 19 Quadratically constrained quadratic programs (QCQPs) are widely studied in the optimization literature. Unfortunately, a general nonconvex QCQP is NP-hard. Problem (4.2), in particular, is nonconvex. This is because a constraint of the form (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0 is nonconvex in 𝑝 1 , . . . , 𝑝 𝑘 . For nonconvex QCQPs, relaxation methods exist to obtain approximate solutions, as well as provide bounds on the optimal value. In the next section, we will study the semidefinite programming relaxation problem (4.2). To motivate this relaxation, we convert problem (4.2) into matrix form. For two 𝑛×𝑛 matrices 𝐴, 𝐵, we define the Frobenius inner product 𝐴•𝐵 = tr( 𝐴𝑇 𝐵) = Í𝑛 Í𝑛 𝑖=1 𝑗=1 𝑎 𝑖 𝑗 𝑏 𝑖 𝑗 . 0 © ª ­ .. ® ­ . ®   ­ ® 𝑑×𝑘 Let 𝑋 = 𝑝 1 . . . 𝑝 𝑘 ∈ R . Let e𝑖 = ­­−1®® ∈ R 𝑘 , where −1 appears at the ­ .. ® ­ . ® ­ ® «0¬ ©0ª ­ .. ® ­ . ® ­ ® ­−1® ­ ® ­ . ® 𝑖-th entry, and let e𝑖 𝑗 = ­­ .. ®® ∈ R 𝑘 , where −1 appears at the 𝑖-th entry, and 1 ­ ® ­1® ­ ® ­ .. ® ­ . ® ­ ® 0 « ¬ ! !   𝜃   0 𝑖 appears at the 𝑗-th entry. Then 𝜃 𝑖 − 𝑝𝑖 = 𝐼 𝑋 , 𝑝 𝑗 − 𝑝𝑖 = 𝐼 𝑋 , e𝑖 e𝑖 𝑗 20 ! !  0   𝜃𝑖 𝜃𝑖 −𝑝𝑖 = 𝐼 𝑋 , − 𝑝𝑖 = 𝐼 𝑋 2 . We have e𝑖 e𝑖 2  ! !  𝜃 𝑇   0 𝑖 (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) = 𝐼 𝑋 𝐼 𝑋 e𝑖 e𝑖 𝑗 ! !  𝐼   0  = 𝜃 𝑇𝑖 e𝑇𝑖 𝐼 𝑋 𝑋𝑇 e𝑖 𝑗 ! !  𝐼  𝑋 0 = 𝜃 𝑇𝑖 e𝑇𝑖 𝑋 𝑇 𝑋 𝑇 𝑋 e𝑖 𝑗 ! !  𝜃   𝐼 𝑋 𝑖 𝑇 = 𝑇 • . 0 e 𝑖𝑗 𝑋 𝑋𝑇 𝑋 e𝑖  Similarly, 𝐼 (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) = 𝑇 𝑋 𝑋𝑇 𝑋 and 𝑘 ∑︁ 2 𝐼 𝜃𝑖 𝑤𝑖 − 𝑝𝑖 = 𝑇 2 𝑋 𝑖=1 ! 𝑋 𝑋 𝑋𝑇 𝑋 ! • •  𝜃 𝑘  ∑︁ 𝑖=1 ! 𝑖  e𝑖 𝑤𝑖 𝜃𝑖 2 e𝑖 0 e𝑇𝑖 !  𝑇 𝜃𝑖 2  , e𝑇𝑖  . Problem (4.2) may now be written as ! ! 𝑘 𝜃𝑖    ∑︁ 𝐼 𝑋 𝜃 𝑖𝑇 2 𝑇 minimize 𝑋∈R𝑑×𝑘 • 𝑤 e𝑖 𝑖 2 𝑋𝑇 𝑋𝑇 𝑋 e𝑖 𝑖=1 ! !  𝜃   𝐼 𝑋 𝑖 𝑇 s.t. • 0 e𝑖 𝑗 ≤ 0, 𝑖, 𝑗 = 1, . . . , 𝑘, 𝑖 ≠ 𝑗, 𝑋𝑇 𝑋𝑇 𝑋 e𝑖 ! !  𝜃   𝐼 𝑋 𝑖 𝑇 • ≤ 0, 𝑖 = 1, . . . , 𝑘. 0 e𝑖 𝑋𝑇 𝑋𝑇 𝑋 e𝑖 (4.3) ! ! ! 𝜃𝑖       𝑇 𝜃 𝜃 Í 𝑖 𝑖 e = 𝑘 𝑤 𝑖 2 𝜃 𝑖 e𝑇 , 𝐴 e𝑖 𝑗 = e𝑖 = Put 𝐶 0 e𝑇𝑖𝑗 , 𝐵 0 e𝑇𝑖 , 𝑌 = 𝑖=1 𝑖 2 e𝑖 e𝑖 e𝑖 !  𝐴e + 𝐴e𝑇   e e𝑇  𝐼 𝑋 𝑖𝑗 𝐵 +𝐵 𝑖𝑗 e e . Since 𝑌 is symmetric, 𝑌 • 𝐴𝑖 𝑗 = 𝑌 • , 𝑌 • 𝐵𝑖 = 𝑌 • 𝑖 2 𝑖 , 𝑌 • 2 𝑇 𝑇 𝑋 𝑋 𝑋   e𝑖 𝑗 + 𝐴 e𝑇 e𝑖 + 𝐵 e𝑇 𝐴 𝐵 e 𝐶 e𝑇 e 𝐶 e𝑇 𝑖𝑗 𝐶+ 𝑖 e = 𝑌 • 𝐶+ 𝐶 . Let 𝐴 = , 𝐵 = 𝑖 𝑗 𝑖 2 2 2 , 𝐶 = 2 . In semidefinite programming, it is customary to symmetrize the coefficient matrices. Hence, we write 21 (4.3) in equivalent symmetric form: minimize 𝑋∈R𝑑×𝑘 𝐼 𝑋𝑇 s.t. 𝐼 𝑋𝑇 𝐼 𝑋𝑇 ! 𝑋 •𝐶 𝑋𝑇 𝑋 ! 𝑋 𝑋𝑇 𝑋 • 𝐴𝑖 𝑗 ≤ 0, 𝑖, 𝑗 = 1, . . . , 𝑘, 𝑖 ≠ 𝑗, • 𝐵𝑖 ≤ 0, 𝑖 = 1, . . . , 𝑘. (4.4) ! 𝑋 𝑋𝑇 𝑋 A direct calculation shows that 𝐶, 𝐴𝑖 𝑗 , 𝐵𝑖 have the following forms: Í𝑘 𝜃 𝑖 𝜃 𝑖𝑇 © 𝑖=1 𝑤 𝑖 4 𝑇 ­ ­ −𝑤 1 𝜃 1 2 ­ ­ .. ­ . 𝐶 = ­­ 𝜃𝑇 ­ −𝑤 𝑖 2𝑖 ­ .. ­ . ­ ­ 𝜃 𝑇𝑘 −𝑤 𝑘 2 « −𝑤 1 𝜃21 . . . −𝑤 𝑖 𝜃2𝑖 𝑤1 .. . 𝑤𝑖 . . . −𝑤 𝑘 𝜃2𝑘 ª ® ® ® ® ® ®, ® ® ® .. ® . ® ® 𝑤𝑘 ¬ Í𝑘 𝜃 𝜃𝑇 𝜃𝑇 where 𝑖=1 𝑤 𝑖 𝑖4 𝑖 is 𝑑 × 𝑑, −𝑤 𝑖 𝜃2𝑖 appears in the (𝑑 + 𝑖)-th column, −𝑤 𝑖 2𝑖 appears in the (𝑑 + 𝑖)-th row. 0 . . . − 𝜃2𝑖 © 𝑑×𝑑 ­ .. ­ . ­ 𝜃𝑇 ­− 𝑖 1 ­ 𝐴𝑖 𝑗 = ­ .2 ­ .. ­ ­ 𝜃𝑗 ­ 2 − 12 ­ . . « . ... 𝜃𝑗 2 − 12 0 ... ª ® ® ® ® ® ®, ® ® ® ® ® ¬ 𝜃 where − 𝜃2𝑖 appears in the (𝑑 + 𝑖)-th column, 2𝑗 appears in the (𝑑 + 𝑗)-th column, 𝜃𝑇 𝜃𝑇 − 2𝑖 appears in the (𝑑 + 𝑖)-th row, and 2𝑗 appears in the (𝑑 + 𝑗)-th row. 𝜃𝑖 ©0𝑑×𝑑 . . . − 2 ­ .. ­ . 𝐵𝑖 = ­­ 𝜃 𝑇 1 ­ − 2𝑖 ­ . . « . . . .ª ® ® ®, ® ® ® ¬ 𝜃𝑇 where − 𝜃2𝑖 appears in the (𝑑 + 𝑖)-th column, and − 2𝑖 appears in the (𝑑 + 𝑖)-th row. 22 4.2 The SDP Relaxation For any 𝑛 > 0, let 𝑆 𝑛 be the set of real symmetric 𝑛 × 𝑛 matrices. For a symmetric matrix 𝑌 , we write 𝑌 ⪰ 0 if 𝑌 is positive semidefinite, and 𝑌 ≻ 0 if it is positive definite. Recall from the last section that we reformulated (2.1) as (4.4): minimize𝑍 ∈𝑆 𝑑+𝑘 s.t. 𝑍 •𝐶 𝑍 • 𝐴𝑖 𝑗 ≤ 0, 𝑖, 𝑗 = 1, . . . , 𝑘, 𝑖 ≠ 𝑗, 𝑍 • 𝐵𝑖 ≤ 0, 𝑖 = 1, . . . , 𝑘, ! 𝑍= 𝐼 𝑋𝑇 𝑋 . 𝑋𝑇 𝑋 ! 𝐼 𝑋 Observe that 𝑍 = is a positive semidefinite matrix of rank 𝑑. In fact, 𝑋𝑇 𝑋𝑇 𝑋 we have the following equvalence: ! 𝐼 𝑋 Proposition 10. Let 𝑍 = ∈ 𝑆 𝑑+𝑘 , with 𝑍 ⪰ 0. Then 𝑍 has rank 𝑑 if and 𝑋𝑇 𝑌 only if 𝑌 = 𝑋 𝑇 𝑋. Proof. If 𝑌 = 𝑋 𝑇 𝑋, then 𝑍 = 𝑈 𝑇 𝑈, where 𝑈 =   𝐼 𝑋 . Since 𝑈 has 𝑑 independent rows, rank 𝑈 = 𝑑. Hence, rank 𝑈 𝑇 𝑈 = rank 𝑈 = 𝑑. Conversely, assume 𝑍 ⪰ 0 has rank 𝑑. Then  𝑍 admits  decomposition of the form 𝑍 = 𝑈 𝑇 𝑈, where 𝑈 ∈ R𝑑×(𝑑+𝑘) . Write 𝑈 = 𝑀 𝑁 , where 𝑀 ∈ R𝑑×𝑑 , 𝑁 ∈ R𝑑×𝑘 . Then ! ! 𝐼 𝑋 𝑀𝑇 𝑀 𝑀𝑇 𝑁 𝑇 = 𝑍 =𝑈 𝑈 = . 𝑋𝑇 𝑌 𝑁𝑇 𝑀 𝑁𝑇 𝑁 In particular, 𝑀 𝑇 𝑀 = 𝐼, so 𝑀 is an orthogonal matrix. Also, 𝑋 = 𝑀 𝑇 𝑁, 𝑌 = 𝑁 𝑇 𝑁. It follows that 𝑌 = 𝑁 𝑇 𝑁 = 𝑁 𝑇 𝑀 𝑀 𝑇 𝑁 = (𝑀 𝑇 𝑁)𝑇 (𝑀 𝑇 𝑁) = 𝑋 𝑇 𝑋. □ ! 𝐼 𝑋 From Proposition 10, we see that the condition 𝑍 = is equivalent to 𝑋𝑇 𝑋𝑇 𝑋 ! 𝐼 𝑋 𝑍= 𝑇 ⪰ 0 for some 𝑌 ∈ 𝑆 𝑘 , and rank 𝑍 = 𝑑. The semidefinite programming 𝑋 𝑌 23 relaxation of QCQP is obtained by removing the rank constraint: minimize𝑍 ∈𝑆 𝑑+𝑘 s.t. 𝑍 •𝐶 𝑍 • 𝐴𝑖 𝑗 ≤ 0, 𝑖, 𝑗 = 1, . . . , 𝑘, 𝑖 ≠ 𝑗, 𝑍 • 𝐵𝑖 ≤ 0, 𝑖 = 1, . . . , 𝑘, (4.5) ! 𝑍= 𝐼 𝑋 ⪰ 0. 𝑋𝑇 𝑌 Since (4.5) is a relaxation of (4.4), the optimal value of (4.5) is a lower bound for the optimal value of (4.4). We sometimes need to specify the dependence of problem (4.5) on the input data 𝜃 = (𝜃 1 , . . . , 𝜃 𝑘 ) and 𝑤 = (𝑤 1 , . . . , 𝑤 𝑘 ). We will refer to it as Problem (4.5) with parameters (𝜃, 𝑤). In the next section, we will explore further relation between (4.5) and the (4.4). For the remainder of this section, we will discuss some known facts about semidefinite programming in general. Preliminaries on Semidefinite Programming Semidefinite programming is a generalization of linear programming. It has become a popular method in optimization due to two reasons: 1. A wide range of engineering problems can be formulated in terms of semidefinite programming. 2. Methods exist to solve this class of problems, both theoretically (strong duality) and numerically (interior point method). We will briefly discuss duality theory for semidefinite programming. The standard form of semidefinite program (SDP) is 𝑠∗ = inf𝑛 𝑋 • 𝐶 𝑋∈𝑆 s.t. 𝑋 • 𝐴𝑖 = 𝑎𝑖 , 𝑖 = 1, . . . , 𝑚, (4.6) 𝑋 ⪰ 0, where 𝐶, 𝐴𝑖 ∈ 𝑆 𝑛 . The dual problem is 𝑑∗ = sup 𝑚 ∑︁ 𝑦𝑖 𝑎𝑖 𝑦 1 ,...,𝑦 𝑚 ∈R 𝑖=1 s.t. 𝐶 − 𝑚 ∑︁ 𝑦𝑖 𝐴𝑖 ⪰ 0. 𝑖=1 The following theorem concerning strong duality of SDP can be found in [1]. (4.7) 24 Theorem 11. Assume there exists 𝑋 feasible for (4.6) such that 𝑋 ≻ 0, and that Í𝑚 there exist 𝑦 1 , . . . , 𝑦 𝑚 ∈ R such that 𝐶 − 𝑖=1 𝑦𝑖 𝐴𝑖 ≻ 0. Then both (4.6) and (4.7) ∗ ∗ attain their optimal values, and 𝑠 = 𝑑 . Moreover, a feasible primal dual pair Í𝑚 (𝑋, 𝑦) is optimal if and only if 𝑋 • (𝐶 − 𝑖=1 𝑦𝑖 𝐴𝑖 ) = 0. Our problem (4.5) is not in standard form because it contains inequality constraints. We need to adapt the preceding strong duality theorem to our case of interest. Corollary 12. Consider a semidefinite program with both equality and inequality constraints: 𝑠∗ = inf𝑛 𝑋 • 𝐶 𝑋∈𝑆 s.t. 𝑋 • 𝐴𝑖 = 𝑎𝑖 , 𝑖 = 1, . . . , 𝑚, 𝑋 • 𝐵𝑗 ≤ 𝑏𝑗, 𝑗 = 1, . . . , 𝑘, (4.8) 𝑋 ⪰ 0, and its dual problem 𝑑∗ = 𝑚 ∑︁ sup 𝑦 1 ,...,𝑦 𝑚 ∈R,𝑧1 ,...,𝑧 𝑘 ≤0 𝑖=1 s.t. 𝐶 − 𝑚 ∑︁ 𝑦𝑖 𝐴𝑖 − 𝑘 ∑︁ 𝑖=1 𝑦𝑖 𝑎𝑖 + 𝑘 ∑︁ 𝑧𝑗𝑏𝑗 𝑗=1 (4.9) 𝑧 𝑗 𝐵 𝑗 ⪰ 0. 𝑗=1 Assume there exists 𝑋 ≻ 0 such that 𝑋 • 𝐴𝑖 = 𝑎𝑖 , 𝑋 • 𝐵 𝑗 < 𝑏 𝑗 , and there exist Í Í𝑚 𝑦𝑖 𝐴𝑖 − 𝑘𝑗=1 𝑧 𝑗 𝐵 𝑗 ≻ 0. Then both 𝑦 1 , . . . , 𝑦 𝑚 ∈ R, 𝑧1 , . . . , 𝑧 𝑘 < 0 such that 𝐶 − 𝑖=1 (4.8) and (4.9) attain their optimal values, and 𝑠∗ = 𝑑 ∗ . Moreover, a feasible primal Í𝑚 Í dual pair (𝑋, 𝑦, 𝑧) is optimal if and only if 𝑋 • (𝐶 − 𝑖=1 𝑦𝑖 𝐴𝑖 − 𝑘𝑗=1 𝑧 𝑗 𝐵 𝑗 ) = 0 and Í𝑘 𝑗=1 𝑧 𝑗 (𝑏 𝑗 − 𝑋 • 𝐵 𝑗 ) = 0. ! ! ! 𝐶 0 𝐴 0 𝐵 0 𝑗 e= e𝑖 = 𝑖 e𝑗 = Proof. Put 𝐶 ,𝐴 ,𝐵 ∈ 𝑆 𝑛+𝑘 , where 𝐸 𝑗 is 𝑘 × 𝑘 0 0 0 0 0 𝐸𝑗 with 1 at the 𝑗 𝑗-th entry, zero everywhere else. e e•𝐶 𝑠∗ = inf 𝑋 e 𝑛+𝑘 𝑋∈𝑆 s.t. e𝑖 = 𝑎𝑖 , e• 𝐴 𝑋 e• 𝐵 e𝑗 = 𝑏 𝑗 , 𝑋 𝑖 = 1, . . . , 𝑚, 𝑗 = 1, . . . , 𝑘, ! 𝑋 0 e= 𝑋 ⪰ 0. 0 diag(𝑡 1 , . . . , 𝑡 𝑘 ) (4.10) 25 e be zero can be stated as The requirement that certain off-diagonal entries of 𝑋 𝐹𝑖 𝑗 +𝐹𝑖𝑇𝑗 e• 𝐹 e𝑖 𝑗 = 0, where 𝐹 e𝑖 𝑗 = equality constraints: 𝑋 , and 𝐹𝑖 𝑗 has a 1 at the 𝑖 𝑗th 2 entry, zero everywhere else. Hence, (4.10) is an SDP in standard form.! Observe that 𝑋∗ 0 𝑋 ∗ is optimal for problem (4.8) if and only if ⪰ 0, where ∗ 0 diag(𝑡1 , . . . , 𝑡 ∗𝑘 ) 𝑡 ∗𝑗 = 𝑏 𝑗 − 𝑋 ∗ • 𝐵 𝑗 , is optimal for (4.10). The dual of (4.10) is ∗ 𝑚 ∑︁ sup 𝑑 = 𝑦𝑖 𝑎𝑖 + 𝑦 1 ,...,𝑦 𝑚 ,𝑧1 ,...,𝑧 𝑘 , 𝑓𝑖 𝑗 ∈R 𝑖=1 s.t. 𝐶− Í𝑚 𝑖=1 𝑦 𝑖 𝐴𝑖 − 𝑘 ∑︁ 𝑧𝑗𝑏𝑗 𝑗=1 Í𝑘 0 𝑗=1 𝑧 𝑗 𝐵 𝑗 diag(−𝑧1 , . . . , −𝑧 𝑘 ) 0 (4.11) ! − ∑︁ 𝑓𝑖 𝑗 𝐹𝑖 𝑗 ⪰ 0. 𝑖, 𝑗 Observe that (𝑦 ∗ , 𝑧∗ ) is optimal for (4.9) if and only if there exist 𝑓𝑖∗𝑗 ∈ R such that (𝑦 ∗ , 𝑧∗ , 𝑓 ∗ ) is optimal for (4.11). By assumption, there exists 𝑋 ≻ 0 such that 𝑋 • 𝐴𝑖 ! = 𝑎𝑖 , 𝑋 • 𝐵 𝑗 < 𝑏 𝑗 . Let 𝑋 0 e𝑖 = 𝑎𝑖 , e = e• 𝐴 𝑡 𝑗 = 𝑏 𝑗 − 𝑋 • 𝐵 𝑗 . Then 𝑋 ≻ 0, and 𝑋 0 diag(𝑡 1 , . . . , 𝑡 𝑘 ) e• 𝐵 e𝑗 = 𝑏 𝑗 . Also by assumption, there exist 𝑦 1 , . . . , 𝑦 𝑚 ∈ R, 𝑧1 , . . . , 𝑧 𝑘 < 0 𝑋 Í𝑚 Í such that 𝐶 − 𝑖=1 𝑦𝑖 𝐴𝑖 − 𝑘𝑗=1 𝑧 𝑗 𝐵 𝑗 ≻ 0. Letting 𝑓𝑖 𝑗 = 0, we obtain (𝑦, 𝑧, 𝑓 ) such ! Í𝑚 Í 𝐶 − 𝑖=1 𝑦𝑖 𝐴𝑖 − 𝑘𝑗=1 𝑧 𝑗 𝐵 𝑗 0 Í that − 𝑓𝑖 𝑗 𝐹𝑖 𝑗 ≻ 0. By theorem 0 diag(−𝑧1 , . . . , −𝑧 𝑘 ) 11, (4.10) and (4.11) satisfy strong duality. Moreover, a feasible primal dual pair e 𝑦, 𝑧, 𝑓 ) is optimal if and only if ( 𝑋, ! ! o n 𝐶 − Í𝑚 𝑦 𝐴 − Í 𝑘 𝑧 𝐵 ∑︁ 0 𝑋 0 𝑖=1 𝑖 𝑖 𝑗=1 𝑗 𝑗 − 𝑓𝑖 𝑗 𝐹𝑖 𝑗 = 0 • 0 diag(𝑡1 , . . . , 𝑡 𝑘 ) 0 diag(−𝑧1 , . . . , −𝑧 𝑘 ) or equivalently, 𝑋 • (𝐶 − Í𝑚 𝑖=1 𝑦 𝑖 𝐴𝑖 − Í𝑘 𝑗=1 𝑧 𝑗 𝐵 𝑗 ) = 0 and Í𝑘 𝑗=1 𝑧 𝑗 𝑡 𝑗 = 0. □ Strong Duality of (4.5) The dual of (4.5) is maximize tr(𝑉) ! 𝑉 0 s.t. 𝐶 − 𝑦𝑖 𝑗 𝐴𝑖 𝑗 − 𝑧 𝑖 𝐵𝑖 − ⪰ 0, 0 0 𝑖≠ 𝑗 𝑖=1 ∑︁ 𝑘 ∑︁ 𝑦𝑖 𝑗 ≤ 0, 𝑧𝑖 ≤ 0, 𝑉 ∈ 𝑆 𝑑 . (4.12) 26 Lemma 13. Problem (4.12) is strictly feasible. That is, there ! exist 𝑦𝑖 𝑗 < 0, 𝑧𝑖 < 0 𝑉 0 Í𝑘 Í 𝑧 𝑖 𝐵𝑖 − ≻ 0. and 𝑉 ∈ 𝑆 𝑑 such that 𝐶 − 𝑖≠ 𝑗 𝑦𝑖 𝑗 𝐴𝑖 𝑗 − 𝑖=1 0 0 Proof. For any 𝑉 ∈ 𝑆 𝑑 , ! ! Í𝑘 𝜃 𝑖 𝜃 𝑖𝑇 𝑉 0 𝑤 − 𝑉 Ξ 𝑖 𝑖=1 4 𝐶− = 0 0 Ξ𝑇 diag(𝑤 1 , . . . , 𝑤 𝑘 )   Í𝑘 𝜃 𝑖 𝜃 𝑖𝑇 ! 𝑉 0 − 𝜇𝐼, so 𝐶 − = 0 0 where Ξ = −𝑤 1 𝜃21 . . . −𝑤 𝑘 𝜃2𝑘 . Let 𝑉 = − 𝑖=1 4 ! 𝜇𝐼 Ξ −1 𝑇 . For sufficiently large 𝜇, 𝜇𝐼 − Ξdiag(𝑤 −1 1 , . . . , 𝑤 𝑘 )Ξ ≻ 𝑇 Ξ diag(𝑤 1 , . . . , 𝑤 𝑘 ) ! 𝑉 0 0. By the Schur complement criterion, 𝐶 − ≻ 0. For sufficiently small 𝜀, 0 0 ! 𝑉 0 Í Í𝑘 −𝜀 < 𝑦𝑖 𝑗 , 𝑧𝑖 < 0 guarantees 𝐶 − − 𝑖≠ 𝑗 𝑦𝑖 𝑗 𝐴𝑖 𝑗 − 𝑖=1 𝑧𝑖 𝐵𝑖 ≻ 0. □ 0 0 Lemma 14. Assume 0 ∉ {𝜃 !1 , . . . , 𝜃 𝑘 }. Then problem (4.5) is strictly feasible. That 𝐼 𝑋 is, there exists 𝑍 = 𝑇 ≻ 0 such that 𝑍 • 𝐴𝑖 𝑗 < 0, 𝑍 • 𝐵𝑖 < 0 for all 𝑖, 𝑗. 𝑋 𝑌 Proof. In R𝑑+1 , let Γ be the ball centered at (0, . . . , 0, 1)𝑇 with radius 1. Γ is a closed convex set in R𝑑+1 containing 0. Let ( 𝑝𝑖 , 𝑞𝑖 ) = 𝑝 Γ (𝜃 𝑖 ), where 𝑝𝑖 ∈ R𝑑 , 𝑞𝑖 ∈ R. !     𝐼 𝑋 Let 𝑋 = 𝑝 1 . . . 𝑝 𝑘 , 𝑋 ′ = 𝑞 1 . . . 𝑞 𝑘 , 𝑌 = 𝑋 𝑇 𝑋 + (𝑋 ′)𝑇 𝑋 ′, 𝑍 = . 𝑋𝑇 𝑌 Then 𝑍 • 𝐴𝑖 𝑗 = ((𝜃 𝑖 , 0) − ( 𝑝𝑖 , 𝑞𝑖 )) · (( 𝑝 𝑗 , 𝑞 𝑗 ) − ( 𝑝𝑖 , 𝑞𝑖 )), 𝑍 • 𝐵𝑖 = ((𝜃 𝑖 , 0) − ( 𝑝𝑖 , 𝑞𝑖 )) · (−( 𝑝𝑖 , 𝑞𝑖 )). Let 𝑧 = (0, . . . , 0, 1), 𝑣 𝑖 = (𝜃 𝑖 , 0) − 𝑧. It’s clear from geometry that ( 𝑝𝑖 , 𝑞𝑖 ) = 𝑧 + |𝑣𝑣 𝑖𝑖 | , and |𝑣 𝑖 | = |(𝜃 𝑖 , 1)| > 1. Moreover, ((𝜃 𝑖 , 0) − ( 𝑝𝑖 , 𝑞𝑖 )) · (( 𝑝 𝑗 , 𝑞 𝑗 ) − ( 𝑝𝑖 , 𝑞𝑖 ))    𝑣𝑗 𝑣 𝑖   𝑣 𝑖  = 𝑧 + 𝑣𝑖 − 𝑧 + · 𝑧+ − 𝑧+ |𝑣 𝑖 | |𝑣 𝑗 | |𝑣 𝑖 | 𝑣𝑖  𝑣 𝑗 𝑣𝑖  = (|𝑣 𝑖 | − 1) · − |𝑣 𝑖 | |𝑣 𝑗 | |𝑣 𝑖 |  𝑣𝑖 · 𝑣 𝑗  = (|𝑣 𝑖 | − 1) −1 . |𝑣 𝑖 ||𝑣 𝑗 | 27 By Cauchy-Schwarz, 𝑣 𝑖 · 𝑣 𝑗 ≤ |𝑣 𝑖 ||𝑣 𝑗 |. Moreover, 𝑣 𝑖 , 𝑣 𝑗 are not collinear. Indeed, if 𝑣 𝑖 = 𝛼𝑣 𝑗 , then (𝜃 𝑖 − 𝛼𝜃 𝑗 , 0) = (1 − 𝛼)𝑧. For the last coordinate to be zero, we must have 𝛼 = 1. But then 𝜃 𝑖 − 𝜃 𝑗 = 0, which is a contradiction. Thus, 𝑣 𝑖 · 𝑣 𝑗 < |𝑣 𝑖 ||𝑣 𝑗 |. We deduce that  𝑣𝑖 · 𝑣 𝑗  ((𝜃 𝑖 , 0) − ( 𝑝𝑖 , 𝑞𝑖 )) · (( 𝑝 𝑗 , 𝑞 𝑗 ) − ( 𝑝𝑖 , 𝑞𝑖 )) = (|𝑣 𝑖 | − 1) − 1 < 0. |𝑣 𝑖 ||𝑣 𝑗 | Similarly,    𝑣 𝑖   𝑣 𝑖  ((𝜃 𝑖 , 0) − ( 𝑝𝑖 , 𝑞𝑖 )) · (0 − ( 𝑝𝑖 , 𝑞𝑖 )) = 𝑧 + 𝑣 𝑖 − 𝑧 + · 0− 𝑧+ |𝑣 𝑖 | |𝑣 𝑖 | 𝑣𝑖  𝑣𝑖  = (|𝑣 𝑖 | − 1) · −𝑧− |𝑣 𝑖 | |𝑣 𝑖 |   < (|𝑣 𝑖 | − 1) |𝑧| − 1 = 0. ! 𝐼 𝑋 We conclude that 𝑍 = ⪰ 0, with 𝑍 • 𝐴𝑖 𝑗 < 0, 𝑍 • 𝐵𝑖 < 0 for all 𝑖, 𝑗. By 𝑋𝑇 𝑌 ! 𝐼 𝑋 e= the Schur complement criterion, 𝑌 − 𝑋 𝑇 𝑋 ⪰ 0. Put 𝑍 . Then for 𝑋 𝑇 𝑌 + 𝜀𝐼 e • 𝐴𝑖 𝑗 < 0, 𝑍 e • 𝐵𝑖 < 0 for all 𝑖, 𝑗. Moreover, 𝑌 + 𝜀𝐼 − 𝑋 𝑇 𝑋 ≻ 0, sufficiently small 𝜀, 𝑍 e ≻ 0. so 𝑍 □ Remark 5. Any feasible value of the dual problem (4.12) is a lower bound for the optimal value of Problem (4.4). 4.3 Relation between SDP and QCQP In this section, we investigate the question of when the solution of the relaxed problem (4.5) gives a solution of the complete problem (4.4). In the case when relaxation fails to solve the complete problem, we provide an economic interpretation for this relaxation gap. 𝑇 Recall that (4.5) relaxes (4.4) by dropping ! the constraint 𝑌 = 𝑋 𝑋, or equivalently 𝐼 𝑋 (by Proposition 10), the rank = 𝑑 constraint. We say that Problem (4.5) 𝑋𝑇 𝑌 ! 𝐼 𝑋 with parameters (𝜃, 𝑤) is exact if every optimal solution 𝑍 = satisfies 𝑋𝑇 𝑌 rank 𝑍 = 𝑑. Í𝑘 Theorem 15. Put Ω = {𝜃 1 , . . . , 𝜃 𝑘 }, 𝜇 = 𝑖=1 𝑤 𝑖 𝛿𝜃 𝑖 . Problem (4.5) with parameters (𝜃, 𝑤) is exact if and only if (Ω, 𝜇) is localizable. 28 ! 𝐼𝑑 𝑋 optimal for (4.5), 𝑋𝑇 𝑌 with rank 𝑍 = 𝑑 + 𝑟 > 𝑑. Since 𝑍 ⪰ 0, 𝑌 − 𝑋 𝑇 𝑋 ⪰ 0. Moreover, since rank 𝑍 > 𝑑, 𝑌 − 𝑋 𝑇 𝑋 ≠ 0. In fact, by the Guttman rank additivity formula (see [16]), 𝑇 ′ 𝑇 ′ rank (𝑌 − 𝑋 𝑇 𝑋) = 𝑟. Hence, there exists 𝑋 ′ ∈ R𝑟×𝑘 such that ! 𝑌 = 𝑋 ! 𝑋 + (𝑋 ) 𝑋 . 𝑝𝑖 𝜃𝑖 Put 𝑋 = ( 𝑝 1 , . . . , 𝑝 𝑘 ), 𝑋 ′ = ( 𝑝′1 , . . . , 𝑝′𝑘 ), and let 𝑝e𝑖 = ′ , e 𝜃𝑖 = . Then 𝑝𝑖 0 Proof. Suppose (Ω, 𝜇) is localizable. Consider 𝑍 = (e 𝜃 𝑖 − 𝑝e𝑖 ) · ( 𝑝e𝑗 − 𝑝e𝑖 ) = (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) + (−𝑝′𝑖 ) · ( 𝑝′𝑗 − 𝑝′𝑖 ) = 𝜃 𝑇𝑖 ( 𝑝 𝑗 − 𝑝𝑖 ) + e𝑇𝑖 𝑋 𝑇 𝑋e𝑖 𝑗 + e𝑇𝑖 (𝑋 ′)𝑇 𝑋 ′e𝑖 𝑗 = 𝜃 𝑇𝑖 𝑋e𝑖 𝑗 + e𝑇𝑖 𝑌 e𝑖 𝑗 !  0   𝑇 𝑇 =𝑍• 𝜃 𝑖 e𝑖 e𝑖 𝑗 = 𝑍 • 𝐴𝑖 𝑗 ≤ 0, (e 𝜃 𝑖 − 𝑝e𝑖 ) · (−e 𝑝𝑖 ) = (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) + | 𝑝′𝑖 | 2 = 𝜃 𝑇𝑖 (−𝑝𝑖 ) + e𝑇𝑖 𝑋 𝑇 𝑋e𝑖 + e𝑇𝑖 (𝑋 ′)𝑇 𝑋 ′e𝑖 = 𝜃 𝑇𝑖 𝑋e𝑖 + e𝑇𝑖 𝑌 e𝑖 !  0   =𝑍• 𝜃 𝑇𝑖 e𝑇𝑖 e𝑖 = 𝑍 • 𝐵𝑖 ≤ 0, 29 and 𝑘 ∑︁ 𝑘 𝜃  ∑︁ e 2 2 𝜃𝑖 𝑖 𝑤𝑖 − 𝑝𝑖 = 𝑤𝑖 − 𝑝𝑖 + | 𝑝′𝑖 | 2 2 2 𝑖=1 𝑖=1 = 𝑘 ∑︁  |𝜃 | 2  𝜃𝑇 − 2 𝑖 𝑝𝑖 + | 𝑝𝑖 | 2 + | 𝑝′𝑖 | 2 4 2 𝑖 𝑤𝑖 𝑖=1 = 𝑘 ∑︁  |𝜃 | 2  𝜃𝑇 − 2 𝑖 𝑋e𝑖 + e𝑇𝑖 𝑋 𝑇 𝑋e𝑖 + e𝑇𝑖 (𝑋 ′)𝑇 𝑋 ′e𝑖 4 2 𝑖 𝑤𝑖 𝑖=1 𝑘 ∑︁  |𝜃 | 2  𝜃 𝑇𝑖 𝑇 𝑤𝑖 − 2 𝑋e𝑖 + e𝑖 𝑌 e𝑖 = 4 2 𝑖=1 ! 𝑘  𝜃𝑖  𝑇  ∑︁ = 𝑍 • 𝑤 𝑖 2 𝜃2𝑖 ; e𝑇𝑖 e𝑖 𝑖=1 𝑖 = 𝑍 • 𝐶. By Proposition 8, there exists a convex set Γ in R𝑑+𝑟 such that 0 ∈ Γ, and 𝑝e𝑖 = 𝑝 Γ ( e 𝜃 𝑖 ). By localizability, 𝑝e𝑖 ∈ R𝑑 , so 𝑝′𝑖 = 0. But this implies 𝑋 ′ = 0, and rank 𝑍 = 𝑑, contradiction. Conversely, assume (4.5) is exact. Consider a higher dimension 𝑑 ′ = 𝑑 + 𝑟 > 𝑑, ! ! 𝜃 𝑝 ′ 𝑖 𝑖 and a convex region Γ ⊆ R𝑑 containing 0. Put e 𝜃𝑖 = . Let 𝑝e𝑖 = 𝑝 Γ ( e 𝜃𝑖 ) = ′ , 0 𝑝𝑖 𝑑 ′ 𝑟 where 𝑝𝑖 ∈ R , 𝑝𝑖 ∈ R . Assume Γ is optimal: 𝑘 ∑︁ 𝑤𝑖 𝑖=1   𝑋′  e 2 𝜃𝑖 − 𝑝e𝑖 = 𝑠∗ . 2  Let 𝑋 = 𝑝 1 . . . 𝑝 𝑘 , = , and 𝑌 = 𝑋 𝑇 𝑋 + (𝑋 ′)𝑇 𝑋 ′, 𝑍 = ... ! 𝐼𝑑 𝑋 . As before, a direct calculation shows that 𝑍 is feasible for (4.5), with 𝑋𝑇 𝑌 2 Í𝑘 e 𝑍 • 𝐶 = 𝑖=1 𝑤 𝑖 𝜃2𝑖 − 𝑝e𝑖 = 𝑠∗ . Since (4.5) is exact, rank 𝑍 = 𝑑. It follows that 𝑝′1 𝑝′𝑘 𝑌 = 𝑋 𝑇 𝑋, and 𝑋 ′ = 0. We conclude 𝑝e𝑖 = 𝑝 Γ (𝜃 𝑖 ) ∈ R𝑑 . □ Remark 6. Theorem 15 provides an interpretation of the relaxation gap when Problem (4.5) fails to be exact. When such a gap exists, one can exceed the optimal value of problem (2.8) by embedding the problem in higher dimensions. 𝑌 − 𝑋 𝑇 𝑋 is accounted for by the last 𝑑 ′ − 𝑑 coordinates of 𝑝 Γ (𝜃 1 ), . . . , 𝑝 Γ (𝜃 𝑘 ) of the higherdimensional optimum. 30 Remark 7. We may also view the nonexactness of Problem (4.5) in terms of the original optimal fund menus problem. Suppose, in addition to the 𝑑 existing assets, the fund manager is able to offer 𝑟 additional artificial assets whose returns (in excess of the risk free rate) are independent with mean 0, and that investors have no exposure to these additional assets. The corresponding shape optimization problem is precisely 𝑘 ∑︁ 2 𝜃𝑖 𝑤 𝑖 − 𝑝 Γ (𝜃 𝑖 ) minimizeΓ 2 (4.13) 𝑖=1 s.t. Γ ⊆ R𝑑+𝑟 closed and convex, 0 ∈ Γ. When exactness/localizability fails, the optimal 𝑝 Γ (𝜃 1 ), . . . , 𝑝 Γ (𝜃 𝑘 ) do not lie in R𝑑 . The last 𝑟 coordinates of 𝑝 Γ (𝜃 𝑖 ) represent the amount invested in the 𝑟 artificial assets by type 𝜃 𝑖 . Since investors have no initial exposure to them, the zero mean return artificial assets can only decrease their utility. If all assets were offered separately, no one would invest in the artificial ones. Thus, failure of regularity represents an opportunity for the fund manager to extract more profit by bundling assets that are of no value to investors. We conclude this section with a sufficient condition for uniqueness of Problem (4.4). Proposition 16. If Problem (4.5) with parameters (𝜃, 𝑤) is exact, then both (4.5) and (4.4) have a unique solution. Proof. Since (4.5) is exact, by Theorem (15), any optimal! solution has rank 𝑑,!and ! 𝐼𝑑 𝑋 𝐼𝑑 𝑋1 𝐼𝑑 𝑋2 is of the form 𝑍 = . Let 𝑍1 = , 𝑍2 = be 𝑇 𝑇 𝑇 𝑇 𝑇 𝑋 𝑋 𝑋 𝑋1 𝑋1 𝑋1 𝑋2 𝑋2𝑇 𝑋2 two solutions. Since (4.5) is a convex problem, 12 𝑍1 + 21 𝑍2 is also optimal. By assumption, ! 1 1 𝑋 + 𝑋 𝐼𝑑 1 1 1 2 2 𝑍1 + 𝑍2 = 1 𝑇 1 𝑇 1 𝑇2 1 𝑇 2 2 2 𝑋1 + 2 𝑋2 2 𝑋1 𝑋1 + 2 𝑋2 𝑋2 has rank 𝑑. Consequently, 1 𝑇 1 1 1 1 1 𝑋1 𝑋1 + 𝑋2𝑇 𝑋2 = ( 𝑋1 + 𝑋2 )𝑇 ( 𝑋1 + 𝑋2 ) 2 2 2 2 2 2 1 𝑇 1 𝑇 1 𝑇 1 = 𝑋1 𝑋1 + 𝑋1 𝑋2 + 𝑋2 𝑋1 + 𝑋2𝑇 𝑋2 . 4 4 4 4 31 Subtracting 12 𝑋1𝑇 𝑋1 + 12 𝑋2𝑇 𝑋2 from both sides, we find 1 1 1 1 0 = − 𝑋1𝑇 𝑋1 + 𝑋1𝑇 𝑋2 + 𝑋2𝑇 𝑋1 − 𝑋2𝑇 𝑋2 4 4 4 4 1 = − (𝑋1 − 𝑋2 )𝑇 (𝑋1 − 𝑋2 ). 4 This implies 𝑋1 = 𝑋2 . Hence, the solution of (4.5) is unique. Due to exactness,!any solution 𝑝 1 , . . . , 𝑝 𝑘 of (4.4) corresponds to an optimal solution   𝐼𝑑 𝑋 𝑍 = of (4.5) via 𝑋 = 𝑝 1 . . . 𝑝 𝑘 . Consequently, the solution of 𝑋𝑇 𝑋𝑇 𝑋 (4.4) is also unique. □ 4.4 Special Cases The following proposition shows that when there is only one asset, and all investors share similar level of exposure to it, then the type distribution is regular. Proposition 17. Assume 0 < 𝜃 1 < · · · < 𝜃 𝑘 ∈ R, and 𝜃2𝑘 ≤ 𝜃 1 . Then for any Í𝑘 𝑤 1 , . . . , 𝑤 𝑘 > 0, ({𝜃 1 , . . . , 𝜃 𝑘 }, 𝑖=1 𝑤 𝑖 𝛿𝜃 𝑖 ) is localizable. Proof. For convenience, put 𝜁𝑖 = 𝜃2𝑖 . Suppose Γ is a convex region containing 0 such that 𝜃 1 , . . . , 𝜃 𝑘 are projected to 𝑝 1 , . . . , 𝑝 𝑘 ∈ R𝑑 , with 𝑝 1 , . . . , 𝑝𝑟−1 ∈ R, 𝑝𝑟 ∉ R. Since dim span(R ∪ {𝑝𝑟 }) = 2, we may assume (after change of coordinates) that 𝑝𝑟 = ( 𝑝′𝑟 , 𝑞𝑟 ) ∈ R2 , where 𝑞𝑟 ≠ 0. Note that by Proposition 8, 𝑝 1 , . . . , 𝑝 𝑘 satisfy (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0 (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0 for all 𝑖 ≠ 𝑗, for all 𝑖. Let H𝑟n = {𝑥 ∈ R𝑑 | (𝑥 − 𝑝𝑟 ) · (𝜃 𝑟 − o𝑝𝑟 ) ≤ 0}. Then 𝑝 1 , . . . , 𝑝 𝑘 ∈ Γ ⊆ H𝑟 . Let 𝐵𝑖 = 𝑥 ∈ R𝑑 𝑥 − 𝑝𝑟2+𝜃 𝑖 ≤ 𝑝𝑟 2−𝜃 𝑖 be the Euclidean ball in R𝑑 with diameter [ 𝑝𝑟 , 𝜃𝑖 ]. Since ( 𝑝𝑟 − 𝑝𝑖 ) · (𝜃 𝑖 − 𝑝𝑖 ) ≤ 0, we must have 𝑝𝑖 ∈ 𝐵𝑖 . Indeed, 𝑝𝑖 − 𝑝𝑟 + 𝜃𝑖 2 𝑝𝑟 + 𝜃𝑖 2 = | 𝑝𝑖 | 2 − 𝑝𝑖 · ( 𝑝𝑟 + 𝜃𝑖 ) + 2 2 𝑝 𝑟 + 𝜃𝑖 2 = | 𝑝𝑖 | 2 − 𝑝𝑖 · 𝑝𝑟 − 𝑝𝑖 · 𝜃𝑖 + 2    𝑝𝑟 + 𝜃𝑖 2  = | 𝑝𝑖 | 2 − 𝑝𝑖 · 𝑝𝑟 − 𝑝𝑖 · 𝜃𝑖 + 𝑝𝑟 𝜃𝑖 + − 𝑝𝑟 𝜃𝑖 + 2 𝑝𝑟 − 𝜃𝑖 2 = ( 𝑝𝑟 − 𝑝𝑖 ) · (𝜃 𝑖 − 𝑝𝑖 ) + 2 𝑝𝑟 − 𝜃𝑖 2 ≤ . 2 32 We have shown that 𝑝𝑖 ∈ H𝑟 ∩ 𝐵𝑖 for 𝑖 > 𝑟. We claim that |𝜁𝑖 − 𝑝𝑖 | ≥ inf 𝑧∈H𝑟 ∩𝐵𝑖 |𝜁𝑖 − 𝑧| = |𝜁𝑖 − 𝑝𝑟 | for 𝑖 > 𝑟. To see this, consider the problem minimize |𝜁𝑖 − 𝑧| 2 𝑝𝑟 + 𝜃𝑖 2 𝑝𝑟 − 𝜃𝑖 2 ≤ , s.t. 𝑧− 2 2 (𝜃 𝑟 − 𝑝𝑟 ) · (𝑧 − 𝑝𝑟 ) ≤ 0. The Lagrangian is 𝐿 (𝑧, 𝜆1 , 𝜆2 )  𝑝𝑟 − 𝜃𝑖 2  𝑝𝑟 + 𝜃𝑖 2 − + 𝜆2 (𝜃 𝑟 − 𝑝𝑟 ) · (𝑧 − 𝑝𝑟 ) = |𝜁𝑖 − 𝑧| 2 + 𝜆1 𝑧 − 2 2 = |𝜁𝑖 − 𝑧| 2 + 𝜆1 ( 𝑝𝑟 − 𝑧)(𝜃 𝑖 − 𝑧) + 𝜆 2 (𝜃 𝑟 − 𝑝𝑟 ) · (𝑧 − 𝑝𝑟 )   = (1 + 𝜆1 )|𝑧| 2 + − 2𝜁1 − 𝜆 1 ( 𝑝𝑟 + 𝜃 𝑖 ) + 𝜆 2 (𝜃 𝑟 − 𝑝𝑟 ) · 𝑧 + |𝜁𝑖 | 2 + 𝜆 1 𝑝𝑟 · 𝜃 𝑖 − 𝜆 2 𝜃 𝑟 · 𝑝𝑟 , where 𝜆 1 , 𝜆2 ≥ 0. ∇𝑧 𝐿(𝑧, 𝜆1 , 𝜆2 ) = 𝜆 1 (−𝑝𝑟 − 𝜃 𝑖 + 2𝑧) + 𝜆 2 (−𝑝𝑟 + 𝜃 𝑟 ) + 2𝑧 − 2𝜁𝑖 . 2(𝜃 𝑖 −𝜁𝑖 ) 𝑟 −𝜁𝑖 ) It’s easy to verify that 𝑧 = 𝑝𝑟 , 𝜆 1 = 2(𝜃 𝜃 𝑖 −𝜃 𝑟 , 𝜆 2 = 𝜃 𝑖 −𝜃 𝑟 satisfy ∇𝑧 𝐿(𝑧, 𝜆 1 , 𝜆 2 ) = 0. Note that 𝑧 = 𝑝𝑟 is primal feasible. Also, since 𝜁𝑖 ≤ 𝜃 𝑟 < 𝜃 𝑖 , 𝜆 1 , 𝜆2 ≥ 0 must be dual feasible. We found a primal-dual pair satisfying the Karush-Kuhn-Tucker condition. Hence, 𝑝𝑟 is the minimizer. Define 𝑝e1 , . . . , 𝑝e𝑘 by 𝑝e𝑖 = 𝑝𝑖 for 𝑖 = 1, . . . , 𝑟 − 1, and 𝑝e𝑖 = 𝑝𝑟 for 𝑖 = 𝑟, . . . , 𝑘. We claim that they satisfy (𝜃 𝑖 − 𝑝e𝑖 ) · ( 𝑝e𝑗 − 𝑝e𝑖 ) ≤ 0 (𝜃 𝑖 − 𝑝e𝑖 ) · (−e 𝑝𝑖 ) ≤ 0 for all 𝑖 ≠ 𝑗, for all 𝑖. By construction, it suffices to check (𝜃 𝑗 − 𝑝𝑟 ) · ( 𝑝𝑖 − 𝑝𝑟 ) ≤ 0 (𝜃 𝑗 − 𝑝𝑟 ) · (−𝑝𝑟 ) ≤ 0 for 𝑖 < 𝑟 < 𝑗, for 𝑗 > 𝑟. To prove the first inequality, fix 𝑖 < 𝑟 < 𝑗. First note that 𝑝𝑖 ≤ 𝜃 𝑖 . This follows directly from (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0. Next, we have 𝑝𝑖 ≤ 𝑝′𝑟 (recall that 𝑝′𝑟 is the 33 first coordinate of 𝑝𝑟 ∈ R2 ). Indeed, suppose, to the contrary, 𝑝𝑖 > 𝑝′𝑟 . Then 𝑝′𝑟 < 𝑝𝑖 ≤ 𝜃 𝑖 ≤ 𝜃 𝑟 , and |𝜃 𝑟 − 𝑝𝑟 | 2 = |𝜃 𝑟 − 𝑝′𝑟 | 2 + |𝑞𝑟 | 2 > |𝜃 𝑟 − 𝑝𝑖 | 2 . 𝑝𝑖 would be a closer point in Γ to 𝜃 𝑟 than 𝑝𝑟 , contradiction. Since 𝑖 < 𝑟 < 𝑗, 𝑝𝑖 ≤ 𝑝′𝑟 , 𝜃 𝑟 ≤ 𝜃 𝑗 , and (𝜃 𝑗 − 𝜃 𝑟 ) · ( 𝑝𝑖 − 𝑝𝑟 ) = (𝜃 𝑗 − 𝜃 𝑟 )( 𝑝𝑖 − 𝑝′𝑟 ) ≤ 0. We already know (𝜃 𝑟 − 𝑝𝑟 ) · ( 𝑝𝑖 − 𝑝𝑟 ) ≤ 0, so adding the two inequalities gives (𝜃 𝑗 − 𝑝𝑟 ) · ( 𝑝𝑖 − 𝑝𝑟 ) ≤ 0. For the second inequality, fix 𝑗 > 𝑟. We know that (𝜃 𝑟 − 𝑝𝑟 ) · (−𝑝𝑟 ) = (𝜃 𝑟 − 𝑝′𝑟 ) (−𝑝′𝑟 ) + |𝑞𝑟 | 2 ≤ 0. From this, we deduce that 𝑝′𝑟 ≥ 0 (if 𝑝′𝑟 < 0, then from (𝜃 𝑟 − 𝑝′𝑟 )(−𝑝′𝑟 ) ≤ 0 we find 𝜃 𝑟 − 𝑝′𝑟 ≤ 0, so 0 ≤ 𝜃 𝑟 ≤ 𝑝′𝑟 < 0, contradiction). Since 𝜃 𝑗 ≥ 𝜃 𝑟 and 𝑝′𝑟 ≥ 0, (𝜃 𝑗 − 𝜃 𝑟 ) · (−𝑝𝑟 ) ≤ 0. We already know (𝜃 𝑟 − 𝑝𝑟 ) · (−𝑝𝑟 ) ≤ 0, so adding the two inequalities gives (𝜃 𝑗 − 𝑝𝑟 ) · (−𝑝𝑟 ) ≤ 0. ! 𝑝′𝑟 for 𝑖 ≥ 𝑟. It’s Now define 𝑝 1 , . . . , 𝑝 𝑘 as follows: 𝑝𝑖 = 𝑝e𝑖 = 𝑝𝑖 for 𝑖 < 𝑟, 𝑝𝑖 = 0 easy to verify that they satisfy (𝜃 𝑖 − 𝑝𝑖 ) · ( 𝑝 𝑗 − 𝑝𝑖 ) ≤ 0 for all 𝑖 ≠ 𝑗, (𝜃 𝑖 − 𝑝𝑖 ) · (−𝑝𝑖 ) ≤ 0 for all 𝑖. By Proposition 8, there exists a convex region Γ ⊆ R𝑑 containing 0 such that 𝑝𝑖 = 𝑝 Γ (𝜃 𝑖 ) for 𝑖 = 1, . . . , 𝑘. Moreover, 𝑘 ∑︁ 2 𝑤 𝑖 |𝜁𝑖 − 𝑝𝑖 | ≥ 𝑖=1 > 𝑟−1 ∑︁ 𝑖=1 𝑘 ∑︁ 2 𝑤 𝑖 |𝜁𝑖 − 𝑝𝑖 | + 𝑘 ∑︁ 𝑤 𝑖 |𝜁𝑖 − 𝑝𝑟 | 2 𝑖=𝑟 𝑤 𝑖 |𝜁𝑖 − 𝑝𝑖 | 2 . 𝑖=1 It follows that the convex set Γ we started with cannot be optimal. □ 34 The situation covered by Proposition 17 is one-dimensional. We next study a special case that goes beyond one dimension. We show that when 𝜃 1 , . . . , 𝜃 𝑘 are linearly independent, (4.5) is exact. It results from the convenient structure of the dual problem (4.12). We will use the following lemma: Lemma 18. Suppose 𝑦𝑖∗𝑗 , 𝑧𝑖∗ , 𝑉 ∗ are optimal for the dual problem (4.12). Let 𝑆 ∗ = ! 𝑉 0 Í Í 𝑘 . If rank 𝑆 ∗ ≥ 𝑘, then (4.5) is exact. 𝑧𝑖∗ 𝐵𝑖 − 𝐶 − 𝑖≠ 𝑗 𝑦𝑖∗𝑗 𝐴𝑖 𝑗 − 𝑖=1 0 0 Proof. Suppose 𝑍 ∗ is optimal for (4.5). Then 𝑍 ∗ • 𝑆 ∗ = 0. Since 𝑍 ∗ , 𝑆 ∗ are both positive semidefinite, we have the matrix product 𝑍 ∗ 𝑆 ∗ = 0. Since 𝑍 ∗ , 𝑆 ∗ are (𝑑 + 𝑘) × (𝑑 + 𝑘), rank 𝑍 ∗ + rank 𝑆 ∗ ≤ 𝑑 + 𝑘. Since rank 𝑆 ∗ ≥ 𝑘, it must be that rank 𝑍 ∗ ≤ 𝑑. By Proposition 10, Problem (4.5) is exact. □ With Lemma 18, it suffices to show that rank 𝑆 ∗ ≥ 𝑘 whenever we wish to show that the SDP relaxation is exact. We now present the special case of interest. Proposition 19. Suppose 𝜃 1 , . . . , 𝜃 𝑘 are linearly independent. Then for any 𝑤 1 , . . . , 𝑤 𝑘 > 0, problem (4.5) with parameters (𝜃, 𝑤) is exact. Proof. Suppose 𝑦𝑖∗𝑗 , 𝑧𝑖∗ , 𝑉 ∗ are optimal for (4.12). Let 𝑆 ∗ = 𝐶 − ! 𝑉 0 Í𝑘 ∗ . Then 𝑆 ∗ takes the form 𝑖=1 𝑧𝑖 𝐵𝑖 − 0 0 Í𝑘 𝜃 𝑖 𝜃 𝑖𝑇 ∗ 𝑤 𝑓1 𝑓2 𝑖 © 𝑖=1 4 −𝑉 ­ 𝑇 𝑓1 𝑒 11 𝑒 12 ­ ­ ∗ 𝑆 = ­­ 𝑓2𝑇 𝑒 21 𝑒 22 ­ . .. .. .. ­ . . ­ 𝑇 𝑓𝑘 𝑒 𝑘1 𝑒 𝑘2 « . . . 𝑓𝑘 ª ® . . . 𝑒 1𝑘 ® ® . . . 𝑒 2𝑘 ®® , . ® .. . .. ®® . . . 𝑒𝑘 𝑘 ¬ where 𝜃 𝑖 ∑︁ ∗ 𝜃 𝑗 𝜃 𝑖 ∑︁ ∗ 𝜃 𝑖 𝑦𝑖 𝑗 + 𝑧𝑖∗ − 𝑦 𝑗𝑖 , + 2 𝑗≠𝑖 2 2 2 𝑗≠𝑖 ∑︁ 𝑒𝑖𝑖 = 𝑤 𝑖 − 𝑦𝑖∗𝑗 − 𝑧𝑖∗ , 𝑖 = 1, . . . , 𝑘, 𝑓𝑖 = −𝑤 𝑖 𝑗≠𝑖 1 1 𝑒𝑖 𝑗 = − 𝑦𝑖∗𝑗 − 𝑦 ∗𝑗𝑖 , 2 2 𝑖 ≠ 𝑗. ∗ 𝑖≠ 𝑗 𝑦 𝑖 𝑗 𝐴𝑖 𝑗 − Í 𝑖 = 1, . . . , 𝑘, 35 We show that 𝑓1 , 𝑓2 , . . . , 𝑓 𝑘 are linearly independent. Write   𝜃 ∑︁ 𝜃 𝑗 ∑︁ 𝑖 𝑓𝑖 = − 𝑤 𝑖 + 𝑦𝑖∗𝑗 + 𝑧𝑖∗ − 𝑦 ∗𝑗𝑖 . 2 2 𝑗≠𝑖 𝑗≠𝑖 Since 𝜃 1 , . . . , 𝜃 𝑘 are linearly independent, it suffices to show that Í ∗ ∗ −𝑦 ∗12 ... −𝑦 ∗1𝑘 −𝑤 + 1 𝑗≠1 𝑦 1 𝑗 + 𝑧 1 ª © Í ® ­ ® ­ −𝑦 ∗2𝑘 −𝑦 ∗21 −𝑤 2 + 𝑗≠2 𝑦 ∗2 𝑗 + 𝑧∗2 . . . ® ­ .. .. .. ® ­ .. . . . . ® ­ ® ­ Í ∗ ∗ ∗ ∗ −𝑦 𝑘1 −𝑦 𝑘2 . . . −𝑤 𝑘 + 𝑗≠𝑘 𝑦 𝑘 𝑗 + 𝑧 𝑘 ¬ « ∗ ∗ is nonsingular. Since 𝑦𝑖 𝑗 ≤ 0, 𝑧𝑖 ≤ 0, this matrix is strictly diagonally dominant, hence indeed nonsingular. Having established linear independence of 𝑓1 , . . . , 𝑓 𝑘 , we have shown that rank 𝑆 ∗ ≥ 𝑘. By Lemma 18, Problem (4.5) is exact. □ This result can be partially extended to the case when 𝑑 ≥ 𝑘. Lemma 20. Let 𝑣(𝜃, 𝑤) be the optimal value of problem (4.5) with parameters (𝜃, 𝑤). Then for any pair 𝜃, 𝜃 ′ ∈ R𝑑×𝑘 , 𝑘 9 ∑︁ |𝑣(𝜃, 𝑤) − 𝑣(𝜃 , 𝑤)| ≤ 𝑤 𝑖 [2 max{|𝜃 𝑖 |, |𝜃 𝑖′ |}|𝜃 𝑖 − 𝜃 𝑖′ | + |𝜃 𝑖 − 𝜃 𝑖′ | 2 ]. 4 𝑖=1 ′ (4.14) In particular, if 𝜃 𝑙 ∈ R𝑑×𝑘 converges to 𝜃, then lim𝑙→∞ 𝑣(𝜃 𝑙 , 𝑤) = 𝑣(𝜃, 𝑤). Proof. Put 𝜁𝑖 = 𝜃2𝑖 . By Theorem 15, there exists 𝑟 ≥ 0 and a closed convex Í𝑘 set Γ ⊆ R𝑑+𝑟 such that 0 ∈ Γ and 𝑣(𝜃, 𝑤) = 𝑖=1 𝑤 𝑖 |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )| 2 . The map 𝑝 Γ : R𝑑 → R𝑑 is contractive, that is, | 𝑝 Γ (𝑥) − 𝑝 Γ (𝑦)| ≤ |𝑥 − 𝑦| (see [13]). Consequently, |𝜁𝑖′ − 𝑝 Γ (𝜃 𝑖′)| = |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 ) − [𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )] + [𝜁𝑖′ − 𝑝 Γ (𝜃 𝑖′)]| ≤ |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )| + |𝜁𝑖 − 𝜁𝑖′ | + | 𝑝 Γ (𝜃 𝑖 ) − 𝑝 Γ (𝜃 𝑖′)| 1 ≤ |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )| + |𝜃 𝑖 − 𝜃 𝑖′ | + |𝜃 𝑖 − 𝜃 𝑖′ |, 2 and |𝜁𝑖′ − 𝑝 Γ (𝜃 𝑖′)| 2 9 ≤ |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )| 2 + 3|𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )||𝜃 𝑖 − 𝜃 𝑖′ | + |𝜃 𝑖 − 𝜃 𝑖′ | 2 4 9 9 ≤ |𝜁𝑖 − 𝑝 Γ (𝜃 𝑖 )| 2 + |𝜃 𝑖 ||𝜃 𝑖 − 𝜃 𝑖′ | + |𝜃 𝑖 − 𝜃 𝑖′ | 2 . 2 4 36 Upon summation over 𝑖, we find ′ 𝑣(𝜃 , 𝑤) ≤ 𝑘 ∑︁ 𝑤 𝑖 |𝜁𝑖′ − 𝑝 Γ (𝜃 𝑖′)| 2 𝑖=1 𝑘 9 ∑︁ ≤ 𝑣(𝜃, 𝑤) + 𝑤 𝑖 [2|𝜃 𝑖 ||𝜃 𝑖 − 𝜃 𝑖′ | + |𝜃 𝑖 − 𝜃 𝑖′ | 2 ]. 4 𝑖=1 Inequality (4.14) follows from reversing the roles of 𝜃 and 𝜃 ′. □ Corollary 21. When 𝑑 ≥ 𝑘, Problem (4.5) admits a solution of rank 𝑑. Proof. Since 𝑑 ≥ 𝑘, there exists a sequence (𝜃 1𝑙 , . . . , 𝜃 𝑙𝑘 ) → (𝜃 1 , . . . , 𝜃 𝑘 ) such that for each 𝑙, 𝜃 1𝑙 , . . . , 𝜃 𝑙𝑘 are linearly independent. Let 𝐶 𝑙 , 𝐴𝑖𝑙 𝑗 , 𝐵𝑖𝑙 be the coefficient matrices for Problem (4.5) with input (𝜃 1𝑙 , . . . , 𝜃 𝑙𝑘 ). 𝐼 𝑝 1𝑙 . . . 𝑝 𝑙𝑘 © 𝑑 ª ­ ( 𝑝 𝑙 )𝑇 𝑦 𝑙 . . . 𝑦 𝑙 ® ® ­ 1 11 1𝑘 Let 𝑍 𝑙 = ­ . ® be the optimal solution for Problem (4.5) with . . . . . . . ­ . . . ®® . ­ 𝑙 𝑇 𝑙 𝑙 « ( 𝑝 𝑘 ) 𝑦 𝑘1 . . . 𝑦 𝑘 𝑘 ¬ input 𝜃 𝑙 . By Proposition 19, rank 𝑍 𝑙 = 𝑑, and there exists a closed convex set Γ𝑙 ⊆ R𝑑 such that 0 ∈ Γ𝑙 , and 𝑝𝑖𝑙 = 𝑝 Γ𝑙 (𝜃 𝑖𝑙 ). We know that | 𝑝𝑖𝑙 | ≤ |𝜃 𝑖𝑙 |. Moreover, since rank 𝑍 𝑙 = 𝑑, we must have |𝑦𝑖𝑙 𝑗 | = | 𝑝𝑖𝑙 · 𝑝 𝑙𝑗 | ≤ |𝜃 𝑖𝑙 ||𝜃 𝑙𝑗 |. This analysis shows 𝑙 that the sequence {𝑍 𝑙 }∞ 𝑙=1 is bounded. After passing to a subsequence, 𝑍 converges to some matrix 𝑍. Note that 𝑍 is feasible for Problem (4.5) with input 𝜃, and that rank 𝑍 = 𝑑. Also, lim𝑙→∞ 𝑍 𝑙 • 𝐶 𝑙 = 𝑍 • 𝐶. By Lemma 20, 𝑍 is optimal. □ Remark 8. This result is weaker than Proposition 19 because it does not imply uniqueness of solution for (4.5). It guarantees that an optimal solution of rank 𝑑 exists, but there may be additional solutions with higher rank. Stated in terms of the fund menu problem, if there are at least as many assets as the number of types, then the manager cannot (strictly) increase aggregate fee by introducing additional independent assets with zero mean return. 37 BIBLIOGRAPHY [1] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001. [2] Carl M Bender et al. “What is the optimal shape of a city?” In: Journal of Physics A: Mathematical and General 37.1 (2003), p. 147. [3] Mats Bengtsson and Björn Ottersten. “Optimum and suboptimum transmit beamforming”. In: Handbook of antennas in wireless communications. CRC press, 2018, pp. 18–1. [4] Samuel Burer and Yinyu Ye. “Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs”. In: Mathematical Programming 181.1 (2020), pp. 1–17. [5] Guillaume Carlier, Ivar Ekeland, and Nizar Touzi. “Optimal derivatives design for mean–variance agents under adverse selection”. In: Mathematics and Financial Economics 1.1 (2007), pp. 57–80. [6] Jakša Cvitanić and Julien Hugonnier. “Optimal fund menus”. In: Mathematical Finance 32.2 (2022), pp. 455–516. [7] Georg Faber. “Beweis, dass unter allen homogenen Membranen von gleicher Fläche und gleicher Spannung die kreisförmige den tiefsten Grundton gibt”. In: (1923). [8] Michel X Goemans and David P Williamson. “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”. In: Journal of the ACM (JACM) 42.6 (1995), pp. 1115–1145. [9] Sunyoung Kim and Masakazu Kojima. “Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations”. In: Computational optimization and applications 26.2 (2003), pp. 143–154. [10] Antoine Lemenant and Edoardo Mainini. “On convex sets that minimize the average distance”. In: ESAIM: Control, Optimisation and Calculus of Variations 18.4 (2012), pp. 1049–1072. [11] Michael Mussa and Sherwin Rosen. “Monopoly and product quality”. In: Journal of Economic theory 18.2 (1978), pp. 301–317. [12] Jean-Charles Rochet and Philippe Choné. “Ironing, sweeping, and multidimensional screening”. In: Econometrica (1998), pp. 783–826. [13] Rolf Schneider. Convex bodies: the Brunn–Minkowski theory. 151. Cambridge university press, 2014. [14] Anthony Man-Cho So and Yinyu Ye. “Theory of semidefinite programming for sensor network localization”. In: Mathematical Programming 109.2 (2007), pp. 367–384. 38 [15] VA Yakubovich. “S-procedure in nonlinear control theory”. In: Vestnick Leningrad Univ. Math. 4 (1997), pp. 73–93. [16] Fuzhen Zhang. The Schur complement and its applications. Vol. 4. Springer Science & Business Media, 2006. 39 Appendix A GAMMA CONVERGENCE We provide justification for focusing on the finite case of minimizing 2 𝑝 Γ (𝜃 𝑖 ) . 𝜃𝑖 𝑖=1 𝑤 𝑖 2 − Í𝑘 Consider a bounded region Ω ⊆ R𝑑 and a finite measure 𝜇. We may discretize 𝜇 by partitioning R𝑑 into dyadic cubes and forming a weighted sum of point-masses at the centers. Formally, let D𝑛 be the collection of dyadic cubes in R𝑑 of length 2−𝑛 . For each 𝑄 𝑖 ∈ D𝑛 , let 𝜃 𝑖 be the center of 𝑄 𝑖 . Define ∑︁ 𝜇𝑛 := 𝜇(Ω ∩ 𝑄 𝑖 )𝛿𝜃 𝑖 (A.1) 𝑄 𝑖 ∈D𝑛 Let C be the collection of closed convex subsets of R𝑑 containing the origin, and ∫ 𝜃 2 let F𝑛 (Γ) := 2 − 𝑝 Γ (𝜃) 𝑑𝜇 𝑛 . Loosely speaking, as the dyadic cube partition gets finer, the discretized problem minimizeΓ∈C F𝑛 (Γ) “approximates” the target problem minimizeΓ∈C F (Γ) better. The precise formulation of such approximation (often known as gamma-convergence in calculus of variations) is given by the following result: Proposition 22. Suppose Ω ⊆ R𝑑 is bounded, and 𝜇 is a finite measure on Ω. Define 𝜇𝑛 as in (A.1). Then there exists a sequence of minimizers {Γ𝑛 } for problems minimizeΓ∈C F𝑛 (Γ) having an accumulation point in Δ𝐻 . Moreover, any such accumulation point is an optimal solution of minimizeΓ∈C F (Γ). Lemma 23. Suppose {Γ𝑛 } is a sequence in C such that Γ𝑛 → Γ in Δ𝐻 . Then F𝑛 (Γ𝑛 ) → F (Γ). Proof. |F𝑛 (Γ𝑛 ) − F (Γ)| ≤ |F𝑛 (Γ𝑛 ) − F (Γ𝑛 )| + |F (Γ𝑛 ) − F (Γ)|. By Proposition 6, the second term on the right tends to 0 as 𝑛 → ∞. ∫ 2 Now consider the first term. On each dyadic cube 𝑄 𝑖 , 𝑄 2𝜃 − 𝑝 Γ𝑛 (𝜃) 𝑑𝜇𝑛 = 𝑖 ∫ 𝜃 2 𝑖 − 𝑝 Γ𝑛 (𝜃 𝑖 ) 𝑑𝜇. Since | 𝑝 Γ𝑛 (𝜃)| ≤ |𝜃|, and | 𝑝 Γ𝑛 (𝜃 𝑖 ) − 𝑝 Γ𝑛 (𝜃)| ≤ |𝜃 𝑖 − 𝜃|, 𝑄𝑖 2 ∫ ∫ ∫ 2 2 𝜃𝑖 𝜃 − 𝑝 Γ𝑛 (𝜃 𝑖 ) 𝑑𝜇 − − 𝑝 Γ𝑛 (𝜃) 𝑑𝜇 ≲ (|𝜃 𝑖 | + |𝜃|)|𝜃 𝑖 − 𝜃|𝑑𝜇. 𝑄𝑖 2 𝑄𝑖 2 𝑄𝑖 ∫ Í By the dominated convergence theorem, as 𝑛 → ∞, 𝑄 𝑖 ∈D𝑛 𝑄 (|𝜃 𝑖 | + |𝜃|)|𝜃 𝑖 − 𝑖 𝜃|𝑑𝜇 → 0. □ 40 Proof of Proposition 22. Since Ω is bounded, all 𝜇𝑛 are supported in a large enough ball, and we may assume that Γ𝑛 are contained in this ball. By the Blaschke selection theorem, we may assume that {Γ𝑛 } contains a subsequence that converges in the Hausdorff distance. Suppose Γ is any accumulation point of {Γ𝑛 }. By Lemma 23, F𝑛 (Γ𝑛 ) → F (Γ). Moreover, if Γ′ ∈ C, then F (Γ′) = lim F𝑛 (Γ′) ≥ lim F𝑛 (Γ𝑛 ) = F (Γ). Consequently, Γ is a minimizer of F (·). □ 41 Appendix B NUMERICAL RESULTS We examine the numerical solutions of Problem (4.5) in several cases of interest. Each case consists of points 𝜃 1 , . . . , 𝜃 𝑘 in R2 with uniform weight 𝑤 1 = · · · = 𝑤 𝑘 = 1. We plot the types 𝜃 1 , . . . , 𝜃 𝑘 (blue), the optimal convex set Γ (shaded region), as well as the projection points 𝑝 Γ (𝜃 1 ), . . . , 𝑝 Γ (𝜃 𝑘 ). In addition to the plots, we will be interested in the numerical value of 𝜆 𝑑+1 (𝑆 ∗ )—the (𝑑 + 1)-st smallest eigenvalue of the optimal dual slack matrix ! 𝑘 ∗ 0 ∑︁ ∑︁ 𝑉 𝑆∗ = 𝐶 − 𝑦𝑖∗𝑗 𝐴𝑖 𝑗 − 𝑧𝑖∗ 𝐵𝑖 − 0 0 𝑖≠ 𝑗 𝑖=1 for Problem (4.12). A strictly positive value implies rank 𝑆 ∗ ≥ 𝑘. By Lemma (18), it allows us to verify, a posteriori, that the SDP numerical solution is exact for the complete problem (4.4). The numerical solution is implemented with Python package CVXPY. 42 (a) random, 𝜆3 (𝑆 ∗ ) = 0.27 (b) random, 𝜆3 (𝑆 ∗ ) = 0.30 (c) grid, 𝜆3 (𝑆 ∗ ) = 0.54 (d) radial, 𝜆3 (𝑆 ∗ ) = 0.55 Figure B.1: Numerical solutions for random/nonrandom types