Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

0
votes
1answer
37 views

Unique critical point and psd implies pd and hence strict relative maximum

Let $f(x)$ be of class $C^{(2)}$ on an open set A, $x_0\in A\subseteq R^n$ a critical point. In addition, the hessian matrix of f(x) at $x_0$, $H(x_0)=\{f_{ij}\}|_{x=x_0}$, is negative semi-definite. ...
16
votes
4answers
430 views
+100

How do you prove that $\{ Ax \mid x \geq 0 \}$ is closed?

Let $A$ be a real $m \times n$ matrix. How do you prove that $\{ Ax \mid x \geq 0, x \in \mathbb R^n \}$ is closed (as in, contains all its limit points)? The inequality $x \geq 0$ is ...
1
vote
2answers
98 views

Decrease in the size of gradient in gradient descent

Gradient descent reduces the value of the objective function in each iteration. This is repeated until convergence happens. The question is if the norm of gradient has to decrease as well in every ...
1
vote
0answers
15 views

Benders decomposition Master Problem

I am currently working on implementation of Bender's Decomposition for MIP. I am looking at the simplest model \begin{equation} \begin{split} \min_{x,y} &\; c^Tx + f(y)\\ s.t. & \; Ax + Dy \ge ...
1
vote
0answers
16 views

Interpolating polynomial such that it is convex in specified region

The problem I have is that I have data at two points $x_1,x_2$ and $x_2>x_1>0$. At these two points, I know that the function $f$ has values $f(x_1)$ and $f(x_2)$ respectively. It is also ...
0
votes
1answer
7 views

Strongly monotone and cocoercive

