Aug 2026· TOP - An Official Journal of the Spanish Society of Statistics and Operations Research· 0 citations· 13 references
TL;DR
A new concept of upper semicontinuity for a vector-valued function and (weak and strong) duality statements under the assumption that the vector-valued objective function is D -quasiconvex and D -upper semicontinuous are proved.
Abstract
It is well-known that duality theory is a fundamental tool in various areas of mathematics. There are great advantages to including or using the dual problem and duality statements. Especially, solving the dual problem can be done using other methods of analysis or numerical mathematics. We consider a primal vector optimization problem with an objective function acting between a linear topological space
X
and a linear topological space
Y
equipped with a pointed closed convex cone
$$D\subset Y$$
D
⊂
Y
with nonempty interior. The feasible set is supposed to be a closed convex cone. The aim of this paper is to construct a simple and easy-to-handle dual problem by exploiting the special structure of the primal problem and using a suitable nonlinear scalarization. The computation of the dual image set involves the minimization of a nonlinear scalarization of the primal vector-valued objective function subject to only one linear inequality constraint. We introduce a new concept of upper semicontinuity for a vector-valued function and prove (weak and strong) duality statements under the assumption that the vector-valued objective function is
D
-quasiconvex and
D
-upper semicontinuous. Furthermore, we study special cases.
We present a generalization of the well-known homogeneous self-dual embedding model, which is widely used in conic optimization. The new embedding applies to a problem of minimizing the sum of two proper lower-semicontinuous convex functions and can be represented as a single inequality that uses perspectives of these functions and of their conjugates. A solution to the proposed embedding encodes a primal-dual solution to the original problem when available, or an infeasibility certificate otherwise. We then use the Douglas-Rachford algorithm to find a solution to the embedding and discuss its efficient implementation by exploiting the problem structure. The resulting algorithm recovers an existing method for solving quadratic cone programs as a special case. We demonstrate the generality and effectiveness of the algorithm on a class of convex optimization problems with non-smooth objective function and non-conic constraints.
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
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 presents two different types of proximal gradient methods, with line search and without line search, for solving unconstrained set-valued optimization problems under the lower set-less ordering relation induced by a solid cone that is convex, pointed, and closed. The objective mapping of the problem involves finitely many functions, with each one being the sum of a continuously differentiable function and a convex function that is proper and closed. We present an approach to characterize weakly minimal points of the problem with the help of weakly efficient points of a family of vector optimization problems. Thereafter, we establish a stationarity condition along with its connection with weakly minimal points of the problem under study. Based on the stationary condition, the concept of a descent direction at a non-stationary point is discussed. In view of the line search-based method, we formulate an Armijo-type line search condition and establish the existence of such a step-size. For the proposed methods, global convergence is established under mild assumptions. The convergence analysis of the proximal gradient method with line search provides a theoretical advancement over the convergence results previously established for the steepest descent method in set-valued optimization problems. In addition, we analyze the computational complexity of the proposed methods and show that both methods achieve a convergence rate of $\mathcal{O}(1/\sqrt{k})$. Numerical results are reported to test the performance of the methods in practice.
Ravi Raushan, Debdas Ghosh, Anshika et al.· 0 citations
The quadratic optimization-free (QO-free) method is a class of powerful and effective algorithms for solving nonlinearly constrained optimization problems in Euclidean spaces. The aim of the present work is to extend this method to solve optimization problems on manifolds with additional equality and inequality constraints. We first present a specific algorithm in the manifold setting. At each iteration, three linear systems sharing a common linear operator are solved to determine the master search direction. In addition, a higher-order correction direction is obtained by solving a reduced linear least squares subproblem to circumvent the Maratos effect which is assumed not to arise in existing related literature. A Riemannian arc search is then performed within the tangent space of the current iterate to generate the new iterate. Under appropriate assumptions, we establish the global and strong convergence of the proposed method. Moreover, we prove that the unit step size will eventually be accepted by the arc search, upon which the superlinear convergence of the algorithm is established. Finally, numerical results demonstrate that the proposed method is very competitive compared with other existing approaches.
Chun-Ming Tang, Hao He, Wen Huang et al.· 0 citations
In a real Hilbert space, we study a bilevel optimization problem that consists in minimizing an outer convex function over the zero set of a maximally monotone operator. In the smooth setting, where the outer objective is convex and Fr\'echet differentiable and the inner operator is single-valued, continuous and monotone, we associate with the problem a first-order dynamical system that can be viewed as a monotone flow applied to a dynamically regularized operator. Under suitable geometric conditions on the inner problem --- either a weak Attouch-Czarnecki-type integrability condition or the stronger assumption of sharpness --- we establish last-iterate convergence rates for both the outer and inner residuals, together with weak convergence of the trajectories to optimal solutions of the bilevel problem. In the smooth+nonsmooth setting, we enrich the outer objective with a proper, convex, and lower semicontinuous function, while the inner operator is augmented by the subdifferential of a function with the same properties. We propose a regularized proximal-extragradient algorithm in which both the forward and backward steps are performed with respect to dynamically regularized operators and functions, respectively. Under geometric assumptions on the inner problem analogous to those in the smooth setting, we establish last-iterate convergence rates for both the outer and inner residuals, together with weak convergence of the iterates to optimal solutions of the bilevel problem.
R. Boț, Enis Chenchene, D. A. Hulett· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
