by Wong Oi Ping. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 77-79). / Abstracts in English and Chinese. / Chapter 1 --- LP-minimizing and Stationary Sequences --- p.8 / Chapter 1.1 --- Residual function --- p.8 / Chapter 1.2 --- Minimizing sequences --- p.14 / Chapter 1.3 --- Stationary sequences --- p.17 / Chapter 1.4 --- On the equivalence of minimizing and stationary se- quence --- p.21 / Chapter 1.5 --- Complementarity conditions --- p.25 / Chapter 1.6 --- Subdifferential-based stationary sequence --- p.29 / Chapter 1.7 --- Convergence of an Iterative Algorithm --- p.32 / Chapter 2 --- Minimizing And Stationary Sequences In Nonsmooth Optimization --- p.38 / Chapter 2.1 --- Subdifferential --- p.38 / Chapter 2.2 --- Stationary and minimizing sequences --- p.40 / Chapter 2.3 --- C-convex and BC-convex function --- p.43 / Chapter 2.4 --- Minimizing sequences in terms of sublevel sets --- p.44 / Chapter 2.5 --- Critical function --- p.48 / Chapter 3 --- Optimization Conditions --- p.52 / Chapter 3.1 --- Introduction --- p.52 / Chapter 3.2 --- Second-order necessary and sufficient conditions with- out constraint --- p.55 / Chapter 3.3 --- The Lagrange and G-functions in constrained problems --- p.63 / Chapter 3.4 --- Second-order necessary conditions for constrained prob- lems --- p.73 / Chapter 3.5 --- Sufficient conditions for constrained problems --- p.74 / Bibliography

Lee Sung Tak. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 100-101). / Abstracts in English and Chinese. / Chapter 1 --- Introduction and Synopsis --- p.1 / Chapter 2 --- Literature Review --- p.5 / Chapter 3 --- The primal-dual interior point algorithm and the self-dual embedding method: Revisit --- p.7 / Chapter 4 --- The Warm-Start Strategy (WSS) --- p.25 / Chapter 5 --- Experimental result and analysis I: Parametric programming case --- p.31 / Chapter 5.1 --- The Big-Mac Problem --- p.33 / Chapter 5.2 --- The randomly generated problem and the Netlib problem --- p.46 / Chapter 5.3 --- Chapter summary --- p.53 / Chapter 6 --- Experimental result and analysis II: Adding rows and columns --- p.54 / Chapter 6.1 --- The Big-Mac problem --- p.57 / Chapter 6.2 --- The randomly generated problem and the Netlib problem --- p.66 / Chapter 6.3 --- The ball constraint problem --- p.82 / Chapter 6.4 --- Chapter Summary --- p.94 / Chapter 7 --- Summary and conclusion --- p.96 / Bibliography --- p.100 / Chapter A --- Appendix --- p.102

by Shiu-Tung Ng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 100-103). / Abstract also in Chinese. / Chapter 1 --- Preliminary --- p.5 / Chapter 1.1 --- Linear and Convex Optimization Model --- p.5 / Chapter 1.2 --- Notations for Linear Optimization --- p.5 / Chapter 1.3 --- Definition and Properties of Convexities --- p.7 / Chapter 1.4 --- Useful Theorem for Unconstrained Minimization --- p.10 / Chapter 2 --- Linear Optimization --- p.11 / Chapter 2.1 --- Self-dual Linear Optimization Model --- p.11 / Chapter 2.2 --- Definitions and Main Theorems --- p.14 / Chapter 2.3 --- Self-dual Embedding and Simple Example --- p.22 / Chapter 2.4 --- Newton step --- p.25 / Chapter 2.5 --- "Rescaling and Definition of δ(xs,w)" --- p.29 / Chapter 2.6 --- An Interior Point Method --- p.32 / Chapter 2.6.1 --- Algorithm with Full Newton Steps --- p.33 / Chapter 2.6.2 --- Iteration Bound --- p.33 / Chapter 2.7 --- Background and Rounding Procedure for Interior-point Solution --- p.36 / Chapter 2.8 --- Solving Some LP problems --- p.42 / Chapter 2.9 --- Remarks --- p.51 / Chapter 3 --- Convex Optimization --- p.53 / Chapter 3.1 --- Introduction --- p.53 / Chapter 3.1.1 --- Convex Optimization Problem --- p.53 / Chapter 3.1.2 --- Idea of Interior Point Method --- p.55 / Chapter 3.2 --- Logarithmic Barrier Method --- p.55 / Chapter 3.2.1 --- Basic Concepts and Properties --- p.55 / Chapter 3.2.2 --- k-Self-Concordance Condition --- p.62 / Chapter 3.2.3 --- Short-step Logarithmic Barrier Algorithm --- p.64 / Chapter 3.2.4 --- Initialization Algorithm --- p.67 / Chapter 3.3 --- Center Method --- p.70 / Chapter 3.3.1 --- Basic Concepts and Properties --- p.70 / Chapter 3.3.2 --- Short-step Center Algorithm --- p.75 / Chapter 3.3.3 --- Initialization Algorithm --- p.76 / Chapter 3.4 --- Properties and Examples on Self-Concordance --- p.78 / Chapter 3.5 --- Examples of Convex Optimization Problem --- p.82 / Chapter 3.5.1 --- Self-concordant Logarithmic Barrier and Distance Function --- p.82 / Chapter 3.5.2 --- General Convex Optimization Problems --- p.91 / Chapter 3.6 --- Remarks --- p.98 / Bibliography

