ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Sat, 05 Dec 2020 18:11:09 GMT2020-12-05T18:11:09Z50351- Representing the space of linear programs as the Grassmann manifoldhttps://scholarbank.nus.edu.sg/handle/10635/126643Title: Representing the space of linear programs as the Grassmann manifold
Authors: Zhao, G.
Abstract: Each linear program (LP) has an optimal basis. The space of linear programs can be partitioned according to these bases, so called the basis partition. Discovering the structures of this partition is our goal.We represent the space of linear programs as the space of projection matrices, i.e., the Grassmann manifold. A dynamical system on the Grassmann manifold, first presented in Sonnevend et al. (Math Program 52:527-553), is used to characterize the basis partition as follows: From each projection matrix associated with an LP, the dynamical system defines a path and the path leads to an equilibrium projection matrix returning the optimal basis of the LP. We will present some basic properties of equilibrium points of the dynamical system and explicitly describe all eigenvalues and eigenvectors of the linearized dynamical system at equilibrium points. These propertieswill be used to determine the stability of equilibrium points and to investigate the basis partition. This paper is only a beginning of the research towards our goal. © Springer-Verlag 2008.
Fri, 01 Jan 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1266432010-01-01T00:00:00Z
- A multiple-cut analytic center cutting plane method for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/44200Title: A multiple-cut analytic center cutting plane method for semidefinite feasibility problems
Authors: Toh, K.-C.; Zhao, G.; Sun, J.
Abstract: We consider the problem of finding a point in a nonempty bounded convex body F in the cone of symmetric positive semidefinite matrices S+ m. Assume that Γ is defined by a separating oracle, which, for any given m × m symmetric matrix Ŷ, either confirms that Ŷ ∈ Γ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i = 1,...,p, p ≤ pmax, such that Γ is in the polyhedron {Y ∈ S+ m | Ai • Y ≤ Ai • Ŷ, i = 1, ⋯,p}. We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of positive definite matrices which are approximate analytic centers of a shrinking polytope in S+ m. The algorithm terminates with a point in F within O(m3pmax/ε2) Newton steps (to leading order), where e is the maximum radius of a ball contained in Γ.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442002002-01-01T00:00:00Z
- Asymptotic behavior of Helmberg-Kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theoryhttps://scholarbank.nus.edu.sg/handle/10635/102888Title: Asymptotic behavior of Helmberg-Kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
Authors: SIM CHEE KHIAN; Zhao, G.
Abstract: An interior-point method (IPM) defines a search direction at each interior point of the feasible region. These search directions form a direction field, which in turn gives rise to a system of ordinary differential equations (ODEs). Thus, it is natural to define the underlying paths of the IPM as the solutions of the system of ODEs. In Sim and Zhao (Math. Program. Ser. A, [2007], to appear), these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to the given monotone semidefinite linear complementarity problem (SDLCP). Off-central paths for a simple example are also studied in Sim and Zhao (Math. Program. Ser. A, [2007], to appear) and their asymptotic behavior near the solution of the example is analyzed. In this paper, which is an extension of Sim and Zhao (Math. Program. Ser. A, [2007], to appear), we study the asymptotic behavior of the off-central paths for general SDLCPs using the dual HKM direction. We give a necessary and sufficient condition for when an off-central path is analytic as a function of √μ at a solution of the SDLCP. Then, we show that, if the given SDLCP has a unique solution, the first derivative of its off-central path, as a function of √μ, is bounded. We work under the assumption that the given SDLCP satisfies the strict complementarity condition. © 2007 Springer Science+Business Media, LLC.
Tue, 01 Apr 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028882008-04-01T00:00:00Z
- On the implementation of a log-barrier progressive hedging method for multistage stochastic programshttps://scholarbank.nus.edu.sg/handle/10635/103807Title: On the implementation of a log-barrier progressive hedging method for multistage stochastic programs
Authors: Liu, X.; Toh, K.-C.; Zhao, G.
Abstract: A progressive hedging method incorporated with self-concordant barrier for solving multistage stochastic programs is proposed recently by Zhao [G. Zhao, A Lagrangian dual method with self-concordant barrier for multistage stochastic convex nonlinear programming, Math. Program. 102 (2005) 1-24]. The method relaxes the nonanticipativity constraints by the Lagrangian dual approach and smoothes the Lagrangian dual function by self-concordant barrier functions. The convergence and polynomial-time complexity of the method have been established. Although the analysis is done on stochastic convex programming, the method can be applied to the nonconvex situation. We discuss some details on the implementation of this method in this paper, including when to terminate the solution of unconstrained subproblems with special structure and how to perform a line search procedure for a new dual estimate effectively. In particular, the method is used to solve some multistage stochastic nonlinear test problems. The collection of test problems also contains two practical examples from the literature. We report the results of our preliminary numerical experiments. As a comparison, we also solve all test problems by the well-known progressive hedging method. © 2010 Elsevier B.V. All rights reserved.
Sat, 15 May 2010 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038072010-05-15T00:00:00Z
- On the choice of parameters for power-series interior point algorithms in linear programminghttps://scholarbank.nus.edu.sg/handle/10635/103774Title: On the choice of parameters for power-series interior point algorithms in linear programming
Authors: Zhao, G.
Abstract: In this paper we study higher-order interior point algorithms, especially power-series algorithms, for solving linear programming problems. Since higher-order differentials are not parameter-invariant, it is important to choose a suitable parameter for a power-series algorithm. We propose a parameter transformation to obtain a good choice of parameter, called a k-parameter, for general truncated powerseries approximations. We give a method to find a k-parameter. This method is applied to two powerseries interior point algorithms, which are built on a primal-dual algorithm and a dual algorithm, respectively. Computational results indicate that these higher-order power-series algorithms accelerate convergence compared to first-order algorithms by reducing the number of iterations. Also they demonstrate the efficiency of the k-parameter transformation to amend an unsuitable parameter in power-series algorithms. © 1995 The Mathematical Programming Society, Inc.
Sun, 01 Jan 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1037741995-01-01T00:00:00Z
- Complementarity demand functions and pricing models for multi-product marketshttps://scholarbank.nus.edu.sg/handle/10635/103013Title: Complementarity demand functions and pricing models for multi-product markets
Authors: Soon, W.; Zhao, G.; Zhang, J.
Abstract: In contrast to single-product pricing models, multi-product pricing models have been much less studied because of the complexity of multi-product demand functions. It is highly non-trivial to construct a multi-product demand function on the entire set of non-negative prices, not to mention approximating the real market demands to a desirable accuracy. Thus, many decision makers use incomplete demand functions which are defined only on a restricted domain, e.g. the set where all components of demand functions are non-negative. In the first part of this paper, we demonstrate the necessity of defining demand functions on the entire set of non-negative prices through some examples. Indeed, these examples show that incomplete demand functions may lead to inferior pricing models. Then we formulate a type of demand functions using a Nonlinear Complementarity Problem (NCP). We call it a Complementarity-Constrained Demand Function (CCDF). We will show that such demand functions possess certain desirable properties, such as monotonicity. In the second part of the paper, we consider an oligopolistic market, where producers/sellers are playing a non-cooperative game to determine the prices of their products. When a CCDF is incorporated into the best response problem of each producer/seller involved, it leads to a complementarity constrained pricing problem facing each producer/seller. Some basic properties of the pricing models are presented. In particular, we show that, under certain conditions, the complementarity constraints in this pricing model can be eliminated, which tremendously simplifies the computation and theoretical analysis. © 2009 Cambridge University Press.
Thu, 01 Oct 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1030132009-10-01T00:00:00Z
- Nonminimal product differentiation as a bargaining outcomehttps://scholarbank.nus.edu.sg/handle/10635/103627Title: Nonminimal product differentiation as a bargaining outcome
Authors: Rath, K.P.; Zhao, G.
Abstract: It is well known that in a duopoly model of product choice with quadratic transportation cost, the firms locate at the extreme endpoints of the market. Jehiel (1992, Int. J. Ind. Organ, 10, 633-641) has examined this model in an infinite horizon setting where in the initial period the firms choose location and in subsequent periods charge the Nash bargaining solution prices. Then, in the unique equilibrium both firms locate at the center of the market. This paper examines the case when the firms instead charge the prices determined by either the egalitarian bargaining solution or the Kalai-Smorodinski bargaining solution. It is shown that central agglomeration is an equilibrium. Furthermore, there is a continuum of symmetric equilibria in addition where the firms locate apart from each other. So the products are not necessarily minimally differentiated. Thus different bargaining solutions provide quite different outcomes. © 2003 Elsevier Science (USA). All rights reserved.
Sat, 01 Feb 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1036272003-02-01T00:00:00Z
- Successive linear approximation solution of infinite-horizon dynamic stochastic programshttps://scholarbank.nus.edu.sg/handle/10635/104216Title: Successive linear approximation solution of infinite-horizon dynamic stochastic programs
Authors: Birge, J.R.; Zhao, G.
Abstract: Models for long-term planning often lead to infinite-horizon stochastic programs that offer significant challenges for computation. Finite-horizon approximations are often used in these cases, but they may also become computationally difficult. In this paper, we directly solve for value functions of infinite-horizon stochastic programs. We show that a successive linear approximation method converges to an optimal value function for the case with convex objective, linear dynamics, and feasible continuation. © 2007 Society for Industrial and Applied Mathematics.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1042162007-01-01T00:00:00Z
- A note on treating a second order cone program as a special case of a semidefinite programhttps://scholarbank.nus.edu.sg/handle/10635/102717Title: A note on treating a second order cone program as a special case of a semidefinite program
Authors: SIM CHEE KHIAN; Zhao, G.
Abstract: It is well known that a vector is in a second order cone if and only if its "arrow" matrix is positive semidefinite. But much less well-known is about the relation between a second order cone program (SOCP) and its corresponding semidefinite program (SDP). The correspondence between the dual problem of SOCP and SDP is quite direct and the correspondence between the primal problems is much more complicated. Given a SDP primal optimal solution which is not necessarily "arrow-shaped", we can construct a SOCP primal optimal solution. The mapping from the primal optimal solution of SDP to the primal optimal solution of SOCP can be shown to be unique. Conversely, given a SOCP primal optimal solution, we can construct a SDP primal optimal solution which is not an "arrow" matrix. Indeed, in general no primal optimal solutions of the SOCP-related SDP can be an "arrow" matrix. © Springer-Verlag 2004.
Fri, 01 Apr 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027172005-04-01T00:00:00Z
- On second-order properties of the moreau-yosida regularization for constrained nonsmooth convex programshttps://scholarbank.nus.edu.sg/handle/10635/103752Title: On second-order properties of the moreau-yosida regularization for constrained nonsmooth convex programs
Authors: Meng, F.; Zhao, G.
Abstract: In this paper, we attempt to investigate a class of constrained nonsmooth convex optimization problems, that is, piecewise C2 convex objectives with smooth convex inequality constraints. By using the Moreau-Yosida regularization, we convert these problems into unconstrained smooth convex programs. Then, we investigate the second-order properties of the Moreau-Yosida regularization η. By introducing the (GAIPCQ) qualification, we show that the gradient of the regularized function n is piecewise smooth, thereby, semismooth.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1037522004-01-01T00:00:00Z
- Underlying paths in interior point methods for the monotone semidefinite linear complementarity problemhttps://scholarbank.nus.edu.sg/handle/10635/104421Title: Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem
Authors: Sim, C.-K.; Zhao, G.
Abstract: An interior point method defines a search direction at each interior point of the feasible region. The search directions at all interior points together form a direction field, which gives rise to a system of ordinary differential equations (ODEs). Given an initial point in the interior of the feasible region, the unique solution of the ODE system is a curve passing through the point, with tangents parallel to the search directions along the curve. We call such curves off-central paths. We study off-central paths for the monotone semidefinite linear complementarity problem (SDLCP). We show that each off-central path is a well-defined analytic curve with parameter μ ranging over (0, ∞) and any accumulation point of the off-central path is a solution to SDLCP. Through a simple example we show that the off-central paths are not analytic as a function of √ μ and have first derivatives which are unbounded as a function of μ at μ = 0 in general. On the other hand, for the same example, we can find a subset of off-central paths which are analytic at μ = 0. These "nice" paths are characterized by some algebraic equations. © Springer-Verlag 2007.
Sat, 01 Sep 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1044212007-09-01T00:00:00Z
- Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problemshttps://scholarbank.nus.edu.sg/handle/10635/103065Title: Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems
Authors: Zhou, G.; Toh, K.-C.; Zhao, G.
Abstract: Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves ε-feasibility and ε-complementarity in at most O(n 2 ln(1/ε)) iterations with a properly chosen starting point.
Mon, 01 Mar 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1030652004-03-01T00:00:00Z
- A lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programminghttps://scholarbank.nus.edu.sg/handle/10635/102666Title: A lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming
Authors: Zhao, G.
Abstract: This paper presents an algorithm for solving multi-stage stochastic convex nonlinear programs. The algorithm is based on the Lagrangian dual method which relaxes the nonanticipativity constraints, and the barrier function method which enhances the smoothness of the dual objective function so that the Newton search directions can be used. The algorithm is shown to be of global convergence and of polynomial-time complexity.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026662005-01-01T00:00:00Z
- Analytic center cutting-plane method with deep cuts for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/102860Title: Analytic center cutting-plane method with deep cuts for semidefinite feasibility problems
Authors: Chua, S.K.; Toh, K.C.; Zhao, G.Y.
Abstract: An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set Γ in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point Ŷ that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that Ŷ ∈ Γ or returns a cut A ∈ S m such that {Y ∈ S m: A• Y ≤ A• Ŷ - ξ} ⊃Γ, where ξ ≥ 0. Ŷ ∉ Γ, an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that Γ contains a ball with radius ε > 0, the algorithm obtains eventually a point in Γ, with a worst-case complexity of O*(m 3/ε 2) on the total number of cuts generated.
Mon, 01 Nov 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1028602004-11-01T00:00:00Z
- Two stage equilibrium and product choice with elastic demandhttps://scholarbank.nus.edu.sg/handle/10635/104411Title: Two stage equilibrium and product choice with elastic demand
Authors: Rath, K.P.; Zhao, G.
Abstract: This paper examines a two stage model of product choice with elastic demand. Duopolists choose locations and then prices. Consumers' demand is linear in price. Transportation cost is quadratic and is a lump sum. For each pair of locations, there is a price equilibrium in the second stage. The first stage equilibrium locations are unique, symmetric and depend upon the ratio of the reservation price and the transportation cost parameter. When this ratio exceeds a certain critical value, the locations are at the extreme end points of the market. As the ratio decreases, the locations gradually move towards the center. © Elsevier Science B.V.
Thu, 01 Nov 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1044112001-11-01T00:00:00Z
- Lagrangian-dual functions and Moreau-Yosida regularizationhttps://scholarbank.nus.edu.sg/handle/10635/44185Title: Lagrangian-dual functions and Moreau-Yosida regularization
Authors: Meng, F.; Zhao, G.; Goh, M.; De Souza, R.
Abstract: In this paper, we consider the Lagrangian-dual problem of a class of convex optimization problems. We first discuss the semismoothness of the Lagrangian-dual function φ. This property is then used to investigate the second-order properties of the Moreau-Yosida regularization η of the function φ, e.g., the semismoothness of the gradient g of the regularized function η. We show that φ and g are piecewise C2 and semismooth, respectively, for certain instances of the optimization problem. We establish a relationship between the original problem and the Fenchel conjugate of the regularization of the corresponding Lagrangian dual problem. We also find some instances of the optimization problem whose Lagrangian-dual function φ is not piecewise smooth. However, its regularized function still possesses nice second-order properties. Finally, we provide an alternative way to study the semismoothness of the gradient under the structure of the epigraph of the dual function. © 2008 Society for Industrial and Applied Mathematics.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/441852008-01-01T00:00:00Z
- Semismoothness of solutions to generalized equations and the Moreau-Yosida regularizationhttps://scholarbank.nus.edu.sg/handle/10635/104094Title: Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization
Authors: Meng, F.; Sun, D.; Zhao, G.
Abstract: We show that a locally Lipschitz homeomorphism function is semismooth at a given point if and only if its inverse function is semismooth at its image point. We present a sufficient condition for the semismoothness of solutions to generalized equations over cone reducible (nonpolyhedral) convex sets. We prove that the semismoothness of solutions to the Moreau-Yosida regularization of a lower semicontinuous proper convex function is implied by the semismoothness of the metric projector over the epigraph of the convex function. © Springer-Verlag 2005.
Tue, 01 Nov 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1040942005-11-01T00:00:00Z
- The curvature integral and the complexity of linear complementarity problemshttps://scholarbank.nus.edu.sg/handle/10635/104276Title: The curvature integral and the complexity of linear complementarity problems
Authors: Zhao, G.; Zhu, J.
Abstract: In this paper, we propose a predictor-corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date. © 1995 The Mathematical Programming Society, Inc.
Sun, 01 Oct 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1042761995-10-01T00:00:00Z
- An analytic center cutting plane method for semidefinite feasibility problemshttps://scholarbank.nus.edu.sg/handle/10635/44210Title: An analytic center cutting plane method for semidefinite feasibility problems
Authors: Sun, J.; Toh, K.-C.; Zhao, G.
Abstract: Semidefinite feasibility problems arise in many areas of operations research. The abstract form of these problems can be described as finding a point in a nonempty bounded convex body Γ in the cone of symmetric positive semidefinite matrices. Assume that Γ is defined by an oracle, which for any given m × m symmetric positive semidefinite matrix Ŷ either confirms that Ŷ ε Γ or returns a cut, i.e., a symmetric matrix A such that Γ is in the half-space {Y : A · Y ≤ A · Ŷ}. We study an analytic center cutting plane algorithm for this problem. At each iteration, the algorithm computes an approximate analytic center of a working set defined by the cutting plane system generated in the previous iterations. If this approximate analytic center is a solution, then the algorithm terminates; otherwise the new cutting plane returned by the oracle is added into the system. As the number of iterations increases, the working set shrinks and the algorithm eventually finds a solution to the problem. All iterates generated by the algorithm are positive definite matrices. The algorithm has a worst-case complexity of O* (m3/ε2) on the total number of cuts to be used, where ε is the maximum radius of a ball contained by Γ.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/442102002-01-01T00:00:00Z
- Representing the space of linear programs as the Grassmann manifoldhttps://scholarbank.nus.edu.sg/handle/10635/130043Title: Representing the space of linear programs as the Grassmann manifold
Authors: Zhao, G.
Abstract: Each linear program (LP) has an optimal basis. The space of linear programs can be partitioned according to these bases, so called the basis partition. Discovering the structures of this partition is our goal. We represent the space of linear programs as the space of projection matrices, i.e., the Grassmann manifold. A dynamical system on the Grassmann manifold, first presented in Sonnevend et al. (Math Program 52:527-553), is used to characterize the basis partition as follows: From each projection matrix associated with an LP, the dynamical system defines a path and the path leads to an equilibrium projection matrix returning the optimal basis of the LP. We will present some basic properties of equilibrium points of the dynamical system and explicitly describe all eigenvalues and eigenvectors of the linearized dynamical system at equilibrium points. These properties will be used to determine the stability of equilibrium points and to investigate the basis partition. This paper is only a beginning of the research towards our goal. © 2008 Springer-Verlag.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1300432008-01-01T00:00:00Z
- On the relationship between the curvature integral and the complexity of path-following methods in linear programminghttps://scholarbank.nus.edu.sg/handle/10635/103833Title: On the relationship between the curvature integral and the complexity of path-following methods in linear programming
Authors: Zhao, G.
Abstract: In this paper we study the complexity of primal-dual path-following methods which are a particular kind of interior point method for solving linear programs. In particular we establish a relationship between the complexity and the integral of a weighted curvature along the central trajectory (path) defined in the interior of the feasible solution space of a linear program. An important property of the trajectory, viz., that its higher order derivatives are bounded by a geometric series, is presented. Applying this property we show that the complexity of such methods is bounded from below and from above by the curvature integral. This theorem reduces the complexity analysis to a relatively simple problem of estimating the curvature integral.
Thu, 01 Feb 1996 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1038331996-02-01T00:00:00Z
- Interior point algorithms for linear complementarity problems based on large neighborhoods of the central pathhttps://scholarbank.nus.edu.sg/handle/10635/103436Title: Interior point algorithms for linear complementarity problems based on large neighborhoods of the central path
Authors: Zhao, G.
Abstract: In this paper we study a first-order and a high-order algorithm for solving linear complementarity problems. These algorithms are implicitly associated with a large neighborhood whose size may depend on the dimension of the problems. The complexity of these algorithms depends on the size of the neighborhood. For the first-order algorithm, we achieve the complexity bound which the typical large-step algorithms possess. It is well known that the complexity of large-step algorithms is greater than that of short-step ones. By using high-order power series (hence the name high-order algorithm), the iteration complexity can be reduced. We show that the complexity upper bound for our high-order algorithms is equal to that for short-step algorithms.
Fri, 01 May 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1034361998-05-01T00:00:00Z
- Interior-point methods with decomposition for solving large-scale linear programshttps://scholarbank.nus.edu.sg/handle/10635/103437Title: Interior-point methods with decomposition for solving large-scale linear programs
Authors: Zhao, G.Y.
Abstract: This paper deals with an algorithm incorporating the interior-point method into the Dantszig-Wolfe decomposition technique for solving large-scale linear programming problems. The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.
Thu, 01 Jul 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1034371999-07-01T00:00:00Z
- A superlinearly convergent algorithm for large scale multi-stage stochastic nonlinear programminghttps://scholarbank.nus.edu.sg/handle/10635/102770Title: A superlinearly convergent algorithm for large scale multi-stage stochastic nonlinear programming
Authors: Meng, F.; Tan, R.C.E.; Zhao, G.
Abstract: This paper presents an algorithm for solving a class of large scale nonlinear programming which is originally derived from the multi-stage stochastic convex nonlinear programming. With the Lagrangian-dual method and the Moreau-Yosida regularization, the primal problem is transformed into a smooth convex problem. By introducing a self-concordant barrier function, an approximate generalized Newton method is designed in this paper. The algorithm is shown to be of superlinear convergence. At last, some preliminary numerical results are provided.
Tue, 01 Jun 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027702004-06-01T00:00:00Z
- A smoothing newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programminghttps://scholarbank.nus.edu.sg/handle/10635/102765Title: A smoothing newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming
Authors: Huang, Z.-H.; Sun, D.; Zhao, G.
Abstract: In this paper we propose a smoothing Newton-type algorithm for the problem of minimizing a convex quadratic function subject to finitely many convex quadratic inequality constraints. The algorithm is shown to converge globally and possess stronger local superlinear convergence. Preliminary numerical results are also reported. © 2006 Springer Science + Business Media, LLC.
Sun, 01 Oct 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1027652006-10-01T00:00:00Z
- A decomposition method based on SQP for a class of multistage stochastic nonlinear programshttps://scholarbank.nus.edu.sg/handle/10635/114292Title: A decomposition method based on SQP for a class of multistage stochastic nonlinear programs
Authors: Liu, X.; Zhao, G.
Abstract: Multistage stochastic programming problems arise in many practical situations, such as production and manpower planning, portfolio selections, and so on. In general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. Sequential quadratic programming (SQP) methods are very effective for solving medium-size nonlinear programming. By using the scenario analysis technique, a decomposition method based on SQP for solving a class of multistage stochastic nonlinear programs is proposed, which generates the search direction by solving parallelly a set of quadratic programming subproblems with much less size than the original problem at each iteration. Conjugate gradient methods can be introduced to derive the estimates of the dual multiplier associated with the nonanticipativity constraints. By selecting the step-size to reduce an exact penalty function sufficiently, the algorithm terminates finitely at an approximate optimal solution to the problem with any desirable accuracy. Some preliminary numerical results are reported.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1142922004-01-01T00:00:00Z
- A log-barrier method with Benders decomposition for solving two-stage stochastic linear programshttps://scholarbank.nus.edu.sg/handle/10635/102672Title: A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs
Authors: Zhao, G.
Abstract: An algorithm incorporating the logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time.
Tue, 01 May 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1026722001-05-01T00:00:00Z
- A superlinearly convergent algorithm for large scale multi-stage stochastic nonlinear programminghttps://scholarbank.nus.edu.sg/handle/10635/52765Title: A superlinearly convergent algorithm for large scale multi-stage stochastic nonlinear programming
Authors: Meng, F.; Tan, R.C.E.; Zhao, G.
Abstract: This paper presents an algorithm for solving a class of large scale nonlinear programming which is originally derived from the multi-stage stochastic convex nonlinear programming. With the Lagrangian-dual method and the Moreau-Yosida regularization, the primal problem is transformed into a smooth convex problem. By introducing a self-concordant barrier function, an approximate generalized Newton method is designed in this paper. The algorithm is shown to be of superlinear convergence. At last, some preliminary numerical results are provided.
Tue, 01 Jun 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/527652004-06-01T00:00:00Z
- User capacity analysis of space division multiple access channelhttps://scholarbank.nus.edu.sg/handle/10635/53328Title: User capacity analysis of space division multiple access channel
Authors: Luo, Z.-Q.; Shum, W.-Y.; Zhao, G.
Abstract: Space Division Multiple Access (SDMA), which uses beamforming techniques to exploit the spatial diversity of different users, can significantly increase system capacity as well as the communication range between users and the basestation. In this paper, we consider the SDMA uplink channel, whereby a pool of users wish to communicate with a basestation with a fixed quality of service (QoS) requirement. We analyze the SDMA average user capacity defined as the average maximum number of random users that can be scheduled for simultaneous transmission, while meeting their respective QoS requirements. Using a standard probabilistic model involving narrow-band and far-field assumptions for the random users, we characterize the average user capacity in terms of the number of antennas, the QoS requirement, number of users and the maximum SNR (signal to noise ratio) among all users. These results act as a system design guide, offering insight into the tradeoff between hardware cost and system performance.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/533282003-01-01T00:00:00Z
- User capacity analysis of space division multiple access channelhttps://scholarbank.nus.edu.sg/handle/10635/104650Title: User capacity analysis of space division multiple access channel
Authors: Luo, Z.-Q.; Shum, W.-Y.; Zhao, G.
Abstract: Space Division Multiple Access (SDMA), which uses beamforming techniques to exploit the spatial diversity of different users, can significantly increase system capacity as well as the communication range between users and the basestation. In this paper, we consider the SDMA uplink channel, whereby a pool of users wish to communicate with a basestation with a fixed quality of service (QoS) requirement. We analyze the SDMA average user capacity defined as the average maximum number of random users that can be scheduled for simultaneous transmission, while meeting their respective QoS requirements. Using a standard probabilistic model involving narrow-band and far-field assumptions for the random users, we characterize the average user capacity in terms of the number of antennas, the QoS requirement, number of users and the maximum SNR (signal to noise ratio) among all users. These results act as a system design guide, offering insight into the tradeoff between hardware cost and system performance.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/1046502003-01-01T00:00:00Z
- A predictor-corrector algorithm for a class of nonlinear saddle point problemshttps://scholarbank.nus.edu.sg/handle/10635/45067Title: A predictor-corrector algorithm for a class of nonlinear saddle point problems
Authors: Sun, J.; Zhu, J.; Zhao, G.
Abstract: An interior path-following algorithm is proposed for solving the nonlinear saddle point problem minimax cT x + φ(x) + bT y - ψ(y) -yT Ax subject to (x, y) ∈ X x Y ⊂ Rn x Rm, where φ(x) and ψ(y) are smooth convex functions and X and Y are boxes (hyperrectangles). This problem is closely related to the models in stochastic programming and optimal control studied by Rockafellar and Wets (Math. Programming Studies, 28 (1986), pp. 63-93; SIAM J. Control Optim., 28 (1990), pp. 810-822). Existence and error-bound results on a central path are derived. Starting from an initial solution near the central path with duality gap O(μ), the algorithm finds an ∈-optimal solution of the problem in O(√m + n| log μ/∈|) iterations if both φ(x) and ψ(y) satisfy a scaled Lipschitz condition.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450671997-01-01T00:00:00Z
- On the rate of local convergence of high-order-infeasible-path-following algorithms for P*-linear complementarity problemshttps://scholarbank.nus.edu.sg/handle/10635/45068Title: On the rate of local convergence of high-order-infeasible-path-following algorithms for P*-linear complementarity problems
Authors: Zhao, G.; Sun, J.
Abstract: A simple and unified analysis is provided on the rate of local convergence for a class of high-order-infeasible-path-following algorithms for the P*-linear complementarity problem (P*-LCP). It is shown that the rate of local convergence of a ν-order algorithm with a centering step is ν+1 if there is a strictly complementary solution and (ν+1)/2 otherwise. For the ν-order algorithm without the centering step the corresponding rates are ν and ν/2, respectively. The algorithm without a centering step does not follow the fixed traditional central path. Instead, at each iteration, it follows a new analytic path connecting the current iterate with an optimal solution to generate the next iterate. An advantage of this algorithm is that it does not restrict iterates in a sequence of contracting neighborhoods of the central path.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450681999-01-01T00:00:00Z
- Global linear and local quadratic convergence of a long-step adaptive-mode interior point method for some monotone variational inequality problemshttps://scholarbank.nus.edu.sg/handle/10635/45072Title: Global linear and local quadratic convergence of a long-step adaptive-mode interior point method for some monotone variational inequality problems
Authors: Sun, J.; Zhao, G.
Abstract: An interior point (IP) method is proposed to solve variational inequality problems for monotone functions and polyhedral sets. The method has the following advantages: 1. Given an initial interior feasible solution with duality gap μ0, the algorithm requires at most O[n log(μ0/ε)] iterations to obtain an ε-optimal solution. 2. The rate of convergence of the duality gap is q-quadratic. 3. At each iteration, a long-step improvement is allowed. 4. The algorithm can automatically transfer from a linear mode to a quadratic mode to accelerate the local convergence.
Thu, 01 Jan 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450721998-01-01T00:00:00Z
- A quadratically convergent polynomial long-step algorithm for a class of nonlinear monotone complementarity problemshttps://scholarbank.nus.edu.sg/handle/10635/45083Title: A quadratically convergent polynomial long-step algorithm for a class of nonlinear monotone complementarity problems
Authors: Sun, J.; Zhao, G.
Abstract: Several interior point algorithms have been proposed for solving nonlinear monotone complementarity problems. Some of them have polynomial worst-case complexity but have to confine to short steps, whereas some of the others can take long steps but no polynomial complexity is proven. This paper presents an algorithm which is both long-step and polynomial. In addition, the sequence generated by the algorithm, as well as the corresponding complementarity gap, converges quadratically. The proof of the polynomial complexity requires that the monotone mapping satisfies a scaled Lipschitz condition, while the quadratic rate of convergence is derived under the assumptions that the problem has a strictly complementary solution and that the Jacobian of the mapping satisfies certain regularity conditions. © 2000 OPA (Overseas Publishers Association) N.V. Published by license under the Gordon and Breach Science Publishers imprint.
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450832000-01-01T00:00:00Z
- Quadratic convergence of a long-step interior-point method for nonlinear monotone variational inequality problemshttps://scholarbank.nus.edu.sg/handle/10635/45085Title: Quadratic convergence of a long-step interior-point method for nonlinear monotone variational inequality problems
Authors: Sun, J.; Zhao, G.Y.
Abstract: This paper offers an analysis on a standard long-step primaldual interior-point method for nonlinear monotone variational inequality problems. The method has polynomial-time complexity and its q-order of convergence is two. The results are proved under mild assumptions. In particular, new conditions on the invariance of the rank and range space of certain matrices are employed, rather than restrictive assumptions like nondegeneracy.
Thu, 01 Jan 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/450851998-01-01T00:00:00Z