Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

2
votes
2answers
21 views

minimization with many unknowns and one condition

I haven't done this in quite a while so excuse my perhaps silly question. I'm looking for a solution to a minimization problem (if there is one), that goes like this: I want to minimize (global) ...
1
vote
0answers
48 views

Application of a general “Weierstrass theorem”

http://books.google.at/books?id=9OSrV73a40gC&pg=PA45&lpg=PA45 gives a general Weierstrass theorem. Are there notable applications of this theorem, say in the calculus of variations? (I could ...
1
vote
1answer
132 views

Optimization problem, solve for ( )

Some years from now you are working for a book publisher. He asks you to give him a formula that will tell him the length and width of a book page that contains A square inches of printed text, a left ...
1
vote
1answer
248 views

Finding minimum sum of absolute differences between heights of $n$ boys and $m$ girls

Given two sets $A$ and $B$, $A$ has heights of $n$ boys and $B$ has heights of $m$ girls, $m \ge n$. We have to find one solution of pairing up $n$ boys with $n$ (out of $m$) girls so that the sum of ...
0
votes
1answer
34 views

Strong convexity of a function with cases

Given a set $S = \{x_1,\dotsc,x_n\} \subset \mathbb{R}$, is the function \begin{align} f&: (0,\infty) \to \mathbb{R} \\ f&(p) = 2p^2 + \frac{1}{n}\sum_{i=1}^n \max(0, -p^2-x_i) \end{align} ...
0
votes
0answers
25 views

dual value of a linear constraint

Assume a minimization problem. The dual of an inequality '<' constraint is the marginal improvement in the objective function (ie marginal reduction) by marginally increasing the right-hand-side ...
0
votes
1answer
45 views

Constrained optimization with complex variables

Is there a theory of constrained optimization with complex variables, do you know any textbook on that topic? The typical textbooks on constrained optimization deal with real variables. I actually ...
1
vote
1answer
284 views

How many n square can fit into a square of side N

Suppose we have n small squares of equal sizes that has area w. Suppose we have a fix square S of area A such that for area A, one area w < area A. If square S's area A, length, and width are ...
0
votes
0answers
40 views

Question about the ellipsoid method

I have some technical question concerning the ellipsoid method Referring to the paper : http://paswkshop.comm.utoronto.ca/~weiyu/01658226.pdf It is mentioned in p.1317 at the last line in the left ...
0
votes
1answer
289 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
0
votes
3answers
75 views

Minimum value of $\sqrt{(1+1/y)(1+1/z)}$

If $y,z > 0$ and $y + z = c$ where $c$ is a constant, then what's the minimum value of $$\sqrt{\left(1+\frac1y\right)\left(1+\frac1z\right)}$$ I am having a hard time solving this.
1
vote
1answer
41 views

Need help with the graph of a function

In the optimization problem max: $$6x+2xy-2x^2-2y^2$$ subject to $x+2y\le2$ and $-x+y^2\le1$ I need to draw the graph of the feasible region in order to determine if the problem has global solutions, ...
1
vote
1answer
34 views

Need help with optimization concepts.

In some optimization problems with inequality constraints some of the aforementioned constraints can be x>=0 , y>=0 and so on. I think these constraints are called non negativity constraints; they ...
2
votes
1answer
735 views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
1answer
42 views

Matrix optimization

I'm trying to minimize over $U$ the objective $\|X^{\top}UU^{\top}UU^{\top}X\|_F^2 = \text{trace}(X^{\top}UU^{\top}UU^{\top}XX^{\top}UU^{\top}UU^{\top}X)$ subject to $U^{\top}U = I$, where $X \in ...
2
votes
0answers
24 views

Finding optimal hyperplane

I have a set of vectors $\{V_i\}$ in $n$-dimensional space. There is a number corresponded to each vector $\alpha_i = f(V_i)$ ($\alpha_i$ can be negative). I want to find a hyperplane which would ...
3
votes
2answers
81 views

Minimum of $|\det(X+iC)|$

Let $C$ be a fixed real $n\times n$ matrix, $X$ be an arbitrary real $n\times n$ matrix. Find the minimum value of: $$|\det(X+iC)|=\sqrt{\det(X+iC)\det(X-iC)}$$ When $n=1$ it's clear that the ...
2
votes
2answers
52 views

Lagrangian method gives the wrong answer in a standard constrained optimization problem

