All Questions
Tagged with nonlinear-optimization convex-optimization
183 questions
1
vote
0
answers
29
views
Change in active constraints when perturbing the objective of a QP
Suppose I have a quadratic program (with positive semidefinite cost matrix) with affine (polytopic) constraints. It is known that the solution to this is piecewise affine, with the ``pieces'' defined ...
- 11
1
vote
0
answers
45
views
Inequality Involving Concave Monotonic Function
Assume that $ f: \mathbb{R} \to \mathbb{R}_+ $ is a concave, non-decreasing and positive function. Let $\mathbb{X}$ be a finite set consisting of $ 0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$. ...
0
votes
0
answers
72
views
Minimizing the Spectral Norm of the Hadamard Product of a Quadratic Form Using CVX
I am trying to use CVX to minimize the spectral norm of the Hadamard product of two matrices, one of which is in quadratic form. Specifically, I am trying to minimize $\|{\bf A} \odot {\bf XX}^H\|_2$, ...
- 43
2
votes
1
answer
170
views
Equivalence of minimizing trace and determinant over matrix quadratic form in multivariate regression
Consider the multivariate regression model
$$Y = XB + E$$
where $Y$ is $n \times p$ and corresponds to the dependent variables, $X$ is $n \times k$ and corresponds to the independent variables, $B$ is ...
0
votes
1
answer
74
views
Clarification about this optimisation problem
Good morning everybody. First of all, I apologise to ask here the same question I asked on MSE three days ago, but I am in fact re-asking since I obtained no relevant advice. Perhaps I will hear some ...
- 149
0
votes
1
answer
104
views
Optimality condition for strongly convex function under sparsity constraint
Let $f: \mathbb{R}^p \to \mathbb{R}$ be a $2s$-sparse strongly smooth, $2s$-sparse strongly convex and twice differentiable function. In other words, there exists positive constants $\alpha, L >0$ ...
- 399
1
vote
1
answer
309
views
Numerical estimation of partial derivatives of convolved functions when closed forms do not exist
Summary: Some peak functions are convolutions which may not have a closed form solution. A classical example can that of a Voigt which is a convolution of a Lorentzian and a Gaussian, followed by ...
- 879
0
votes
0
answers
129
views
Primal optimal attained implies dual optimal attained
Given some optimization problem
$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$
we can find the dual problem
$$\max_{\lambda\in\mathbb{R}^m} g(...
- 275
1
vote
1
answer
176
views
Maximization of $\ell^2$-norm
Consider for $r,c>0$ the set
$$X_{r,c}=\{x \in \ell^1(\mathbb{N}) \mid \|x\|_1=r,\, \forall i \in \mathbb{N}: |x_i|<c\}.$$
Then I can show that $\inf_{x \in X_{r,c}} \|x\|_2 = 0.$
But is it ...
- 11
1
vote
1
answer
187
views
Bound the distance between two vectors on the probability simplex
Let $a,b$ be two vectors with strictly positive elements and $\delta = 1 - \frac{\langle a,b \rangle}{\|a\|\|b\|}$. Bound the following optimization problem as a function of $\delta$
$$\sup_{x>0} \...
- 135
1
vote
1
answer
84
views
optimization over moving domains
Let $A, B$ be Banach spaces, and for any $a\in A$, $B_a\in B$ is a measurable subset. Consider the following optimization problem:
$$L(a)=\inf_{b\in B_a}\ell(b),$$
where $\ell(b)$ is a infinite-times ...
- 87
1
vote
0
answers
70
views
LICQ vs MFCQ who is stronger [closed]
I want to ask you which constraint is stronger: MFCQ or LICQ.
- 11
2
votes
1
answer
175
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
- 43
0
votes
0
answers
55
views
Relationship of optimal solutions between the total function and the sub function
This is an unconstrained convex optimization problem. Let $\mathcal{N}=\left\{1,\ldots,n\right\}$, $2\leq n<\infty$. Suppose there are many strongly convex functions $f_i(x)$, where $x\in\mathbb{R}^...
- 1
1
vote
1
answer
209
views
Does the value function of a quadratic program stay convex when adding constraints?
I am interested in the value function of a quadratic program of the form
$$
v(y)=\min_x \frac{1}{2} x^\top Q(y) x,
$$
subject to a linear equality constraint
$$
E(y)x=d(y),
$$
and a linear inequality ...
- 379
0
votes
2
answers
531
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
- 21
0
votes
0
answers
57
views
optimization of mixed linear and infinity norm
I have the following optimization problem:
Given a complex sequence $H_i$, $1 \leq i\leq N$. Find a complex sequence $G_i$ that minimizes:
$$ \lambda\cdot\max_i { |H_i\cdot G_i - 1|^2 } + \sum_i |G_i|^...
- 101
1
vote
2
answers
121
views
How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?
I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...
- 175
2
votes
0
answers
178
views
Can we get the exact solution of large-scale quadratic programming problems (quadratic objective, linear inequality constraints) using KKT condition?
Crossposted at Computational Science SE
Consider a quadratic programming problem with the following format:
$$
\text{min} Q(x) = c^Tx+\frac{1}{2}x^TDx \\
$$
$$
\text{s.t.} Ax\leq b, \\
x\geq 0
$$
...
- 21
3
votes
1
answer
189
views
Sensitivity of the solution of QP with respect to parameters
Given a quadratic program,
$$\begin{array}{ll} \text{minimize} & \displaystyle \frac12 x^TAx + b^Tx \\ \text{subject to} & Cx \le d \end{array}$$
Suppose $A \succ 0$, so the program strongly ...
- 33
1
vote
1
answer
130
views
Analytic expression for the min value of $g(t):= \sqrt{(t-1)^2 + a^2}+ b|t|$ subject to $|t-1| \le c$
Disclaimer. Not sure this is MO-level but would really appreciate some help with this. Thanks in advance. Moved from SE.
Let $a,b,c \ge 0$, and define a function $g:\mathbb R \to \mathbb R$ by $g(t) :=...
- 6,853
1
vote
1
answer
169
views
Best projection on non-convex discrete set with two constraints
I want to compute the projection of a vector $\left( x\right) _{1\leq
i,j\leq n}\in \lbrack 0,1]^{n\times n}$ on the following discrete set
$$
S=\left\{ x\in \{0,1\}^{n\times n}:x_{i,j}+x_{j,i}\leq 1;\...
- 47
1
vote
1
answer
1k
views
Is a Lipschitz continuous gradient equivalent to this condition?
I know if a function $f: \mathbb{R}^n \to \mathbb{R}$ is $L$-smooth, i.e. its gradient $\nabla f$ is $L$-Lipschitz continuous, then it satisfies the following inequality for any $x, x_0 \in \mathbb{R}^...
- 163
5
votes
3
answers
496
views
Eigenvectors that are tensor products?
Consider a fixed $N\times N$ positive definite symmetric matrix $A$.
Assume $N=d^r$ for some $d,r\geq 1$.
I wonder if one can find a closed formula for the maximizer/maximum of the function $$f(x):=\...
- 2,135
1
vote
0
answers
97
views
How to solve the following optimization problem?
Let $G=(V,E)$ be a connected network with $|V|=n$. Consider the following optimization problem
I'm trying to know under which conditions the following minimization problem has solution :
$${\sum _{i=1}...
- 47
2
votes
0
answers
64
views
Question about (stochastic parallel-gradient descent) SPGD and (simultaneous perturbation stochastic approximation) SPSA [closed]
I wonder if someone could shed some light on this. I'm curious if stochastic parallel-gradient descent and simultaneous perturbation stochastic approximation refer to the same optimization techniques.
- 21
1
vote
0
answers
41
views
Fitting a non-periodic sum of periodic time series
The problems is as follows: you have $n$ points $(x_1,y_1),\dots,(x_n,y_n)$ and you want to fit the following equation to the data points:
$$y=\theta_1\cos(\theta_2 x+\theta_3) + \theta_4\cos(\theta_5 ...
- 3,098
0
votes
0
answers
75
views
Maximize entropy under Kulback-Leibler divergence
I posed this question in math.stackexchange.com, but have not received any answer. I would like to try my luck here.
In this question, it is to solve
\begin{align}
\max_p &-\int dy\,p(y)\ln p(y) \\...
- 2,239
1
vote
0
answers
202
views
Matrix relative condition number
I've been working on some distributed optimization problems and faced a bit of a challenge with the following question.
Given $A_1, A_2, .., A_m \in M_n({\mathbb{R})} $ symmetric positive definite ...
- 11
0
votes
0
answers
156
views
Optimal solution of complex optimization problem
Let $Q(x)=a(x)e^{jb(x)}$ be a complex function of $x$. We want to approximate this function with $R(x)=\alpha e^{jx\beta}$ such that
\begin{align}
\text{arg}\min_{\alpha,\beta} \int_{-\frac{A}{2}}^{\...
- 287
1
vote
1
answer
50
views
Point of tangency is an optimal point for a monotone, quasi-concave function
Given $U : \mathbb{R^2} \to \mathbb{R}$ is monotone and quasi-concave, consider the following problem :
$$\max_{(x,y) \ \in \ \mathbb{R}^2}[U(x,y)] \text{ subject to } p_1 x + p_2 y \leq M ; \ (p_1, ...
4
votes
1
answer
163
views
Gap to fill in the Aubin–Ekeland proof of the mountain-pass theorem
Working through the proof of the mountain-pass theorem given in Applied Nonlinear Analysis by Aubin & Ekeland, at what seems to be a critical point of the proof (the top of page 274) they refer to ...
- 193
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
1
vote
2
answers
270
views
Can we substitute this KKT condition into this optimization problem to reformulate the optimization problem?
Suppose I have the following optimization problem
$$ \min\limits_{\mathbf{x},\mathbf{y}} f(\mathbf{x},\mathbf{y}) \tag{1} $$
It is already known that the target function $f$ is continuous and ...
- 73
1
vote
0
answers
98
views
Solution of a simple optimization problem
Let $\mathbf{U}_1$ and $\mathbf{U}_2$ be two arbitrary unitary matrices and $\mathbf{D}$ be a diagonal matrix. What is the solution of the following optimization problem?
\begin{align}
\min_{\mathbf{...
- 287
0
votes
0
answers
124
views
The best unitary matrices that approximate a matrix product
Let $\mathbf{A}$ be an arbitrary $N\times N$ complex matrix. Moreover, $\mathcal{U}_1$ and $\mathcal{U}_2$ are distinct subsets of all unitary matrices. Suppose the matrices $\mathbf{U}_1$ and $\...
- 287
4
votes
1
answer
336
views
Which set of functions admits the existence of the minimizer?
Let $a,b \in \mathbb R$ and consider the functional $J$ on $X$:
$$J[u] = \int_0^1 \left( (u'(x))^2 -a)^2 + b \ln (1+ u^2(x))\right) dx$$
Providing reasons specify if the $\inf J$ over $X$ is attained ...
- 159
1
vote
2
answers
278
views
Optimization of a integral function
I have a function $h(y,x_1,x_2,\ldots,x_n)$. It is known that the minimum value of $h$ for any $y$ is attained when $x_1 = x_n$ and $x_2 = x_3 = \cdots = x_{n-1}$. Now consider the following function
\...
- 211
3
votes
0
answers
91
views
What is the name for this type of optimization problem?
As we all know, a classic optimization problem can be represented in the following way:
Given a function $f: A \to \mathbb{R}$, find an element $x_0 \in A$ such that $f(x_0) \le f(x)$ for all $x \in ...
- 141
4
votes
5
answers
2k
views
Reference request: importance of Lipschitz continuity
I see that Lipschitz continuity is a common assumption used in optimisation, statistics, machine learning, etc.
Could you point me in the direction of some literature that discusses why Lipschitz ...
- 161
0
votes
0
answers
109
views
How to find a set given its support function
Let $\mathcal{U}$ be a convex and compact set. Its support function is defined as $\delta^*(v|\mathcal{U})=\sup_{u\in \mathcal{U}} v^T u$. Assume that we are given the support function $\delta^*(v|\...
- 53
3
votes
1
answer
227
views
Relaxations for the spectral norm maximization problem
Optimizing the spectral norm of some positive semidefinite matrix $A(x) \in S^{n}$, w.r.t. a list of variables $x \in \mathbb{R}^d$ and semidefinite constraints is, in general, a nonconvex problem (...
- 33
0
votes
0
answers
92
views
Optimization problem where the objective function returns a function instead of a real number
As we all know, a classic optimization problem can be represented in the following way:
Given: a function $f: A \rightarrow \mathbb{R}$ from some set $A$ to the real numbers
Sought: an element $x_0 ∈ ...
- 141
1
vote
0
answers
59
views
Minimizing square roots with the consecutive ones property
Let $A=[a_{ik}]$ be a matrix with the consecutive ones property in each column, i.e. each column consists of a single consecutive block of $1$'s (with zeros everywhere else). Is there anything at all ...
- 4,049
1
vote
0
answers
140
views
Factorization of argmax
We consider a function $f(s_{1:p}, a_{1:p})$, where $p>1$ is an integer, $s_{1:p}$ denotes $(s_1,\ldots,s_p)^\top \in R^p$, and $a_{1:p}$ denotes $(a_1,\ldots,a_p)^\top \in R^p$.
Question: What is ...
- 1,127
1
vote
1
answer
211
views
Does coercivity/supercoercivity conjugates?
According to Wikipedia, a function $f: \mathbb{R}^n \to \mathbb{R} \cup \{-\infty, +\infty\}$ is called coercive if,
$$f(x) \to +\infty \text{ as } \|x\| \to +\infty$$
and it is super-coercive if
$$\...
- 125
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
3
votes
1
answer
158
views
Numerical scheme for convex optimization
Given $(e_n)_{-N\le n\le N}\in\mathbb R^{2N+1}$ and $-1<x<1$, solve
\begin{eqnarray}
&&\max_{(q_n)_{-N\le n\le N}\in\mathbb R^{2N+1}_+}~ \sum_{n=-N}^N (e_n-\log(q_n))q_n \\
\mbox{s.t.} &...
user128095
0
votes
0
answers
43
views
Breaking up an infinite-dimensional optimization problem into a sequence of finite-dimensional problems
My question is a bit vague. I have an infinite-dimensional convex optimization problem and I can solve constrained versions of the problem by restricting the domain of the objective function to a ...
user85365