Solving operations research problems with approximation algorithms has been an important topic since approximation algorithm can provide near-optimal solutions to NP-hard problems while achieving computational efficiency. In this thesis, we consider two different problems in the field of optimal control and scheduling theory respectively and develop efficient approximation algorithms for those problems with performance guarantee. Chapter 2 presents approximation algorithms for solving the optimal execution problem for demand-response contract in electricity markets. Demand side participation is essential for achieving real-time energy balance in today's electricity grid. Demand-response contracts, where an electric utility company buys options from consumers to reduce their load in the future, are an important tool to increase demand-side participation. In this chapter, we consider the operational problem of optimally exercising the available contracts over the planning horizon such that the total cost to satisfy the demand is minimized. In particular, we consider the objective of minimizing the sum of the expected ℓ_β-norm of the load deviations from given thresholds and the contract execution costs over the planning horizon. For β=∞, this reduces to minimizing the expected peak load. The peak load provides a good proxy to the total cost of the utility as spikes in electricity prices are observed only in peak load periods. We present a data driven near-optimal algorithm for the contract execution problem. Our algorithm is a sample average approximation (SAA) based dynamic program over a multi-period planning horizon. We provide a sample complexity bound on the number of demand samples required to compute a (1+ε)-approximate policy for any ε>0. Our SAA algorithm is quite general and we show that it can be adapted to quite general demand models including Markovian demands and objective functions. For the special case where the demand in each period is i.i.d., we show that a static solution is optimal for the dynamic problem. We also conduct a numerical study to compare the performance of our SAA based DP algorithm. Our numerical experiments show that we can achieve a (1+ε)-approximation in significantly smaller numbers of samples than what is implied by the theoretical bounds. Moreover, the structure of the approximate policy also shows that it can be well approximated by a simple affine function of the state. In Chapter 3, we study the NP-hard coflow scheduling problem and develop a polynomial-time approximation algorithm for the problem with constant approximation ratio. Communications in datacenter jobs (such as the shuffle operations in MapReduce applications) often involve many parallel flows, which may be processed simultaneously. This highly parallel structure presents new scheduling challenges in optimizing job-level performance objectives in data centers. Chowdhury and Stoica [13] introduced the coflow abstraction to capture these communication patterns, and recently Chowdhury et al. [15] developed effective heuristics to schedule coflows. In this chapter, we consider the problem of efficiently scheduling coflows so as to minimize the total weighted completion time, which has been shown to be strongly NP-hard [15]. Our main result is the first polynomial-time deterministic approximation algorithm for this problem, with an approximation ratio of $64/3$, and a randomized version of the algorithm, with a ratio of 8+16sqrt{2}/3. Our results use techniques from both combinatorial scheduling and matching theory, and rely on a clever grouping of coflows. In Chapter 4, we carry out a comprehensive experimental analysis on a Facebook trace and extensive simulated instances to evaluate the practical performance of several algorithms for coflow scheduling, including our approximation algorithms developed in Chapter 3. Our experiments suggest that simple algorithms provide effective approximations of the optimal, and that the performance of the approximation algorithm of Chapter 3 is relatively robust, near optimal, and always among the best compared with the other algorithms, in both the offline and online settings.

