Exploiting Overlap Information in Chance-constrained Program with Random Right-hand Side

We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more

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 … Read more

A Limited Memory Subspace Minimization Conjugate Gradient Algorithm for Unconstrained Optimization

Subspace minimization conjugate gradient (SMCG) methods are a class of high potential iterative methods for unconstrained optimization. The orthogonality is an important property of linear conjugate gradient method. It is however observed that the orthogonality of gradients in linear conjugate gradient method is often lost, which usually causes the slow convergence of conjugate gradient method. … Read more

Efficient presolving methods for the influence maximization problem in social networks

We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the … Read more

Equipping Barzilai-Borwein method with two dimensional quadratic termination property

A new 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 new stepsize is that its computation only depends on the BB stepsizes in previous iterations without the use of exact line searches and Hessian, and hence it can easily … Read more

Optimization with Least Constraint Violation

Study about theory and algorithms for constrained optimization usually assumes that the feasible region of the optimization problem is nonempty. However, there are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A … Read more

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 … Read more

A primal-dual interior-point relaxation method with adaptively updating barrier 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. In the proposed method, the barrier parameter is updated in every step as done in interior-point methods for linear programs, which is prominently different from the existing interior-point methods … Read more

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 … Read more

On the asymptotic convergence and acceleration of gradient methods

We consider the asymptotic behavior of a family of gradient methods, which include the steepest descent and minimal gradient methods as special instances. It is proved that each method in the family will asymptotically zigzag between two directions. Asymptotic convergence results of the objective value, gradient norm, and stepsize are presented as well. To accelerate … Read more