In this paper, an algorithm for maximizing a convex function over a convex feasible set is proposed. The algorithm, called CoMax, consists of two phases: in phase 1, a feasible starting point is obtained that is used in a gradient ascent algorithm in phase 2. The main contribution of the paper is connected to phase 1; five different methods are used to approximate the original NP-hard problem of maximizing a convex function (MCF) by a tractable convex optimization problem. All the methods use the minimizer of the convex objective function in their construction. In phase 2, the gradient ascent algorithm yields stationary points to the MCF problem. The performance of CoMax is tested on a wide variety of MCF problems, demonstrating its efficiency. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant 406.17.511]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplementary Information [ https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1238 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.6884872 ].

We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. Our results provide extensions to known results from the literature. We also consider hard quadratic constraints: those that are convex in uncertain matrix-valued parameters. For the robust counterpart of such constraints, we derive inner and outer tractable approximations. As an application, we show how to construct a natural uncertainty set based on a statistical confidence set around a sample mean vector and covariance matrix and use this to provide a tractable reformulation of the robust counterpart of an uncertain portfolio optimization problem. We also apply the results of this paper to norm approximation problems. Summary of Contribution: This paper develops new theoretical results and algorithms that extend the scope of a robust quadratic optimization problem. More specifically, we derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We also consider hard quadratic constraints: those that are convex in uncertain matrix-valued parameters. For the robust counterpart of such constraints, we derive inner and outer tractable approximations.

Maximizing a convex function over convex constraints is an NP-hard problem in general. We prove that such a problem can be reformulated as an adjustable robust optimization (ARO) problem in which each adjustable variable corresponds to a unique constraint of the original problem. We use ARO techniques to obtain approximate solutions to the convex maximization problem. In order to demonstrate the complete approximation scheme, we distinguish the cases in which we have just one nonlinear constraint and multiple linear constraints. Concerning the first case, we give three examples in which one can analytically eliminate the adjustable variable and approximately solve the resulting static robust optimization problem efficiently. More specifically, we show that the norm constrained log-sum-exp (geometric) maximization problem can be approximated by (convex) exponential cone optimization techniques. Concerning the second case of multiple linear constraints, the equivalent ARO problem can be represented as an adjustable robust linear optimization problem. Using linear decision rules then returns a safe approximation of the constraints. The resulting problem is a convex optimization problem, and solving this problem gives an upper bound on the global optimum value of the original problem. By using the optimal linear decision rule, we obtain a lower bound solution as well. We derive the approximation problems explicitly for quadratic maximization, geometric maximization, and sum-of-max-linear-terms maximization problems with multiple linear constraints. Numerical experiments show that, contrary to the state-of-the-art solvers, we can approximate large-scale problems swiftly with tight bounds. In several cases, we have equal upper and lower bounds, which concludes that we have global optimality guarantees in these cases. Summary of Contribution: Maximizing a convex function over a convex set is a hard optimization problem. We reformulate this problem as an optimization problem under uncertainty, which allows us to transfer the hardness of this problem from its nonconvexity to the uncertainty of the new problem. The equivalent uncertain optimization problem can be relaxed tightly by using adjustable robust optimization techniques. In addition to building a new bridge between convex maximization and robust optimization, this approach also gives us strong algorithms that improve the state-of-the-art optimization solvers both in solution time and quality for various convex maximization problems.

We study the problem of computing the capacity of a discrete memoryless channel under uncertainty affecting the channel law matrix, and possibly with a constraint on the average cost of the input distribution. The problem has been formulated in the literature as a max-min problem. We use the robust optimization methodology to convert the max-min problem to a standard convex optimization problem. For small-sized problems, and for many types of uncertainty, such a problem can be solved in principle using interior point methods (IPMs). However, for large-scale problems, IPMs are not practical. Here, we suggest an O(1/T) first-order algorithm based on [1] which is applied directly to the max-min problem.

Robust optimization is a methodology that can be applied to problems that are affected by uncertainty in their parameters. The classical robust counterpart of a problem requires the solution to be feasible for all uncertain parameter values in a so-called uncertainty set and offers no guarantees for parameter values outside this uncertainty set. The globalized robust counterpart (GRC) extends this idea by allowing controlled constraint violations in a larger uncertainty set. The constraint violations are controlled by the distance of the parameter from the original uncertainty set. We derive tractable GRCs that extend the initial GRCs in the literature: our GRC is applicable to nonlinear constraints instead of only linear or conic constraints, and the GRC is more flexible with respect to both the uncertainty set and distance measure function, which are used to control the constraint violations. In addition, we present a GRC approach that can be used to provide an extended trade-off overview between the objective value and several robustness measures.