This work considers the problem faced by a decision maker (planner) trying to optimize over incomplete data. The missing data is privately held by agents whose objectives are dierent from the planner's, and who can falsely report it in order to advance their objectives. The goal is to design optimization mechanisms (algorithms) that achieve "good" results when agents' reports follow a game-theoretic equilibrium. In the first part of this work, the goal is to design mechanisms that provide a small worst-case approximation ratio (guarantee a large fraction of the optimal value in all instances) at equilibrium. The emphasis is on strategyproof mechanisms|where truthfulness is a dominant strategy equilibrium|and on the approximation ratio at that equilibrium. Two problems are considered|variants of knapsack and facility location problems. In the knapsack problem, items are privately owned by agents, who can hide items or report fake ones; each agent's utility equals the total value of their own items included in the knapsack, while the planner wishes to choose the items that maximize the sum of utilities. In the facility location problem, agents have private linear single sinked/peaked preferences regarding the location of a facility on an interval, while the planner wishes to locate the facility in a way that maximizes one of several objectives. A variety of mechanisms and lower bounds are provided for these problems. The second part of this work explores the problem of reassigning students to schools. Students have privately known preferences over the schools. After an initial assignment is made, the students' preferences change, get reported again, and a reassignment must be obtained. The goal is to design a reassignment mechanism that incentivizes truthfulness, provides high student welfare, transfers relatively few students from their initial assignment, and respects student priorities at schools. The class of mechanisms considered is permuted lottery deferred acceptance (PLDA) mechanisms, which is a natural class of mechanisms based on permuting the lottery numbers students initially draw to decide the initial assignment. Both theoretical and experimental evidence is provided to support the use of a PLDA mechanism called reversed lottery deferred acceptance (RLDA). The evidence suggests that under some conditions, all PLDA mechanisms generate roughly equal welfare, and that RLDA minimizes transfers among PLDA mechanisms.

Shen Ruijun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (leaves 72-74). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Portfolio Selection Problem --- p.1 / Chapter 1.1.1 --- The Mean-Variance Approach --- p.1 / Chapter 1.1.2 --- The Utility Function Approach --- p.2 / Chapter 1.2 --- Conic Programming and Duality Theory --- p.3 / Chapter 1.2.1 --- Cones and Conic Programming --- p.3 / Chapter 1.2.2 --- Second Order Cones --- p.4 / Chapter 1.3 --- Uncertainties and Robust Optimization --- p.5 / Chapter 1.4 --- Problem Formulation --- p.8 / Chapter 1.4.1 --- Utility Approach Based on a Single-Stage Tree --- p.8 / Chapter 1.4.2 --- Utility Approach Based on a Two-St age Tree --- p.10 / Chapter 1.4.3 --- Robust Counterpart of the Single-Stage Model --- p.14 / Chapter 1.4.4 --- Robust Counterpart of the Two-Stage Model --- p.16 / Chapter 2 --- Single-Stage Robust Selection --- p.20 / Chapter 2.1 --- A Specific Model --- p.20 / Chapter 2.1.1 --- Assumptions --- p.20 / Chapter 2.1.2 --- Formulation of the Model --- p.21 / Chapter 2.1.3 --- Solution for the Model --- p.22 / Chapter 2.2 --- The General Model --- p.26 / Chapter 2.2.1 --- Assumptions --- p.26 / Chapter 2.2.2 --- Solving the model --- p.27 / Chapter 3 --- Results on Two-Stage Models --- p.30 / Chapter 3.1 --- A Specific Two-Stage Robust Model --- p.30 / Chapter 3.1.1 --- Assumptions --- p.30 / Chapter 3.1.2 --- Formulation of the model --- p.32 / Chapter 3.1.3 --- Solution for the Model --- p.33 / Chapter 3.2 --- The General Two-Stage Robust Model --- p.40 / Chapter 3.2.1 --- Assumptions --- p.40 / Chapter 3.2.2 --- Solution for the Model --- p.41 / Chapter 3.2.3 --- General Model with Ellipsoidal Uncertainty Sets --- p.45 / Chapter 4 --- Numerical Results --- p.53 / Chapter 4.1 --- Scenario Tree Generation --- p.53 / Chapter 4.2 --- Numerical Results for the problem (SRP2) --- p.56 / Chapter 5 --- Conclusion --- p.67 / Chapter A --- Equation Derivation --- p.69 / Bibliography --- p.72

Ng, Chi Kong. / "May 2003." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (p. 175-187). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. Ann Arbor, MI : ProQuest Information and Learning Company, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

