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.

0
votes
0answers
15 views

Differences of Convex Optimization Problem [DC]

I am trying to solve a Difference of Convex Optimization Problem, I have $$\min_x f(x)-g(x)$$ $f(x), g(x)$ are quadratic functions with respect to $x$ with positive semi-definite terms. And $x$ is ...
0
votes
0answers
27 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
0answers
19 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
24 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
22 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 ...
5
votes
0answers
203 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
55 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
61 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
24 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
24 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
37 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
25 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
32 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
35 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
37 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
26 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
59 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
57 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
30 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
56 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
87 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
38 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
30 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
36 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
34 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
57 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 ...
4
votes
1answer
72 views

Least squares problem with a quadratic constraint

I have to minimize $e_1^2+e_2^2+e_3^2$ subject to $\mathbf{e}^\top \mathbf{A} \mathbf{e} + \mathbf{e}^\top \mathbf{b} +c =0$ with $\mathbf{e} = [e_1, e_2, e_3]^\top$ I know that matrix $\mathbf{A}...
0
votes
1answer
50 views

Sequential convex optimization vs Projected gradient descent

$$\textbf{1) Projected Gradient Descent} $$ $$\min_x \space f(x), \text{ subject to } x∈C $$ $$y_k+1=x_k−t_k∇f(x_k)$$ $$x_{k+1}=\operatorname*{argmin}_{x∈C}‖y_{k+1}−x‖$$ $$\textbf {2) Sequential ...
0
votes
2answers
51 views

Minimize the maximum magnitude of several quadratic functions

I have a collection of quadratic functions \begin{align} f_i(x) = \frac{1}{2}x^T Q_i x, \qquad i = 1,\dots,m, \end{align} where each $Q_i$ is an indefinite $n \times n$ matrix and $x \in \{-1,1\}^n$....
10
votes
3answers
363 views

Box-constrained orthogonal matrix

Given constants $\ell, u \in \mathbb{R}^{3 \times 3}$ and the following system of constraints in $P \in \mathbb{R}^{3 \times 3}$ $$ P^T P = I_{3 \times 3},\quad \ell_{ij} \leq P_{ij} \leq u_{ij}, $$ I ...
0
votes
0answers
41 views

Minimize linear system with non-convex regularization

I would like to solve the following regularized minimization problem iteratively $\underset{x}{\arg \min} ||Ax-b||_2^2 - \lambda R(|x|) $ where $x\in \mathbb{C}^n, b\in \mathbb{C}^m ,A \in \mathbb{C}...
1
vote
0answers
32 views

Can I get a closed form of this optimization problem?

$$\begin{array}{ll} & \underset{w \in \mathbb R^n}{\text{minimize}} & & \quad w^{H} w \\ & \text{subject to} & & w^{H} A w \geq 1 \\ & & & w^{H} B w \geq 1 \...
1
vote
1answer
58 views

Dual formulation of norm-constrained nonconvex problem

I'm currently trying to derive the dual problem of a nonconvex optimization problem. For context: I want to find an upper bound of the worst-case approximation error when approximating the elements of ...
1
vote
3answers
104 views

Minimum of the quartic $(x^2-1)^2+y^2$ using KKT conditions

Consider the following optimization problem. $$\begin{array}{ll} \text{minimize} & (x^2-1)^2+y^2\\ \text{subject to} & x^2 - 4 \le 0\\ & x + y \le 0\end{array}$$ Using KKT ...
0
votes
0answers
41 views

Optimal solution when the region is not convex

Consider the problem $$\min x^2+x+y+\cdots$$ $$s.t.\ x+y = 0$$ $$x^2-4=0$$ Write the KKT conditions and find the optimal solution. Attempt Suppose I did write the KKT conditions. For the optimal ...
0
votes
0answers
19 views

Concave quadratic function unbounded below

$$f(x) = y^\top x - \frac{1}{2} x^\top Q x$$ where $Q$ is both symmetric and positive definite is shown here to be bounded above. However, is the following proof correct for $f(x)$ being unbounded ...
1
vote
2answers
51 views

