January 2019 – Page 3 – Optimization Online

Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality, and Saddle-Points

Published: 2019/01/14, Updated: 2019/01/15

Nonlinear Optimization, Stochastic Programming complexity, conditional gradient, newton method, nonconvex optimization, stochastic optimization, zeroth-order algorithms

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To … Read more

Best Subset Selection via Cross-validation Criterion

Published: 2019/01/13

Ryuhei Miyashiro

Yuichi Takano

Integer Programming, Statistics cross-validation, integer programming, ridge regression, statistics, subset selection

This paper is concerned with the cross-validation criterion for best subset selection in a linear regression model. In contrast with the use of statistical criteria (e.g., Mallows’ $C_p$, AIC, BIC, and various information criteria), the cross-validation only requires the mild assumptions, namely, samples are identically distributed, and training and validation samples are independent. For this … Read more

A fully mixed-integer linear programming formulation for economic dispatch with valve-point effects, transmission loss and prohibited operating zones

Published: 2019/01/12

(Mixed) Integer Linear Programming, Applications - Science and Engineering economic dispatch, fully mixed-integer linear programming, non-continuous, non-linear programming, nonconvex optimization, nonsmooth

Economic dispatch (ED) problem considering valve-point effects (VPE), transmission loss and prohibited operating zones (POZ) is a very challenging issue due to its intrinsic non-convex, non-smooth and non-continuous natures. To achieve a near globally solution, a fully mixed-integer linear programming (FMILP) formulation is proposed for such an ED problem. Since the original loss function is … Read more

Two-stage Stochastic Programming with Linearly Bi-parameterized Quadratic Recourse

Published: 2019/01/10, Updated: 2019/10/15

Stochastic Programming difference of convex, stochastic programming, two stage

This paper studies the class of two-stage stochastic programs (SP) with a linearly bi-parameterized recourse function defined by a convex quadratic program. A distinguishing feature of this new class of stochastic programs is that the objective function in the second stage is linearly parameterized by the first-stage decision variable, in addition to the standard linear … Read more

Coupled task scheduling with time-dependent processing times

Published: 2019/01/10

Mostafa Khatami

Amir Salehipour

Applications - OR and Management Sciences, Scheduling

The single machine coupled task scheduling problem includes a set of jobs, each with two separated tasks and there is an exact delay between the tasks. We investigate the single machine coupled task scheduling problem with the objective of minimizing the makespan under identical processing time for the first task and identical delay period for … Read more

Forecasting conceivable interest rate market scenarios and significant losses on interest rate portfolios using mathematical optimization

Published: 2019/01/10, Updated: 2019/01/15

Katsuhiro Tanaka

Constrained Nonlinear Optimization, Finance and Economics mathematical optimization, portfolio optimization, reverse stress test, risk management, stress test, uncertainty set

This study proposes a mathematical optimization programming model that simultaneously forecasts interest rate market scenarios and significant losses on interest rate market portfolios. The model includes three main components. A constraint condition is set using the Mahalanobis distance, which consists of innovation terms in a dynamic conditional correlation-generalized autoregressive conditional heteroscedasticity (DCC-GARCH) model that represent … Read more

Coupled task scheduling with exact delays: Literature review and models

Published: 2019/01/10

T.C.E. Cheng

Mostafa Khatami

Amir Salehipour

Applications - OR and Management Sciences, Scheduling

The coupled task scheduling problem concerns scheduling a set of jobs, each with at least two tasks and there is an exact delay period between two consecutive tasks, on a set of machines to optimize a performance criterion. While research on the problem dates back to the 1980s, interests in the computational complexity of variants … Read more

Approximating L1-Norm Best-Fit Lines

Published: 2019/01/09

J. Paul Brooks

JH Dulá

Data-Mining

Sufficient conditions are provided for a deterministic algorithm for estimating an L1-norm best-fit one-dimensional subspace. To prove the conditions are sufficient, fundamental properties of the L1-norm projection of a point onto a one-dimensional subspace are derived. Also, an equivalence is established between the algorithm, which involves the calculation of several weighted medians, and independently-derived algorithms … Read more

A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

Published: 2019/01/08

Sunyoung Kim

Masakazu Kojima

Kim-Chuan Toh

Linear, Cone and Semidefinite Programming completely positive reformulation of quadratic and polynomial optimization problems, conic optimization problems, faces of the completely positive cone, hierarchies of copositivity

We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with a class of geometrically defined nonconvex conic programs and their covexification. The class of nonconvex conic programs is described with a linear objective function in a linear space $V$, and the constraint … Read more