| 1. |
- Banert, Sebastian, et al.
(författare)
-
A general double-proximal gradient algorithm for d.c. programming
- 2019
-
Ingår i: Mathematical programming. - : SPRINGER HEIDELBERG. - 0025-5610 .- 1436-4646. ; 178:1-2, s. 301-326
-
Tidskriftsartikel (refereegranskat)abstract
- The possibilities of exploiting the special structure of d.c. programs, which consist of optimising the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave part, or both, are evaluated by one of their subgradients. In this paper we propose an algorithm which allows the evaluation of both the concave and the convex part by their proximal points. Additionally, we allow a smooth part, which is evaluated via its gradient. In the spirit of primal-dual splitting algorithms, the concave part might be the composition of a concave function with a linear operator, which are, however, evaluated separately. For this algorithm we show that every cluster point is a solution of the optimisation problem. Furthermore, we show the connection to the Toland dual problem and prove a descent property for the objective function values of a primal-dual formulation of the problem. Convergence of the iterates is shown if this objective function satisfies the Kurdyka-Lojasiewicz property. In the last part, we apply the algorithm to an image processing model.
|
|
| 2. |
- Blomvall, Jörgen, et al.
(författare)
-
Solving multistage asset investment problems by the sample average approximation method
- 2006
-
Ingår i: Mathematical programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 108:2-3, s. 571-595
-
Tidskriftsartikel (refereegranskat)abstract
- The vast size of real world stochastic programming instances requires sampling to make them practically solvable. In this paper we extend the understanding of how sampling affects the solution quality of multistage stochastic programming problems. We present a new heuristic for determining good feasible solutions for a multistage decision problem. For power and log-utility functions we address the question of how tree structures, number of stages, number of outcomes and number of assets affect the solution quality. We also present a new method for evaluating the quality of first stage decisions.
|
|
| 3. |
- Brill, Markus, et al.
(författare)
-
Phragmén's voting methods and justified representation
- 2024
-
Ingår i: Mathematical programming. - : Springer. - 0025-5610 .- 1436-4646. ; 203:1-2, s. 47-76
-
Tidskriftsartikel (refereegranskat)abstract
- In the late 19th century, Swedish mathematician Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants—one minimizing the maximum load and one minimizing the variance of loads—and a sequential variant. We study Phragmén's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential variant satisfies proportional justified representation, which is a rare property for committee monotonic methods. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén's methods and provide mixed-integer programming based algorithms for computing them.
|
|
| 4. |
- Flinth, Axel, et al.
(författare)
-
On the linear convergence rates of exchange and continuous methods for total variation minimization
- 2021
-
Ingår i: Mathematical Programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 190, s. 221-257
-
Tidskriftsartikel (refereegranskat)abstract
- We analyze an exchange algorithm for the numerical solution total-variation regularized inverse problems over the space M(Omega) of Radon measures on a subset Omega of R-d. Our main result states that under some regularity conditions, the method eventually converges linearly. Additionally, we prove that continuously optimizing the amplitudes of positions of the target measure will succeed at a linear rate with a good initialization. Finally, we propose to combine the two approaches into an alternating method and discuss the comparative advantages of this approach.
|
|
| 5. |
- Forsgren, Anders
(författare)
-
Optimality conditions for nonconvex semidefinite programming
- 2000
-
Ingår i: Mathematical programming. - 0025-5610 .- 1436-4646. ; 88:1, s. 105-128
-
Tidskriftsartikel (refereegranskat)abstract
- This paper concerns nonlinear semidefinite programming problems for which no convexity assumptions can be made. We derive first- and second-order optimality conditions analogous to those for nonlinear programming. Using techniques similar to those used in nonlinear programming, we extend existing theory to cover situations where the constraint matrix is structurally sparse. The discussion covers the case when strict complementarity does not hold. The regularity conditions used are consistent with those of nonlinear programming in the sense that the conventional optimality conditions for nonlinear programming are obtained when the constraint matrix is diagonal.
|
|
| 6. |
- Forsgren, Anders, et al.
(författare)
-
Primal and dual active-set methods for convex quadratic programming
- 2016
-
Ingår i: Mathematical programming. - : Springer Berlin/Heidelberg. - 0025-5610 .- 1436-4646. ; 159:1-2, s. 469-508
-
Tidskriftsartikel (refereegranskat)abstract
- Computational methods are proposed for solving a convex quadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal-dual form. The primal method maintains feasibility of the primal inequalities while driving the infeasibilities of the dual inequalities to zero. The dual method maintains feasibility of the dual inequalities while moving to satisfy the primal inequalities. In each of these methods, the search directions satisfy a KKT system of equations formed from Hessian and constraint components associated with an appropriate column basis. The composition of the basis is specified by an active-set strategy that guarantees the nonsingularity of each set of KKT equations. Each of the proposed methods is a conventional active-set method in the sense that an initial primal- or dual-feasible point is required. In the second part of the paper, it is shown how the quadratic program may be solved as a coupled pair of primal and dual quadratic programs created from the original by simultaneously shifting the simple-bound constraints and adding a penalty term to the objective function. Any conventional column basis may be made optimal for such a primal-dual pair of shifted-penalized problems. The shifts are then updated using the solution of either the primal or the dual shifted problem. An obvious application of this approach is to solve a shifted dual QP to define an initial feasible point for the primal (or vice versa). The computational performance of each of the proposed methods is evaluated on a set of convex problems from the CUTEst test collection.
|
|
| 7. |
- Glad, Torkel, 1947-, et al.
(författare)
-
A Multiplier Method with Automatic Limitation of Penalty Growth
- 1979
-
Ingår i: Mathematical programming. - : Springer. - 0025-5610 .- 1436-4646. ; 17:1, s. 140-155
-
Tidskriftsartikel (refereegranskat)abstract
- This paper presents a multiplier method for solving optimization problems with equality and inequality constraints. The method realizes all the good features that were foreseen by R. Fletcher for this type of algorithm in the past, but which suffers from none of the drawbacks of the earlier attempts.
|
|
| 8. |
- Golovin, Daniel, et al.
(författare)
-
Improved approximations for two-stage min-cut and shortest path problems under uncertainty
- 2015
-
Ingår i: Mathematical Programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 149:1, s. 167-194
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we study the robust and stochastic versions of the two-stage min-cut and shortest path problems introduced in Dhamdhere et al. (in How to pay, come what may: approximation algorithms for demand-robust covering problems. In: FOCS, pp 367–378, 2005), and give approximation algorithms with improved approximation factors. Specifically, we give a 2-approximation for the robust min-cut problem and a 4-approximation for the stochastic version. For the two-stage shortest path problem, we give a 3.39'>3.39 3.39 -approximation for the robust version and 6.78'>6.78 6.78 -approximation for the stochastic version. Our results significantly improve the previous best approximation factors for the problems. In particular, we provide the first constant-factor approximation for the stochastic min-cut problem. Our algorithms are based on a guess and prune strategy that crucially exploits the nature of the robust and stochastic objective. In particular, we guess the worst-case second stage cost and based on the guess, select a subset of costly scenarios for the first-stage solution to address. The second-stage solution for any scenario is simply the min-cut (or shortest path) problem in the residual graph. The key contribution is to show that there is a near-optimal first-stage solution that completely satisfies the subset of costly scenarios that are selected by our procedure. While the guess and prune strategy is not directly applicable for the stochastic versions, we show that using a novel LP formulation, we can adapt a guess and prune algorithm for the stochastic versions. Our algorithms based on the guess and prune strategy provide insights about the applicability of this approach for more general robust and stochastic versions of combinatorial problems.
|
|
| 9. |
- Gustavsson, Emil, 1987, et al.
(författare)
-
Primal convergence from dual subgradient methods for convex optimization
- 2015
-
Ingår i: Mathematical Programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 150:2, s. 365-390
-
Tidskriftsartikel (refereegranskat)abstract
- When solving a convex optimization problem through a Lagrangian dual reformulation subgradient optimization methods are favorably utilized, since they often find near-optimal dual solutions quickly. However, an optimal primal solution is generally not obtained directly through such a subgradient approach unless the Lagrangian dual function is differentiable at an optimal solution. We construct a sequence of convex combinations of primal subproblem solutions, a so called ergodic sequence, which is shown to converge to an optimal primal solution when the convexity weights are appropriately chosen. We generalize previous convergence results from linear to convex optimization and present a new set of rules for constructing the convexity weights that define the ergodic sequence of primal solutions. In contrast to previously proposed rules, they exploit more information from later subproblem solutions than from earlier ones. We evaluate the proposed rules on a set of nonlinear multicommodity flow problems and demonstrate that they clearly outperform the ones previously proposed.
|
|
| 10. |
- Haarala, Napsu, et al.
(författare)
-
Globally Convergent Limited Memory Bundle Method for Large-Scale Nonsmooth Optimization
- 2007
-
Ingår i: Mathematical programming. - : Springer Science and Business Media LLC. - 0025-5610 .- 1436-4646. ; 109:1, s. 181-205
-
Tidskriftsartikel (refereegranskat)abstract
- Many practical optimization problems involve nonsmooth (that is, not necessarily differentiable) functions of thousands of variables. In the paper [Haarala, Miettinen, Mäkelä, Optimization Methods and Software, 19, (2004), pp. 673-692] we have described an efficient method for large-scale nonsmooth optimization. In this paper, we introduce a new variant of this method and prove its global convergence for locally Lipschitz continuous objective functions, which are not necessarily differentiable or convex. In addition, we give some encouraging results from numerical experiments.
|
|
