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)

1
vote
1answer
44 views

Duality - linear programming

I have to find a respective dual programme for the given LP $$ \max \ 2 x_1 + 2x_2$$ s.t. $ -x_1 - x_2 \ge -5 \\\phantom{-}x_1,\phantom{,,}x_2 \ge 0$ I got this: $$\min \ 5y_1$$ s.t. $y_1 \ge 2 ...
0
votes
2answers
65 views

Prove convexity of function over space of positive definite matrices

I want to show that the function $f(X) = -log \ det(X)$ is convex on the space $S$ of positive definite matrices. What I have done: It seems like this problem could be tackled by considering the ...
1
vote
1answer
231 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
1answer
50 views

Type of convex function?

I want a convex function $f:\mathbb{R} \to \mathbb{R}$ with the following property: given points $x,d \in \mathbb{R}$, and $\alpha \in (0,1)$, we have $$f(x + \alpha d) \geq \alpha f(x + d).$$ Is ...
0
votes
0answers
31 views

Minimization of the integral with respect to a parameter

Intro Let $f$ be a a real-valued function parametrized by a parameter $\alpha \in \mathbb{R}$ and let $J\colon \mathbb{R} \to \mathbb{R}$ be a functional defined as follows: $$J(\alpha) = ...
0
votes
1answer
42 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
4
votes
2answers
136 views

Finite difference method

I wanted to ask something regarding the finite difference approximation. I used the finite difference to calculate the numerical derivatives of my function. The finite difference is given by the ...
0
votes
1answer
26 views

Solving for stationary points for questions of the following type

How do you solve questions like $f(x,y) = x^2y + y^3x -xy$ for stationary points? A link to an educational resource that goes over this would be very helpful as well, as I don't even know what ...
1
vote
0answers
455 views

Maximum volume of an open box with a square base?

A box with a square base and an open top is to be made. You have 1200cm^2 of material to make it. What is the maximum volume the box could have? Here's what I did: 1200 = x^2+4xz; where x=length of ...
1
vote
3answers
314 views

Optimization problem?

Hi I was having trouble figuring out this question. Find the point on the circle $x^2 + y^2 = 1$ in the first quadrant where the tangent line to the circle encloses with the coordinate axes a ...
0
votes
1answer
19 views

Find the largest lower bound that covers p percent of the data

Suppose that you have a finite set $X\subseteq \mathbb R$, and you want to solve the following constrained optimization problem Find $\max a$ such that $\frac{|\{ x \in X: x>a \}|}{|X|}\ge ...
2
votes
1answer
53 views

Analytical solution to the first PCA direction

It is known that the first PCA direction for a dataset of $n$ points is the unit vector with max variance after projecting the points onto this vector. I wonder whether there are some analytical ...
1
vote
1answer
36 views

when do we have polynomial local minimum = to global minimum

When does a multivariate polynimial has only one stationary point so that local minimum is global minimum?
1
vote
1answer
32 views

Weighted Norm Minimization

I have a minimization problem of the form $min (w_1 \|x\|+w_2\|y\|)$ subject to constraints $A_1x=b_1$, $A_2y=b_2$, $0< l_1 \leq x \leq u_1$ and $0< l_2 \leq y \leq u_2$ where ...
0
votes
1answer
41 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
0
votes
1answer
287 views

Optimization question on graph

I was having trouble with this question. A triangle has one side parallel to the x-axis, two vertices on the part of the parabola $$y =3 − {x^2\over 12}$$ above the x-axis and the third vertex at ...
1
vote
1answer
584 views

Related Rates/ Optimization problem

I was having trouble figuring out this problem. A fisherman is in a boat 3 km from the nearest point A on the coast. The fisherman wishes to return to his camp C located 5 km from the point A. The ...
2
votes
1answer
46 views

Is it true that a quasiconvex, increasing and continous function, is convex?

Let $f:\mathbb R^n \to \mathbb R$ be a continuous and increasing function. Let $f$ be quasiconvex. Let $f(0)=0$. Can we say that $f(x)$ is convex ? If yes, how do we prove it ? Thank you very much ...
1
vote
2answers
44 views

Optimizing a ranch

"A rancher wants to fence in an area of 1000000 square feet in a rectangular field and then divide it in half with a fence down the middle, parallel to one side. What is the shortest length of fence ...
3
votes
2answers
49 views

Maximising a sum - closed form?

As a follow up to this question, I am wondering the following: Suppose $\sum_{i=1}^n x_i=0,\;\sum_{i=1}^n x_i^2=1$. Is it there a closed form for $\max \sum_{i=1}^n x_ix_{i+1}?$ ($x_{n+1}=x_1$) For ...
0
votes
1answer
1k views

