Questions tagged [nonconvex]
The nonconvex tag has no usage guidance.
43
questions
2
votes
1
answer
111
views
How to formulate a convex expression to minimize the difference between Frobenius norm of a positive semidefinite matrix and a positive value
So what I am trying to do is to minimize the distance between the Frobenius norm of a PSD matrix and a real positive value, which can be formulated as
$$\min \left|\|\textbf{P}\|_F - J\right|^2$$
...
- 21
1
vote
0
answers
63
views
min(f(x)) is convex or concave based on type of f(x)
i have f(x) that is concave function. My question is g=min(f(x)) is concave or convex? And max(g) is concave or convex? there is a theorem for this?
- 11
2
votes
0
answers
34
views
Calculating a submanifold of minimal values
I have a (numerical, noisy) function $f$ that I'd like to optimize (in 3 < dimension < 10).
The function $f$ has a fairly prominent valley/ravine structure due to physical symmetries present in ...
2
votes
0
answers
122
views
Efficient solver of a Integer programming
I am solving an Integer programming using MATLAB, yet the efficiency is low.
Here is the problem:
Suppose $v$ is a $N \times 1$ vector. For $v_i \in v$, $v_i \in \{0,1\}$.
$D$ is a 0-1 matrix, which ...
- 21
2
votes
0
answers
99
views
Black box optimization
I have a simulation which gives a scalar result depending on the choice of some continuous design variables. I am trying to minimize the output of the simulation. As a first step, I want to study the ...
- 21
2
votes
0
answers
62
views
Convergence of Truncated Newton for non-convex Hessian
I was wondering if anyone could enlighten me about the convergence properties of the truncated newton method in case of a non-positive definite hessian $\nabla^2 f = H$. From the Book 'Numerical ...
2
votes
0
answers
185
views
Proving convexity of Frobenius norm and correlation function formulations of an optimization problem
I have been working on formulating my requirements in the form of an optimization problem in a multi-output regression setting.
Firstly, I would like to make the variables I used in the problem and ...
- 21
1
vote
0
answers
90
views
Ramp least squares estimation
With some given $s$ value, let
\begin{equation}
\begin{aligned}
h(\beta)&=\min(\sum_{i=1}^n(Y_i - X_i\beta)^2, s)\\
&=\sum_{i=1}^n(Y_i - X_i\beta)^2-\max(0, \sum_{i=1}^n(Y_i - X_i\beta)...
- 173
1
vote
0
answers
97
views
Best optimizer for unconnstrained non-convex nonlinear least-square optimization problem?
I am looking for a very good optimizer to the following problem:
$$\min_{P,\Theta}\lVert APD(\Theta)P^{-1} -B \rVert_F$$
where $A,B \in \mathbb{R}^{n\times m}$, $P \in \mathbb{R}^{m\times m}$, $D\in \...
6
votes
1
answer
185
views
How to solve a 4th order nonnegative LASSO problem?
I need to solve the following 4th order nonnegative LASSO problem:
$$
\min_{x \geq 0} \quad || |Ax|^2 - b ||^2 + \lambda ||x||_1
$$
where $|\cdot|^2$ denotes element-wise squared. $A$ is small size (e....
- 163
0
votes
0
answers
968
views
Solving a non-convex optimization problem using fmincon
I am trying to solve a non-convex optimization problem using fmincon().
At each iteration, I am iteratively looking for the optimum value and when the termination ...
- 33
0
votes
0
answers
54
views
Minimizing the ratio of two specific non negative quadratic convex functions
$F$ is $m\times m$ diagonal, with real non negative elements
$D$ is $n \times m$ complex
$P$ is $n \times 1$ complex
$A$ is $m \times 1$ complex.
Minimize $\Gamma(A)$, with respect to $A$.
$$\...
- 141
2
votes
1
answer
141
views
Is there an optimization scheme/algorithm that converges, for this non-convex scenario but with some special properties
I have a smooth function $f(x) = \frac{g(x)}{h(x)}$ that is the ratio of two smooth convex functions $g(x)$ and $h(x)$. It is known that $f(x)$ has a global minimum, achieved at the unique point $x_0$....
- 141
2
votes
1
answer
2k
views
A robust algorithm to sort a non-convex polygon vertices
Let v_{0},...,v_{N-1} be N points in a Cartesian xy plane defining the vertices of closed polygon (i.e. v_{N} = v_{0}).
Let P_{0}...
- 139
1
vote
0
answers
52
views
Efficient numerical optimization of an "almost separable" function
I have come across an optimization problem with the following objective function:
$$f(x_0,y_0,z_0,x_1,y_1,z_1,...,x_N,y_N,z_N) = \sum_{i=0}^N f_i(x_i,y_i,z_i, \alpha(x_{i+1}-x_i) + \beta(y_{i+1}-y_i))...
- 41
1
vote
1
answer
439
views
Piecewise-Linear Quadratic Optimization for an "Almost Convex" Problem
I have a 7-14 dimensional piecewise linear cost function I'd like to minimize with two quadratic terms of the form:
$$
f(X) = X^tCX + d \sum_i |x_i-x^*_i|^2 + \sum_i P_i(x_i-x^0_i)
$$
$$ \sum_i x_i ...
- 113
0
votes
1
answer
69
views
reduced system: primal-dual interior point method for nonconvex constrained problem
When solving a reduced KKT system of a nonlinear (and nonconvex) constrained program after eliminating slack and dual variables, how do we actually take the next step in a primal-dual method?
For ...
- 325
0
votes
1
answer
86
views
Why can't we discretize continuous domains in distributed non-convex constraint optimization problems?
Consider a non-convex distributed optimization problem.
We have $X$ = a set of $n$ decision variables: $x_i$ where $i=1..n$ and $x_i \in R$, the set of Reals.
We have $F$ = a set of $m$ constraint ...
1
vote
0
answers
103
views
Minimizing the products of variables
My problem
Maximize
$$\min_{i} \{\ c_i \cdot \prod_{j \in A(i)} {x_{j}} \prod_{j \in B(i)} {y_{j}} \} $$
Subject to
\begin{align}
&\sum_{j \in C(k)} x_{j} = 1,\ \forall k \\
&l \leq x_{j}...
- 111
1
vote
0
answers
287
views
Constrained optimization: Stationary point vs. Nash point
1s question: definition of stationary point for constrained optimization
As far as I know, a stationary point of a constrained optimization problem is a stationary point of the Lagrangian (that has ...
- 515
4
votes
1
answer
173
views
Optimization of non-smooth, non-convex, locally Lipschitz functions of type exp(-abs(x))
What would be the numerical method of choice to find minima in a non-smooth, non-convex, locally Lipschitz function $f: \mathbb{R}^n\rightarrow \mathbb{R}$.
The function $f$ is mostly smooth but ...
- 193
2
votes
0
answers
89
views
Global optimization with known distributions of some variables
I'm solving simple single-objective multidimensional global optimization problem using various stochastic algorithms like Monte-Carlo, GA and other evolutionary approaches. The task is formulated as ...
- 21
1
vote
0
answers
166
views
preconditioning LBFGS?
I want to minimize an energy of the form
$$V_1(\mathbf{x}) + V_2(\mathbf{x})$$
where $V_1$ is much stiffer than $V_2$. When I try to use LBFGS, convergence is extremely slow, as the solution ...
- 263
6
votes
1
answer
665
views
Global convergence in trust region algorithm
I was reading about TR methods and there are some terms, which are confusing for me.
It says, method is globaly convergent. What does it really mean? Converges to global minima, or converges for ...
- 109
1
vote
0
answers
277
views
Numerical solution of non-linear advection equation other than inviscid burgers
I am solving a non-linear advection equation of the form $u_t + f(u)_x = 0$ where $f(u)$ is a complicated function of $u$. I am solving this equation using a first order fully implicit scheme (...
- 23
24
votes
5
answers
9k
views
Why should non-convexity be a problem in optimization?
I was very surprised when I started to read something about non-convex optimization in general and I saw statements like this:
Many practical problems of importance are non-convex, and most
non-...
- 907
1
vote
0
answers
152
views
Minimization of the sum of convex function and non-linear non convex function
I'm trying to minimize the unconstrained scalar sum of a quadratic convex function (to which a convex optimizer is readily applied) and a non-linear and non-convex function which is differentiable.
...
- 141
4
votes
2
answers
4k
views
Subgradients of non-convex functions
In these notes (section 2.3), it is stated that:
A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$
...
- 515
3
votes
1
answer
274
views
Symmetric nonnegative matrix factorization
Suppose $A\in\mathbb{R}_+^{n\times n}$ is symmetric. I would like to factorize $A\approx UU^\top$ by solving
$$
\begin{array}{rl}
\min_U & \sum_{ij} \left(A_{ij}\ln\frac{A_{ij}}{[UU^\top]_{ij}}+[...
- 1,341
2
votes
0
answers
103
views
non convex, non linear optimization involving matrix differential equation solution
I'm trying to develop an inferential procedure for a multivariate dependent Markov process. Basically, the procedure could be considered as a non linear regression, with a known dependence structure ...
- 21
2
votes
1
answer
325
views
Minimal surface finite differences problem - Matlab assemble
I face to the following problem:
$$(1+u_x^2)u_{yy} - 2u_xu_yu_{xy} + (1+u_y^2)u_{xx}=0.$$ Problem needs to be discretized and assembled.
Does anybody know how to proceed in Matlab?
2
votes
0
answers
362
views
Finite difference scheme for solving nonlinear least-squares problem
I am dealing with following problem:
$$
\min_{u,\gamma}\Bigg\{ \frac{1}{1000} \iint_{S_2} {\gamma (x,y)^2 dxdy} + \iint_{S_2} {[u(x,y) - u_0 (x,y)]^2 dxdy} + \iint_{S_2} {[\Delta u(x,y) - \gamma (...
4
votes
2
answers
229
views
non-convex quadratic with only one quadratic constraint?
I have a non-convex optimization problem in the form:
\begin{align}
\min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr
\text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq \frac{1}{n-...
- 221
4
votes
2
answers
676
views
Finding a global minimum of non-convex quasi-smooth function that is costly to evaluate
I have a bounded non-convex function in 10-dimensional space. The function is quasi-smooth, you can imagine a histogram, here is an illustration, it just shows the idea and not related to my ...
- 41
5
votes
2
answers
228
views
Is there guaranteed global solver for such an eigenvalue problem?
The original nonlinear optimization problem I have is as follows:
For constant symmetric matrices $A=A^T, B_i=B_i^T(\forall i\in\mathbb{N}) \in \mathbb{R}^{n\times n}, \text{rank}(A)=n,$
$$\arg\min\...
- 729
0
votes
2
answers
147
views
Nonconvex Optimization
Consider the following optimization problem:
$\text{max}_{p} \quad ||p||^2 \\
s.t: x\geq 0\\
p\in D$
where $D$ is a convex set. Is this problem $\mathcal{NP}$-hard?
- 575
3
votes
2
answers
632
views
Affect of approximating a non-differentiable function on optimisation of minimisation
I am looking at a problem of constrained minimization, where the function to be minimized contains the Heaviside function, and as such is not twice continuously differentiable.
My question is what ...
- 173
0
votes
1
answer
738
views
Non convex optimization
I have the following Max Min optimization problem that appears to be non convex.
link
where t p c are my variables and all others are constants. I took the eigen values of the hermetian part of the ...
- 13
6
votes
2
answers
3k
views
linear independence constraint qualification: what to do when they don't hold?
I want to solve a general nonlinear constrained optimization problem
$$\min_q\ f(q)\quad \textrm{s.t.}\quad g_i(q) = 0,\ h_j(q) \geq 0.$$
The problem is that while the equality constraints $g_i(q)$ ...
- 263
2
votes
3
answers
2k
views
Global optimisation with discontinuous objective
I'm looking at a global minimisation problem on the $n$-sphere ($n$ of the order 10--50) but with a complete swine of an objective --- it is (effectively) a black box; it is piecewise smooth but with ...
- 590
1
vote
0
answers
20
views
Reduction for NP-hardness [duplicate]
Consider the following optimization problem:
\begin{align}
\text{Min}_{i\neq j\neq s\neq t} |x_i x_j-x_sx_t|\\
s.t: Ax=b\\
x\geq 0;
\end{align}
This problem can be seen as an instance of non convex ...
- 575
3
votes
2
answers
750
views
NP-Completeness
Consider an instance of non-convexoptimization problem:
It seems that this problem is NP-complete. How can I find a suitable reduction for this?
- 575
7
votes
1
answer
258
views
Algorithm for dealing with medium-size non-convex QCQP
I have the following problem in $x \in \mathbb C^{205}$
$$\displaystyle\min_{x}x^HAx$$
subject to the following constraints
$$x^HBx = 1$$
$$x^HC_ix = 0$$
for $i \in \{0,1,\dots,203\}$, where $A$ ...
- 1,320