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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

2
votes
2answers
27 views

Question about solving of the equation using derivatives.

What I want to do is to find a certain x,y that minimizes a function f(x,y) which is given below. $x, y \in R$, (R is real set) $f(x,y) = x^{2}+y^{2}$ Yes, the answer is (x,y) = (0,0). But, assume ...
3
votes
4answers
58 views

How to minimize this sum of squares?

Given $a, b > 0$ and $c \in \mathbb R$, how can I find the $x, y$ that minimize the following quadratic function? $$f (x,y) := (x-y+c)^2 + ax^2 +by^2 $$
0
votes
0answers
56 views

Solving underdetermined linear system using least squares

As in case of linear overdetermined system of equations, we can prove that the cost function i.e. the least square function is convex. But in linear underdetermined system, we know that there exist ...
2
votes
0answers
25 views

Is there an equivalence between subgradient and stochastic gradient?

Consider the optimization problem $$\min_x \; f(x) := \sum_{i=1}^m f_i(x).$$ A subgradient method at each iteration takes a subgradeint descent step $$ x^+ = x - \alpha g, \quad g\in \partial f(x)...
0
votes
0answers
14 views

Proximal operator of an $\ell_\infty$ norm with a constraint [duplicate]

Dear Convex Optimization Experts, My question is related to this post: The Proximal Operator of the $ {L}_{\infty} $ (Infinity Norm), but not really same, I think, as I have a constraint. Apologies ...
0
votes
1answer
22 views

Prox Operator of $ {L}_{1} $ Norm with Linear Equality Constraint (Sum of Elements)

