Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

Relaxation in nonconvex optimal control problems with subdifferential operators

We consider the minimization problem of an integral functional in a separable Hilbert space with integrand not convex in the control defined on solutions of the control system described by nonlinear evolutionary equations with mixed nonconvex constraints. The evolutionary operator of the system is the subdifferential of a proper, convex, lower semicontinuous function depending on time. Along with the initial problem, the author considers the relaxed problem with the convexicated control constraint and the integrand convexicated with respect to the control. Under sufficiently general assumptions, it is proved that the relaxed problem has an optimal solution, and for any optimal solution, there exists a minimizing sequence of the initial problem converging to the optimal solution with respect to trajectories and the functional. An example of a controlled parabolic variational inequality with obstacle is considered in detail. __________ Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 26, Nonlinear Dynamics, 2005.     

Regularized parametric Kuhn-Tucker theorem in a Hilbert space

For a parametric convex programming problem in a Hilbert space with a strongly convex objective functional, a regularized Kuhn-Tucker theorem in nondifferential form is proved by the dual regularization method. The theorem states (in terms of minimizing sequences) that the solution to the convex programming problem can be approximated by minimizers of its regular Lagrangian (which means that the Lagrange multiplier for the objective functional is unity) with no assumptions made about the regularity of the optimization problem. Points approximating the solution are constructively specified. They are stable with respect to the errors in the initial data, which makes it possible to effectively use the regularized Kuhn-Tucker theorem for solving a broad class of inverse, optimization, and optimal control problems. The relation between this assertion and the differential properties of the value function (S-function) is established. The classical Kuhn-Tucker theorem in nondifferential form is contained in the above theorem as a particular case. A version of the regularized Kuhn-Tucker theorem for convex objective functionals is also considered.     

Global convergence of the partitioned BFGS algorithm for convex partially separable optimization

Global convergence is proved for a partitioned BFGS algorithm, when applied on a partially separable problem with a convex decomposition. This case convers a known practical optimization method for large dimensional unconstrained problems. Inexact solution of the linear system defining the search direction and variants of the steplength rule are also shown to be acceptable without affecting the global convergence properties.     

一类不可微二次规划逆问题

本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确求解过程中发现其仍是目标函数可分离变量的凸优化问题,由于其变量都是矩阵,所以采用适合多个矩阵变量的交替方向法求解,通过引入新的变量,使其每个子问题的解都具有显示表达式.最后给出采用的G-ADMM法求解本文问题的数值实验.数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题.     

Optimality conditions and duality results for nonsmooth vector optimization problems with the multiple interval-valued objective function

In this paper, both Fritz John and Karush-Kuhn-Tucker necessary optimality conditions are established for a (weakly) LU-efficient solution in the considered nonsmooth multiobjective programming problem with the multiple interval-objective function. Further, the sufficient optimality conditions for a (weakly) LU-efficient solution and several duality results in Mond-Weir sense are proved under assumptions that the functions constituting the considered nondifferentiable multiobjective programming problem with the multiple interval-objective function are convex.     

Convergence rate of a proximal multiplier algorithm for separable convex minimization

In this paper, we analyse the convergence rate of the proximal algorithm proposed by us in the article [A proximal multiplier method for separable convex minimization. Optimization. 2016; 65:501–537], which has been proposed to solve a separable convex minimization problem. We prove that, under mild assumptions, the primal-dual sequences of the algorithm converge linearly to the optimal solution for a class of proximal distances.     

Subdifferential inclusions with unbounded perturbation: Existence and relaxation theorems

The paper studies an evolution inclusion in a separable Hilbert space whose right-hand side contains the subdifferential of a proper convex lower semicontinuous function of time and a set-valued perturbation. Together with this inclusion, an inclusion with convexified perturbation values is considered. The existence and density of the solution set of the initial inclusion in the closure of the solution set of the inclusion with convexified perturbation are proved. This property is usually called relaxation. Traditional assumptions for relaxation theorems are the compactness property of the convex function and the boundedness of the perturbation. In the present paper, such assumptions are not made. Assumptions for subdifferential inclusions described by polyhedral sweeping processes and variational inequalities with time-dependent obstacles and constraints are specified.     

Extremality conditions for the quasi-concavity function and applications

A maximum principle for the lower envelope of two strictly subharmonic functions is proved, and subsequently used to investigate the first- and second-order extremality conditions for the quasi-concavity function. An application is done to the Dirichlet problem associated to elliptic equations involving the Laplacian as well as the minimal surface operator, when the domain of the problem is a convex ring and two constant boundary values are prescribed. The right-hand side may depend on the solution and on any of its first derivatives, and must depend on the space variable. The solution is proved to have convex level sets and a non-vanishing gradient. Assumptions are translation-invariant. Poisson’s equation is considered explicitly.     

Duality Theorems for Separable Convex Programming Without Qualifications

In the research of mathematical programming, duality theorems are essential and important elements. Recently, Lagrange duality theorems for separable convex programming have been studied. Tseng proves that there is no duality gap in Lagrange duality for separable convex programming without any qualifications. In other words, although the infimum value of the primal problem equals to the supremum value of the Lagrange dual problem, Lagrange multiplier does not always exist. Jeyakumar and Li prove that Lagrange multiplier always exists without any qualifications for separable sublinear programming. Furthermore, Jeyakumar and Li introduce a necessary and sufficient constraint qualification for Lagrange duality theorem for separable convex programming. However, separable convex constraints do not always satisfy the constraint qualification, that is, Lagrange duality does not always hold for separable convex programming. In this paper, we study duality theorems for separable convex programming without any qualifications. We show that a separable convex inequality system always satisfies the closed cone constraint qualification for quasiconvex programming and investigate a Lagrange-type duality theorem for separable convex programming. In addition, we introduce a duality theorem and a necessary and sufficient optimality condition for a separable convex programming problem, whose constraints do not satisfy the Slater condition.     