A map $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ is $m$-strongly monotone if $$ (x-y)^{\sf T}((f(x)-f(y)) \geq m \|x-y\|_2^2 $$ for $m > 0$ and is $\delta$-cocoercive if $$ (x-y)^{\sf T}((f(x)-f(y)) \...
0
votes
0answers
19 views

Number of solutions to a system of nonlinear equations for n number of variables

We can use Descartes' rule of signs to find the number of roots for a polynomial. We can use Bezout's Theorem to find the number of roots to a nonlinear system of equations with two variables. What ...
4
votes
1answer
49 views

How can I experiment with Lagrange multiplier in QCQP?

Suppose we want to solve following optimization problem (it is a PCA problem in this post) $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \mathbf w^\top \...
1
vote
0answers
14 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...
2
votes
1answer
1k 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 ...
0
votes
1answer
39 views

maximize 3-variable linear function [version 1.0]

This problem came up when I was trying to solve a bigger, probabilistic problem. So at the end it boils down to this: how can we maximize the function $f(x_2,x_3,x_4) = \frac{18}{100}x_2 + \frac{...
0
votes
0answers
26 views

Sum/product of two functions of two variables are to be minimized

I have two functions $f(x,y)$ and $g(x,y)$ whose sum/product (whichever is possible) is to be minimized. The values of $x,y$ can vary in the interval $0<x,y<1$ (hence none of them can have a ...
1
vote
0answers
23 views

Gradient Descent and Scale of Data and Objective Function

One way to tune step size in gradient descent is via backtracking line search. backtracking line search (with parameters α ∈ (0, 1/2), β ∈ (0, 1)) starting at $t = 1$, repeat $t := \beta t$ ...
1
vote
1answer
23 views

Why $f:R^2\to R$, with $\mbox{dom} f=R^2_+$ and $f(x_1,x_2) =x_1x_2$ is quasiconcave?

Why $f:R^2\to R$, with $\mbox{dom} f=R^2_+$ and $f(x_1,x_2) =x_1x_2$ is quasiconcave? I have tried to use Jensen eniquality to check that superlevel set $\{x\in R^2_+ | x_1x_2 \ge \alpha\}$ is convex....
1
vote
1answer
21 views

Is the root of a sum of squared differences convex?

Let $x \in \mathbb{R}^n$. Let there be a collection of functions $d_i = (x_j - x_k)^2$ (note that the subscripts $j$ and $k$ are fixed for each $d_i$, and there can be repeated use of subscripts on ...
0
votes
1answer
33 views

Related to Caratheodary theorem

If $P$ is a set of vectors $\textbf{x}_i$'s where every $\textbf{x}_i$ is of dimension $d$ and $|P|=K$. In this case at many places I have seen that the vectors $\textbf{x}_2-\textbf{x}_1,\textbf{x}...
2
votes
1answer
549 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
11 views

McCormick Envelopes with more then 2 variable

Suppose that I have the function $z=\sin(x)\cdot y$, where $0\leq x<=0.5$ and $0\leq y\leq 1.0$. If I do the best convex relaxation of $\sin$ and than compute $z=\operatorname{Relax} \sin(x) \cdot ...
2
votes
3answers
2k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
0
votes
1answer
35 views

What are spurious local optima?

I keep seeing that word "spurious" (when used in the context of optimization), but I'm having trouble finding a good reference on what the definition of the term is.
0
votes
1answer
18 views

floor/ceiling/round functions in the constraints of an optimization?

I have a constrained optimization problem in which I have to impose a "floor" or "ceiling" constraint to the solution. In fact I decided to use these nonlinear rounding functions because I needed to ...
0
votes
0answers
13 views

Demonstrating convexity of a convex optimization problem

I am working on the following problem. Consider the following function $\textit{f}: \mathbb{R^n}$ × $\mathbb{R^n}$ → $\mathbb{R}$. $$f(\vec{z},\vec{d}) := \min_{t \in \mathbb{R},\vec{v} \in \mathbb{...
1
vote
1answer
20 views

On accelerated Proximal Gradient Methods

I am working on accelerated optimization scheme, which unified in the paper by Paul Tseng, "On Accelerated Proximal Gradient Methods for Convex-Concave Optimization". But unfortunately, it is ...
0
votes
1answer
12 views

Does projected gradint descent(pgd) results in the same minimizer as the one given by unconstrained gd and projected back on the constrained set?

For $f: \mathbb{R}^n \mapsto \mathbb{R}$ with $f(x) < \infty,\;\forall x \in \mathbb{R}^n$ and for convenience let's assume $f$ is continuously differentiable. Suppose we are trying to solve the ...
0
votes
1answer
19 views

Is convexity the most general dividing line between “easy” and “hard” optimization problems.

Just got started with Boyd's Convex Optimization. It's great stuff and I see how it directly subsumes the all-important linear programming class of models. However, it seems that if a problem is non-...
0
votes
1answer
45 views

Minimizing a strictly convex function with inequality constraint

So we've been learning about the Kuhn Tucker conditions in my non-linear optimization course and I've been having trouble with this problem: QUestion: description here Question: a strictly convex ...
2
votes
1answer
26 views

What are some applications of entropy maximization and minimum volume covering ellipsoid?

I'm reading Boyd's Convex Optimization textbook. In particular, I'm currently focusing on Chapter 5 (Duality). There is a frequent recurrence of two examples: Minimum volume covering ellipsoid \...
1
vote
1answer
45 views

A question about Lagrange multiplier in optimization

I read @amoeba 's answer in this post, PCA optimization problem is $$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \|\mathbf w\|_2=1 $$ where $\mathbf C$ ...
0
votes
0answers
27 views

How do I prove that this function is concave on $f_{ij}(x)$?

I am trying to apply convex optimization to the following problem- ${f^*}(x) = \mathop {\arg \max }\limits_{{f_i}(x)} \sum\limits_i {\ln \left\{ {u_i^* - \sum\limits_j {\frac{1}{{\left( {1 - {\rho _{...
0
votes
1answer
52 views

Directional Derivative defines Descent Direction

Let $f:\mathbb{R}^m \mapsto \mathbb{R}$ be a proper convex function that is not necessarily differentiable and let $x\in\mathbb{R}^n$ be such that $\mathbf{0} \notin \partial f(x)$. I want to prove ...
1
vote
1answer
1k views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
1
vote
1answer
18 views

Individually checking constraints for convexity in Optimisation problem valid?

I have a quadratic minimisation problem where both the objective fn and constraints have some quadratic terms. (Such as a throttle variable (continous) * On/Off (integer variable)). My question is: ...
1
vote
0answers
51 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
0
votes
1answer
27 views

Robusness of median

If we let $X$ be a set of pints in $\mathrm{R}^2$, and let $g(X) = \arg \min_{y \in \mathrm{R}^2} \sum_{x_i \in X} \parallel x_i -y \parallel_2$ (geometric median of $X$). If $X$ and $X'$ are ...
0
votes
0answers
14 views

Uniqueness of projection implies convexity [duplicate]

Prove that for a compact set A in finite dimensional Euclidean space X, A is convex if and only if for any point x in X, the projection of x to A is unique. If we know A is convex, we can show the ...
0
votes
0answers
9 views

Minimizing component-wise convex functions

I want to minimize a function $f(\vec x,\vec y)$, whereby $\vec x$ and $\vec y$ are vectors. If I hold $\vec x$ constant, $f(\vec x,\vec y)$ is convex with respect to $\vec y$, and the reverse is true ...
2
votes
1answer
78 views

Linear program with two equality constraints

Compute the minimal value of $$x_1 + 2x_2 + 3x_3$$ when $x_1$, $x_2$, $x_3$ satisfy $$x_1 − 2x_2 + x_3 = 4$$ $$−x_1 + 3x_2 = 5$$ and $$x_1 \ge 0, \qquad x_2 \ge 0, \qquad ...
0
votes
3answers
70 views

Orthogonal Projection onto the $ {\ell}_{\infty} $ Ball

What is the Ortohogonal Projection onto the $ {\ell}_{\infty} $ Ball? Namely, given $ x \in {\mathbb{R}}^{n} $ what would be: $$ {\mathcal{P}}_{ { \left\| \cdot \right\| }_{\infty} \leq 1 } \left( x ...
0
votes
1answer
34 views

Convex or non-convex function

I want to minimize the following function $$\frac{a}{bxy+cd}e^{\frac{a}{bxy+cd}}H+2-\Gamma(1,\frac{eaf}{b(1-x)},\frac{eagf}{bx(1-y)})$$ where $a,b,c,d,e,f,g,H$ are constants and greater than $0$. $\...
2
votes
0answers
23 views

How to deal with a convex constraint

I want to deal with a convex constraint \begin{align} F(P)=P^{H}AP_{0}+P_{0}^{H}AP-P_{0}^{H}AP_{0}\succeq 0 \end{align} where $(\cdot)^{H}$ represents Hermitian transpose, $A$ is a positive definite ...
3
votes
2answers
1k views

Time complexity of a convex quadratically constrained quadratic program (QCQP)

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP) problem? And any references? Thank you very much.
3
votes
0answers
550 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through Lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...
0
votes
0answers
12 views

Optimal Transport of a Translated Density

I've been writing an implementation to the Monge-Kantorovich optimal transport problem in Euclidean space with a quadratic cost function. The outline is that we have densities $f(x)$ and $g(y)$ s.t. $...
-1
votes
0answers
13 views

reference request quadratic optimization problem

I have this problem and it seems similar to something people must have studied in quadratic optimization/non-convex optimization. $\min_{a,b \in [0,1]^n} a^TM b\\ \text{subject to. } a^TQb\geq \alpha$...
2
votes
1answer
25 views

Finding minimizer from different order

Let a nonnegative function $f(x,y)$: $\mathbb R^2\to \mathbb R$ be second order continuous differentiable. We also know that $f$ is not convex in its two arguments, but only separately in each of them....
1
vote
0answers
42 views

How to solve a binary generalized assignment problem

I have the following generalized assignment problem: Z=max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ such that $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad\quad\...
0
votes
1answer
25 views

Exact line search in convex optimization

For a convex function $f$ what do we know about convexity of the exact line search problem? $$\min_{\alpha \ge 0} f(x+ \alpha p_k)$$ I think because the function is convex and is linear in variable, ...
2
votes
0answers
99 views

Relaxation of non-convex QCQP with one quadratic and one linear constraint

According to Boyd we know that a non-convex QCQP problem with one quadratic constraint has strong duality with the relaxed SDP or Lagrange counterpart. (check "Convex Optimization" by Boyd, Appendix B)...
0
votes
0answers
27 views

Non convex constraint and possible relaxations.

I am trying to solve a minimization problem of the form $\min_{\alpha,u} \|Xu-\alpha\|^{2}_{2}+\lambda\sum_{i,j}^{n}|\alpha_i-\alpha_j|$ subject to $\|u\|_{2}=1$ where $X$ is $n\times p$ and $u$ is $...
1
vote
1answer
26 views

Showing that this set satisfies the closed criterion

Suppose we have the subset $S = \{ \lambda v \mid \lambda \geq 0 \} + K $, where $v$ is a vector in $\mathbb{R^3}$ and $K$ is a convex hull of six other vectors. How do I show that it satisfies the ...