Price Optimization with Practical Constraints

In this paper, we study a retailer price optimization problem which includes the practical constraints: maximum number of price changes and minimum amount of price change (if a change is recommended). We provide a closed-form formula for the Euclidean projection onto the feasible set defined by these two constraints, based on which a simple gradient … Read more

A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables

We propose a gradient-based method for quadratic programming problems with a single linear constraint and bounds on the variables. Inspired by the GPCG algorithm for bound-constrained convex quadratic programming [J.J. More’ and G. Toraldo, SIAM J. Optim. 1, 1991], our approach alternates between two phases until convergence: an identification phase, which performs gradient projection iterations … Read more

A Dual Gradient-Projection Method for Large-Scale Strictly Convex Quadratic Problems

The details of a solver for minimizing a strictly convex quadratic objective function subject to general linear constraints is presented. The method uses a gradient projection algorithm enhanced with subspace acceleration to solve the bound-constrained dual optimization problem. Such gradient projection methods are well-known, but are typically employed to solve the primal problem when only … Read more

Local Convergence of an Algorithm for Subspace Identification from Partial Data

GROUSE (Grassmannian Rank-One Update Subspace Estimation) is an iterative algorithm for identifying a linear subspace of $\R^n$ from data consisting of partial observations of random vectors from that subspace. This paper examines local convergence properties of GROUSE, under assumptions on the randomness of the observed vectors, the randomness of the subset of elements observed at … Read more

Hager-Zhang Active Set Algorithm for Large-Scale Continuous Knapsack Problems

The structure of many real-world optimization problems includes minimization of a nonlinear (or quadratic) functional subject to bound and singly linear constraints (in the form of either equality or bilateral inequality) which are commonly called as continuous knapsack problems. Since there are efficient methods to solve large-scale bound constrained nonlinear programs, it is desirable to … Read more

Duality-Based Algorithms for Total-Variation-Regularized Image Restoration

Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the … Read more

An Active-Set Algorithm for Nonlinear Programming Using Parametric Linear Programming

This paper describes an active-set algorithm for nonlinear programming that solves a parametric linear programming subproblem at each iteration to generate an estimate of the active set. A step is then computed by solving an equality constrained quadratic program based on this active-set estimate. This approach respresents an extension of the standard sequential linear-quadratic programming … Read more

Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems

Many problems in signal processing and statistical inference involve finding sparse solutions to under-determined, or ill-conditioned, linear systems of equations. A standard approach consists in minimizing an objective function which includes a quadratic (squared $\ell_2$) error term combined with a sparseness-inducing ($\ell_1$) regularization term.{\it Basis pursuit}, the {\it least absolute shrinkage and selection operator} (LASSO), … Read more

In pursuit of a root

The basis pursuit technique is used to find a minimum one-norm solution of an underdetermined least-squares problem. Basis pursuit denoise fits the least-squares problem only approximately, and a single parameter determines a curve that traces the trade-off between the least-squares fit and the one-norm of the solution. We show that the function that describes this … Read more