Reduction of a Minimization Problem of a Separable Convex Function Under Linear Constraints to a Fixed Point Problem

The paper is devoted to studying a constrained nonlinear optimization problem of a special kind. The objective functional of the problem is a separable convex function whose minimum is sought for on a set of linear constraints in the form of equalities. It is proved that, for this type of optimization problems, the explicit form can be obtained of a projection operator based on a generalized projection matrix. The projection operator allows us to represent the initial problem as a fixed point problem. The explicit form of the fixed point problem makes it possible to run a process of simple iteration. We prove the linear convergence of the obtained iterative method and, under rather natural additional conditions, its quadratic convergence. It is shown that an important application of the developed method is the flow assignment in a network of an arbitrary topology with one pair of source and sink.     

One-phase parabolic free boundary problem in a convex ring

This paper studies a free boundary problem for the heat equation in a convex ring. It is proved that the considered problem has unique solution under some conditions on the initial data.     

A proximal point algorithm converging strongly for general errors

In this paper a proximal point algorithm (PPA) for maximal monotone operators with appropriate regularization parameters is considered. A strong convergence result for PPA is stated and proved under the general condition that the error sequence tends to zero in norm. Note that Rockafellar (SIAM J Control Optim 14:877–898, 1976) assumed summability for the error sequence to derive weak convergence of PPA in its initial form, and this restrictive condition on errors has been extensively used so far for different versions of PPA. Thus this Note provides a solution to a long standing open problem and in particular offers new possibilities towards the approximation of the minimum points of convex functionals.     

Global linear convergence of a path-following algorithm for some monotone variational inequality problems

We consider a primal-scaling path-following algorithm for solving a certain class of monotone variational inequality problems. Included in this class are the convex separable programs considered by Monteiro and Adler and the monotone linear complementarity problem. This algorithm can start from any interior solution and attain a global linear rate of convergence with a convergence ratio of 1 ?c/√m, wherem denotes the dimension of the problem andc is a certain constant. One can also introduce a line search strategy to accelerate the convergence of this algorithm.     

A decomposition-dualization approach for solving constrained convex minimization problems with applications to discretized obstacle problems

Summary In this paper, we shall be concerned with the solution of constrained convex minimization problems. The constrained convex minimization problems are proposed to be transformable into a convex-additively decomposed and almost separable form, e.g. by decomposition of the objective functional and the restrictions. Unconstrained dual problems are generated by using Fenchel-Rockafellar duality. This decomposition-dualization concept has the advantage that the conjugate functionals occuring in the derived dual problem are easily computable. Moreover, the minimum point of the primal constrained convex minimization problem can be obtained from any maximum point of the corresponding dual unconstrained concave problem via explicit return-formulas. In quadratic programming the decomposition-dualization approach considered here becomes applicable if the quadratic part of the objective functional is generated byH-matrices. Numerical tests for solving obstacle problems in ¹ discretized by using piecewise quadratic finite elements and in ² by using the five-point difference approximation are presented.     

On Generalizations of the Frank-Wolfe Theorem to Convex and Quasi-Convex Programmes

In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or a quasi-convex polynomial function over the feasible set defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities, where the faithfully convex functions satisfy some mild assumption. The conditions are provided in the form of an algorithm, terminating after a finite number of iterations, the implementation of which requires the identification of implicit equality constraints in a homogeneous linear system. We prove that the optimal solution set of the considered problem is nonempty, this way extending the attainability result well known as the so-called Frank-Wolfe theorem. Finally we show that our extension of the Frank-Wolfe theorem immediately implies continuity of the solution set defined by the considered system of (quasi)convex inequalities.     

Application of the alternating direction method of multipliers to separable convex programming problems

This paper presents a decomposition algorithm for solving convex programming problems with separable structure. The algorithm is obtained through application of the alternating direction method of multipliers to the dual of the convex programming problem to be solved. In particular, the algorithm reduces to the ordinary method of multipliers when the problem is regarded as nonseparable. Under the assumption that both primal and dual problems have at least one solution and the solution set of the primal problem is bounded, global convergence of the algorithm is established.     

Convex-concave fractional programming with each variable occurring in a single constraint

The problem considered is that of maximizing the ratio of a concave and a convex function under the assumption that each variable occurs in exactly one component constraint. Such problems occur in the allocation of resources to activities. It is demonstrated that the problem is separable and that componentwise optimization can be applied to determine a solution. A method is given that can be used to evaluate the quality of any feasible solution in terms of an associated upper bound of the optimal value of the objective function: optimal and almost optimal solutions can be recognized. A fast incremental method of generating feasible solutions is described.     

Local Entropy Conditions in Transonic Potential Flow Problems

The transonic potential flow problem is handled as a variational problem over a closed convex set which is given by a bound for the gas velocity and by a local entropy condition. It can be shown that the minimum problem has a solution though the functional need not be convex and the given set is not compact. Furthermore, the convergence of an approximation method (KATCHANOV'S method) for the solution to the corresponding variational inequality is proved.