What is the meaning of “girth” of a rectangular box?

Here's an optimization problem. A parcel delivery service will deliver a package only if the length plus the girth (distance around, taken perpendicular to the length) does not exceed 112 inches. ...
1
vote
0answers
52 views

Example of a k-matroid

Let the set $K_i = (S, I_i)$ be a matroid for each $i \in \{1 \ldots k\}$. We define $K = (S, I) $ where $I = \{ X \subset S $ | $ X \in \bigcap_{i=1}^k I_i\}$ The claim now is that $K$ is a ...
1
vote
1answer
56 views

Maximisation problem

I am trying the following question: If$$a+b+c+d=0,\;a^2+b^2+c^2+d^2=1$$ Then what is the maximum value of $ab+bc+cd+da?$ By the rearrangement inequality I can get $ab+bc+cd+da\leq 1$ but I am ...
1
vote
1answer
64 views

An example of a continuous function on $\mathbb R^2$ with two critical points, both of them minima

Knowing you can not use the minimum bound, there exists a function $f ( x , y )$ continuous in $\mathbb R ^ 2$ that has exactly two critical points which are (both) the minimum? Can you give me an ...
1
vote
2answers
65 views

If a continuous function has one relative extremum, then it is actually an absolute extremum

The following statement makes sense intuitively, but is there a way to prove it mathematically? (This is something we make use of in applied optimization in calculus.) If $f$ is continuous on an ...
0
votes
1answer
52 views

Help with Gram-Schmidt problem

I'm supposed to show that the Gram-Schmidt process: $\textbf{a}_j = \left\{ \begin{array}{lr} \textbf{d}_j, \;\;\textbf{if} \;\;\lambda_j = 0\\ \sum_{i=j}^n \lambda_i\textbf{d}_i ...
1
vote
1answer
23 views

max and minimum qudratic function problem

A piece of wire $20$ metres long is cut into $2$ pieces and each piece is bent to form a square. Determine the length of the two pieces so that the sum of the areas of the two squares is a minimum. ...
3
votes
2answers
48 views

Could someone explain the Lagrangian Method?

I understand the method, technically, but what is actually going on? We set the gradient of the function equal to the gradient of the constraint (multiplied by a constant), and in doing so, we find ...
0
votes
1answer
50 views

Optimization Problem (Linear Algebra)

I am not trying to cheat or anything, so any reference to online literature or MOOCs, that teach this stuff, will be highly appreciated. The problem is to prove that the following optimization ...
0
votes
1answer
39 views

Project a function on a space?

The problem I'm solving is $\begin{cases} & \dot{x}_{1} = -u \\ & \dot{x}_{2} = 4x_{1} \end{cases}$ $x_{1}(0) = x_{2}(0)=0, |u| \leq 3, t \in [0;2], u^{0}(t)\equiv0, J[u] = -2x_{1}(2) + ...
1
vote
1answer
477 views

Does every strongly convex function has a stationary point?

Say does every differentiable $\mu$-strongly convex function $f:\mathbb{R}^n\mapsto\mathbb{R}$, with $\mu>0$ have a point where its gradient is $0$? If not so which is the minimum you can impose ...
0
votes
1answer
33 views

simple problem of calculus.

A company wishes to manufacture a box with a volume of $36ft^3$ that is open on top and twice as long as it is wide.Find the dimensions of the box produced from the minimum amount of material. My ...
1
vote
0answers
109 views

SOCP or SDP optimization problem

I am studying an optimization problem \begin{equation} \mathbf{w}^* = \text{argmax} \sum_{d=1}^D \log \bigg( \frac{|\mathbf{f}_d^H\mathbf{w}|^2+c_1}{|\mathbf{f}_d^H\mathbf{w}|^2+c_2} \bigg)\\ \\ ...
1
vote
2answers
39 views

maximization of a particular ratio

We are given a ratio: $$\frac{g(x)}{f(x)}$$ where: $$g(x) \in \mathbb{R}^{+}$$ $$f(x) \in \mathbb{N}\: \cap f(x)\ge 2$$ So $g(x)$ returns values in $[0,+\infty]$ while $f(x)$ returns values in ...
4
votes
3answers
235 views

Geometric interpretation of duality and Slater's condition

I am trying to study about optimization problems, Lagrange duality and related topics. I came across some presentation on the net, which claims to show the geometric interpretation of the duality and ...
0
votes
0answers
73 views

