Researcher profile

Yu-Hong Dai

Yu-Hong Dai contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
12works
0followers
8topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

A Novel Negative $\ell_1$ Penalty Approach for Multiuser One-Bit Massive MIMO Downlink with PSK Signaling

This paper considers the one-bit precoding problem for the multiuser downlink massive multiple-input multiple-output (MIMO) system with phase shift keying (PSK) modulation and focuses on the celebrated constructive interference (CI)-based problem formulation. The existence of the discrete one-bit constraint makes the problem generally hard to solve. In this paper, we propose an efficient negative $\ell_1$ penalty approach for finding a high-quality solution of the considered problem. Specifically, we first propose a novel negative $\ell_1$ penalty model, which penalizes the one-bit constraint into the objective with a negative $\ell_1$-norm term, and show the equivalence between (global and local) solutions of the original problem and the penalty problem when the penalty parameter is sufficiently large. We further transform the penalty model into an equivalent min-max problem and propose an efficient alternating optimization (AO) algorithm for solving it. The AO algorithm enjoys low per-iteration complexity and is guaranteed to converge to the stationary point of the min-max problem. Numerical results show that, compared against the state-of-the-art CI-based algorithms, the proposed algorithm generally achieves better bit-error-rate (BER) performance with lower computational cost.

preprint2022arXiv

A primal-dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs

Based on solving an equivalent parametric equality constrained mini-max problem of the classic logarithmic-barrier subproblem, we present a novel primal-dual interior-point relaxation method for nonlinear programs with general equality and nonnegative constraints. In each iteration, our method approximately solves the KKT system of a parametric equality constrained mini-max subproblem, which avoids the requirement that any primal or dual iterate is an interior-point. The method has some similarities to the warmstarting interior-point methods in relaxing the interior-point requirement and is easily extended for solving problems with general inequality constraints. In particular, it has the potential to circumvent the jamming difficulty that appears with many interior-point methods for nonlinear programs and improve the ill conditioning of existing primal-dual interior-point methods as the barrier parameter is small. A new smoothing approach is introduced to develop our relaxation method and promote convergence of the method. Under suitable conditions, it is proved that our method can be globally convergent and locally quadratically convergent to the KKT point of the original problem. The preliminary numerical results on a well-posed problem for which many interior-point methods fail to find the minimizer and a set of test problems from the CUTEr collection show that our method is efficient.

preprint2022arXiv

A primal-dual majorization-minimization method for large-scale linear programs

We present a primal-dual majorization-minimization method for solving large-scale linear programs. A smooth barrier augmented Lagrangian (SBAL) function with strict convexity for the dual linear program is derived. The majorization-minimization approach is naturally introduced to develop the smoothness and convexity of the SBAL function. Our method only depends on a factorization of the constant matrix independent of iterations and does not need any computation on step sizes, thus can be expected to be particularly appropriate for large-scale linear programs. The method shares some similar properties to the first-order methods for linear programs, but its convergence analysis is established on the differentiability and convexity of our SBAL function. The global convergence is analyzed without prior requiring either the primal or dual linear program to be feasible. Under the regular conditions, our method is proved to be globally linearly convergent, and a new iteration complexity result is given.

preprint2022arXiv

A semi-conjugate gradient method for solving unsymmetric positive definite linear systems

The conjugate gradient (CG) method is a classic Krylov subspace method for solving symmetric positive definite linear systems. We introduce an analogous semi-conjugate gradient (SCG) method for unsymmetric positive definite linear systems. Unlike CG, SCG requires the solution of a lower triangular linear system to produce each semi-conjugate direction. We prove that SCG is theoretically equivalent to the full orthogonalization method (FOM), which is based on the Arnoldi process and converges in a finite number of steps. Because SCG's triangular system increases in size each iteration, we study a sliding window implementation (SWI) to improve efficiency, and show that the directions produced are still locally semi-conjugate. A counterexample illustrates that SWI is different from the direct incomplete orthogonalization method (DIOM), which is FOM with a sliding window. Numerical experiments from the convection-diffusion equation and other applications show that SCG is robust and that the sliding window implementation SWI allows SCG to solve large systems efficiently.