In this paper we consider the problem of learning an n x n Kernel matrix from m similarity matrices under general convex loss. Past research have extensively studied the m =1 case and have derived several algorithms which require sophisticated techniques like ACCP, SOCP, etc. The existing algorithms do not apply if one uses arbitrary losses and often can not handle m > 1 case. We present several provably convergent iterative algorithms, where each iteration requires either an SVM or a Multiple Kernel Learning (MKL) solver for m > 1 case. One of the major contributions of the paper is to extend the well known Mirror Descent(MD) framework to handle Cartesian product of psd matrices. This novel extension leads to an algorithm, called EMKL, which solves the problem in O(m^2 log n) iterations; in each iteration one solves an MKL involving m kernels and m eigen-decomposition of n x n matrices. By suitably defining a restriction on the objective function, a faster version of EMKL is proposed, called REKL, which avoids the eigen-decomposition. An alternative to both EMKL and REKL is also suggested which requires only an SVM solver. Experimental results on real world protein data set involving several similarity matrices illustrate the efficacy of the proposed algorithms.

Motivated from real world problems, like object categorization, we study a particular mixed-norm regularization for Multiple Kernel Learning (MKL). It is assumed that the given set of kernels are grouped into distinct components where each component is crucial for the learning task at hand. The formulation hence employs $l_\infty$ regularization for promoting combinations at the component level and $l_1$ regularization for promoting sparsity among kernels in each component. While previous attempts have formulated this as a non-convex problem, the formulation given here is an instance of non-smooth convex optimization problem which admits an efficient Mirror-Descent (MD) based procedure. The MD procedure optimizes over product of simplexes, which is not a well-studied case in literature. Results on real-world datasets show that the new MKL formulation is well-suited for object categorization tasks and that the MD based algorithm outperforms state-of-the-art MKL solvers like \texttt{simpleMKL} in terms of computational effort.

We consider the problem of multichannel estimation, in which we seek to estimate multiple input vectors that are observed through a set of linear transformations and corrupted by additive noise. The input vectors x/sub k/ are known to satisfy a weighted norm constraint. We discuss both the case where the linear transformations are fixed (certain) and the case where they are only known to reside in some deterministic uncertainty set. We seek the linear estimator that minimizes the worst-case mean-squared error (MSE) across all possible values of the linear transformations and possible values of x/sub k/. We show that for an arbitrary choice of weighting matrix, the minimax MSE estimator can be formulated as a solution to a semidefinite programming problem (SDP). In the case in which the linear transformations are fixed and the norms are unweighed, the minimax MSE multichannel estimator has an explicit closed from solution. Finally, we demonstrate through examples, that the minimax MSE estimator can significantly increase the performance over conventional least-squares based methods.

We develop a new linear estimator for estimating an unknown vector x in a linear model, in the presence of bounded data uncertainties. The estimator is designed to minimize the worst-case regret across all bounded data vectors, namely the worst-case difference between the MSE attainable using a linear estimator that does not know the true parameters x, and the optimal MSE attained using a linear estimator that knows x. We demonstrate through several examples that the minimax regret estimator can significantly increase the performance over the conventional least-squares estimator, as well as several other least-squares alternatives.

Images produced from positron emission tomography (PET) data sources are important for detecting tumors. To improve the resolution of images produced by PET scanners we develop a procedure (optimal locally adjustable filtering OLAF) where the parameters of filters (eg, Metz, Gauss) are adjusted "optimally" at each point of the reconstructed image in terms of a global objective function, which combines goodness-of-fit, and entropy terms The optimization problem is solved by a specialized genetic algorithm. The approach was tested on several PET data sets (simulated and clinical) (Levkovitz et al., 1998) and has demonstrated that OLAF improves both contrast and uniformity, compared to usual fixed post-processing filtering methods.

In this paper,we present coincidence-list-ordered sets expectation-maximization (COSEM), an algorithm for iterative image reconstruction directly from list-mode coincidence acquisition data. The COSEM algorithm is based on the ordered sets EM algorithm for binned data but has several extensions that makes it suitable for rotating two planar detector tomographs. We develop the COSEM algorithm and extend it to include analytic calculation of detection probability, noise reducing iterative filtering schemes, and on-the-fly attenuation correction methods. We present an adaptation of COSEM to the Varicam\VG camera and show results from clinical and phantom studies.

A new generalized average mutual information measure (GAMIM) is introduced in terms of Csiszar\phi-divergence, and the associated rate distortion functionR_{\phi}is studied. The main objective is to derive in a unified way a dual representation ofR_{\phi}, then to use it to generalize classical results (corresponding to\phi(t) = t \log t) in rate distortion theory and extend results associated with other concepts of GAMIM. Our development uses the methodology of convex programming duality extensively.