Uniform duality in semi-infinite convex optimization

We study infinite sets of convex functional constraints, with possibly a set constraint, under general background hypotheses which require closed functions and a closed set, but otherwise do not require a Slater point. For example, when the set constraint is not present, only the consistency of the conditions is needed. We provide hypotheses, which are necessary as well as sufficient, for the overall set of constraints to have the property that there is no gap in Lagrangean duality for every convex objective function defined on ℝⁿ. The sums considered for our Lagrangean dual are those involving only finitely many nonzero multipliers. In particular, we recover the usual sufficient condition when only finitely many functional constraints are present. We show that a certain compactness condition in function space plays the role of finiteness, when there are an infinite number of functional constraints. The author's research has been partially supported by Grant ECS8001763 of the National Science Foundation.     

Imputing a variational inequality function or a convex objective function: A robust approach

To impute the function of a variational inequality and the objective of a convex optimization problem from observations of (nearly) optimal decisions, previous approaches constructed inverse programming methods based on solving a convex optimization problem [17], [7]. However, we show that, in addition to requiring complete observations, these approaches are not robust to measurement errors, while in many applications, the outputs of decision processes are noisy and only partially observable from, e.g., limitations in the sensing infrastructure. To deal with noisy and missing data, we formulate our inverse problem as the minimization of a weighted sum of two objectives: 1) a duality gap or Karush–Kuhn–Tucker (KKT) residual, and 2) a distance from the observations robust to measurement errors. In addition, we show that our method encompasses previous ones by generating a sequence of Pareto optimal points (with respect to the two objectives) converging to an optimal solution of previous formulations. To compare duality gaps and KKT residuals, we also derive new sub-optimality results defined by KKT residuals. Finally, an implementation framework is proposed with applications to delay function inference on the road network of Los Angeles, and consumer utility estimation in oligopolies.     

Iterative processes for solving incorrect convex variational problems

The present paper is concerned with a general approach to the construction and the numerical analysis of stable methods solving semi-infinite convex programs and variational inequalities of elliptical type in case where the considered problems are incorrect. The approach which is based on the application of the PROX-regularization (cf. Martinet, 1970; Ekeland and Temam, 1976; Rockafellar, 1976; Brézis and Lions, 1978; Lemaire, 1988) secures the strong convergence of the minimizing sequence. The possibility of the algorithmical realization is described and depends on the smoothness properties of the solutions.Supported by Deutsche Forschungsgemeinschaft under grant Ti 191/1-1.     

Path-following proximal approach for solving Ill-posed convex semi-infinite programming problems

For a class of ill-posed, convex semi-infinite programming problems, a regularized path-following strategy is developed. This approach consists in a coordinated application of adaptive discretization and prox-regularization procedures combined with a penalty method. At each iteration, only an approximate minimum of a strongly convex differentiable function has to be calculated, and this can be done by any fast-convergent algorithm. The use of prox-regularization ensures the convergence of the iterates to some solution of the original problem. Due to regularization, an efficient deleting rule is applicable, which excludes an essential part of the constraints in the discretized problems.This research was supported by the German Research Society (DFG).The authors are grateful to the anonymous referees for their valuable comments.     

Directional differentiability of the optimal value function in convex semi-infinite programming

In this paper, directional differentiability properties of the optimal value function of a parameterized semi-infinite programming problem are studied. It is shown that if the unperturbed semi-infinite programming problem is convex, then the corresponding optimal value function is directionally differentiable under mild regularity assumptions. A max-min formula for the directional derivatives, well-known in the finite convex case, is given.     

Proximal level bundle methods for convex nondifferentiable optimization,saddle-point problems and variational inequalities

We study proximal level methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We show that they enjoy almost optimal efficiency estimates. We give extensions for solving convex constrained problems, convex-concave saddle-point problems and variational inequalities with monotone operators. We present several variants, establish their efficiency estimates, and discuss possible implementations. In particular, our methods require bounded storage in contrast to the original level methods of Lemaréchal, Nemirovskii and Nesterov.This research was supported by the Polish Academy of Sciences.Supported by a grant from the French Ministry of Research and Technology.     

A constrained optimization approach to solving certain systems of convex equations

This research presents a new constrained optimization approach for solving systems of nonlinear equations. Particular advantages are realized when all of the equations are convex. For example, a global algorithm for finding the zero of a convex real-valued function of one variable is developed. If the algorithm terminates finitely, then either the algorithm has computed a zero or determined that none exists; if an infinite sequence is generated, either that sequence converges to a zero or again no zero exists. For solving n-dimensional convex equations, the constrained optimization algorithm has the capability of determining that the system of equations has no solution. Global convergence of the algorithm is established under weaker conditions than previously known and, in this case, the algorithm reduces to Newton’s method together with a constrained line search at each iteration. It is also shown how this approach has led to a new algorithm for solving the linear complementarity problem.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

Isolated calmness of solution mappings in convex semi-infinite optimization

This paper is concerned with isolated calmness of the solution mapping of a parameterized convex semi-infinite optimization problem subject to canonical perturbations. We provide a sufficient condition for isolated calmness of this mapping. This sufficient condition characterizes the strong uniqueness of minimizers, under the Slater constraint qualification. Moreover, on the assumption that the objective function and the constraints are linear, we show that this condition is also necessary for isolated calmness.     

