Questions tagged [non-convex-optimization]
A non-convex optimization problem is one where either the objective function is non-convex in a minimization problem (or non-concave in a maximization problem) or where the feasible region is not convex.
646
questions
-2
votes
0
answers
16
views
How this non-convex function innerly approximated as convex function???
The function is $ P= \left \| \hat{\mathbf{b}}^{H}\left ( \boldsymbol{\theta} \right )\mathbf{v} \right \|^{2}$ is non-convex.
And it has been approximated as follows:
$\left \| \hat{\mathbf{b}}^{H}...
0
votes
0
answers
4
views
Which divergence or measure is more suitable for graph clustering application using symmetric NMF
Symmetric NMF is a well know tool used for graph clustering applications.
Given a similarity matrix $X \in \mathcal{R}^{n\times n}$, symmetric NMF seek to factorize it into o production of the form $...
- 562
0
votes
0
answers
8
views
Outer approximation algorithm for non-convex integer nonlinear program
Consider a particular non-convex binary nonlinear problem of the following form:
$$ \min_X f(X) \\
\text{s.t. } X = (x_1, \ldots, x_L)^T \in \{0, 1\}^{L \times V } \\
\sum_{j=1}^V X_{ij} = \sum_{j=1}...
- 23
0
votes
0
answers
29
views
Try to analyze the given function is convex , non-convex, concave or non-concave?
The function is given as follows:
$\hat{\mathbf{b}}^{H}\left ( \boldsymbol{\theta} \right ) = \left ( \mathbf{b_{u}} + \mathbf{A_{u}}diag \left ( \mathbf{d_{u}} \right )\boldsymbol{\theta} \right ) \...
0
votes
0
answers
12
views
Example of empty Clarke subdifferential for function lipschitz over a closed convex set
If $f:\mathbb{R}^n\rightarrow\mathbb{R}\cup\{+\infty\}$ is a proper lower semi-continuous function that is Lipschitz continuous over $\text{dom}(f)$, where $\text{dom}(f):=\{x\in\mathbb{R}^n:f(x)<+\...
- 977
0
votes
0
answers
16
views
Convert non-convex optimization problems into convex optimization problems
Let A ∈ Rm×n, b ∈ Rm, c ∈ Rn, and d ∈ R. Prove that the nonconvex optimization problem
min
x∈Rn
∥Ax−b∥/(c⊤x +d)
subject to ∥x∥ ≤ 1;cTx+d > 0
is equivalent to the convex optimization problem
min (y∈...
- 1
2
votes
0
answers
80
views
Maximizing a function that contain a binomial coefficient term?
I am an electrical engineer and I am interested in maximizing an objective function that contains a binomial coefficient $\binom{n}{k}
= \frac{{n!}}{{\left( {n - k} \right)!k!}}$.
This is a follow up ...
2
votes
2
answers
160
views
How to reformulate or linearize the phrase "become redundant" or "not needed"?
I am an electrical engineer and currently I have to deal with an optimization problem with a very specific requirement:
$\begin{array}{*{20}{c}}
{\mathop {Min}\limits_x }&{f\left( x \right)}\\
{{...
0
votes
0
answers
66
views
How can DC programming be used for non-convex problem and why is this DC approach interesting? [closed]
I am an electrical engineering who is currently working on some optimization problems. From a little bit of literature review, I see that people praise this difference of convex optimization so much ...
0
votes
0
answers
24
views
how the constraint in equation 11b converted to equation 16 using sequential convex approximation method
the constraint that I want to transfer to convex shape
the inequality that used to transfer it with the sequential convex approximation method
- 1
1
vote
1
answer
37
views
Indicator function with multiple conditions in optimization
I have the following problem
$$\begin{align*}
& \min \ f(X) \newline
& X = \begin{cases}
1&; x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \newline
0&; \text{otherwise}.
\end{cases} \...
- 919
0
votes
1
answer
44
views
C-VaR approximation problem
In the paper written by Rockafellar about C-VaR (https://www.ise.ufl.edu/uryasev/files/2011/11/CVaR1_JOR.pdf), it is explained that this quantity can be approximated using the following problem (...
- 384
0
votes
0
answers
47
views
Proof of convergence for a heavy-ball adaptive step-size algorithm for non-convex functions
I am struggling with prooving convergence for an optimizer which uses adaptive step-size with heavy ball algorithm for convex and non-convex functions. In some literature, I could find a regret bound ...
- 21
0
votes
0
answers
37
views
How an indicator function can be approximated to a convex one?
I'm reviewing a paper on Schedule Optimization of Electric Vehicles, and they're using a function that I am not familiar with.
They're proposing as one of the objective functions to minimize:
$$ \eta^{...
3
votes
0
answers
82
views
Equivalence of Matrix Determinant Maximization Problems?
I am interested in an optimization problem involving parameters $\boldsymbol{\mu}$ and $\boldsymbol{\pi}$, both strictly positive stochastic vectors, and variable $n \times n$ matrix $W$:
\begin{...
- 182
3
votes
0
answers
17
views
Verification of the optimal solution of D.C. func on the boundary
Here comes my question, while solving the optimization problem
\begin{equation}
\begin{aligned}
\min\quad &x^TQx+q^Tx\\
& x=(x_1,x_2)^T\in\{(x_1,x_2)^T|x_1,x_2\geq0,x_1+x_2\leq x_0\}
\...
- 31
1
vote
1
answer
29
views
Minimizing sum of square of three distances under monotone transformation -- is the solution unique?
Let $f:[0,1]\to[0,1]$ be a differentiable, strictly increasing, and concave function with $f(0)=0,$ $f(1)=1$, and $f'(0)<\infty$. Does the function
$$
F(x,y) = \alpha (x-y)^2 + f^2(x) + \big(1-f(...
- 1,545
0
votes
0
answers
21
views
DC programming and saddle-point problems
Is there any relation between two?
DC programming problems $$\min_{x\in \mathbb{R}^n} f(x)-g(x),$$
where $f,g$ are both differentiable and convex functions.
Saddle-point programming aim to solve the ...
- 29
-1
votes
2
answers
79
views
given a binary point, design a quadratic which is minimized at that point!
Given a binary vector $x$, I need to efficiently construct a matrix $A$ such that $x$ is a global minimizer of $z^TAz$ over binary $z$'s. I need the diagonal elements to be positive.
- 384
0
votes
0
answers
24
views
How to transform optimization problems involving Bessel functions into convex optimization problems
I have a set of data points $\{ (x_i,y_i) \}$. The target is to find a curve that fits these points best, so I use the least square method:
$$
\min \sum_j^p| f(x_j)-y_j |^2 \\
\text{where } f(x) = a x ...
- 93
3
votes
1
answer
81
views
Dimension of the manifold of symmetric rank $r$ $n\times n$ matrices
I'm currently reading through the paper "Low-rank matrix completion by Riemannian
optimization—extended version" by Vandereycken, and in this paper the author states that the set
$\mathcal{M}...
- 53
1
vote
0
answers
54
views
Can we bound the derivative *of* a max using derivatives *at* the max?
Executive summary: If we can bound the derivatives of some multivariate function with respect a continuous variable, do we automatically get bounds on the behavior of the maximum of that function with ...
- 26.8k
1
vote
2
answers
130
views
Can I linearize this piecewise function so it can be used in an objective function for my LP optimization model?
Thanks for taking the time to read this.
I am looking for methods to linearize this piecewise function so that it can be added to an optimization function of a linear programming problem. I figured ...
- 13
0
votes
0
answers
39
views
What algorithm to use to optimize an expensive multi-variable function that is known to be dominated by a term depending only on the first few inputs?
I have an expensive-to-evaluate high-dimensional ($n=22$) objective function $f$ that I need to minimize numerically without taking derivatives. The function $f$ can be expressed as a sum of several ...
- 101
0
votes
0
answers
18
views
The dual of this SDP with a simple nonconvex constraint
In this problem we're optimizing over variables $X\in \text{PSD}_n$ and $Y\in\mathbb R^{d\times n}$ for some $d\le n$.
\begin{align}
&\text{Maximize}&&\langle A_0, Z\rangle\\
&\...
- 66
2
votes
0
answers
41
views
Point in polytope that is farthest from the origin
Given the tall matrix ${\bf A} \in {\Bbb R}^{n \times m}$ (where $n > m$) and the vector ${\bf b} \in {\Bbb R}^n$,
$$ \max_{{\bf x} \in {\Bbb R}^m} \, \left\| {\bf x} \right\|_2 \quad \text{subject ...
- 21
0
votes
0
answers
22
views
is a function which all stationary points are global minima prox-regular for some $\alpha$>0?
Let $f$ be a function which all stationary points are global minima. This type of functions are also known as invex. It means, there exits $\eta(x,y)$ such that $f(x)-f(y) \geq \zeta_{y}^{T}\eta(x,y)$ ...
4
votes
2
answers
109
views
Box-constrained QCQP
Let ${\bf A} \in \mathbb{R}^{n \times n}$ be a symmetric positive semidefinite (PSD) matrix, let ${\bf a} \in \mathbb{R}^n$ and let ${\bf B} \in \mathbb{R}^{n \times n}$ be a symmetric indefinite ...
- 2,118
0
votes
0
answers
32
views
convert constrained problem to unconstrained problem
I am currently working on a mathematical problem involving a non-convex function, $f: \mathbb{R}^{d} \rightarrow \mathbb{R}$. I have a constrained optimization problem that I would like to convert ...
- 1
0
votes
0
answers
36
views
Commercial solvers for non-convex optimization problems
Is there any recommended commercial non-convex solver for bilinear equality constraints? E.g.,
$$ \begin{aligned} x_1 x_2 &= x_3 \\ x_1 x_3 &= x_4 \\ &\vdots \\
x_1 x_n &= x_{n+1} \end{...
- 139
0
votes
0
answers
13
views
Handling non-convex feasible region (sigmoidal constraint) of a quadratic programming (Quadratic programming with sigmoidal constraint)
I have a quadratic programming problem with a non-convex feasible region. The problem is as follow
\begin{align}&\min_{x\in \mathbb{R}^M_+} x^T\pmb{A}x+\pmb{b}^Tx \\
&\; \text{s.t.} \quad 1^...
- 3,093
1
vote
0
answers
53
views
IPOPT solver cannot solve MPC problem in presence of non-convex objective
I am using the IPOPT solver to solve a multi-agent MPC problem. I notice that once I add quadratic collision avoidance cost - 100 * (||xi - xj||-radius)**2, where <...
0
votes
1
answer
53
views
Conditions for the squared gradient norm to be convex?
Let $f\colon \mathbb{R}^n \to \mathbb{R}$ be a differentiable function. I am looking for conditions under which the function $$x\mapsto \Vert\nabla f(x)\Vert^2$$ is convex.
It obviously hold if $f$ is ...
- 203
0
votes
1
answer
73
views
Solve eigenvalues-constrained optimization problem
I have the following constrained optimization problem
\begin{align}
\mathop{\text{min}}_\mathbf{Kp,Kd} && (\mathbf{Kd} - \mathbf{Kd_d})^2 + (\mathbf{Kp} - \mathbf{Kp_d})^2 \\
\text{subject to:}...
0
votes
0
answers
20
views
Dual characterization of minimal elements
I came across a concept in Boyd's book "Convex Optimization" that I'm struggling to grasp intuitively. The concept is stated as follows:
-If λ ≻K∗ 0 and x minimizes λ^T.z over z ∈ S, then x ...
4
votes
0
answers
81
views
Bounded gradient flow solutions without compact sublevel sets
A standard result in the theory of dynamical systems states that for a continuous system $(*)$ defined by $\dot{x}(t) = F(x)$, where $ F : \mathbb{R}^n \rightarrow \mathbb{R}^n $ locally Lipschitz, if ...
- 411
0
votes
0
answers
37
views
Lipschitz Hessian implies Lipschitz Hessian diagonal for non-convex function?
I am working on an optimization problem where the function $f$ is assumed to have Lipschitz-continuous gradients and Hessian
\begin{align}
\| \nabla^2 f(x) - \nabla^2f(y) \| \leq L_1 \| x -y \|, \...
- 11
1
vote
0
answers
49
views
Minimizing multivariate quartic function with L4-norm
I need to minimize a function $v(h)$ of the form
\begin{align}
v(h) = \langle g,h \rangle + \langle Ah, h \rangle + a \cdot \|h\|_4^4,
\end{align}
where $a \in \mathbb{R}$ is scalar, $g,h \in \mathbb{...
- 11
1
vote
0
answers
76
views
Majorization-Minimization with Unit Modulus Constraint
When we have an optimization problem (P1) of the form:
$$\text{(P1): }\min_{\boldsymbol{\phi}} f(\boldsymbol{\phi})\triangleq \boldsymbol{\phi}^{\dagger}\mathbf{Q}\boldsymbol{\phi}+\operatorname{Re}\...
- 21
3
votes
1
answer
69
views
Which probability mass function has the largest Euclidean norm?
Fix $n > 1$ and let $[n] := \{ 1, 2, \dots, n \}$. Which probability mass function (PMF) over $[n]$ has the largest $2$-norm?
Doodling for the cases $n \in \{2,3\}$ does suggest that
the maximal $...
- 21.5k
0
votes
0
answers
54
views
Two methods for solving bivariate optimization problems — how do they compare?
Consider the unconstrained non-convex optimization problem:
$$\min\limits_{x,y} f(x,y)$$
Suppose that for fixed $x$, the function $y \mapsto f(x,y)$ is convex. In this case, I believe there are two ...
- 1
1
vote
0
answers
52
views
NP-hardness of maximizing convex quadratic over linear inequality constraints
I have the following problem:
\begin{align}
\max_{x} \quad & \| x - \hat{x} \|_2^2 \\
\text{s.t.} \quad & x^\top a_i \leq b_i, \quad \forall i \in \{ 1,\ldots,N \},
\end{align}
where $x \in \...
- 723
1
vote
1
answer
64
views
Constrained non-convex QP
Consider the optimization problem:
$$
\begin{aligned}
\text{maximize}&\sum_{k=1}^9\left(x_k+\frac{k}{9}\right)^2\\
\text{subject to}&\begin{cases}\bar{x}\succeq \bar{0}\\\sum_{k=1}^9x_k=1.\end{...
- 79
0
votes
1
answer
85
views
Linear program plus sphere constraint
I have the following optimization problem:
\begin{align}
\min_{x} \quad & x^\top \hat{x} \\
\text{s.t.} \quad & x^\top a_i \leq 0, \quad \forall i \in \{ 1,\ldots,N \} \\
& \|x\|_2 = 1,
\...
- 723
0
votes
0
answers
13
views
Proving lower bounds on a minimization problem over positive semidefinite matrices with a bounded maximal rank
Given a minimization optimization problem of a linear target function over the set of positive semidefinite matrices of some fixed maximal rank, subject to affine constraints, what are (analytical) ...
- 101
2
votes
2
answers
86
views
Minimum of a non-convex function
Let,
\begin{align}
f(x,y)=\frac{1}{y^2}+\left(\frac{x}{y}+\sqrt{2-\frac{1-x^2}{y^2}}\right)^2,
\end{align}
where $0 \le x\le 1$, $-1 \le y \le0$, $x^2 + y^2 \le 1$ and $x^2 + 2y^2 \ge 1$. What is the $...
- 81
0
votes
1
answer
21
views
Convexity of set of mixture distributions
A set of mixture distributions $Q$ is defined as,
$Q = \{f | f(.) = \sum_{i=1}^{k} q_{i} f_{i}(.) \}$,
where each $f_{i}$ is a probability density and $\sum_{i=1}^{k} q_{i}=1$ and $q_{i}>0$.
Is set ...
- 53
0
votes
1
answer
81
views
Optimal solution to the primal and the Lagrangian dual when there is duality gap
Consider the primal problem $\max_{x\in\mathcal{X}} f(x)$ subject to $g(x)\leq 1$ and its Lagrangian dual $\min_{\lambda\geq 0}\max_{x\in\mathcal{X}}\{f(x)+\lambda(1-g(x)\}$ with no convexity ...
- 377
0
votes
0
answers
25
views
When do equality and inequality constrained problems agree?
Let $f:\mathbb{R}^d\to\mathbb{R}$ and $h:\mathbb{R}^d\to\mathbb{R}$. Consider a solution $x^\ast$ to the equality constrained optimisation problem
$$ x^\ast \in \underset{x}{\text{argmin}} f(x) \quad\...
- 388
0
votes
2
answers
178
views
Indicator constraint in optimization
I am trying to formulate an optimization problem with the following constraint:
$y = 1$ if $x \le c$ and $y = 0$ if $x > c$ which is basically an indicator function $y = 1[x \le c]$ and $c$ would ...
- 25