All Questions
480 questions with no upvoted or accepted answers
2
votes
0
answers
56
views
Whether $d_x(t) := \|P_t(x)-x\|_H$ is increasing in $t$ where $P_t:H \to H$ is the proximal operator of a convex function
Let $H$ be a Hilbert space (e.g Euclidean $\mathbb R^n$), and fix a proper convex function $f:H \to (-\infty,+\infty]$. Given any $t \ge 0$, let $P_t:H \to H$ be the proximal operator of $f$ at level $...
- 6,853
2
votes
0
answers
224
views
Minimisation and maximisation of the modulus of a complex valued function
I am new to complex analysis and I would be grateful to be guided in the following problem. We know that if $f$ is a function from $\Bbb C \to \Bbb R$, then $|f|$ is a function from from $\Bbb R^2 \to\...
- 826
2
votes
0
answers
73
views
Calculating the minimum distance between points using p norm
I’m trying to gain some insight about a problem I’ve been thinking about recently. I have managed to bring it about to the following form:
Find $\min\limits_{x} \sum\limits_{i=1}^{n} |x-x_{i}|^p$, ...
- 121
2
votes
1
answer
875
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
- 1,171
2
votes
0
answers
44
views
Convergent algorithm for minimizing nonconvex smooth function
Let $\Phi$ be the Gaussian CDF and for $\gamma\ge 0$ and $h>0$, define a loss function $\ell_h:\{\pm 1\} \times \mathbb R$ by
$$
\ell_{\gamma,h}(y,y') := \phi_{\gamma,h}(yy') := \Phi((yy'-\gamma)/h)...
- 6,853
2
votes
0
answers
79
views
Convex optimization over compact sets defined as Aumann set-valued integrals
Let $(X,P)$ be a probability measure space. Let $K$ be a convex compact subset of $\mathbb R^d$ and let $F:X \to 2^{K}$ be a set-valued map. Assume that $F$ is:
closed (i.e $F(x)$ is closed for ...
- 6,853
2
votes
1
answer
506
views
Effect of duplicated row on singular values and vectors
Let $\mathbf{A}$ be a $n\times n$ matrix with Singular Value Decomposition (SVD) $\mathbf{A}=\mathbf{U}\mathbf{S}\mathbf{V}$ and $\mathbf{a}_1$ be the first row of $\mathbf{A}$. What can we say about ...
- 287
2
votes
0
answers
152
views
A truncated Frobenius norm of a matrix is convex or not?
Given a positive integer $k$ and a matrix $X\in \mathbb{R}^{m\times n}$. A truncated frobenius norm of a matrix $X$ is defined by
$$\Vert X \Vert_{k,F} = \sqrt{\sum_{i=k+1}^{m} \sigma_i^2(X)},$$
where ...
- 143
2
votes
0
answers
56
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,772
2
votes
0
answers
37
views
Stochastic gradient descent in 'stronger' settings
I am minimzing a function $F(x) = \mathbb E(f(x,\Xi))$ where $\Xi$ is some random value, by a stochastic gradient descent that generates a random number $\xi$ from the distribution of $\Xi$ at each ...
- 686
2
votes
0
answers
162
views
Three-constraint homogeneous QCQP
Consider the homogeneous quadratically constrained quadratic program,
$$\min_{u^T u =1} u^T A_1 u$$
$$\textrm{subject to}\quad u^T A_2 u = 0,\quad u^T A_3 u = 0$$
This problem is particularly studied ...
- 1,203
2
votes
0
answers
47
views
Why not use global optimization algorithms like PSO to solve decentralized control problems?
I do not see many works that use global optimization algorithms to solve decentralized control problems. Here the decentralized control problem means some entries of the feedback matrix are ...
- 21
2
votes
0
answers
143
views
inverse of moment-generating function in terms of moments
Let $\{h_i\}$ be decreasing sequence of $n$ positive reals. Define distribution $p(X=h_i)\propto h_i$ and let $g(s)=E_X[e^{sX}]$ be the moment generating function. For instance, for $h=\{1,\frac{1}{4},...
- 2,442
2
votes
0
answers
159
views
Complexity of Quadratic Programming where the symmetric matrix Q is positive semidefinite only in the feasible directions
playing around with stuff for my dissertation, I derived a quadratic problem in the general form
\begin{equation}
\begin{aligned}
\min_{x} \quad & x^TQx + c^Tx \\
\textrm{s.t.} \quad & Ax \leq ...
- 21
2
votes
0
answers
102
views
How to prove/disprove this surface integral is convex?
This question is related to the following:
Convexity of volume in terms of a deformation - the context is summarized below for clarity.
In the setting of convex optimization, I am looking for a convex ...
- 51
2
votes
0
answers
141
views
Optimization of functionals with constraints
I have a minimization problem as follows:
$\min\left( \int_0^1\int_0^1\beta(t)\beta(s)G_1(t, s)dtds\right)^{1/2}+\left( \int_0^1\int_0^1\beta(t)\beta(s)G_2(t, s)dtds\right)^{1/2} $
$\texttt{s.t.}\;\;\;...
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
2
votes
0
answers
162
views
Lagrangian multipliers and a variant of Newton's method
A variant of Newton's method for solving the equality constrained problem
\begin{equation}
\begin{array}{ll}
\min &f(x) \\
\text{s.t.} & h(x) = 0
\end{array}
\end{equation}
is as follows:
\...
- 97
2
votes
0
answers
51
views
Conjugate of composition in Bochner spaces
Let $H$ be a separable Hilbert space (of non-zero dimension), let $(\Omega,\Sigma,\mu)$ be a finite measure space, and let $L^2(\mu;H)$ be the Bochner-space $\mu$-integrable $H$-valued functions. ...
2
votes
0
answers
166
views
How to solve a QCQP where constraints are balls?
I want to solve the following optimization problem in variables $\theta_1, \theta_2, \dots, \theta_K$
\begin{equation}
\begin{aligned}
& \underset{\theta}{\text{minimize}}
& & \...
2
votes
0
answers
110
views
A strong duality for convex functional optimization that admits Lipschitz continuity constraints?
Problem Statement
I am looking for formal proof---hopefully textbook material---of two items:
an analogue to Slater's condition [1] that obtains strong duality for optimization of convex functionals; ...
2
votes
0
answers
616
views
block diagonal approximation of (SPD) matrix
I am interested in approximating a symmetric matrix in a block diagonal form, i.e. compute just some entries of the matrix located in blocks around the diagonal. Are there any theoretical guarantees ...
- 335
2
votes
0
answers
43
views
Weak relaxation of a strongly lower semi-continuous functional
Let $F$ be a lower semicontinuous functional on a Banach space $X$, wrt its strong topology. Is there a known form for the relaxation (lower semicontinuous envelope) of $F$ with respect to the weak ...
- 5,405
2
votes
0
answers
40
views
Numerical algorithms for geodesically convex optimization
I want to solve a minimization problem of the form
$\inf_{x \in M} f(x)$
where $M$ is a Hadamard manifold and $f$ is geodesically convex (but not differentiable). Since I know that in general a ...
user85365
2
votes
0
answers
171
views
How to sweep the leaves efficiently?
A cleaner, denoted by $P$, aims to sweep $n\ge 1$ leaves that appear one by one in a courtyard modeled by a compact set $D\subset \mathbb R^2$. Denote by $x_0$ the initial position of $P$ and by $v>...
user128095
2
votes
0
answers
46
views
Notion of distance between linear programs
Consider the linear programming problem
\begin{align}
\max_{x}&~c^Tx \\~s.t.~~a^Tx &\leq B~,~0\leq x_i \le1
\end{align}
where $c$ and $a$ are $n \times 1$ given non-negative vectors. $B$ is a ...
- 1,421
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
- 21
2
votes
0
answers
45
views
First moments of uniform distribution on a curve from (0,0) to (1,1) in two-space
The curve $\Gamma$ in $\mathbb{R}^2$ is defined by a continuous and monotonically increasing function $f(x)\in\text{C}[0,1]$, where $f(0)=0$, $f(1)=1$.
Let $(X,Y)$ is jointly and uniformly ...
- 550
2
votes
0
answers
66
views
Proving the existence of a dual for an infinite linear program
I am concerned with proving the existence of the dual of an infinite linear program. In addition to the writings of Rockafellar, Luenberger, and Boyd & Vandenberghe on: subdifferentials, Legendre-...
- 121
2
votes
1
answer
307
views
Positivity of quadratic form minus linear form on the simplex
Let $a_{ij}$ be the elements of a $n$-dimensional covariance matrix. Can we prove the following?
$$ 1-\sum_{k=1}^n a_{ik} \lambda_k + \sum_{j=1}^n \sum_{k=1}^n \lambda_j a_{jk} \lambda_k > 0, \...
- 21
2
votes
0
answers
406
views
Pros and cons of using integer programming alone or combined integer and global optimization?
First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
2
votes
0
answers
93
views
Variational forms of non-convex functions
I am trying to understand what kind of variational forms exist for non-convex functions. Alternatively, are there conjugate forms which attain strong duality? For a non-convex function $f$, I am ...
- 41
2
votes
0
answers
52
views
Zeroth order method with near-optimal rate that works in practice?
I want to find a ZO (zeroth-order, i.e. no access to gradient) algorithm to minimize a strongly-convex deterministic objective (say, as a sum of smooth and nonsmooth proximable functions). I want such ...
- 41
2
votes
0
answers
47
views
A linear program where coordinate descent works pretty well
I am working with a polytope $P\subset \mathbb{R}_+^n$ with the property that there are at about $n!$ minimizers of $\sum_{i=1}^n x_i$, in the following sense:
Select any coordinate $j$ and set $...
- 21
2
votes
0
answers
111
views
Maximization of an integral functional over a closed convex set
I want to maximize $$F(w):=\sum_{1\le i,\:j\le2}\int\lambda^{\otimes2}({\rm d}(x,y))\left(w_i(x)f_j(x,y)\wedge w_j(y)f_i(y,x)\right)g_{ij}(x,y)$$ over the closed convex set $$S:=\left\{w\in{\mathcal L^...
- 167
2
votes
0
answers
98
views
State-of-the-Art algorithms for bilevel optimization
I want to numerically solve a bilevel optimization problem of the form
$$ \min_y f(y, \hat x(y)), \qquad \hat x(y) = \arg\min_x g(x, y) $$
(for simplicity assume that $\min_x g(x, y)$ exists and is ...
- 121
2
votes
2
answers
323
views
Reference request on computational schemes for $\inf_{x\in\Omega^n}\sup_{y\in\mathbb R^n}F(x,y)$
Let $\Omega\subset \mathbb R^d$ be compact, $\rho$ be a density function on $\Omega$ and $p_1,\ldots, p_n\in (0,1)$ be weights satisfying $\int_{\Omega}\rho(z)dz=1=\sum_{k=1}^n p_k$. We consider the ...
user128095
2
votes
0
answers
148
views
Generalization of Farkas' Lemma to Hermitian Matrices
I recently stumbled upon a well-known version of Farkas' Lemma which, roughly speaking, I would like to generalize from real vectors to hermitian matrices, as it seems promising for something else I ...
2
votes
0
answers
30
views
Find the point that minimizes the summation of L_\infty norms to three given points
Given three points $\omega_1$, $\omega_2$, $\omega_3 \in \mathbb{R}^d$, how can I find the point $\omega \in \mathbb{R}^d$ such that the summation of its $\ell_\infty$ distances to these three points ...
- 33
2
votes
0
answers
249
views
Continuity of a constrained parameterized convex optimization problem
Consider the parameterized optimization problem:
\begin{align}
\boldsymbol{s}(p)= &\arg \min_{ \boldsymbol{x}} \quad g( \boldsymbol{x})\\
\text{s.t. } & \boldsymbol{A}(p) \textbf{x} = \...
- 88
2
votes
0
answers
326
views
Lipschitz min implies Lipschitzian argmin?
Let $X$ be a Hilbert space, and suppose that $f:X^2\rightarrow \mathbb{R}$ is a Lipschitz, supercoercive, convex function such that (for every $y \in X$) the set
$$
\operatorname*{argmin}_{x\in X} f(x,...
- 5,405
2
votes
0
answers
131
views
Variant of Sion's minimax theorem
Sion's minimax theorem assumes that $f:X\times Y\to\mathbb{R}$ is being minimized w.r.t. $x$ and maximized w.r.t. $y$, where at least one of $X,Y$ is compact (additional (quasi)convexity and semi-...
- 6,541
2
votes
0
answers
75
views
Removing an unwanted constraint in proof of Fenchel-Rockafellar theorem
I am trying to prove the Fenchel-Rockafellar theorem, that
$$ \inf_x \left[ f(x) + g(Ax) \right] = - \inf_\beta \left[ f^\star(A^T \beta) + g^\star(-\beta) \right] $$
under the usual regularity ...
- 922
2
votes
0
answers
42
views
Dual representation of problems involving $f$-divergences
Studying some problems arising in decision-making under model uncertainty, I'm led to consider the following problems.
Let $\mathbb E_P$ and $\mathbb V_P$ denote the expectation and variance ...
- 6,853
2
votes
0
answers
283
views
Derivative with multiple summation operators
I have a defined utility function as Eq.(1), and I am seeking the minimized utility subjects to some constraints. The notation used is as following:
\linebreak
$V$ is the set of nodes, $v_i\in V$; $O$...
- 21
2
votes
0
answers
43
views
Partitioning $n$-space based on linear combinations
I'm trying to figure out the approximate number of areas the positive $n$-space will be divided into if we partition it as follows: we have $k$ linear functions $F_1$, $F_2$, ..., $F_k$ on $n$ ...
- 21
2
votes
0
answers
88
views
Gradient Descent with derivative constraints
tl;dr: I need bound results for the derivative of some big honking function.
tfa: I am trying to solve an optimization problem:
Find a parameter vector $\theta$ so that $\sum_x \log f(\theta, x) \...
- 245
2
votes
0
answers
46
views
increasing inter-class distances results in decreasing linear regression error
Let $\{\mathbf{x}_i, y_i \}$ be a set of binary-labeled samples ($\mathbf{x}_i \in \mathbb{R}^d, y_i \in \{a,b\}, a,b\in\mathbb{R}$). Let $\{ \mathbf{x}'_i, y_i \}$ be also such a set.
Define $\mathbf{...
- 183
2
votes
0
answers
2k
views
How to find a positive solution to an under-determined linear system (if such a solution exists)?
Like the title says, if an under-determined system of linear equations does have at least one positive solution, how to find it efficiently?
Suppose we have an under-determined system:
$$Ax = b$$
...
- 121
2
votes
0
answers
80
views
Making a polyhedron integral by selecting value for a specific co-ordinate of constraint vector
I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector ...
- 123