Convergence Analysis On Some First-order Optimization Algorithms

In this thesis,we consider the first-order optimization algorithms for solving submodu-lar maximization and two-stage stochastic nonlinear programming problems.In the first part of the thesis,we introduce the algorithms for solving the submodular maximization problem.First,we use the conditional gradient algorithm with a fixed step size to solve the determin-istic continuous Diminishing Returns(DR)-submodular problem.Under the conditions that the objective function is monotone and non-monotone,we derive the convergence results of the proposed algorithm,respectively.The existing research results mainly focus on the case where the constraint set is down-closed convex,in this thesis we extend the constraint set in the monotone case to the general convex set.Further,we extend the algorithm to random case,and propose the mini-batch stochastic conditional gradient algorithm for solving the s-tochastic continuous DR-submodular maximization problem.For the case that the objective function is monotone and non-monotone,we prove that the algorithm respectively achieves((1-1/0))OPT-)and((1/0))OPT-)guarantee after operating on(1/~2)iterations.In addi-tion,our algorithm can also be applied to solve the discrete submodular maximization problem subject to a general matroid constraint through continuous relaxation,and the same approxima-tion guarantees are achieved.In the second part of the thesis,We consider a class of two-stage stochastic nonlinear programming problems.The objective function in the first-stage is of the composite form.We propose an inexact stochastic proximal subgradient algorithm and establish its convergence under mild conditions.