Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
0answers
52 views

What is the maximum value of $x^TAx$ subject to $x\in\{\pm1\}^n$?

Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum? $$\max_{x\in\{\pm1\}^n}x^T A x$$ My attempt: if all $a_{ij}\geq 0$, then \begin{equation} \...
1
vote
0answers
24 views

Is it possible to solve a system of equations for the phase of complex exponentials

I have a problem which I initially thought was simple but am not so sure anymore. I'd like to solve the following system of equations $$\alpha_1 = e^{j\mathbf{x}\theta_1} + e^{j\mathbf{x}\theta_2} + ...
0
votes
0answers
17 views

Linearization of two continuous variable [on hold]

i have two continuous variable, that i want to linearized them. in the below equations v(t) and g(t) are the continuous variables, and hd(t) is a parameter. i want to implement this equations in the ...
0
votes
0answers
27 views

Quadratic program reformulation maximum to minimum

I am newbie in optimization problem, I have the following optimization problem: $$\max \quad \frac{1}{2}x^THx - q^THx$$ $$\text{s.t.} \;\;l\leq x \leq u$$ where $H, q$ are known constants, and H is ...
0
votes
0answers
5 views

Numerically determining if a critical point is a saddle point in the presence of inequality constraints

I have a constrained optimization problem $$\min_{\mathbf{x}} f(\mathbf{x}) \quad \mathrm{s.t.}\quad g(\mathbf{x}) = \mathbf{0}, h(\mathbf{x}) \geq \mathbf{0}$$ and need to probe if a critical point $\...
3
votes
0answers
50 views

Maximize a sum of posynomials