Why is $\max_{c^TBc=1}c^T a a^Tc =a^TB^{-1}a$?

I'm having some trouble in understanding the last step in this sequence of equalities: $$\max_{c}\frac{c^Taa^Tc}{c^TBc}=\max_{c^TBc=1}c^T a a^Tc =a^TB^{-1}a$$ I would think that the maximum would ...
1
vote
2answers
70 views

KKT optimality conditions in optimization exercise

Consider the following problem $$\max \Big(x_1-\frac{9}{4}\Big)^2+\big(x_2-2\big)^2$$ $$s.t.\quad x_2-x_1^2\ge0\\ x_1+x_2\le 6\\x_1,x_2\ge0$$ Write the KKT optimality conditions and verify ...
1
vote
0answers
43 views

Concavity of a simple objective function

I have a maximization problem with the following objective function $$ f= \log\left(\sum_{i=1}^nx_i\right)+\log\left(1-\sum_{i=1}^n\frac{x_i}{y_i}\right). $$ I would like to show that $f$ is concave ...
0
votes
1answer
37 views

Maximization of bilinear objective over convex body [closed]

Let $C \in \mathbb{R}^n$ be a convex compact body. Given the following optimization problem: $$\max_{x \in C\\ \left\| v \right\|_2 \leq 1} \left< x, v \right>$$ where $\left<\cdot,\cdot\...
1
vote
1answer
33 views

Projection onto the Set of Orthogonal Matrices - $ \mathcal{O}^{n} = \left\{ X \in \mathbb{R}^{n \times n} \mid {X}^{T} X = I \right\} $

Let $ \mathcal{O}^{n} $ be the set defined by $ \mathcal{O}^{n} = \left\{ X \in \mathbb{R}^{n \times n} \mid {X}^{T} X = I \right\} $, namely the set of Orthognal Matrices of size $ n \times n $. I ...
0
votes
1answer
35 views

Question on bilinear programming

Could someone please explain the meaning and applications of bilinear programming? I know about linear programming and the term 'bilinear' but I don't really understand the difference between linear, ...
0
votes
1answer
32 views

Gradient descent converges to critical points for non-convex functions

i was wondering, is there a way to show that gradient descent can converge only to critical points or escape to infinity in a non convex function, assuming that it is C2 and also, as a result, ...
0
votes
0answers
13 views

Demonstrate an equality between two equations. Convex and nonConvex problem

how can I demonstrate that solving this $min_{\alpha^{(1)},...,\alpha^{(k)},\beta_1,...,\beta_k}$ $L_T(\alpha^{(1)},...,\alpha^{(k)},\beta_1,...,\beta_k)\doteq \frac{1}{2m}*\sum_{i=1}^{m}(f_T(\...
3
votes
1answer
239 views

Minimize $ \mbox{tr} ( X^T A X ) + \lambda \mbox{tr} ( X^T B ) $ subject to $ X^T X = I $ - Linear Matrix Function with Norm Equality Constraint

We have the following optimization problem in tall matrix $X \in\mathbb R^{n \times k}$ $$\begin{array}{ll} \text{minimize} & \mbox{tr}(X^T A X) + \lambda \,\mbox{tr}(X^T B)\\ \text{subject to} &...
0
votes
0answers
30 views

Solution of non-convex smooth function with non-convex constraints

I am trying to solve the following minimization problem \begin{equation*} \begin{aligned} & \underset{x,y}{\text{minimize}} & & H(x,y) \\ & \text{subject to} & & f(x,y) \leq \...
1
vote
0answers
23 views

Convergence of non-convex optimization algorithms to an $\epsilon$-accurate solution

In non-convex optimization, the argument $x \in \mathbb R^p$ is said to obtian an $\epsilon$-accurate solution if $$\|\nabla f(x)\|^2\leq \epsilon$$ However, with the increase of the dimension $p$, ...