This work considers a quadratic minmax problem with coupled inner constraints and proposes a method to compute a class of stationary points and shows in particular that the method is polynomial in the special case where the inner feasible set of the authors' constrained minmax problem is independent from outer variables.
Abstract
We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable{non-degeneracy} conditions. Then based on a suitable log barrier function, we build an infeasible interior point-type {single loop method} (which does not explicitly distinguish between the outer and inner problem) and prove that a non-degenerate stationary point is an attraction point as the algorithm moves along the designed central path. We show in particular that our method is polynomial in the special case where the inner feasible set of our constrained minmax problem is independent from outer variables. Our numerical experiments, on both synthetic data and a class of min-cost flow problems, showcase the behavior of our method and how it outperforms existing algorithms from the literature in terms of the quality of the computed stationary points.
For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.
F. Curtis, Ling-Jun Guo, Daniel P. Robinson· 0 citations
We investigate the optimization problem of minimizing a nonsmooth function that satisfies a nonsmooth version of the descent lemma over a nonempty and closed but not necessarily convex set. The objective function belongs to the class of upper-$\mathcal{C}^2$ functions, whereas the constraints may promote a sparse or low-rank structure. We propose a projected subgradient method with two different globalization strategies: (a) a nonmonotone linesearch and, under additional assumptions, (b) an auto-conditioned method, where the stepsize is given by a formula depending on data from past iterations. We show that both methods converge to solutions that satisfy a stronger stationarity concept than one would expect from the subdifferential sum-rule, which is particularly important since the optimization problems of interest are inherently nonconvex. Finally, we present promising numerical results when applying the algorithm to an MPEC-style problem as well as the matrix optimization problems MAXCUT and Robust PCA.
Christian Kanzow, Jannis Krüger, Leo Lehmann· 0 citations
This work proposes a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint, and constructs a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain.
We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. We provide a complete characterization of every optimal fixed-step method. Moreover, we show every optimal fixed-step method can be derived from the constructive approach of~\cite{constructive_approach} and provide a polyhedral representation of the set of optimal methods through proof multipliers. From this characterization, we show that no anytime optimal fixed-step subgradient methods exist.
As an extension of convex quadratic optimization (CQO) problems, the weighted convex quadratic optimization (WCQO) plays an important role in the domain of mathematical programming and engineering. In this paper, we propose a short-step primal-dual interior-point algorithm for solving WCQO based on the strategy of weighted-path. The latter generates only full-Newton steps and requires no line search. Under appropriate conditions, the algorithm converges locally quadratically to an optimal solution of WCQO. Moreover, it has the best well-known polynomial complexity, namely, O(√n log(n/ϵ)).
Finally, some numerical results are reported to confirm the efficiency of our proposed algorithm.
Rima Hamadouche, L. Derbal, M. Achache· Reserche operationelle· 0 citations
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
Benjamin Grimmer, Alex L. Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