How can I use Mehrotra's predictor-corrector primal-dual interior point method to solve a problem that is not in the form of cTx?

I am not very familiar with optimization methods. I am studying the paper "Blind channel identification for speech dereverberation using l1-norm sparse learning" (here: http://linyq.com/NIPS2007.pdf). ...
0
votes
1answer
32 views

a calculus optimization problem

Given points A(2,1) and B(5,4), find the point on the x-axis P(x,0) in the interval [2,5] that maximizes the angle APB. How can I devise an optimize equation and a constraint equation out of this?
1
vote
0answers
69 views

Newton's method for unconstrained optimization applied to a quartic function in R2

I am faced with the task of applying Newton's method to the following problem: $$ \text{min} ~~~~~ 8x_1x_2+\frac{1}{4}(x_1-x_2)^4 $$ where $x \in \mathbb{R}^2$. For clarification, the Newton method ...
1
vote
0answers
44 views

Property of Newton step for self-concordant convex functions

Suppose $f(x)$ is a convex and self-concordant function minimized at $x^*$. I have two starting points $\tilde{x}_0$ and $\hat{x}_0$ such that $|\hat{x}_0-x^*| \le |\tilde{x}_0 - x^*|$. We also know ...
1
vote
1answer
71 views

Optimization of competitive scenario

Suppose we have a function $f(x_1,x_2)$ with the following properties: Let $x^*=\arg \max_{x_1} f(x_1,x_2=x^*)$ and $x^*=\arg \min_{x_2}f(x_1=x^*,x_2)$. $f(x_1,x_2)$ is concave in $x_1$. ...
4
votes
1answer
130 views

Optimization of a Cylinder In a Sphere WITHOUT Using Calculus

I have a quick question. I'm curious as to how to do an optimization question WITHOUT using calculus. Question: Determine the dimensions of the cylinder of maximum volume that can be inscribed in a ...
1
vote
1answer
54 views

Finding critical points of a multivariable function

Let $f(x,y)=e^{x^2-xy+y^2}$ (a) Find all the critical points of the following function. (b) Find the all the local maxima and local minima of the function if there is any. What i tried. I tried ...
0
votes
1answer
79 views

Optimization to minimize cost using the function C=Tq^(1/a)+F

I was given the function of $C=Tq^{1/a}+F$ where $C$ is total cost, $q$ is output, $a$ is a positive parametric constant, $F$ is the fixed cost, and $T$ measures the technology available (also a ...
4
votes
2answers
139 views

Duality in quadratically constrained quadratic program

I have been given the primal quadratic program with a single quadratic constraint as given below: $$ \text{min} ~~~~~~~~~~~~~~~~~~~~~~~~~ \frac{1}{2}x^{T}Qx $$ \begin{align*} \text{subject ...
2
votes
0answers
57 views

norm over differentiable functions computable from derivatives only

I'm running an optimization algorithm, minimizing the norm $||f-\hat f||$ of some objective function $f(x_1,x_2,x_3,y_1,y_2,y_3)$. The function $f$ cannot be computed directly, but its second ...
0
votes
1answer
1k views

Maximizing total tax revenue with function Qs+-8+P and Qd=(80/3)-(1/3P)

The supply and demand equations of a good are given by Qs= -8+P Qd=(80/3) - (1/3)P P is measured in dollars. Suppose the government decides to impose a constant per unit tax of $t on the supplier. ...
0
votes
0answers
102 views

Optimization to minimize cost function

I have the function $C=Tq^{\frac 1a }+F$. Where $C$ is total cost, $q$ is output, $a$ is a positive parametric constant, $F$ is fixed cost, and $T$ measures the technology available to the firm ...
0
votes
1answer
34 views

Optimization problem $L(R, PQ) \rightarrow \min$

Suppose we have some $n \times m$ matrix $R$ and we want to find non-negative decomposition on matrices $P$ of dimension $n \times d$ and $d \times m$-matrix $Q$. But since exact decomposition usually ...
0
votes
1answer
30 views

Necessary condition of optimality for functionals

Let $C(a, b)$ denote the set of all surjective and continuously differentiable functions $\alpha:[a, b] \rightarrow [a, b]$. Consider the functional on $C(a, b)$ $$ F[\alpha(t)] = \int_a^b ...
0
votes
2answers
2k views

Finding the center of mass of a cylinder

Help finding center of mass of soda can? If you represent the soda can as a right-circular cylinder radius=$4$ cm height =$12$ cm We are told to neglect the mass of the can itself. When the can ...