In this thesis we study the theory and algorithms for separated continuous linear programming (SCLP) and its extensions. / Throughout this thesis, some numerical examples are used to illustrate the algorithms that we propose. In particular, we solve a special LQ control problem with sign constraints on the state and the control variables as an instance of SCCP, yielding a new solution method for such kind of LQ control problems. / We first investigate the relationships among SCLP, the dual of SCLP and the corresponding discretized versions of them. By using the symmetric primal and dual structure and an even partition of the time interval [0, T], we show that the strong duality holds between SCLP and its dual problem under some mild assumption. This is actually an alternative proof for the strong duality theorem. The other constructive proof is due to Weiss [50]. Our new proof is more direct and can be easily extended to prove the same strong duality results for the extensions of SCLP. Based on these results, we propose an approximation algorithm which solves SCLP with any prescribed precision requirement. Our algorithm is in fact a polynomial-time approximation (PTA) scheme. The trade-off between the quality of the solution and the computational effort is explicit. / We then study the extensions of SCLP; that is, separated continuous conic programming (SCCP) and its generalized version (GSCCP). It turns out that our results on SCLP can be readily extended to SCCP and GSCCP. To our knowledge, SCCP and GSCCP are new models with novel applications. / Wang Xiaoqing. / "June 2005." / Advisers: Shuzhong Zhang; David Da-Wei Yao. / Source: Dissertation Abstracts International, Volume: 67-01, Section: B, page: 0520. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2005. / Includes bibliographical references (p. 122-127). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.

In this thesis, we consider the following two important subjects in the modern variational analysis for the corresponding nonconvex/nonmonotone and nonsmooth cases: geometric results and the variational inequality problem. By using the variational technique, we first present several nonsmooth (nonconvex) geometric results (including an approximate projection result, an extended extremal principle, nonconvex separation theorems, a nonconvex generalization of the Bishop-Phelps theorem and a separable point result) which extend some fundamental theorems in linear functional analysis, convex analysis and optimization theory. Then, by transforming the variational inequality problem into equivalent optimization problems, we establish some error bound result for the nonsmooth and nonmonotone variational inequality problem. / Variational arguments are classical techniques whose use can be traced back to the early development of the calculus of variations. Rooted in the physical principle of least action they have evolved greatly in connection with applications in optimization theory and optimal control. Recently, the discovery of modern variational principles and nonsmooth analysis further expand the range of applications of these techniques and give a new way for extending some geometric results in linear functional analysis and convex analysis. / Li, Guoyin. / "August 2007." / Adviser: Kung-Fu Ng. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1043. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 80-86). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

Guo, Zhishan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 71-82). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement i --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constrained Pseudoconvex Optimization --- p.1 / Chapter 1.2 --- Recurrent Neural Networks --- p.4 / Chapter 1.3 --- Thesis Organization --- p.7 / Chapter 2 --- Literature Review --- p.8 / Chapter 2.1 --- Pseudo convex Optimization --- p.8 / Chapter 2.2 --- Recurrent Neural Networks --- p.10 / Chapter 3 --- Model Description and Convergence Analysis --- p.17 / Chapter 3.1 --- Model Descriptions --- p.18 / Chapter 3.2 --- Global Convergence --- p.20 / Chapter 4 --- Numerical Examples --- p.27 / Chapter 4.1 --- Gaussian Optimization --- p.28 / Chapter 4.2 --- Quadratic Fractional Programming --- p.36 / Chapter 4.3 --- Nonlinear Convex Programming --- p.39 / Chapter 5 --- Real-time Data Reconciliation --- p.42 / Chapter 5.1 --- Introduction --- p.42 / Chapter 5.2 --- Theoretical Analysis and Performance Measurement --- p.44 / Chapter 5.3 --- Examples --- p.45 / Chapter 6 --- Real-time Portfolio Optimization --- p.53 / Chapter 6.1 --- Introduction --- p.53 / Chapter 6.2 --- Model Description --- p.54 / Chapter 6.3 --- Theoretical Analysis --- p.56 / Chapter 6.4 --- Illustrative Examples --- p.58 / Chapter 7 --- Conclusions and Future Works --- p.67 / Chapter 7.1 --- Concluding Remarks --- p.67 / Chapter 7.2 --- Future Works --- p.68 / Chapter A --- Publication List --- p.69 / Bibliography --- p.71