Réunion d'hiver SMC 2016
Niagara Falls, 2 - 5 décembre 2016
Optimisation à grande échelle : théorie, algorithmes et applications. Un hommage à Jonathan Borwein
Org: Heinz Bauschke (University of British Columbia, Kelowna) et Henry Wolkowicz (University of Waterloo)
[PDF]
Org: Heinz Bauschke (University of British Columbia, Kelowna) et Henry Wolkowicz (University of Waterloo)
[PDF]
- SEDI BARTZ, University of British Columbia, Kelowna
Multi-marginal monotonicity and convex analysis [PDF]
-
Similar to the two-marginal case, multi-marginal monotonicity and convex analysis arise naturally in the framework of multi-marginal optimal transport theory. However, even for classical cost functions, unlike in the two-marginal case, multi-marginal monotonicity and convex analysis is a largely an unexplored territory. We present natural problems and discuss open questions, recent resolutions and generalizations from the well studied two-marginal monotone operator theory and convex analysis to the multi-marginal settings. In particular, we discuss the existence of explicit $c$-splitting potentials and multi-marginal maximal monotonicity theory.
- HEINZ BAUSCHKE, UBC (Kelowna campus)
Remembering Jon Borwein [PDF]
-
This is not a formal talk; instead, we will
share memories of Jonathan Borwein who unexpectedly
passed away and who was a collaborator, mentor, friend, or
colleague to many of the speakers in this session.
- JIAWEI CHEN, Southwest University, PRC and UBC Okanagan, CA
Optimality conditions of constrained inverse variational inequalities via image space analysis [PDF]
-
Inverse variational inequalities (IVI) is a special model of variational inequalities, which was extensively applied to transportation, economic management, optimal control and algorithm design and so on. In this talk, we introduce a new constrained IVI. By using oriented distance function and indicator function, two nonlinear (regular) weak separation functions are proposed. Moreover, by the nonlinear separation functions, theorems of the weak alternative and necessary and sufficient optimality conditions for constrained IVI are established. A global saddle-point condition for a nonlinear function is also derived. It is shown that the existence of a saddle point, which implies the existence of solutions of IVI with constraints, is equivalent to a nonlinear regular separation
of two suitable subsets of the image space. The relationships between constrained IVI and its primal variational inequalities are also presented under some suitable conditions.
- TIM HOHEISEL, McGill University
Epi-convergent smoothing with applications to convex-composite functions [PDF]
-
Smoothing methods have become part of the standard tool set for the study and solution of
nondifferentiable and constrained optimization problems as well as a range of other
variational and equilibrium problems. In this note we synthesize and extend recent results due to
Beck and Teboulle on infimal convolution smoothing for convex functions
with those of X. Chen on gradient consistency for nonconvex functions.
We use epi-convergence techniques to define a notion of epi-smoothing that allows us to
tap into the rich variational structure of the subdifferential calculus for nonsmooth, nonconvex, and
nonfinite-valued functions. As an illustration of the versatility and range of epi-smoothing techniques,
the results are applied to the general constrained optimization for which nonlinear programming
is a special case.
- RICHARD HOSHINO, Quest University Canada
Solving Quadratic Optimization Problems using the Cauchy-Schwarz Inequality [PDF]
-
Quadratic Programming (QP) is an example of a non-linear programming problem, where the goal is to optimize a quadratic function on $n$ variables, subject to linear constraints on those variables. In this talk, we provide an alternative way of solving one special type of QP problem, via the Cauchy-Schwarz Inequality.
We apply the technique to determine the optimal fare prices for any transportation network that charges its commuters by total travel distance, where the goal is to maximize fare revenue given a fixed ridership. Our ``fare price formula'' is applied to a well-known 47-station transportation network in British Columbia with 400,000 daily commuters.
This research will inform the work of Metro Vancouver's transportation authority, an organization that is in the process of conducting a comprehensive review of transit fare policy for the first time in its history.
- MEHDI KARIMI, University of Waterloo
Convex optimization via domain-driven barriers and primal-dual algorithms [PDF]
-
During the last two decades, primal-dual algorithms enjoyed very significant advances in solving convex optimization problems in conic form over symmetric cones. However, many other highly demanded convex optimization problems lack comparable advances. To close this gap, we propose a theory of infeasible-start primal-dual interior-point algorithms for convex optimization problems in "domain-driven" formulation. We show that the domain-driven formulation covers many interesting classes of optimization problems including those in a conic form, naturally (without artificial embedding variables etc.). After presenting our techniques, and our convergence theorems, we introduce our Matlab-based code that solves a large class of problems including LP, SOCP, SDP, QCQP, Geometric programming, and Entropy programming among others, and mention some numerical challenges.
This talk is based on joint work with Mehdi Karimi.
- YVES LUCET, University of British Columbia
Approximate Subdifferential Computation in Computational Convex Analysis [PDF]
-
Computational convex analysis focuses on the computation of convex operators that routinely appear in convex analysis e.g. Legendre-Fenchel conjugate, Moreau envelope, etc. After recalling what computation the (open source) CCA numerical library allows, we will switch the focus from convex transforms like the Legendre-Fenchel transform to convex operators like the subdifferential. We will present results on efficiently computing the approximate subdifferential of a convex univariate function.
Joint work with W. Hare, A. Bajaj, and D. Kumar.
- WALAA MOURSI, University of British Columbia (Okanagan campus)
The Douglas-Rachford algorithm in the possibly inconsistent case [PDF]
-
The Douglas–Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this talk, we advance
the understanding of the inconsistent case significantly by presenting a complete proof of the full weak convergence in the convex feasibility setting. We also provide linear rate of convergence and strong convergence in special cases.
- DOMINIQUE ORBAN, Ecole Polytechnique and GERAD, Montreal
LSLQ: An Iterative Method for Linear Least-Squares Problems with a Forward Error Minimization Property [PDF]
-
We propose an iterative method named LSLQ for solving consistent linear systems or linear least-squares problems $A x \approx b$ of any shape based on the Golub-Kahan process, where the dominant cost consists in products with $A$ and $A^T$. In the rank deficient case, LSLQ identifies the minimum least-squares solution. LSLQ is formally equivalent to SYMMLQ (Paige and Saunders, 1975) applied to the normal equations so that the estimate norm $\|x_k\|_2$ increases monotonically and the forward error $\|x_k - x^*\|_2$ decreases monotonically. We provide lower and upper bound estimates on the forward error along the LSLQ iterations. The upper bound translates to an upper bound on the forward error in the Euclidean norm for LSQR, which was previously unavailable. We report numerical experiments on standard test problems and on a full-wave inversion problem arising from geophysics in which an approximate least-squares solution corresponds to an approximate gradient of a relevant penalty function that is to be minimized.
(joint work with Ron Estrin (ICME, Stanford) and Michael A. Saunders (ICME, Stanford))
- HUNG PHAN, University of Massachusetts Lowell
Applying Geometric Constraints in Three Dimensions [PDF]
-
In Computer Assisted Design (CAD), an object can be represented as a triangular mesh in three dimensions. In many cases, a problem is to enforce certain constraints on the individual triangles in the mesh. For example, in civil engineering, a designer may be concerned about drainage requirements of a grading site that is represented as a Triangulated Irregular Network (TIN). Hence, the designer may want to enforce some slope and flow direction constraints on the triangles.
In this talk, we model various engineering constraints as geometric constraints in three dimensions. We then find projection operators for these constraints, and solve the problem by iteratively applying these projectors. Besides, we also consider optimization problems in which we seek solutions that are optimal with respect to certain criteria.
(*) Joint-work with Valentin Koch (AutoDesk, Inc.)
- GREG REID, University of Western Ontario
Optimization and critical point methods for numerical characterization of real varieties [PDF]
-
Given a system of polynomial equations with real approximate coefficients, a fundamental unsolved problem is to give a stable numerical algorithm to characterize its real solution set (real variety). This means stably computing at least one real approximate point on each connected real solution component of the variety. There has been dramatic recent progress in this area, and I will describe some of this progress including our recent contributions. This is joint work with Fei Wang, Henry Wolkowicz and Wenyuan Wu.
The techniques described involve semi-definite programming, facial reduction and critical point methods. The critical points are real points on the variety that optimize the distance from a point or plane to the real solution components. Some comments about larger structured problems will be made.
- HRISTO SENDOV, The University of Western Ontario
Stronger Rolle's Theorem for Complex Polynomials [PDF]
-
Every Calculus student is familiar with the classical Rolle's theorem stating that if a real polynomial $p$ satisfies $p(-1) = p(1)$, then it has a critical point in $(-1, 1)$. In 1934, L. Tschakaloff strengthened this result by finding a minimal interval, contained in $(-1,1)$, that holds a critical point of every real polynomial with $p(-1) = p(1)$, up to a fixed degree. In 1936, he expressed a desire to find an analogue of his result for complex polynomials.
This talk will present the following Rolle's theorem for complex polynomials. If $p(z)$ is a complex polynomial of degree $n\geq 5$, satisfying $p(-i)=p(i)$, then there is at least one critical point of $p$ in the union $D[-c;r] \cup D[c;r]$ of two closed disks with centres $-c, c$ and radius $r$, where $$ c= \cot (2\pi/n),\;\;\; r=1/ \sin (2\pi/n). $$ If $n=3$, then the closed disk $D[0; 1/\sqrt{3}]$ has this property; and if $n=4$ then the union of the closed disks $D[-1/3; 2/3] \cup D[1/3; 2/3]$ has this property. In the last two cases, the domains are minimal, with respect to inclusion, having this property.
This theorem is stronger than any other known Rolle's Theorem for complex polynomials. In particular, it answers Tschakaloff's question for polynomials of degree $3$ and $4$.
This is a joint work with Blagovest Sendov from the Bulgarian Academy of Sciences.
- STEFAN SREMAC, University of Waterloo
A Semidefinite Programming Approach to D-Optimal Designs [PDF]
-
In statistics, a D-Optimal Design Matrix is used to construct efficient experiments. One such matrix is the circulant type D-Optimal Design Matrix, which is characterized by binary, circulant matrix variables satisfying the so called periodic autocorrelation constraint. The problem can easily be reduced from the space of $n\times n$ matrices to a combinatorial feasibility problem over $n$-vectors. It has become well known that combinatorial optimization problems may be `lifted' to semidefinite programs and in turn provide strong approximations. In this talk we present an approach to the D-Optimal Design problem utilizing semidefinite programming (SDP). We use both the first and second SDP liftings, then use facial reduction to break symmetries in the feasible set, and solve the reduced problem using the Douglas-Rachford (DR) method and the Alternating Direction Method of Multipliers (ADMM).
- MATTHIAS TAKOUDA, Laurentian University
On the Doubly Stochastic Matrix Completion Problem [PDF]
-
A doubly stochastic matrix is a square matrix where the sum of each row or column entries is 1. We explore the problem of reconstructing a doubly stochastic matrix using projections-based algorithms, commonly used to tackle feasibility problems.
- MOHAMED TAWHID, Thompson Rivers University
Genetic whale optimization algorithm for minimizing molecular potential energy function [PDF]
-
We propose a new hybrid algorithm by combining the whale optimization
algorithm and the genetic algorithm in order to minimize a simplified
model of the potential energy function of the molecule. The proposed
algorithm is called Accelerated Whale Optimization Algorithm (AWOA).
Also, we test the proposed algorithm with different molecule size with
up to 200 dimensions to minimize the potential energy function.
Moreover, we compared the proposed algorithm against 8 benchmark
algorithms, in order to verify the efficiency of it for solving
molecules potential energy function. The numerical experiment results
show that the proposed algorithm is a promising and efficient algorithm
and can obtain the global minimum or near global minimum of the
molecular energy function faster than the other comparative algorithms
in reasonable time. Moreover, we apply this algorithm on large scale
unconstrained optimization problems and nonlinear systems.
--------Joint Work with Ahmed F. Ali and Abdelmonem M. Ibrahim
- JÓZSEF VASS, York University
Minimization of the Inverse Problem Error between the Solutions of the KCE Equations and Experimental Data [PDF]
-
An ill-posed inverse problem is introduced for the determination of parameters that induce a given exact solution of the parametrized system of partial differential equations of Kinetic Capillary Electrophoresis (KCE). The problem is set up as the minimization of an error between the a priori given solution and the approximating solutions for various parameters — this is the target function of the optimization problem, with the parameters as its independent variables. The practical resolution of the problem hinges partly on the efficient generation of solutions to the PDE — the direct problem — which implies the efficiency of the target function evaluation. This optimization requires an efficient algorithm for processing high volumes of data. The problem is highly relevant to experiments carried out for the evaluation of pharmaceuticals via the estimation of kinetic rate constants of their binding to therapeutic targets.
- FEI WANG, University of Western Ontario
Polynomial optimization by SDP and facial reduction [PDF]
-
Recent breakthroughs have been made in the use of semidefinite programming and its application to real polynomial solving. Existing methods are computationally
expensive and have poorer accuracy on larger examples. In this talk we give a method to compute the generators of the real radical
for any given degree d. We combine the use of moment matrices and techniques from SDP optimization: facial reduction first
developed by Borwein and Wolkowicz. In use of the semidefinite moment matrices to compute the real radical, the maximum
rank property is very key, and with facial reduction, it can be guaranteed with very high accuracy. Our algorithm can be used
to test the real radical membership of a given polynomial. In a special situation, we can determine the real radical ideal in the
positive dimensional case
- SHAWN WANG, University of British Columbia
Generalized quadratic functions and epiconvergences [PDF]
-
We consider the epigraphical limit of a sequence of quadratic functions and categorize the results. We also explore the question of when a quadratic function is an Moreau envelope of a generalized quadratic.This is a joint work with Chayne Planiden.
- HENRY WOLKOWICZ, University of Waterloo
Low-Rank Matrix Completion (LRMC) using Nuclear Norm (NN) with Facial Reduction (FR) [PDF]
-
Minimization of the NN is often used as a surrogate, convex
relaxation, for solving LRMC problems.
The minimum NN problem can be solved as a trace minimization
semidefinite program (SDP). The SDP and its dual are regular
in the sense that they both satisfy strict feasibility.
FR has been successful in regularizing
many problems where strict feasibility fails, e.g., SDP relaxations
of discrete optimization problems such as QAP, GP,
as well as sensor network localization.
Here we take advantage of the structure at optimality for the NN
minimization and show that even though strict
feasibility holds, the FR framework can be successfully applied
to obtain a proper face that contains the optimal set. This can
dramatically reduce the size of the final NN problem while
guaranteeing a low-rank solution. We include numerical tests for
both exact and noisy cases.
(work with Shimeng Huang)