preprint2022arXiv

Mirror frameworks for relatively Lipschitz and monotone-like variational inequalities

Nonconvex-nonconcave saddle-point optimization in machine learning has triggered lots of research for studying non-monotone variational inequalities (VI). In this work, we introduce two mirror frameworks, called mirror extragradient method and mirror extrapolation method, for approximating solutions to relatively Lipschitz and monotone-like VIs. The former covers the well-known Nemirovski's mirror prox method and Nesterov's dual extrapolation method, and the recently proposed Bregman extragradient method; all of them can be reformulated into a scheme that is very similar to the original form of extragradient method. The latter includes the operator extrapolation method and the Bregman extrapolation method as its special cases. The proposed mirror frameworks allow us to present a unified and improved convergence analysis for all these existing methods under relative Lipschitzness and monotone-like conditions that may be the currently weakest assumptions.

preprint2022arXiv

Optimal QoS-Aware Network Slicing for Service-Oriented Networks with Flexible Routing

In this paper, we consider the network slicing problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and allocate network resources to meet diverse quality of service (QoS) requirements. We first propose a mixed integer nonlinear program (MINLP) formulation for this problem that optimizes the network resource consumption while jointly considers QoS requirements, flow routing, and resource budget constraints. In particular, the proposed formulation is able to flexibly route the traffic flow of the services on multiple paths and provide end-to-end (E2E) delay and reliability guarantees for all services. Due to the intrinsic nonlinearity, the MINLP formulation is computationally difficult to solve. To overcome this difficulty, we then propose a mixed integer linear program (MILP) formulation and show that the two formulations and their continuous relaxations are equivalent. Different from the continuous relaxation of the MINLP formulation which is a nonconvex nonlinear programming problem, the continuous relaxation of the MILP formulation is a polynomial time solvable linear programming problem, which makes the MILP formulation much more computationally solvable. Numerical results demonstrate the effectiveness and efficiency of the proposed formulations over existing ones.

preprint2022arXiv

Optimality Conditions and Numerical Algorithms for A Class of Linearly Constrained Minimax Optimization Problems

It is well known that there have been many numerical algorithms for solving nonsmooth minimax problems, numerical algorithms for nonsmooth minimax problems with joint linear constraints are very rare. This paper aims to discuss optimality conditions and develop practical numerical algorithms for minimax problems with joint linear constraints. First of all, we use the properties of proximal mapping and KKT system to establish optimality conditions. Secondly, we propose a framework of alternating coordinate algorithm for the minimax problem and analyze its convergence properties. Thirdly, we develop a proximal gradient multi-step ascent decent method (PGmsAD) as a numerical algorithm and demonstrate that the method can find an $ε$-stationary point for this kind of nonsmooth nonconvex-nonconcave problem in ${\cal O}(ε^{-2}\logε^{-1})$ iterations. Finally, we apply PGmsAD to generalized absolute value equations, generalized linear projection equations and linear regression problems and report the efficiency of PGmsAD on large-scale optimization.

preprint2021arXiv

An efficient linear programming rounding-and-refinement algorithm for large-scale network slicing problem

In this paper, we consider the network slicing problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and allocate network resources to meet diverse service requirements, and propose an efficient two-stage algorithm for solving this NP-hard problem. In the first stage, the proposed algorithm uses an iterative linear programming (LP) rounding procedure to place the virtual network functions of all services into cloud nodes while taking traffic routing of all services into consideration; in the second stage, the proposed algorithm uses an iterative LP refinement procedure to obtain a solution for traffic routing of all services with their end-to-end delay constraints being satisfied. Compared with the existing algorithms which either have an exponential complexity or return a low-quality solution, our proposed algorithm achieves a better trade-off between solution quality and computational complexity. In particular, the worst-case complexity of our proposed algorithm is polynomial, which makes it suitable for solving large-scale problems. Numerical results demonstrate the effectiveness and efficiency of our proposed algorithm.