I had this strange problem where the Lagrangian method gives the wrong answer in a constrained optimization problem. Here goes: The problem is $$\max_{c,n,q} \alpha\log(c)+(1-\alpha)\log(nq)$$ ...
0
votes
1answer
18 views

Is $argmin_{\mathbf{x}} f(\mathbf{x})=argmin_{\mathbf{x}} \log{f(\mathbf{x})}$ always true?

Assuming $\mathbf{x}\in \mathbb{R}^n$, $f(\mathbf{x})\gt0 \forall\mathbf{x}\in\mathbb{R}^n$, is $argmin_{\mathbf{x}} f(\mathbf{x})=argmin_{\mathbf{x}} \log{f(\mathbf{x})}$ always true? Why?
0
votes
2answers
48 views

MaxMin: how much does the min “see”?

Consider the following quantity: $$ \max_{a \in \{-1,1\}}\left( \min_{b \in \{-1,0,1\}} ab\right).$$ Since the min is inside, we apply it first, but what value $b$ will be chosen? If the minimum ...
0
votes
1answer
25 views

How to computer the Lagrange multipliers associated with an optimal solution

Suppose I have a solution $x^*\in\mathbb{R}^n$ to the following problem \begin{align*} \text{minimize}_{x}& \sum_{i=1}^n f_i(x)\\ \text{subject to}\quad &g_i(x) = 0\,\,i=1,\ldots,m\\ ...
0
votes
0answers
48 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
2
votes
1answer
214 views

Finding extremum values in a given function using hessian matrix

Please check if my answers are correct specially for part 3 and help me to do the fourth part in this problem Let f(x,y)=x$^4$-8x$^2$+y$^4$-18y$^2$ Find the critical points of f Determine the ...
0
votes
1answer
48 views

Shortest path problem: dual formulation and proof of total unimodularity

The IP formulation of the shortest path problem looks as follows: \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
10 views

Book recommendations for Binary Integer Linear Programming

I'm looking for a book on BILP, which focuses on algorithms / solutions methods. So far, I only found the following books on ILP "Integer and combinatorial optimization" by Nemhauser, George L. ...
0
votes
0answers
20 views

Minimum in complex inner product vector space

I'm stuck at this problem, can someone give me a hint? Let $x_i$ and $y_i$ ($i=\overline{1,n}$) be vectors in an infinite dimensional vector space $V$ with inner product $(,)$ satisfy: ...
1
vote
1answer
54 views

New variable in a convex optimization problem

