1
vote
0answers
36 views

Proving/deciding concavity of a function of two variables

I would like to formally prove that the function $f(x,y) = \frac{(c+1)e^{-x}(xe^{x+y}+y)}{(c+2)(e^{x+y}-1)+e^y} $ is concave ($ c>2$ is a constant, and both $x,\, y \in \mathbf{R_+}$). Plots of ...
0
votes
0answers
14 views

gradient descent - cost reduces and then increases

I am optimizing a function using Gradient Descent. The learning rate is fixed. First for few iterations the cost decreases after that it starts increases. What is the reason for this?
1
vote
0answers
26 views

When result of max of min problem is equal to min of max problem

Let's assume there are two functions $f(x)$ and $g(x)$. I want to know when the optimal $x$ of max of min of $f(x)$ and $g(x)$ is not equal to optimal $x$ of min of max of $\frac{1}{f(x)}$ and ...
1
vote
2answers
42 views

Is the set of all projection matrices a convex set?

The set $\phi=\{P| P^2=P\}$ contains all projection matrix. Is this set $\phi$ convex?
0
votes
0answers
31 views

Fenchel dual vs Lagrange dual

Consider the Fenchel dual and the Lagrangian dual. Are these duals equivalent? In other words, is using one of the these duals (say for solving an optimization), would give the same answer as using ...
0
votes
0answers
13 views

Quasiconcave condition for a power function

Let $f(x, y)= (ax^2+by^2)^n$ where $a, b, n$ are positive, $x, y\in \mathbb{R}$. What is the condition of $n$ so that $f(x, y)$ is a quasiconcave, and concave function? My idea is only calculate ...
2
votes
1answer
51 views

min : sum of L2 norm and squared-L2 norm.

Is there a closed-form solution of the following convex problem: $$\min_x \| x - u \| + C \| x - v \|^2$$ where $\| \cdot \|$ is the L2 norm.
0
votes
2answers
18 views

Solving for gradient of Frobenius norm term

Let's first define a couple of variables: $A,B,C \in \mathbb{R}^{m \times n}, D \in \mathbb{R}^{n \times n}$, and $\mu$ is a scalar. Say I have an ADMM sub-problem that looks like this: $\arg ...
0
votes
1answer
69 views

Convex optimization approximation

Consider the optimization problem $\mathcal{P}_0$ $$ \min_{x \in \mathbb{R}^2} \left\| x-p \right\|^2 $$ $$ \text{sub. to: } \ A x \leq b, \ \ x_1^2 + x_2^2 = 1 $$ where $p \in \mathbb{R}^2$ is a ...
0
votes
1answer
52 views

Model $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty $ into standard form

I need to solve the following convex optimization problem: $\min \frac{1}{2} \parallel Ax-B \parallel_2 + \lambda_1 \parallel Cx \parallel_1 + \lambda_2 \parallel Dx \parallel_\infty$ s.t $x ...
3
votes
0answers
43 views

Strong duality: When does the optimal primal variable coincide with the primal variable giving the dual function.

I'm considering the inequality-constrained optimization problem of finding $$ x^{\star} = \arg \min_{x} f(x) \;\; \text{s.t.} \;\; h(x) \le 0 $$ which is assumed to have a unique minimizer. The ...
1
vote
1answer
55 views

Matrix Maximization