preprint2021arXiv

Equipping Barzilai-Borwein method with two dimensional quadratic termination property

A novel gradient stepsize is derived at the motivation of equipping the Barzilai-Borwein (BB) method with two dimensional quadratic termination property. A remarkable feature of the novel stepsize is that its computation only depends on the BB stepsizes in previous iterations and does not require any exact line search or the Hessian, and hence it can easily be extended for nonlinear optimization. By adaptively taking long BB steps and some short steps associated with the new stepsize, we develop an efficient gradient method for quadratic optimization and general unconstrained optimization and extend it to solve extreme eigenvalues problems. The proposed method is further extended for box-constrained optimization and singly linearly box-constrained optimization by incorporating gradient projection techniques. Numerical experiments demonstrate that the proposed method outperforms the most successful gradient methods in the literature.

preprint2020arXiv

Linear convergence of random dual coordinate incremental aggregated gradient methods

In this paper, we consider the dual formulation of minimizing $\sum_{i\in I}f_i(x_i)+\sum_{j\in J} g_j(\mathcal{A}_jx)$ with the index sets $I$ and $J$ being large. To address the difficulties from the high dimension of the variable $x$ (i.e., $I$ is large) and the large number of component functions $g_j$ (i.e., $J$ is large), we propose a hybrid method called the random dual coordinate incremental aggregated gradient method by blending the random dual block coordinate descent method and the proximal incremental aggregated gradient method. To the best of our knowledge, no research is done to address the two difficulties simultaneously in this way. Based on a newly established descent-type lemma, we show that linear convergence of the classical proximal gradient method under error bound conditions could be kept even one uses delayed gradient information and randomly updates coordinate blocks. Three application examples are presented to demonstrate the prospect of the proposed method.

preprint2020arXiv

On the acceleration of the Barzilai-Borwein method

The Barzilai-Borwein (BB) gradient method is efficient for solving large-scale unconstrained problems to the modest accuracy and has a great advantage of being easily extended to solve a wide class of constrained optimization problems. In this paper, we propose a new stepsize to accelerate the BB method by requiring finite termination for minimizing two-dimensional strongly convex quadratic function. Combing with this new stepsize, we develop gradient methods which adaptively take the nonmonotone BB stepsizes and certain monotone stepsizes for minimizing general strongly convex quadratic function. Furthermore, by incorporating nonmonotone line searches and gradient projection techniques, we extend these new gradient methods to solve general smooth unconstrained and bound constrained optimization. Extensive numerical experiments show that our strategies of properly inserting monotone gradient steps into the nonmonotone BB method could significantly improve its performance and the new resulted methods can outperform the most successful gradient decent methods developed in the recent literature.

preprint2020arXiv

Optimality Conditions for Constrained Minimax Optimization

Minimax optimization problems arises from both modern machine learning including generative adversarial networks, adversarial training and multi-agent reinforcement learning, as well as from tradition research areas such as saddle point problems, numerical partial differential equations and optimality conditions of equality constrained optimization. For the unconstrained continuous nonconvex-nonconcave situation, Jin, Netrapalli and Jordan (2019) carefully considered the very basic question: what is a proper definition of local optima of a minimax optimization problem, and proposed a proper definition of local optimality called local minimax. We shall extend the definition of local minimax point to constrained nonconvex-nonconcave minimax optimization problems. By analyzing Jacobian uniqueness conditions for the lower-level maximization problem and the strong regularity of Karush-Kuhn-Tucker conditions of the maximization problem, we provide both necessary optimality conditions and sufficient optimality conditions for the local minimax points of constrained minimax optimization problems.