Lehigh University

We will present a very general framework for unconstrained stochastic optimization which is based on standard trust region framework using  random models. In particular this framework retains the desirable features such step acceptance criterion, trust region adjustment and ability to utilize of second order models. We make assumptions on the stochasticity that are different from the typical assumptions of stochastic and simulation-based optimization. In particular we assume that our models and function values satisfy some good quality conditions with some probability fixed, but can be arbitrarily bad otherwise. We will analyze the convergence and convergence rates of this general framework and discuss the requirement on the models and function values. We will will contrast our results with existing results from stochastic approximation literature. We will finish with examples of applications arising the area of machine learning. 
 

We present a trust region algorithm for solving nonconvex optimization problems that, in the worst-case, is able to drive the norm of the gradient of the objective below a prescribed threshold $\epsilon > 0$ after at most ${\cal O}(\epsilon^{-3/2})$ function evaluations, gradient evaluations, or iterations.  Our work has been inspired by the recently proposed Adaptive Regularisation framework using Cubics (i.e., the ARC algorithm), which attains the same worst-case complexity bound.  Our algorithm is modeled after a traditional trust region algorithm, but employs modified step acceptance criteria and a novel trust region updating mechanism that allows it to achieve this desirable property.  Importantly, our method also maintains standard global and fast local convergence guarantees.

We will begin by discussing the risk parity portfolio selection problem, which aims to find  portfolios for which the contributions of risk from all assets are equally weighted. The risk parity may be satisfied over either individual assets or groups of assets. We show how convex optimization techniques can find a risk parity solution in the nonnegative  orthant, however, in general cases the number of such solutions can be anywhere between zero and  exponential in the dimension. We then propose a nonconvex least-squares formulation which allows us to consider and possibly solve the general case. 

Motivated by this problem we present several alternating direction schemes for specially structured nonlinear nonconvex problems. The problem structure allows convenient 2-block variable splitting.  Our methods rely on solving convex subproblems at each iteration and converge to a local stationary point. Specifically, discuss approach  alternating directions method of multipliers and the alternating linearization method and we provide convergence rate results for both classes of methods. Moreover, global optimization techniques from polynomial optimization literature are applied to complement our local methods and to provide lower bounds.

There is a well established body of research on quadratic optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to address key combinatorial optimization problems. Along this line of research, we consider quadratically constrained quadratic programs and provide sufficient and necessary conditions for
this type of problems to be reformulated as a conic program over the cone of completely positive matrices. Thus, recent related results for quadratic problems can be further strengthened. Moreover, these results can be generalized to optimization problems involving higher order polynomias.