Consider the convex optimization program $$ \min_{x \in X } x^\top P x + p^\top x \quad \text{ sub. to: } Ax = b $$ where $X \subset \mathbb{R}^n$ is compact, $P \succ 0$, $A \in \mathbb{R}^{m \times ...
1
vote
1answer
17 views

The equality of gradient between different calculations?

Suppose there is a problem $$\min\limits_v\max\limits_x E(v,x).$$ $E$ is a concave function w.r.t. $x$. But w.r.t. $v$, $E$ is a convex function plus a concave function. I can get ...
1
vote
1answer
76 views

Optimize $x^2 + y^2 +2z^2 +z(x^2-y^2)$ subject to $x+y=2$

$$x^{2}+y^{2}+2z^{2}+zx^{2}-zy^{2}\overset{\left(x=2-y\right)}{\longrightarrow}4-4y+2y^{2}+2z^{2}+4z-4yz\rightarrow FOC: \; \begin{cases} -4+4y-4z=0\\ 4z+4-4y=0 \end{cases}\rightarrow y=1+z\rightarrow ...
1
vote
1answer
42 views

least-square optimization with linearly depend solution $x$

What is the exact solution $x_{n \times 1}$ of the following constrained optimization problem \begin{align*} &\min \|A x - b\|^2 \\ s.t.& C x = 0 \end{align*} where $A$ is full column rank $m ...
1
vote
1answer
12 views

Can $\sum_i{d(m_i,Pn_i)^2}$ be minimized over $P$ using linear least squares?

Suppose P is a $2 \times 2$ matrix and both $m_i$ and $n_i$ are given 2 dimensional vectors in Cartesian coordinates, $d$ is an Euclidean distance. Is the following correct? I will try to rewrite the ...
3
votes
0answers
18 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
0
votes
1answer
31 views

Sums of positive and negative distances to the least squares plane

Let $A_{1}, A_{2}, \ldots, A_{n}$ be points in $\mathbb{R}^{3}$ and $\pi_{*}$ be the least squares plane, i. e. $$ \sum \limits_{i = 1}^{n}\rho^{2}(A_{i}, \pi_{*}) = \min_{\pi}\sum \limits_{i = ...
0
votes
1answer
111 views

Calculus Optimization - Finding the minimum cost

In oil pipeline construction, the cost of pipe to go underwater is 60% more than the cost of pipe used in dry-land situations. A pipeline comes to a river that is 1 km wide at point A and must be ...
4
votes
1answer
40 views

Local minimum and gradient [duplicate]

But the proof here below is specially elegant. Is there any function $f$ such that $f$ has a local minimum at $x$ but $\nabla f(x) \neq 0$? Only assumption on $f$ is that it has to be differentiable ...
2
votes
2answers
174 views

Closest distance between two quadratic curves

I'm having trouble with the following problem : "find the closest distance between $x^2+4y^2=4$ and $xy=4$" I tried to solve using the properties of ellipse and hyperbola, but the relatively tilted ...
0
votes
0answers
20 views

Sum of squares of series of boolean variables

I am going to simplify the following series: $$\sum^4_{v=1} \left(1 - \sum^4_{i=1} x_{v,i}\right)^2 + \sum^4_{i=1} \left(1 - \sum^4_{v=1} x_{v,i}\right)^2$$ Since $x_{i,j}$ is a boolean variable, ...
0
votes
1answer
27 views

How do I know if I have imaginary numbers when using Newton Raphson Method?

I am studying Newton-Raphson Method but I am facing questions in my head. As far as I know Newton Raphson Method works on real values, but what if Newton Raphson Method faces an imaginary number when ...
0
votes
1answer
24 views

online estimation of autoregressive process

I am interested about online estimation of autoregressive models. Is there anything I can find in the literature about this topic?
0
votes
0answers
32 views

An error in least square optimization problem in Matlab

I am new to MATLAB and I want to formulate the following lease square expression in Matlab. I have some codes that I am typing here. But the optimization problem solution seems not to be correct. Does ...
3
votes
2answers
155 views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and ...
0
votes
0answers
17 views

Imaginary roots and Real values when using Newton-Raphson Values

I am studying Newton-Raphson Method but I am facing questions in my head. How do I know if I have an imaginary number or imaginary numbers? and What to do when I have them when using Newton Raphson ...
0
votes
0answers
24 views

optimization problem with integrals

There is a maximization problem of the following form \begin{equation} \max_{l(a)} \sum \int \bigg(U(c, 1-l(a)) \bigg) x(a,e) da \end{equation} where $$ c = a(1+ f(L)) + e G(L)l(a) - h $$ $$ L = ...
1
vote
2answers
276 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 ...
1
vote
1answer
297 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 ...
1
vote
1answer
53 views

Find max and min subject to constraint ||x|| = 4

$Q(x,y)=7x^{2}+12xy+12y^{2}$ I only know how to do this is $\|(x,y)\|=1$ If $\|(x,y)\|=1$, the eigenvalues are $16$ and $3$. So obviously $\min=3,\max=16$. I don't know what to do if ...
0
votes
2answers
43 views

How do I know if a function has x roots on x-axis?

I am currently studying Newton Raphson Method. Now I am kind of having a question that how I know if the function ever has a x-root or roots on x-axis? Please let me hear your advice. I am sorry if I ...
0
votes
2answers
41 views

Rectangular Box Optimization Problem

A rectangular box is to have a square base and a volume of 40 ft3. If the material for the base costs \$0.31 per square foot, the material for the sides costs $0.05 per square foot, and the material ...
2
votes
2answers
64 views

Two-way matrix optimization

I have run into a problem like this. Looks a bit unusual, but I think should be doable. Find $U$ achieving $$\min_U \left( \| A - UW \|_2^2 + \| RU - H \|_2^2 \right)$$ $A,U,W,R,H$ are all ...
0
votes
0answers
20 views

Minimization problem with amplitude constraint

I have the following minimization problem: $$\left\| \bf{A}x - y\right\|^2 \to min $$ $$s.t. \left|x_i\right| < 1, \forall i,$$ where $\bf{A}$ is the complex matrix with size of $(n\times m)$, ...