I am dealing with an optimization problem where I have to maximize a sum of posynomials subject to affine constraints. The formulation of the problem (P) is as follows: $$\text{maximize } f(\...
0
votes
1answer
18 views

Analytical solution of a non convex function optimization

I think this is probably obvious but I can not find a formal proof or any other reference on this online. My question is - If there exists a finite number of local minima/maxima of a non-convex ...
0
votes
0answers
16 views

Minimax programming with constraints

I want to solve the following optimization problem: $min\;max_{\mathbf{R}}\,E(\mathbf{R},\mathbf{w}),\;s.t., \mathbf{w}_{l}\leq \mathbf{w}\leq \mathbf{w}_{u}\;and\;\mathbf{R}_{l}\leq \mathbf{R}\leq \...
0
votes
0answers
36 views

L1 constraint on vectors of a matrix

I am trying to solve below minimization problem (rank $k$ approximation of a matrix) which is somewhat sparse SVD \begin{equation*} \begin{aligned} & \underset{B,\Lambda}{\text{minimize}} & &...
1
vote
0answers
18 views

Application of frank wolfe algorithm to non smooth function

I have a function I want to maximize and which is non smooth and non concave/convex $$ F: [-1,1]^{n \times m} \to \mathbb{R}$$ I know that this function has the same points of non-differentiability ...
2
votes
0answers
29 views

Is it possible to “solve” iterative (convex/non-convex) optimization problems via learning (one-shot)?

I might be asking subjective question--and perhaps the answer may both be yes and no depending on the situation/problem definition. Nevertheless, I dare to ask. My questions are two fold: (1) Is it ...
0
votes
0answers
28 views

Trying to formulate optimization problems as a linear program (LP) or a quadratic program (QP)

I'm trying to formulate and determine the variables, objective, and constraints for the minimization problem $\min_\vec{x}f(\vec{x})$ for the following functions $f \in$ ($q,r,s,t$) as linear program (...
0
votes
1answer
32 views

Obvious claim about Kurdyka-Łojasiewicz inequality

Let $H$ be a hilbert space and $f$ a closed, proper, convex function from $H$ to $\mathbb{R}\cup\infty$. We write $[f < \mu]$ to denote the set $\{x\in H: f(x)<\mu\}$, $d$ for the hausdorff ...
0
votes
0answers
33 views

Constraint on product of matrices

I am trying to solve the below optimization problem \begin{equation*} \begin{aligned} & \underset{{A}, {B}, {\Lambda}}{\text{minimize }} & & \|X - AB\Lambda C^TD^T|_F^2 \\ & \text{...
0
votes
1answer
46 views

Diagonal constraint on product of matrices

I am trying to solve the below optimization problem \begin{equation*} \begin{aligned} & \underset{{A}, {B}, {\Lambda}}{\text{minimize }} & & \|X - AB\Lambda B^TA^T|_F^2 \\ & \text{...
0
votes
1answer
59 views

Proving convexity of the negative log complementary probability: $-\log\left(1 - \frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right)$

I am familiar with the convexity proof for \begin{align} f_i(x) &= -\log\left(p_i(x)\right) = -\log\left(\frac{\exp(x_i)}{ \sum_j \exp(x_j)}\right) = \log\left(\sum_j \exp(x_j)\right) -x_i. \end{...
0
votes
2answers
29 views

stopping criteria for mathematical optimisation: objective function target, rather than convergence

Researching stopping criteria for mathematical-optimisation algorithms, any libraries I look at (e.g. matlab, apache commons math) only have iteration limits and convergence criteria (e.g. convergence ...
1
vote
1answer
35 views

Solving an integer (boolean) constraint satisfaction problem

I have a 0-1 integer constraint satisfaction problem of the following form: find binary vectors $x = (x_1,\dots,x_m) \in \{0,1\}^m$ and $y = (y_1, \dots,y_n) \in \{0,1\}^n$ that satisfy the ...
0
votes
0answers
16 views

What algorithm/method can solve this nonconvex problem?

I want to solve this optimization program: $$ \min_{H, f, x_i, \lambda_i} \sum_{i=1}^N ||x_i - y_i||_2^2 $$ subject to $$ H x_i + A_i^T \lambda_i= -f \qquad i = 1...N $$ $$ A_i x_i = b_i \qquad \quad \...
0
votes
0answers
21 views

Can the duality gap be infinite?

Given a primal problem $$ \min_{x \in \mathbf{R}^2} \{ f(x)|g(x)=0 \} $$ that has a solution $f(x^*)=0$ (where $x^*$ is the value of x that minimizes $f$ such that $g(x)=0$), and given a dual ...
0
votes
1answer
50 views

Finding the optimal value for a dual problem in optimization

Consider the following optimization problem: \begin{align*} &\min_{x_1,x_2 \in \mathbb{R}}x_1x_2\\ &\text{Subject to } x_1^2 + x_2^2\le 1, x_1\ge 0, x_2 \ge 0\\ \end{align*} I have been ...
0
votes
0answers
13 views

How to prove that 0-1 NLP problem is NP-hard?

I have written a binary nonlinear programming problem: $\min_{a,Y}\sum_{i=1}^{N}\sum_{j=1}^{K}\Big[ a(1-x_{i,j})+x_{i,j}(e_1y_{i,j}+e2(1-y_{i,j})+e3y_{i,j}) \Big]$ s.t $ b(1-x_{i,j})+x_{i,j}(t_1y_{...
0
votes
0answers
31 views

Smooth but not convex

In Theorem 4.2. of the following lecture http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/Lecture_4_Scribe_Notes.final.pdf it is shown that when the objective function is smooth and not necessarily ...
1
vote
1answer
28 views

How to Reformulate an Image Constraint in the Dual of a Quadratic Program with Nonconvex Constraints?

I have the following nonconvex optimization problem, for which I want to formulate the dual: $\mathcal{P}:\underset{x}{\text{min}} \quad x^\top A x + b^\top x \\ \quad \ \ \text{s.t.} \quad x\in\{0,1\...
1
vote
0answers
25 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))...
0
votes
0answers
23 views

Construction of a linear programming given a solution

suppose given a solution $(x*, y*)$ of the nonlinear programming solution given below, I try to infer some conditions on the functions involved in the problem. The NLP I would like to solve has the ...
9
votes
2answers
443 views

Stable strict local minimum implies local convexity

Let $\bar{x}\in\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ be a $C^2$ function. We have known that if $\nabla f(\bar{x})=0$ and $\nabla^2f(\bar{x})>0$, i.e. $\nabla^2f(\bar{x})$ is ...
0
votes
1answer
58 views

Equivalence of two optimization problems

Consider the optimization problem A defined as $$ \max_{x,y} f(x,y)\text{ subject to } x+y\leq 0. $$ and the optimization problem $B$ defined as $$ \max_{x,y} f(x,y) - \lambda (x+y) $$ where $\lambda$ ...
1
vote
1answer
72 views

Find convex envelope from the non-convex function to prove globally optimal using branch-and-bound

Based on this reference branch-and-bound methods can obtain globally optimal solutions to nonlinear programming problems in which a non-convex function is to be minimized. I have a non-convex function ...
0
votes
0answers
27 views

Maximizing sum of two Rayleigh quotient

Consider the following optimization: \begin{equation} \max_{\boldsymbol{x}} \frac{\boldsymbol{x}^T \boldsymbol{A} \boldsymbol{x}}{\|\boldsymbol{x}\|^2} + \frac{\boldsymbol{x}^T \boldsymbol{B} \...
2
votes
0answers
28 views

On approximation of maximization of quadratic function over a convex set

Given a convex function $f : \mathbb{R}^n \to [0,\infty)$. Let $L = \left\lbrace x \in \mathbb{R}^n \mid f(x) \leq 1 \right\rbrace$ be it's sub-level set and suppose that $L$ is not empty as well as ...
0
votes
0answers
38 views

If the relative value of the most negative eigenvalue is small, can we view the quadratic program as convex?

Consider symmetric matrix $A \in \mathbb{R}^{n \times n}$ with $n-1$ negative eigenvalues and a positive one such that $\lambda_1 > \lambda_2> \dots > \lambda_n$, where $\lambda_n$ is the ...
0
votes
0answers
29 views

Local convergence results for L-BFGS on unconstrained nonconvex problems

I am looking for theoretical convergence results of limited memory BFGS. In the case of convex functions I have found this paper by Liu and Nocedal: On the limited memory BFGS method for large scale ...
0
votes
0answers
21 views

Is the gradient of $f(x,t)=xe^{t/x}$ w.r.t. ($x,t$) a Lipschitz continuous function?

Consider a function $f(x,t)=xe^{t/x}$ where $C \ge x,t\ge0$ with $C$ being a positive constant. Then, is the gradient $\Delta f$ a Lipschitz continuous function over the domain $[0,C]^2$?
0
votes
0answers
37 views

Maximization of convex quadratic functions over polyhedral regions

I am looking for example problems, where the objective function is a (simple) convex quadratic one where the constraints are polyhedral. I need examples where I can test specific algorithms I see. ...
1
vote
0answers
46 views

Box constrained optimization - BFGS

I have written my own code to implement BFGS method for unconstrained problem(FORTRAN). But now I want to convert the same code for solving box constrained optimization problems. How can I go about to ...
0
votes
1answer
31 views

Closed form for $\min_x \sum_k \|(a_k^Tx) / \|x\|^2 x -a_k \|^2$?

Given vectors $\boldsymbol{a}_k$ for $k=1,\dots,n$, and vector $\boldsymbol{x}$, all in $\mathbb{R}^d$. Does there exist a closed form solution for the following problem? \begin{equation} \boldsymbol{...
0
votes
0answers
40 views

Non-convex Constraint Satisfaction problem

I am not an expert on constrained optimization problems so I was wondering whether some of you could help me out. Let $h_{\mu}$ stand for : \begin{equation} h_{\mu} (\vec{X}) = \frac{1}{\sqrt{N}} \...
0
votes
1answer
37 views

Addition of two L-smooth function is also L-smooth?

Assume $f(x)$ has an L-Lipschitz continuous gradient say $L_1$ i.e there is a constant L>0 such that $$\|\nabla f(x) - \nabla f(y)\|_2 \le L\|x-y\|_2$$ for any $x,y$. Also $g(x)$ has an L-Lipschitz ...
0
votes
1answer
82 views

How to maximize the infinity norm over a convex region?

Consider the following optimization model $$\begin{array}{ll} \text{maximize} & \displaystyle\max_{i \in S} |x_{i}|\\ \text{subject to} & Q(x)+ \displaystyle\sum_{i \in S}|x_{i}| \leq m\end{...
0
votes
0answers
23 views

Can this bi-convex problem converge to a stationary point, if I alternatively optimize $x$ and $y$?

I have a bi-convex problem as follows. $$\min_{x,y}f(x,y)\\ s.t. g(x,y)\le 0,\\ h(x,y)=0,\\ x,y\in\mathbb{R}^n,$$where $f(x,y)$ is strongly convex in $x$ for fixed $y$ and strongly convex in $x$ for ...
0
votes
0answers
58 views

Is there any way to solve this optimization problem better than exhaustive search?

Here is the optimization problem: For the function $$ f(x_1,x_2;a_0,b_0)=\\\small\cases{\frac{1}{2}\left[x_1+x_2-x_1x_2+\left(\frac{-1+b_0(1-a_0)}{a_0}x_1+1\right)\left(\frac{-1+b_0(1-a_0)}{a_0}x_2+...
0
votes
1answer
35 views

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient

Does $f(x) = \frac{1}{2}x^TAx$ have an L-Lipschitz continuous gradient i.e there is a constant L>0 such that $$||\nabla f(x) - \nabla f(y)||_2 \le L||x-y||_2$$ for any $x,y$? I tried to derive it ...
0
votes
1answer
75 views

How to solve binary nonlinear programming problems?

I have written binary nonlinear programming problem: Now I want to solve this problem. My decision variables are $x_{i,j}, y_{i,j}$ and $z_{i,j}$. The other terms are constants. N=30 and K=4. I ...
2
votes
1answer
152 views

How to “convexify” a non-convex function?

In the following paper Mengyu Liu, Yuan Liu, Charge-then-Forward: Wireless Powered Communication for Multiuser Relay Networks, IEEE Transactions on Communications, 2018. there is a non-convex ...
1
vote
1answer
41 views

Optimizing to minimize the difference between two normalized vectors. What metric to use?

I am trying to minimize the difference between two normalized vectors of dimension $N$. Currently, I am using an $L_2$ normalized distance. Since the vectors are normalized, they should sit on some ...
1
vote
1answer
32 views

How to maximize the “k-largest” functions?

I want to solve the following optimization problem: $$\max_{x} ~sumk(A\vec{x})$$ $$s.t ~~~ x \geq 0$$ $$~~~~~~~ \sum_i x_i =1 \quad\forall i=1,...,N$$ in which, $A$ and $x$ are matrix and vector ...
0
votes
0answers
38 views

how I can linearize or simplify these complicated and non-linear constraints?

I have some constraints which are in the form $$ \dfrac{x_{1}-x_{2}+x_{3}+\cdots+x_{n}}{(x_{i}-x_{j})^{2}+\cdots+(x_{l}-x_{k})^{2}}+\cdots+\dfrac{x_{1}+x_{2}-x_{3}+\cdots+x_{n}}{(x_{j}-x_{i})^{2}+\...
0
votes
1answer
64 views

Study the convexity of Mean Squared Error with regularization

I want to study the convexity of the Mean Squared Error with regularization loss function. I am using an artificial neural network to compute the output. $$E(w) = MSE(w) = \frac{1}{\mid D \mid}\sum_{...
2
votes
1answer
67 views

Optimization problem where in the objective function the optimizer is divided by the square root of its L1 norm

I met an optimization problem as follow: $$\max_{\bf{x}} \frac{\bf{c}^T\bf{x}}{\sqrt{||\bf{x} ||_1}}, \\ s.t. \quad \bf{x}\in\{0,1\}^N \\ || \bf{x}||_1 \le M$$ where $\bf{x}$ is a non-zero binary ...