Lipschitz behavior of solutions to nonconvex semi-infinite vector optimization problems

This paper is devoted to developing new applications from the limiting subdifferential in nonsmooth optimization and variational analysis to the study of the Lipschitz behavior of the Pareto solution maps in parametric nonconvex semi-infinite vector optimization problems (SIVO for brevity). We establish sufficient conditions for the Aubin Lipschitz-like property of the Pareto solution maps of SIVO under perturbations of both the objective function and constraints.     

Lipschitz continuity ofV-subdifferentials of convex operators

It is proved that theV-subdifferential of a convex operator is locally Lipschitzian on the set of points at which it is continuous and subdifferentiable.Proposition 2.2 was originally stated for Holder continuity ofV-subdifferentials. The author would like to thank J. P. Penot for a very helpful suggestion which led to the present form of this proposition.     

Market price-based convex risk measures: A distribution-free optimization approach

In Cont (2006) [1], a convex risk measure was proposed to measure the impact of uncertainty resulting from the misspecification of derivative models. Evaluation of the risk measures was illustrated on finite families of probability measures. In this paper, we consider the case of infinite families of measures that share common moments, e.g. mean and variance for European-style options. We show that the risk measure can still be efficiently evaluated based on semi-infinite programming. Examples are given that illustrate the benefits of evaluating the risk measure with infinite families of measures and shed light on the limitations of considering only finite families of measures.     

Global stress regularity of convex and some nonconvex variational problems

We derive a global regularity theorem for stress fields which correspond to minimizers of convex and some special nonconvex variational problems with mixed boundary conditions on admissible domains. These are Lipschitz domains satisfying additional geometric conditions near those points, where the type of the boundary conditions changes. In the first part it is assumed that the energy densities defining the variational problem are convex but not necessarily strictly convex and satisfy a convexity inequality. The regularity result for this case is derived with a difference quotient technique. In the second part the regularity results are carried over from the convex case to special nonconvex variational problems taking advantage of the relation between nonconvex variational problems and the corresponding (quasi-) convexified problems. The results are applied amongst others to the variational problems for linear elasticity, the p-Laplace operator, Hencky elasto-plasticity with linear hardening and for scalar and vectorial two-well potentials (compatible case).      

Dini derivative and a characterization for Lipschitz and convex functions on Riemannian manifolds

Dini derivatives in Riemannian manifold settings are studied in this paper. In addition, a characterization for Lipschitz and convex functions defined on Riemannian manifolds and sufficient optimality conditions for constraint optimization problems in terms of the Dini derivative are given.     

Inverse optimization for linearly constrained convex separable programming problems

In this paper, we study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with ℓ₁ and ℓ₂ norms. These inverse optimization problems are either linear programming when ℓ₁ norm is used in the formulation, or convex quadratic separable programming when ℓ₂ norm is used.     

Sequential optimality conditions for composed convex optimization problems

Using a general approach which provides sequential optimality conditions for a general convex optimization problem, we derive necessary and sufficient optimality conditions for composed convex optimization problems. Further, we give sequential characterizations for a subgradient of the precomposition of a K-increasing lower semicontinuous convex function with a K-convex and K-epi-closed (continuous) function, where K is a nonempty convex cone. We prove that several results from the literature dealing with sequential characterizations of subgradients are obtained as particular cases of our results. We also improve the above mentioned statements.     

A dynamic system model for solving convex nonlinear optimization problems

This paper proposes a feedback neural network model for solving convex nonlinear programming (CNLP) problems. Under the condition that the objective function is convex and all constraint functions are strictly convex or that the objective function is strictly convex and the constraint function is convex, the proposed neural network is proved to be stable in the sense of Lyapunov and globally convergent to an exact optimal solution of the original problem. The validity and transient behavior of the neural network are demonstrated by using some examples.     

Metric regularity of semi-infinite constraint systems

We obtain a formula for the modulus of metric regularity of a mapping defined by a semi-infinite system of equalities and inequalities. Based on this formula, we prove a theorem of Eckart-Young type for such set-valued infinite-dimensional mappings: given a metrically regular mapping F of this kind, the infimum of the norm of a linear function g such that F+g is not metrically regular is equal to the reciprocal to the modulus of regularity of F. The Lyusternik-Graves theorem gives a straightforward extension of these results to nonlinear systems. We also discuss the distance to infeasibility for homogeneous semi-infinite linear inequality systems. Dedicated to R. T. Rockafellar on his 70th Birthday Research partially supported by grants BFM2002-04114-C02 (01-02) from MCYT (Spain) and FEDER (E.U.), GV04B-648 and GRUPOS04/79 from Generalitat Valenciana (Spain), and Bancaja-UMH (Spain).     

A sequential quadratic programming with a dual parametrization approach to nonlinear semi-infinite programming

In the sequel of the work reported in Liu et al. (1999), in which a method based on a dual parametrization is used to solve linear-quadratic semi-infinite programming (SIP) problems, a sequential quadratic programming technique is proposed to solve nonlinear SIP problems. A merit function to measure progress toward the solution and a procedure to compute the penalty parameter are also proposed.     

A note on the compactness of the index set in convex optimization. Application to metric regularity

We consider the linear quadratic optimal control problem in the infinite time horizon case for a class of discrete-time systems controlled by a continuous inputs. We show that, under certain hypothesis, the Hilbert uniqueness method can be used to determine the optimal control.