I would like to solve the following optimization problem for a matrix $X$ which is symmetric and positive-semidefinite: $$ \mathrm{maximize} \, \, \, f(X) = \log \mathrm{det} X - k_1 \log(k_2 + a^T X ...
0
votes
1answer
30 views

Optimality conditions in convex programming

I'm reading about Zero-order conditions in Nonlinear Programming and the following confuses me (my questions are below the theory): Consider the set $\Gamma \subset E^{n+1} = \{(r,\textbf{x}): ...
1
vote
0answers
35 views

First order necessary conditions for nondifferentiable nonconvex minimization problem

I am interested in first order necessary conditions for the following minimization problem where the function $f$ is continuous, nondecreasing and concave, with $f(0)=0$, but not necessarily ...
2
votes
1answer
30 views

How to prevent a convex optimization from being unbounded?

I'm novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
0
votes
2answers
56 views

Regularization vs. Inequality Constraint

For what values of a regularization parameter $\alpha$, there is an equivalent inequality constraint in convex optimization? In particular, in the convex optimization problems below $$ \text{ Problem ...
0
votes
0answers
38 views

Finding a solution using the principle of maximum entropy?

I have set of linear constraints and would like to find an answer to its unknown variables, $p_i$'s. One of my options to find a solution for $p_i$'s using maximum entropy problem, $\max(\sum - p_i ...
0
votes
0answers
106 views

Maximize the maximum Eigenvalue under a diagonally constrained matrix

Suppose we have $N\times N$ Hermitian matrix $\mathbf{A}$ I want to find the real $N\times N$ diagonal matrix $\mathbf{D}$ that maximizes the sum of the maximum Eigenvalues : $\mathbf{D}=\arg\max ...
2
votes
2answers
94 views

How to maximize an entropy function?

I'm very novice in optimization and have a convex optimization function of form $\sum_{i,k} p_{k,i}*\log{p_{k,i}} $ to minimize with the following constraints: $\forall i, a_i = \sum_{k=1}^{m} b_k. ...
3
votes
1answer
70 views

Are all non-convex problems created equal?

The distinction between convex and non-convex problems is usually dubbed as the distinction between easy and hard problems. While in the convex case you are golden (local optima are global optima; ...
0
votes
1answer
27 views

Can $\min f'x$ s.t. $(a'x - b)^2 \le d $ be written as a SOCP?

It does not appear to be significantly different from the form listed here: http://en.wikipedia.org/wiki/Second-order_cone_programming with (in article notation) $i = {1}$, $ A = a$, and $b$, $d$ as ...
1
vote
1answer
63 views

Showing a function is concave

Given $F(\underline{x}) = Ax_1 + Bx_2 + \ln(a^2-(x_1^2+x^2_2))$ on $S=\{\underline{x}\in\mathbb{R}\mid x_1^2+x_2^2<a^2\}$ with $A,B,a\in\mathbb{R}$, show that $F$ is concave on $S$. Since we have ...
1
vote
2answers
70 views

Optimization of Product of Different Objective functions (Ex.: Maximize The Product of projections of a complex vector)

Suppose We have this optimization problem which is convex $\mathbf{x}={\arg}\: \underset{\mathbf{x}}\max f_{i}\left (\mathbf{x} \right )$ But the product of different objective function is ...
1
vote
1answer
36 views

Impact of constraints on convex optimization

Let me start by saying I know almost nothing about optimization so please bear with me. Basically, I am wondering whether it is possible to solve a problem with two constraints by solving the problem ...
0
votes
1answer
32 views

Finding the maximum/minimum of a homogeneous function on $R^n$

Suppose that $f:R^n\to R$ is homogeneous. Also, suppose that the $argmin_xf(x)$ is non-empty. Is it true that if there exist $x^*\in R^n$ such that $f(x^*)=0$, then $x^*=argmin_xf(x)$?
1
vote
1answer
65 views

KKT point of a constrained optimization problem

Min$_{x}~x$ Subject to $x \geq 0$ For this problem, is $(x^{*}, \lambda^{*})=$$(0,0)$ a KKT point ? My try : I formulated corresponding Lagrangian and tried to find out the KKT point(s). ...
0
votes
1answer
40 views

Convex functions -> quasi-convex functions -> … can we weaken the assumptions?

First of all let me say that I'm new to optimization. I realized that quasi-convex functions share with convex functions some nice properties, so I wonder if we can push the weakening a little ...
0
votes
1answer
71 views

Can SVD help to solve (inequality) constrained least squares problem?

Consider the following minimization problem: $$ ||Q u - h^{o} ||^{2} \to min \;\;\; s.t. \; u \geq 0 $$ where $Q$ is $m \times n$ matrix and $u$ is $n$-dimensional vector and $h^{0}$ is ...
0
votes
0answers
55 views

Expressing rank condition of a matrix in terms of its elements

Let $x \in \mathbb{R}^{n}$, define $X = xx^{T}$. I have an optimization problem with some linear constraints and few quadratic constraints, and I have to solve for $x$. Using $X$ as the unknown ...
3
votes
2answers
124 views

Singular Values of Matrix as Optimization Problem

Assume that $A$ is a positive semidefinite symmetric matrix. It is known that $$\max_{||y||\leq1} \quad y^TAy$$ Has an analytical solution which is the maximum eigenvalue of $A$. This isn't hard ...
0
votes
0answers
86 views

Calculation of the set for the polar tangent cone?

I have the following theorem in my book. Assume that $\tilde{x}$ is a local minimum from a minimization problem and that f(.) is differentible at $\tilde{x}$ Let $T_X(\tilde{x})$ be the tangent cone ...
-1
votes
2answers
37 views

Constraints in optimization; redundant hardness?

This is not an accurate mathematical problem, and rather a philosophical and ambitious question. As far as I know, unconstrained problems are easier than constrained problems; right? This is mostly ...
2
votes
2answers
170 views

What change of variables, if any, transforms this nonconvex problem into a convex one?

I'm looking for a convex reformulation, if any exists, of the following minimisation problem: Let $A$ be a symmetric, positive definite $n \times n$ matrix, and $b \in \mathbb{R}^n$. Minimise ...
1
vote
0answers
59 views

Some problems with a proof of the Farkas Lemma

The following is a proof of the Farkas Lemma that is creating me quite some problems. [I presented the all proof simply to point out the notation used by the author.] My problem is with the last part ...
1
vote
1answer
112 views

Minimizing a linear function on a strictly convex set.

All the theorems that I know considering the uniqueness of a solution to a minimization/maximization problem requires the strict convexity/strict concavity of the objective function. But consider the ...
0
votes
0answers
33 views

How fast Interior Point method can be when solving Quadratic Programming problems?

Given the following Quadratic Programming problem: $\;\;\;\;\; \min x^TQx+c^Tx $ s.t. $Ax=b$ $\;\;\;\;\; x\ge0$ where $x\in \mathbb{R}^n$, $Q \in \mathbb{R}^{n \times n}$ is a positive ...
1
vote
2answers
138 views

What is a convex optimisation problem? Objective function convex, domain convex or codomain convex?

My teacher in the course Mat-2.3139 did not want to answer this question because it would take too much time. So what does a convex optimisation problem actually mean? Convex objective function? ...
0
votes
1answer
73 views

(pseudo-/quasi-)convexitiy of ratio between quadratic and affine function

Let $X\subseteq\mathbb{R}^n$. I have the following function $f:X\rightarrow\mathbb{R}$: $$ f({\bf x})= \frac{c_1 + \sum_{i=1}^n a_ix_i +\sum_{i=1}^n b_ix_i^2}{c_2+\sum_{i=1}^n d_i x_i}\enspace.$$ All ...
2
votes
0answers
51 views

the objective function $\|F\|_F^2$ is quasiconvex in the optimization?why?

I have read a paper, but I can not understand one optimization thoroughly.Generally, Frobenius norm of one matrix, $\|F\|_F^2$, as the objective function is convex, so we can resolve it not using the ...
0
votes
1answer
114 views

How to get the closed form solution of a non-convex optimization problem?

I want to know if there is a closed form expression for the optimal objective function? How can I get it, if it does exist? Condition: $h,f\in \mathbb{C}^{N\times1}, \epsilon > 0 $. $\max \ \ ...
1
vote
1answer
65 views

A minimization problem

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ ...
1
vote
1answer
46 views

A minimization problem [duplicate]

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \|\frac{w}{x}\|,~w,u\in R^n$$ where $$\frac{w}{x}=(\frac{w_1}{x_1},\dots, \frac{w_n}{x_n})$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ Given $u$, $x$ and $\beta$, ...
0
votes
1answer
679 views

Optimization of a function of two variables.

Suppose we have to minimize a function $f(\mathbf x,\mathbf y)$ where $\mathbf x$, $\mathbf y$ are vectors in Euclidean space. The function is convex in $\mathbf y$ when $\mathbf x$ is kept constant ...
3
votes
1answer
108 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
2
votes
2answers
528 views

How can I solve Lagrange multiplier equation with multi constraints?

This site is really awesome. :) I hope that we can share our ideas through this site! I have an equation as below, $$ min \ \ w^HRw \ \ subject \ \ to \ \ w^HR_aw=J_a, \ w^HR_bw=J_b$$ If there is ...
1
vote
2answers
330 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
1answer
291 views

Positive semidefinite Matrix examples query

This might be really dumb question but I've just started dealing with such matrices. I would like to know why $$\begin{bmatrix} 0 & 1 \\ 1 & x \end{bmatrix}$$ cannot be a positive semidefinite ...
0
votes
1answer
54 views

KKT formulation

How to reformulate the following problem $$min \frac{1}{2} (x_1-a_1)^2+ \frac{1}{2} (x_2-a_2)^2$$ $$s.t. \mathbf{1}^Tx=1$$ $$ ||x||_2\leq2$$ as the following system of KKT conditions: $$(1 + ...
2
votes
0answers
69 views

Nonlinear optimization of constraint parameter - subdifferential?

Disclaimer: I discovered that the FAQ suggests to post research-level to mathoverflow instead of math.stackexchange. I "moved" the question accordingly, cp. post at mathoverflow. Sorry for the ...
1
vote
3answers
177 views

What is the dual of this optimization problem?

Consider the points $x_1, \ldots, x_N \in \mathbb{R}^n$, and a (locally bounded, convex) function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. I am looking for the dual of the following optimization ...