How could one solve the following problem: $$ \operatorname{Prox}_{\gamma f \left( \cdot \right)} \left( y \right) = \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \gamma {\left\| x \...
0
votes
1answer
46 views

Example of convex function which is differentiable, but not twice differentiable?

Are there convex functions for which hessian is not defined, but the gradient is defined everywhere? I was looking at projected gradient descent, as well as Newton's method for solving optimization ...
0
votes
1answer
37 views

How to increase the accuracy of optimal point obtained by ADMM?

What is the best algorithm to polish the optimal point obtained by the ADMM method for a constrained quadratic program? I've already studied the primal-dual method. Although it can obtain a solution ...
0
votes
1answer
64 views

Solve $\min_{\mathbf{x},\mathbf{R}}\left\|\mathbf{y}-\mathbf{x}\right\|_{\mathbf{R}}^2$ s.t. $\mathbf{A}\mathbf{x}=\mathbf{0}$; $\mathbf{R}\succeq0$

Dear optimization experts, Do you have a suggestion how to solve this problem? \begin{align} \min_{\mathbf{x}, \mathbf{R}, \mathbf{\lambda}} f(\mathbf{x}, \mathbf{R}) &= \left\| \mathbf{y} - \...
0
votes
3answers
45 views

Why do we need sub-gradient methods for non-differentiable functions?

Why do we need sub-gradient methods for non-differentiable functions? Consider optimizing $f(x) = max_{i} (a_{i}^Tx+b_{i})$. Clearly this is non-differentiable at multiple points, and the ...
0
votes
1answer
34 views

Prove $f(y) = \min \{|y-x|, x\in S\}$ is convex when $S = \{x\in\mathbb{R}^2|ax_1 + bx_2 = c\}$

Let $S$ be a convex non empty set in $\mathbb{R}^n$. Let $f:\mathbb{R}^n\to \mathbb{R}$ be a function defined by $$f(y) = \min \{|y-x|, x\in S\}$$ This function is convex. Prove this ...
0
votes
0answers
28 views

Primal-dual correspondence in the simplex method

I am trying to understand the dual simplex method and after reading a few different books I got stuck when trying to understand the primal variable to dual constraint correspondence. A lot of sources ...
0
votes
0answers
46 views

Proximal operator of multiplication of two matrices

I have two matrices $A$ and $B$ of size $n \times n$. I am trying to find the proximal operator of the below functions i.e. assume one of the matrices constant while finding the $L1$ proximal operator ...
0
votes
1answer
24 views

Is it guaranteed that a linear programming problem has a unique solution?

Given a generic linear programming problem i.e. minimize $\hat C^T \hat X$ subject to $\hat A \hat X <= \hat B$ and $\hat X >= 0$ Is it guaranteed (mathematically speaking) that a solution ...
1
vote
3answers
71 views

If $\Omega\subset\mathbb{R}^n$ is convex and $f$ is differentiable, then $f(x)-f(y)\geq f'(y)(x-y),\;\forall \;x,y\in \Omega$

Let $\Omega$ be a convex set in $\Bbb{R}^n$. We say that that $f:\Omega\to \Bbb{R}$ is convex if $$f(tx+(1-t)y)\leq tf(x)+(1-t)f(y),\;\forall\;0\leq t\leq 1,\;\&\;\forall\;x,y\in \Omega.$$ I want ...
0
votes
2answers
33 views

Show that the set of global minimizers of $f$ is a convex set. If there can be only one global minimizer, how?

I'm studying non linear optimization and there's the following exercise: Suppose that $f$ is a convex function. Show that the set of global minimizers of $f$ is a convex set. A point $x^*$ is a ...
0
votes
1answer
35 views

Are the standard rules for determining convexity of composition of 2 functions all encompassing?

I was going through Boyd's book and saw the following rules, where $f(x)=h(g(x))$ f is convex if h is convex, h̃ is nondecreasing, and g is convex f is convex if h is convex, h̃ is nonincreasing, and ...
0
votes
0answers
30 views

Optimization with box constraints

I have the following convex optimization problem minimize f(x) subject to box constraints x ∈ [a, b]. I have already solved ...
1
vote
0answers
31 views

Dual problem of unconstrained linear least squares

The following seemingly simple question is confusing the heck out of me: Take the least squares regression problem (for $X \in \mathbb{R}^{n×p}$ and $y \in \mathbb{R}^n$): $$\min_{\beta \in \...
1
vote
1answer
33 views

Caracterization of strongly convex

A differentiable $f$ function is stronglyconvex if and only if $$f(t x_1+ (1-t) x_2) \le t f(x_1) + (1-t) f(x_2) - \frac{t (1-t)m}{2}\Vert x_1-x_2\rVert^2,~t \in [0,1] \quad(1)$$ Other ...
1
vote
1answer
17 views

Is it always true that $f=g+h$ is not convex when $g$ is convex and $h$ is neither convex or concave?

Suppose we have the function $$f=\frac{x^2}{2} + 10y^2 - 10xy$$ where $$g=\frac{x^2}{2} + 10y^2$$ and $$h= - 10xy$$. In this case $f$ is a sum of a convex function $g$ and a function $h$ which is ...
0
votes
0answers
32 views

Optimization problem over integration sublevel set in $\mathbb{R}^n$

Suppose $\phi:\mathbb R^n\to\mathbb R^n$ is a fixed smooth vector field; if it's useful, we can assume $\|\phi(x)\|_2\leq1$ for all $x\in\mathbb R^n$. Consider the following optimization problem ...
2
votes
1answer
25 views

why the proximal operator is well defined?

Let $h$ be a convex function. We define the proximal operator as $$prox_h(x)=argmin_uh(u)+\frac{1}{2}\|u-x\|^2$$ why is this operator well defined? We must see that exist that minimum and is unique. ...
1
vote
0answers
29 views

Equivalence of two optimization problem?

problem 1: \begin{aligned} & \underset{}{\text{maximize}} & & -b^T\mu-(1/4)\sum^{n}_{i=1}(c_i+a_i^{T}\mu-v_i)^2/v_i \\ & \text{subject to} && v \succeq 0. \end{aligned} ...
0
votes
1answer
23 views

Uniqueness of the maximum of a multi-dimensional function

I have a somewhat complicated function of $M+1$ variables, which looks as follows. $$f (x_0, x_1, x_2, \dots, x_M) = \sum_{i=1}^{N_A} \ln \left[1 - \text{erf}\left(x_0 + \sum_{j=1}^M a_{ij} x_j\right)...
0
votes
0answers
26 views

Relative Interior of the relative interior of a convex set

Let $X \subseteq R^n$ be a convex set. I'm curious whether the relative interior of the relative interior of X is equal to the relative interior of X, i.e, using the notation in this Wikipedia article,...
0
votes
0answers
18 views

Undefined values in subgradient optimization

I saw subgradient optimization of a function $f$ described as the following algorithm: start with any $\lambda^{(0)} \ge 0$ then repeat the following for $i = 1, 2, \dots$ compute a subgradient $g$ ...
1
vote
1answer
48 views

What is a simple upper bound for $\exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right)$ given $x \ge0$ and $\delta \in (0, 1)$?

Question For $x \ge 0$ and small $\delta \in (0, 1)$, what is a "simple" good upper bound for $$u(x,\delta) := \exp\left(-\frac{1}{2}(x-(2\log(1/\delta)^{1/2}))^2\right), $$ that doesn't involve $x$ ...
0
votes
0answers
21 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 ...
1
vote
1answer
21 views

Unbounded Values in Lagrangian Relaxation

I'm trying to learn about Lagrangian relaxation from Korte and Vygen (2018) and found a case where I don't know how to proceed. When optimizing $\max \{c^\top x : A'x \le b', x \in Q\}$ the book ...
0
votes
1answer
97 views

Solve Matrix Least Squares (Frobenius Norm) Problem with Lower Triangular Matrix Constraint

Let $\mathbf{A} \in \mathbb{R}^{N \times N}$, $\mathbf{X} \in \mathbb{R}^{N \times M}$, and $\mathbf{B} \in \mathbb{R}^{M \times N}$. We intend to solve for $\mathbf{X}$ by solving the following ...
1
vote
1answer
39 views

Optimization under constraints - unique solution or not

Say we have a problem such as minimize $f(x)$ such that $h(x)=0$ and $g(x) \leq0$. Let the minimum achieved under these constraints be $f(x^*) = p^*$. My question is: If $f(x)$ is convex, are $p^*$ ...
1
vote
0answers
36 views

Characterization of the convex hull in terms of dot product

I am doing some work with Newton Polytopes and I need something of this style: Given $v_1,\dots,v_n\in \mathbb{R}^n$ we have $$\text{conv}(v_1,\dots v_n)=\{v\in \mathbb{R}^n\mid \min_{i=1,\...
3
votes
2answers
60 views

Optimization problem: Objective function not differentiable

Minimize the following problem: $$\min_{x\in \mathbb{R}^n}\max_{i=1 \dots m}\{\langle\nabla f_i({\overline{x}}),x-\overline{x}\rangle\}+\sigma\|x-\overline{x}\|^2 \tag 1,$$ with $F:\mathbb{R}^n\to \...
0
votes
3answers
55 views

How to maximize a piecewise linear convex function $f: \mathbb{R}^n\to \mathbb{R}$?

How to maximize a piecewise linear convex function $f: \mathbb{R}^n\to \mathbb{R}$? I can see that there are many references for minimizing a piecewise linear convex function but not maximizing such a ...
0
votes
0answers
47 views

Quasi Newton Methods Convergence

I am using quasi-newton(BFGS) method with wolfe line search conditions to find the optimum for a convex function. At times, when I run the code, it tends to get stuck at a point which is not optimum. ...
2
votes
1answer
79 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 ...
0
votes
0answers
23 views

optimization problem using softmax and cross-entropy function

I am encountering a problem concerning finding the optimal weights using cross-entropy loss function in the context of passive-aggressive algorithms. Let the following optimization problem:(eq1) $$J(...
0
votes
1answer
32 views

How to find the following condition on the domain of conjugate function of negative geometric mean?

The conjugate function of the negative geometric mean ($f(x)=-(\prod_{i}^{n} x_i)^{1/n}$ over $R^n_{++}$) is given as follows $$f^*(y)=\sup_{x}\left(x^Ty+(\prod_{i}^{n} x_i)^{1/n}\right).$$ I know ...
0
votes
0answers
43 views

Primal Dual Interior Point convergence.

I have developed a Primal Dual Interior point algorithm to solve linear inequality constrained Quadratic problems. But sometimes it cannot reduce the residual so as to satisfy the stop criteria. I ...
2
votes
2answers
57 views

Find the two points with the maximum distance in a sector of a unit disc

Find two points $P,Q$ in a given sector which has an natural angle $= \frac{\pi}{3}$ of a unit disc such that they attain the maximum possible distance between them. Prove where they should be ...
0
votes
1answer
30 views

Gradient of Moreau Envelope

For a convex function $f: \mathbb{R} \to \mathbb{R}$, define the Moreau envelope $$f_{\mu}(x) = \inf_y \left\{ f(y) + \frac{1}{2\mu} (x-y)^2 \right\}$$ and the proximal operator $$\text{prox}_{\mu ...
-3
votes
1answer
38 views

For which $\lambda$ is $\prod_{i=1}^{k} x_i^\lambda$ concave? [closed]

As stated in the question, for which $\lambda$ is $\prod_{i=1}^{k} x_i^\lambda$ concave, $x_i\in (0,1)$ and $\sum_{i}x_i=1$? Thanks
0
votes
1answer
31 views

Strictly concave with Non negativity constraint

Say I intend to maximize a real-valued, strictly concave, twice-differentiable function: \begin{equation} f:\mathbb{R^n} \rightarrow \mathbb{R} \end{equation} If the problem is unconstrained, that ...
1
vote
0answers
69 views

An optimization problem over a bi-linear function

An optimization is to be carried out over the following function: $$f(x_1,x_2;a,b)=\frac{1}{2}\left[x_1+x_2-x_1x_2+c(x_1;a,b)c(x_2;a,b)\right]$$ where $$c(x;a,b)=\sum_{i=0}^n\left[\left(\sum_{j=0}^i\...
0
votes
0answers
43 views

Quadratic Optimization problem with sqrt term

I am trying to solve a mean-variance (quadratic optimization) problem with a non-linear market impact cost term in there. This is the problem I am trying to solve $$\max \alpha a - \gamma x^T \Sigma ...
0
votes
1answer
35 views

Getting the final solution for the subgradient of function $F(x) := \max \{0, \frac1{2}(x^2 - 1)\}$

I have to find the subgradients of the following function. $$F(x) := \max \left\{0, \frac1{2}(x^2 - 1)\right\}$$ Analytically I can see subdifferentials at $x=-1$ is $\nabla f(-1) \in [-1 ,0] $ and ...
0
votes
0answers
42 views

Augumented Lagrangian Method

How should one choose the initial value of lambda(multiplier) while using Augumented Lagrangian Method for constrained optimization?
0
votes
1answer
28 views

Understanding minimization of jointly convex functions

I am trying to understand partial minimization of jointly convex function in one variable. The theorem which I am facing difficulties to understand is expressed as follows. Let $f: R^n \times R^m \...
0
votes
1answer
55 views

Sum of convex functions

Let $f: R \rightarrow R$ be a convex function. Define the function $g$ to be the sum of $f(x)$ taking on different values, i.e. $g(1,2)=f(1)+f(2)$. Does $g$ possess any interesting/special properties ...